## Math Brainteaser – Coin Flipping November 11, 2009

Posted by eric22222 in General, Math.

I’m going to post a few puzzles here, each with a mathematical solution. Mostly just for fun, but it’ll also let you see how I solve problems sometimes. Here we go!

You flip a fair coin. If you get heads, you get one point and flip again. If you get tails, you stop (no change in score). What is the average score you can expect in this game?

You’ll have to click to see my solution. I don’t want to spoil it for people who want to figure it out their way.

I like to start with some data, then find a pattern. This is going to use expected value, too, so brush up on that if you need to.

We know the chance of getting zero points is 50%, the chance of getting exactly one point is 25%, and so on. So here’s that in a table:

x, P(x)
0, 0.5
1, 0.25
2, 0.125
3, 0.0625
4, 0.03125

Now let’s see the product of these numbers:

x, x*P(x)
0, 0.0
1, 0.25
2, 0.25
3, 0.1875
4, 0.125

What we want to get eventually is the sum of all these products. This next table shows the sums up to x:

x, sum(x*P(x))
0, 0.0
1, 0.25
2, 0.5
3, 0.5625
4, 0.6875

Um… hm. Well, each entry gets closer to one… Maybe if I take the difference from 1?

x, 1-sum(x*P(x))
0, 1.0
1, 0.75
2, 0.5
3, 0.4375
4, 0.3125

Hey! I recognize some of those numbers! In fact, their denominators are powers of two! I’ll multiply each by 2^(x+1) to get rid of the decimals:

x, (1-sum(x*P(x)))*2^(x+1)
0, 2.0
1, 3.0
2, 4.0
3, 5.0
4, 6.0

Ha! There it is. Now we just have to work backwards. To keep things less cluttered, I won’t fill all the details around my summation notation, so just remember that’s our sum of products. Also, keep in mind that P(x) =2^(x+1).

$(1-\sum({x \times 2^{x+1}})) \times 2^{x+1} = x+2$

$(1-\sum({x \times 2^{x+1}})) = (x+2) \div (2^{x+1})$

$\sum({x \times 2^{x+1}}) - 1 = -(x+2) \div (2^{x+1})$

$\sum{x \times 2^{x+1}} = 1 - \displaystyle\frac{x+2}{2^{x+1}}$

Okay, stop right there. The left side of the equation is the sum we wanted. That’s the expected value up to x. If we set x to infinity, we get our answer. So what happens to the right side as x approaches infinity? Well, the one is going to stay put, but that fraction is obliterated. The exponential denominator far outweighs the linear numerator. So as x approaches infinity, we’re left with just 1, which is our answer.

Geometric solution

This was one way I checked to make sure the answer made sense. Below, I’ve graphed each possibility up to 8.

An interesting thing to note is that the answer we were looking for is going to be the same as the area under the curve (that is, x times P(x)). Notice that each block is half the size of the last. So if we were to stack them all on top of one another…

Tada! A simple one by one square. Okay, so it’s obvious here that the graph is skewed vertically to show more detail, but trust me, it’s a square.