# coin tossing to infinity **URL:** \ **Category:** Factual Questions\ **Created:** [August 30, 2003, 2:55pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632 "2003-08-30T14:55:37Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 30, 2003, 9:49pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/21 "2003-08-30T21:49:18Z")
> [@](#): > > \*Originally posted by lucwarm \* > **The trouble is that as time goes by you tend to get more and more hopelessly far from the goal. So by the time you get a decent run, it probably won’t help you.** Perhaps I wasn’t clear. In a random binary sequence of infinite length, runs of _arbitrary_ length are expected to occur. Not just of decent length, but of _any_ length. This would not be the first random walk problem I’ve seen where you end up at the origin with a high probability that doesn’t depend on where you start from, despite the fact that the odds appear to be stacked against you. ---
**Author:** ![lucwarm](https://avatars.discourse-cdn.com/v4/letter/l/e19adc/32.png) [@lucwarm](https://boards.straightdope.com/u/lucwarm)\ **Post date:** [August 30, 2003, 10:05pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/22 "2003-08-30T22:05:32Z")
> [@](#): > > \*Originally posted by ultrafilter \* > **Perhaps I wasn’t clear. In a random binary sequence of infinite length, runs of _arbitrary_ length are expected to occur. Not just of decent length, but of _any_ length.** No, I understood. My point is that your run – however long – is likely to be too late to do much good. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 30, 2003, 10:16pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/23 "2003-08-30T22:16:59Z")
Not if it’s long enough. **Crozell** , press the quote button in the bottom right of my post to see how I did the coding. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [August 30, 2003, 10:19pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/24 "2003-08-30T22:19:25Z")
I agree with **lucwarm** on this. As time goes on, the mean of the probability distribution increases linearly with N, the number of coin flips. However, the standard deviation increases as N[sup]1/2[/sup]. So, the number of sigmas below the mean that you need in order to get to the answer is _increasing_ with time, whereas in the typical random-walk problem it’s decreasing. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [August 30, 2003, 10:31pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/25 "2003-08-30T22:31:33Z")
> [@](#): > > _Originally posted by Hari Seldon \* > The probability of doing it in exactly 1000 tosses is 2^{-1000}. It can’t happen in 1001 or 1002, while the chances of its happening in 1003 is 1003_2^{-1003}. After 1006, it is > C(1006,2)\*2^{-1006} and so on. I think I might be able to estimate the resultant sum. > > I won’t go into the details, but I compute that the sum of that series is less than 2^{-999}, which is roughly 10^{-300}. This can’t be right. The very second term of your series is 1003 × 2[sup]-1003[/sup], which is roughly 2[sup]-993[/sup]. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [August 30, 2003, 10:44pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/26 "2003-08-30T22:44:25Z")
> [@](#): > > \*Originally posted by Achernar \* > \*\*This can’t be right. The very second term of your series is 1003 × 2[sup]-1003[/sup], which is roughly 2[sup]-993[/sup]. \*\* Yes I should have multiplied by a 1000, so instead of 10^{-300} it ought to be 10^{-297}. I guess the multiplier of the second term ought to be 1002, since, as observed, the one head cannot be the last (else it would have already been counted). And the remaining terms should also be a bit smaller. However, the analysis I used ignored the first few thousand terms of the series, so the numbers ought to be larger, but it doesn’t change the fact that the odds are very tiny. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [August 30, 2003, 10:58pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/27 "2003-08-30T22:58:36Z")
I agree that the odds are pretty tiny, but I still think we’re talking several orders of magnitude here. The terms increase in size for a while - the fifth term is C(1012, 4) × 2[sup]-1012[/sup] = 10[sup]-294[/sup]. I know the terms in my slightly different series keeps increasing up until term #443. ---
**Author:** ![shijinn](https://avatars.discourse-cdn.com/v4/letter/s/cc9497/32.png) [@shijinn](https://boards.straightdope.com/u/shijinn)\ **Post date:** [August 30, 2003, 11:33pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/28 "2003-08-30T23:33:46Z")
IANAM, but if we’re talking about infinity isn’t a sequence of 1000 or 10000 or 1000000 tails _relatively_ small theoretically? ---
**Author:** ![biqu](https://avatars.discourse-cdn.com/v4/letter/b/7feea3/32.png) [@biqu](https://boards.straightdope.com/u/biqu)\ **Post date:** [August 30, 2003, 11:50pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/29 "2003-08-30T23:50:43Z")
> [@](#): > > _Originally posted by crozell_ > Also, how are you doing subscripts? I tried the \ tags, but they just appeared as the tags themselves when I previewed. Subscripts: x[sub]n[/sub] becomes x[sub]n[/sub]. And if you ever want to see how a poster coded something, just hit the quote button below the post. ---
**Author:** ![Shade](https://avatars.discourse-cdn.com/v4/letter/s/2bfe46/32.png) [@Shade](https://boards.straightdope.com/u/Shade)\ **Post date:** [August 30, 2003, 11:53pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/30 "2003-08-30T23:53:31Z")
Have a look at my approach. I’m sure I’ve made a mistake somewhere, but I think the approach might be useful. Let P(n;event) be the probability of the event, starting with n. Let p[sub]m,n[/sub] be the probability that, starting from m, you ever get to n. By symmetry p[sub]n+1,n[/sub]=p[sub]1,0[/sub]. p[sub]2,0[/sub] =P(2; hit 0) =P(2; hit 0 | hit 1) . P(2; hit 1) + P(2; hit 0 | don’t hit 1) . P(2; dont’ hit 1) =p[sub]1,0[/sub]p[sub]2,1[/sub]+0.(…) =p[sub]1,0[/sub][sup]2[/sup] But p[sub]1,0[/sub] = [sup]1[/sup]/[sub]2[/sub] + ([sup]1[/sup]/[sub]2[/sub])p[sub]3,0[/sub] = [sup]1[/sup]/[sub]2[/sub] + ([sup]1[/sup]/[sub]2[/sub])p[sub]1,0[/sub][sup]3[/sup] Solving the cubic gives p[sub]1,0[/sub]=1/phi, so p[sub]1000,0[/sub]=1/phi[sup]1000[/sup] ---
**Author:** ![Olive\_The\_Other\_Reindeer](https://avatars.discourse-cdn.com/v4/letter/o/f9ae1b/32.png) [@Olive\_The\_Other\_Reindeer](https://boards.straightdope.com/u/Olive_The_Other_Reindeer)\ **Post date:** [August 31, 2003, 12:04am UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/31 "2003-08-31T00:04:28Z")
> [@](#): > > _Originally posted by Zeldar \* > \*\* > I think there are two “rules” or “laws” in effect that seem to conflict with each other._\* \ Let’s see - this was covered in a paper I wrote in 1986 . . . Little’s Law of Large Numbers states that as the sample set increases, the deviation from the ideal distribution decreases exponentially. For example, the deviation from a flat curve for 1000 runs of a lottery may be 10%. For 1,000,000 runs, the deviation decreases to 1%. However, because of the larger sample set, each percentage is larger, thus no assumptions can be made as to any following outcomes to fit the expected ideal curve. I leave this as an interesting exercise for the reader to work out. I have a interesting original proof of this myself, but the margins on the message board are too small to contain it. \ ---
**Author:** ![lucwarm](https://avatars.discourse-cdn.com/v4/letter/l/e19adc/32.png) [@lucwarm](https://boards.straightdope.com/u/lucwarm)\ **Post date:** [August 31, 2003, 12:34am UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/32 "2003-08-31T00:34:37Z")
> [@](#): > > \*Originally posted by ultrafilter \* > **Not if it’s long enough.** Look at it this way . . . how many flips would you have to do to have a reasonable chance of getting 1000 tails in a row? It’s gotta be a LOT more than 5000. After 5000 flips, if nothing special happens, you’ll be somewhere in the vicinity of 3500 spaces away from home. So now, if 1000 tails in a row come along, it’s not anywhere near what you need to get home. You need another 2500 tails. How long do you have to wait to get 2500 tails in a row? It’s gotta be a LOT more than 10,000 flips. etc. etc. * * * Now, there are other ways of getting “home” that don’t involve an uninterrupted streak. But it just seems to me that this is not like a situation where you are waiting for some particular event to happen – like drawing a straight flush in poker. Instead, as the experiment continues, the bar keeps getting higher and higher – very quickly. ---
**Author:** ![David\_Simmons](https://avatars.discourse-cdn.com/v4/letter/d/9de053/32.png) [@David\_Simmons](https://boards.straightdope.com/u/David_Simmons)\ **Post date:** [August 31, 2003, 1:15am UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/33 "2003-08-31T01:15:16Z")
> [@](#): > > \*Originally posted by lucwarm \* > \*\*Disagree. … you are, in effect, claiming that a return to home is certain from any starting point. \*\* > [@](#): > > _Originally posted by ultrafilter_\*\* > > Perhaps I wasn’t clear. In a random binary sequence of infinite length, runs of arbitrary length are expected to occur. Not just of decent length, but of any length.\*\* I’m now leaning to the idea that return to zero is certain, and I have thus covered all bases from “it can’t happen” to “it has to happen.” My reasons are based on **ultrafilter’s** point and I think that you will end up at the origin from any starting point. We have a random walk on a line that runs from zero on the left to as far as necessary (no limit was set in the OP) on the right. So no matter how far the throwing of heads moves the start to the right, sooner or later there has to be a run of tails that will bring you back to zero. ---
**Author:** ![The\_Griffin](https://avatars.discourse-cdn.com/v4/letter/t/a87d85/32.png) [@The\_Griffin](https://boards.straightdope.com/u/The_Griffin)\ **Post date:** [August 31, 2003, 1:17am UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/34 "2003-08-31T01:17:45Z")
Yes but it IS possible to get 1000 tails right at the start. Improbable, but it is clearly possible. So the answer to the original poster’s question is an obvious “yes, it is possible”. I really dont see what infinity has to do with it. It’s always possible, but it get increasing less probable as the number of tosses continues. Quite simple really. ---
**Author:** ![enigmatic](https://avatars.discourse-cdn.com/v4/letter/e/898d66/32.png) [@enigmatic](https://boards.straightdope.com/u/enigmatic)\ **Post date:** [August 31, 2003, 10:07am UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/35 "2003-08-31T10:07:49Z")
The point was that as I see it if you tossed the coin an infinite number of times you would definitely get back to zero, as no matter how many tosses you have made there is always a chance of getting back to the start. Therefore if you keep flipping coins for an infinite length of time eventually that event will occur even though the probability of it happening decreases faster than it is increased by the multiple attempts. I suppose this all depends on your definition of infinity. Another way I thought of expressing sort of the same problem that might make for less complicated maths is as follows. If you were to repeatedly attempt to do something starting with a 1/1000 chance of success which halved with each subsequent attempt 1/1000, 1/2000, 1/4000 etc if you kept on trying an infinite number of times would you eventually succeed. I would say that this is a much clearer cut yes than the above example even though the probability decreases faster with each attempt (although obviously the probability of success in the first few attempts is much higher). As regards the starting number/probability I agree that for any sequence of a defined number of flips/attempts the starting point affects the probability of success, I don’t think this is the case with an infinite series I think there is a 100% probability of success no matter what the starting point is but I can’t really explain why (but I now have a headache). ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [August 31, 2003, 10:11am UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/36 "2003-08-31T10:11:20Z")
> [@](#): > > \*Originally posted by Shade \* > Let P(n;event) be the probability of the event, starting with n. Let p[sub]m,n[/sub] be the probability that, starting from m, you ever get to n. > > By symmetry p[sub]n+1,n[/sub]=p[sub]1,0[/sub]. > > p[sub]2,0[/sub] > =P(2; hit 0) > =P(2; hit 0 | hit 1) . P(2; hit 1) + P(2; hit 0 | don’t hit 1) . P(2; dont’ hit 1) > =p[sub]1,0[/sub]p[sub]2,1[/sub]+0.(…) > =p[sub]1,0[/sub][sup]2[/sup] > > But p[sub]1,0[/sub] = [sup]1[/sup]/[sub]2[/sub] + ([sup]1[/sup]/[sub]2[/sub])p[sub]3,0[/sub] = [sup]1[/sup]/[sub]2[/sub] + ([sup]1[/sup]/[sub]2[/sub])p[sub]1,0[/sub][sup]3[/sup] > > Solving the cubic gives p[sub]1,0[/sub]=1/phi, so p[sub]1000,0[/sub]=1/phi[sup]1000[/sup] I think this has to be right. However, another valid solution to your cubic is p[sub]1,0[/sub] = 1, and I can’t think of a good reason to discount this solution. I found an omission in my analysis before that gave p[sub]6,0[/sub] = 0.0691. I don’t know how to fix it, but I do now believe that value to be too high. Just from that, I like your value of p[sub]6,0[/sub] = 0.0557. ---
**Author:** ![Shade](https://avatars.discourse-cdn.com/v4/letter/s/2bfe46/32.png) [@Shade](https://boards.straightdope.com/u/Shade)\ **Post date:** [August 31, 2003, 12:33pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/37 "2003-08-31T12:33:41Z")
Good point. I’ve an informal agrument on that matter: If you change the probabilities so the probability of subtracting one is slightly greater than half, then p[sub]1,0[/sub] must increase. The 1/phi root increases slightly if the cubic is so adjusted, whereas the 1 root decreases. So the 1/phi must be right. ---
**Author:** ![lucwarm](https://avatars.discourse-cdn.com/v4/letter/l/e19adc/32.png) [@lucwarm](https://boards.straightdope.com/u/lucwarm)\ **Post date:** [August 31, 2003, 3:05pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/38 "2003-08-31T15:05:15Z")
> [@](#): > > \*Originally posted by enigmatic \* > \*\* > Another way I thought of expressing sort of the same problem that might make for less complicated maths is as follows. If you were to repeatedly attempt to do something starting with a 1/1000 chance of success which halved with each subsequent attempt 1/1000, 1/2000, 1/4000 etc if you kept on trying an infinite number of times would you eventually succeed. \*\* I disagree. To see this, let’s consider the probability of at least 1 success in two attempts. That probability is 1- (1 - 1/1000)(1-1/2000), which is approxmately equal to 3/2000, but strictly less. It seems to me that in general, the probability of at least 1 success is strictly less than the sum of the probabilities for each attempt. The series 1/1000 + 1/2000 + 1/4000 . . . converges to 1/500. So it seems to me that the probability of eventual success is something less than 1/500 (but greater than 1/1000 of course) Put another way, there is no number “N” such that the probability of at least one success after N attempts is greater than 1/500. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 31, 2003, 5:55pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/39 "2003-08-31T17:55:22Z")
Has anyone else looked at this as a Markov chain with 0 as an absorbing state? I played around with it a little, but it’s been too long since I did this sort of thing, and I’m making a mistake that I can’t catch. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [August 31, 2003, 6:15pm UTC](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632/40 "2003-08-31T18:15:07Z")
> [@](#): > > \*Originally posted by Shade \* > If you change the probabilities so the probability of subtracting one is slightly greater than half, then p[sub]1,0[/sub] must increase. > > The 1/phi root increases slightly if the cubic is so adjusted, whereas the 1 root decreases. So the 1/phi must be right. Your argument sounds good, but I don’t see the math for it. For instance, if there’s a probability of 0.6 of decreasing, the cubic becomes: p[sub]1,0[/sub] = 0.6 + 0.4p[sub]1,0[/sub][sup]3[/sup] This has roots at 0.823 and 1. So, the 1/phi root increases, and the 1 root is constant. [Previous page](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632.md?page=1) [Next page](https://boards.straightdope.com/t/coin-tossing-to-infinity/198632.md?page=3)