[Guest]

This is a sequel to my previous puzzle those flipping coins

Once again, you start at 0 and flip a coin. If it is heads, you add 1. If it's tails, you subtract one. You keep on doing this until you get back to zero. What is the expected number of times you will flip the coin.

[Guest]

After 2 flips, there is a 50% chance of being at zero, otherwise you have two both heads or both tails and will need 2 more flips to both be the opposite, which is 25% chance. The second 2 flips are only needed if the first 2 did not reach zero, or half the time, so the total chance of reaching zero with 4 or less flips is 62.5.

For 6 flips it is 68.75%, for 8 it is 72.6, and it is around 75% for 10 flips. Each time that zero is not reached, another two flips both heads (or tails if that is the direction needed) are required, for 1/4 chance. And that chance only applies to some of the possibilites, resulting in more and more flips required for any significant increase in the probability that zero will have been reached. So as it goes on, it becomes less and less likely that zero will be reached any time soon if it has not already been reached. To be 90% sure of having reached zero would require 64 flips, and well over 200 are needed to be 95% sure of having reached zero.

[pdqkemp]

I'm sure there is an easier way to say this, but here is what I think the formula basically is:

2/2 + 4/4 + 6/8 + 8/16 + 10/32 + 12/64 + 14/128 + 16/256 + 18/512 + 20/1,024 + 22/2,048 + 24/4,096 + 26/8,192 + 28/16,384 + 30/32,768.......etc., etc., etc......

It appears to me that the number approaches 4.

[Guest]

Obviously, we need only consider even numbers of flips, and the formula works out to

1/n * (1- (sum(previous answers))), so 2 flips = .5 chance, exaclty 4 flips = 1/4(1-.5) = .125

exactly 6 flips = 1/6(1-.625) = .0625

exactly 8 flips = 1/8(1-.6875) = .0390625

etc.

I got the same answers as Nana7 at 64 flips for a cumulative 90% chance, 256 flips for 95%, and 6366 flips for 99%.

To answer the original question the expected number is any even number from 2 to infinity with decreasing chance as you go.

Edited May 8, 2011 by Scott from Eagan

[bonanova]

It should be a simple matter to simulate, counting the number

of flips to reach zero a million times and dividing the sum by

a million. I may try doing this, but first I'm just giving it some

intuitive thought.

[Guest]

I do not believe there is an expected number of times for reaching zero. I could say it is 4 flips by considering each pair of flips as 1 instance and since 1 instance has a 50% chance, then the expected is the reciprocal or 2 instances, hence 4 flips. But that only works if each instance is independant, if we start over after each 2 flips which we do not. As noted before, the chances of reaching zero decrease with each successive failure. I ran several simulations in excel for over a milion flips each and every result was different. Running it for a million successes rather than a million flips might give consistant results but I am doubtful. One thing that was consistant is that for every million flips, it ended with a long run of flips which were basically "stuck" and not likely to reach zero without many millions of more flips ie the final set had not reached zero even with thousands or hundreds of thousands of flips. I think the problem as stated is just too variable to have an expectation. Scott has it right, it is just an even number between 2 and infinity.

Edited May 9, 2011 by Nana7

[Guest]

Let me clarify what "expected number of flips" means. If you were to run a simulation until zero is reached and record the number of flips and then repeat this infinitely many times, what would the average number of flips be.

[Guest]

Let me clarify what "expected number of flips" means. If you were to run a simulation until zero is reached and record the number of flips and then repeat this infinitely many times, what would the average number of flips be.

Based on that wording...

The average number of flips to reach zero after running the simulation infinity times is itself infinity.

[Guest]

Based on that wording...

The average number of flips to reach zero after running the simulation infinity times is itself infinity.

Since the function need not ever return to zero, our numerator has to include infinity as a possible outcome. If I remember correctly, infinity/infinity is either 1 or infinity. Obviously not 1 in this case. Someone who remembers how to do integrals could likely show that the function integrates to infinity.

[Guest]

In order for the sum to be zero, clearly an even number of flips must take place with number of heads and tails being equal.

With this in mind, if we look at the number of ways in which flips could take place becomes easier.

For two flips it is simple either you should get HT or TH and not HH or TT.

If you consider 4 flips of coins, the total number of ways of flipping = 2^4

Of this, there are 4!/(2!2!) ways where heads and tails are equal in number. However, you need to rule out flips starting with HT or TH.

