# To infinity and beyond

September 8th, 2011 at 9:59 pm by Dr. Drang

Here’s a math problem my sixth-grader came home with last night.

You have a bottomless pit with [x] marbles in it. Two of the marbles are black. You reach in and pull out two marbles at random. If [p(x)] is the probability that both marbles are black, what is

[\sum_{x=3}^\infty \;p(x)]

I sure don’t remember doing infinite series when I was in sixth grade. I think the teacher was looking more for the students’ reasoning than a numerical answer, but after my son went to bed, I couldn’t stop myself from writing a little program to get the answer.

The number of ways you can draw two marbles from a set of [x] marbles is the binomial coefficient:

[{x \choose 2} = \frac{x!}{2! (x - 2)!}]Since there’s only one way to get two black marbles in a draw,

[p(x) = \frac{1}{{x \choose 2 }} = \frac{2! (x - 2)!}{x!}]We could write a very simple program that sums up a long series of such terms, but it wouldn’t be very efficient to keep calculating factorials again and again. A better way is to use this recurrence relation,

[{x \choose 2} = {{x-1} \choose 2} + (x-1)]and to recognize that our starting point is

[{2 \choose 2} = 1]Here’s a quick Python program to estimate the answer:

```
python:
1: #!/usr/bin/python
2: from __future__ import division
3:
4: total = 0
5: lastdenominator = 1
6: for x in range(3, 1001):
7: denominator = lastdenominator + (x - 1)
8: p = 1/denominator
9: total += p
10: lastdenominator = denominator
11:
12: print total
```

This gives a total of 0.998. Increasing the upper bound from 1,000 increases the total but never puts it over 1. An upper bound of 1,000,000 gives a total of 0.999998. Pretty clearly, we’re converging to 1.

This is, of course, nothing like a proof. But simple numerical experimentation like this is very compelling and, if you’re of a certain mindset, can seem more real and significant than a formal mathematical derivation.

I don’t know how my son’s teacher covered this problem in class, but I have noticed that my kids do a lot more estimating than I ever did. Roots of equations, for example, are often found by plotting them on a graphing calculator and zooming in to get the coordinate where the function crosses the abscissa—a technique that was impossible when I was in school. There is, no doubt, something lost when kids spend less time on exact methods, but I think the gains made in getting them to think mathematically and make good estimates is worth it.

Carl says:

September 8th, 2011 at 11:02 pm

When I taught GRE prep at Kaplan, we had a similar approach to “proof.” The GRE has questions like, “An odd number plus an even number makes A) Odd B) Even …” We had the students memorize the relevant patterns, but then told them a general way of solving questions of this type. Just do one equation in the family and see what result you get. “1 + 2 = 3. OK, so therefore ANY odd plus ANY even ALWAYS makes an odd.” It’s enough to make a real mathematician cry, but it works when you’re solving questions in a few minutes each under a crunch. :-)

Alex Chan says:

September 9th, 2011 at 2:05 am

Equation 14 on the Wikipedia page about binomial coefficients looks like it might be useful:

Details of the proof are in the equation below it. But it uses induction — would that be expected at sixth grade? I’m not familiar with American education.

Running it with your problem gives [\sum{x=3}^\infty \frac{1}{x\choose 3} = \frac{3}{(3-1){2\choose2} = 1], so clearly you’re ok :).

[Also, I’m getting an error loading the maths in Safari, Chrome and Reeder:

Dr. Drang says:

September 9th, 2011 at 3:05 am

Alex, the error messages you saw came because you visited the site while I was experimenting with a new MathJax configuration. It’s not a permanent condition. What

isa (seemingly) permanent condition is that WordPress does nasty things to comments before MathJax can get a crack at it, so LaTeX equations aren’t rendered properly in the comments unless they’re written in MathJax-compatible HTML. I’d like to fix this, but it’s very low on my to-do list.Tony McDaniel says:

September 9th, 2011 at 6:57 am

I’ve taught probability to fifth graders, but without explicitly discussing binomial coefficients, and certainly without infinite series. I found that using the lottery as an example was something they could understand and found interesting. We also discussed long-term outcomes based on the prize values and probabilities of drawing those prizes. I wrote a program in python to play the lottery repeatedly with randomly generated tickets to model the long-term outcome. They were quite impressed with how well the experimental results and theoretical results matched.

Eddie says:

September 9th, 2011 at 7:27 am

This is a binomial problem. The outcome is either black or not black.

The teacher probably taught them to memorize the fact that an infinite sum of binomial probabilities is always 1. So, the answer would be 1 minus the sum from x=0 to x=2.

jiij says:

September 9th, 2011 at 9:27 am

This is a risk method, because plenty of series that look like they converge when you approach them this way actually diverge

Dr. Drang says:

September 9th, 2011 at 10:14 am

Eddie,

Maybe I’m just dense this morning, but I don’t see how the “runs of misses until

nhits” problem (which is how the negative binomial distribution is presented in the Wikipedia page and how I learned it in a QA/QC context) translates to the stated problem. Also, in this case p(0) = p(1) = 0, but p(2) = 1, so 1 minus the sum of those would be 0, not 1.jiij,

You’re absolutely right for the general case, and the best example of that is the harmonic series (which is probably what you had in mind). There’s also a lovely example in the theory of plates, where the series solution for the stress under a concentrated load never converges. My experience, though, is that writing a program to calculate the series really does show the divergence. That’s certainly the case for the harmonic series:

Increasing the upper bound of the sum gives you an increasing result that’s pretty clearly not converging.

Eddie says:

September 9th, 2011 at 12:24 pm

On the Wikipedia page, see section Relation to the binomial theorem. I was thinking that you could apply the binomial probability formula there to this problem. p would the the probability of black, and 1-p=q would be the probability of not black.

We don’t know what p and q are, but we know that p+q must = 1, so (p+q)^n = 1 regardless of p, q, or n. This result is also consistent with your numerical approach.

I’m generally off the clock as an actuary when I write about Mac productivity-ish things, so I put no guarantees on any of this. :)

Carl says:

September 11th, 2011 at 6:37 am

Haha, I just tried this out in Python:

You heard it here first, the sequence 1/2^n converges at n=60!

Carl says:

September 11th, 2011 at 6:38 am

Let me try again using Markdown:

Dr. Drang says:

September 12th, 2011 at 12:19 am

You’re joking, Carl, but examples like yours do a better job of showing rates of convergence than big O notation does. And it’s a good way to introduce the limits of floating point arithmetic.