Now consider 6 flips, there are 2^6 possibilities out of which 6!/(3!3() ways for equal number of heads and tails flips.

Now discard flips starting with HT, TH or other combinations where first 4 flips settle to zero score.

Carry this on and you get probability for each even number of flips for which the sum could be zero.

Now if we multiply the prob at each step with the number of flips (2*0.5 + 4*0.125 +..)

you should get the expected number of flips.

I did this from 2 to 80 flips and the expected number of flips seems to approach 8.

[Guest]

In order for the sum to be zero, clearly an even number of flips must take place with number of heads and tails being equal.

With this in mind, if we look at the number of ways in which flips could take place becomes easier.

For two flips it is simple either you should get HT or TH and not HH or TT.

If you consider 4 flips of coins, the total number of ways of flipping = 2^4

Of this, there are 4!/(2!2!) ways where heads and tails are equal in number. However, you need to rule out flips starting with HT or TH.

Now consider 6 flips, there are 2^6 possibilities out of which 6!/(3!3() ways for equal number of heads and tails flips.

Now discard flips starting with HT, TH or other combinations where first 4 flips settle to zero score.

Carry this on and you get probability for each even number of flips for which the sum could be zero.

Now if we multiply the prob at each step with the number of flips (2*0.5 + 4*0.125 +..)

you should get the expected number of flips.

I did this from 2 to 80 flips and the expected number of flips seems to approach 8.

Nice job on showing the factorials to determine the routes back to zero. Unfortunately, while it does approach 8 considering cases up to 80 flips, it approaches 320 when considering cases up to 100,000 flips and just keeps going and going and going . . .

[Guest]

Nice job on showing the factorials to determine the routes back to zero. Unfortunately, while it does approach 8 considering cases up to 80 flips, it approaches 320 when considering cases up to 100,000 flips and just keeps going and going and going . . .

Really, are you sure? Because after 80, the increments were very small.

Did you subtract the cases where previous flips are to be rejected? I didnt do it beyond 80 as I was doing it on excel and had to slightly modify formula for ech flip and eventually I got tired of doing it!

[EventHorizon]

It seems there is no expectation. (i.e., there is no number corresponding to the average number of flips needed)

Let E(x) be the expected number of flips before you reach zero starting from number x.

I'll ignore negatives since E(x) = E(-x).

The answer to the problem will be 1+E(1).

E(0) = 0

E(1) = 1 + E(0)/2 + E(2)/2 = 1 + E(2)/2

E(2) = 1 + (1+E(2)/2)/2 + E(3)/2 = 3/2 + E(2)/4 + E(3)/2 => (3/4) * E(2) = 3/2 + E(3)/2 => E(2) = 2 + 2/3 * E(3)

...

E(x) = x + (x/(x+1)) * E(x+1)

E(1) = 1 + E(2)/2 = 1 + 1 + E(3)/3 = 1+1+1+E(4)/4 = ... = x + E(x+1)/(x+1)

E(x) will always be positive for nonzero x, so it seems E(1) just keeps increasing indefinitely as we substitute in equations.

Anyone see a mistake in my reasoning?

A side note for those new to situations where there is no expectation, it's not that uncommon. For instance, the Cauchy distribution has no mean or variance... it simply has too much probability in the tails. That Wikipedia page has a section or two that explains how it is possible to not have a mean or variance.

[Guest]

Really, are you sure? Because after 80, the increments were very small.

Did you subtract the cases where previous flips are to be rejected? I didnt do it beyond 80 as I was doing it on excel and had to slightly modify formula for ech flip and eventually I got tired of doing it!

I think my spreadsheet is sound. I ran it up 1,000,000 flips and at that point the liklihood of each occurance is only 7.98E-10, but when you mutiply that times the 1,000,000 to get the delta on the weighted average you are adding .000798.

Since the OP has not weighed in, perhaps we are on the wrong track though.

[Guest]

some quick hints:

This is basically just a 1-Dimensional random walk. (some research on those may help you.)

You can always try a pascal's triangle-like construction

lastly, the answer is equal to sum from n=1 to n=infinity of n*probability of first hitting zero after n flips

I've seen some good attempts so far, but none quite right. Keep trying and good luck!

[Guest]

Ok, so I figured that for the sum to be zero at 2n^th toss of the coin (and not before), the number of ways is

²ⁿC_n / (2n-1)

Total number of ways in which 2n coins can be tossed = 2²ⁿ

So, P(2n) that the sum would be zero (and not before) = ²ⁿC_n / (2n-1)*2²ⁿ

The required expected number of tosses should then be = sum (for n=1 to infinity) 2n.P(2n)

Now here I am not able to simplify further.

[Guest]

Ok, so I figured that for the sum to be zero at 2n^th toss of the coin (and not before), the number of ways is

²ⁿC_n / (2n-1)

Total number of ways in which 2n coins can be tossed = 2²ⁿ

So, P(2n) that the sum would be zero (and not before) = ²ⁿC_n / (2n-1)*2²ⁿ

The required expected number of tosses should then be = sum (for n=1 to infinity) 2n.P(2n)

Now here I am not able to simplify further.

I'm in a bit of a hurry and don't have my work with me at the moment, but from a quick glance, you seem to be on the right track. I would suggest using "wolfram alpha" to find the sum of the series quickly (though it doesn't always have the answer). If not, there is always calculus or even just a numerical approximation.

[Guest]

the answer is the sum from n=1 to infinity of (2n-2)!/(n-1)!²*4^-(n-1)

I'll leave it to you to figure out why. (hint: I used the Catalan numbers.)

This sum does not converge and thus it is expected to take infinitely long to reach 0 again.

I know that some of you predicted this, and you were right. Your reasoning, though, didn't quite prove it.

[EventHorizon]

the answer is the sum from n=1 to infinity of (2n-2)!/(n-1)!²*4^-(n-1)

I'll leave it to you to figure out why. (hint: I used the Catalan numbers.)

This sum does not converge and thus it is expected to take infinitely long to reach 0 again.

I know that some of you predicted this, and you were right. Your reasoning, though, didn't quite prove it.

Every experiment you run will terminate in a finite number of flips. Think the gambler's ruin problem... it'll always return to 0 eventually. So, infinity cannot be the expected number since every experiment terminates with less flips than it.

It's more correct to say there is no expectation. Page with some definitions / explanations.

Also, I could not find a problem with my proof (yeah, I could have been more formal (i.e., "Assume the expectation exists. Therefore E(1) is finite. ...")). This isn't necessarily my area of expertise, so let me know if I've made a mistake somewhere.

[Guest]

the expected number of times means the sum of each possible number of times times its possibility.....

=2*(1/2)+4*(1/2*1/4)+8*(1/2*1/4*1/8)*......*(2n)*{ 1 / [ 2(n!) ] }*......

=2

unexpectable expected number!?

[Guest]

the way i see it you have 1/2 a chance of getting heads and 1/2 a chance of getting tails so.... 1/2 the time you will get heads and 1/2 the time you will get tails... im not positive but im going to say 2!!!