# Statistical coin flipping question **URL:** \ **Category:** Factual Questions\ **Created:** [March 3, 2005, 1:49am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687 "2005-03-03T01:49:54Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Iamu](https://avatars.discourse-cdn.com/v4/letter/i/ed655f/32.png) [@Iamu](https://boards.straightdope.com/u/Iamu)\ **Post date:** [March 3, 2005, 1:49am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/1 "2005-03-03T01:49:54Z")
Here’s a question for all the math wizards on the boards. I have a feeling it should be easy enough to figure out, but I can’t remember my stat classes for the life of me. Let’s say I’m going to flip a coin (w/exactly 50% chance of landing on either face) an indefinite number of times. Projecting from now, before I start flipping, on which flip can I say that I am 90% certain that the number of heads has equalled the number of tails at least once during the progression of tosses? How do I calculate this, short of charting out every possibility? In case that wasn’t clear, let’s say I’m flipping a coin and using the results to modify x. The initial value of x is zero. Every heads result increases x by one, every tails decreases x by one. On what flip can I be 90% certain that x has reached 0 again at least once? This article is what prompted me to ask: [http://www.rednova.com/news/display/?id=126649#121](http://www.rednova.com/news/display/?id=126649#121) I’m trying to write a program that works on a similar principle to the one being utilized in these tests, so I can maybe personally evaluate their validity. Thanks in advance, teeming millions. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 3, 2005, 2:06am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/2 "2005-03-03T02:06:11Z")
One thing to keep in mind is that you can’t be in state 0 after an odd number of flips, so that complicates things a bit. I’ll have to think about the problem some more–I know I’ve seen an analysis of it, but I threw away those notes a long time ago. It sounds like a variation on the gambler’s ruin problem; perhaps you could search on that. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [March 3, 2005, 2:09am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/3 "2005-03-03T02:09:59Z")
This is a random walk problem in one dimension. I don’t have time to think about it at the moment, but what you want may be mentioned [here](http://mathworld.wolfram.com/RandomWalk1-Dimensional.html). ---
**Author:** ![Xema](https://avatars.discourse-cdn.com/v4/letter/x/9de053/32.png) [@Xema](https://boards.straightdope.com/u/Xema)\ **Post date:** [March 3, 2005, 2:19am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/4 "2005-03-03T02:19:18Z")
Cabbage’s link contains this: > [@](#): > > Surprisingly, the most probable number of sign changes in a walk is 0, followed by 1, then 2, etc. Which seems to be saying that there is no number of trials that will make the probability of an equal number of heads and tails 90%. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [March 3, 2005, 2:34am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/5 "2005-03-03T02:34:32Z")
> [@Xema](#): > > Cabbage’s link contains this: > > > [@](#): > > > > Surprisingly, the most probable number of sign changes in a walk is 0, followed by 1, then 2, etc. > > Which seems to be saying that there is no number of trials that will make the probability of an equal number of heads and tails 90%. I don’t see the connection here. Actually, I do know for a fact that the probability of heads and tails being even at _some_ point converges to 1 as the number of flips increase, from having looked at random walks before. So it’s gotta be 90% eventually. ---
**Author:** ![Askance](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/askance/32/8281_2.png) [@Askance](https://boards.straightdope.com/u/Askance)\ **Post date:** [March 3, 2005, 2:43am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/6 "2005-03-03T02:43:11Z")
> [@Iamu](#): > > Projecting from now, before I start flipping, on which flip can I say that I am 90% certain that the number of heads has equalled the number of tails at least once during the progression of tosses? You’re begging the question; is there necessarily any such flip? Your assumption seems to be that as you flip the probability of this mounts up and will reach 90%, but I see no reason why that should be. After two flips the probability of exactly half heads and half tails so far is 50%. After four it is 6/16 = 37.5%; so as you go on the probability actually lessens. The question is the same as: how many digits does a binary number have to be before 90% of the binary numbers of that many digits are composed of equal numbers of 0s and 1s? I’m fairly sure there will be no such animal. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 3, 2005, 2:44am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/7 "2005-03-03T02:44:59Z")
Like **Cabbage** , I’ve seen the analysis that shows that a symmetric random walk starting out at the origin will, with probability 1, return to the origin. ---
**Author:** ![Xema](https://avatars.discourse-cdn.com/v4/letter/x/9de053/32.png) [@Xema](https://boards.straightdope.com/u/Xema)\ **Post date:** [March 3, 2005, 3:43am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/8 "2005-03-03T03:43:01Z")
> [@ultrafilter](#): > > Like **Cabbage** , I’ve seen the analysis that shows that a symmetric random walk starting out at the origin will, with probability 1, return to the origin. I have to say it sounds plausible that in enough trials anything will come to pass. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 3, 2005, 5:01am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/9 "2005-03-03T05:01:49Z")
> [@Xema](#): > > I have to say it sounds plausible that in enough trials anything will come to pass. Not sure about 2d, but I know that in a 3d random walk, the probability that a given walk will ever return to the origin is significantly less than 1. ---
**Author:** ![Iamu](https://avatars.discourse-cdn.com/v4/letter/i/ed655f/32.png) [@Iamu](https://boards.straightdope.com/u/Iamu)\ **Post date:** [March 3, 2005, 5:16am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/10 "2005-03-03T05:16:43Z")
> [@](#): > > You’re begging the question; is there necessarily any such flip? Your assumption seems to be that as you flip the probability of this mounts up and will reach 90%, but I see no reason why that should be. > > After two flips the probability of exactly half heads and half tails so far is 50%. After four it is 6/16 = 37.5%; so as you go on the probability actually lessens. I don’t think I explained my question clearly; I am asking for the point at which I can be 90% certain that the number of heads has equalled the number of tails **at least once**. I designed the program so that the statistical operations would be as simple and algorithmic as possible; the whole process resets whenever heads and tails equal out, so I’m really only concerned with progressions that don’t even out at all before they hit a statistically meaningful threshold. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 3, 2005, 5:33am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/11 "2005-03-03T05:33:53Z")
> [@Iamu](#): > > I don’t think I explained my question clearly; I am asking for the point at which I can be 90% certain that the number of heads has equalled the number of tails **at least once**. > > I designed the program so that the statistical operations would be as simple and algorithmic as possible; the whole process resets whenever heads and tails equal out, so I’m really only concerned with progressions that don’t even out at all before they hit a statistically meaningful threshold. Let a trial consist of, oh, 1000 runs of n coin flips. If fewer than 900 of them end prematurely for a given n, increase n and try again. ---
**Author:** ![Rico](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rico/32/3582_2.png) [@Rico](https://boards.straightdope.com/u/Rico)\ **Post date:** [March 3, 2005, 5:47am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/12 "2005-03-03T05:47:37Z")
> [@Askance](#): > > After two flips the probability of exactly half heads and half tails so far is 50%. After four it is 6/16 = 37.5%; so as you go on the probability actually lessens. As a seasoned Las Vegas devotee, I think I can say your hypothesis there is missing one important point: _At no time during the series of flips does the size or shape of the coin (object) change. Therefore, assuming the tosses are not designed to ensure one outcome or the other (such as throwing the coin straight up without turning it over), the outcome of **each** throw is 50/50. This does not change on any throw._ Or look at it this way. From [here](http://mathforum.org/library/drmath/view/56587.html): > [@](#): > > Q: I wonder how I can figure out the chances of the following case: > > Flipping a coin five times with the result a combination of T,T,T,H,H. > (T=Tail, H=Head) > > To flip the same coin five times, what will be the chances of getting > the same combination (exact sequence) “right away”? > > A: You will be performing the same experiment 5 times in succession; that is, flipping a coin. Each flip of the coin can result in 2 distinct and equally likely outcomes, H or T. _Moreover, the result of any coin flip is not influenced by or > dependent upon any previous coin flip._ That last statement regarding independence of the coin flips is very important; it tells us that all possible outcomes after 5 coin flips are equally likely, or have the same probability. > > By the Principle of Counting, there are 2_2_2_2_2, or 32 possible > outcomes to your problem. The one you are interested in is (TTTHH). > The chance of getting T(first flip), then T(second flip), then T(third > flip), H on the fourth flip and H on the fifth flip is: > > ``` > (1/2)*(1/2)*(1/2)*(1/2)*(1/2) = 1/32. > > ``` > > In fact, every one of the 32 possible outcomes from flipping a coin 5 > times has the same probability … 1/32. (italics mine) If the probability changed _at all_, games such as roulette would be able to be mathematically figured out and bet to the player’s advantage using only red and black bets. The green 0 and 00 spaces are the house’s only advantage, if you only bet red or black. If there were no 0 and 00, the house advantage would be zero, but then again, so would yours. Make sense? ---
**Author:** ![Iamu](https://avatars.discourse-cdn.com/v4/letter/i/ed655f/32.png) [@Iamu](https://boards.straightdope.com/u/Iamu)\ **Post date:** [March 3, 2005, 6:12am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/13 "2005-03-03T06:12:05Z")
I believe I have more or less found my answer. # of flips probability 2 .5 4 .6875 6 .78515625 8 .84390259 I derived this from the info given on the random walk website given provided by Cabbage. By the time I had bothered to calculate it to 8 flips, I just dropped it into excel and followed the obvious trend on the graph. I believe about 12 or 14 flips should serve my purposes. I think I can feel it out from here based on how much data gets logged. I’m not a math person, though, in case you couldn’t tell, so I’d love to hear any and all further thoughts on this. Thanks a ton, guys 🙂 ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [March 3, 2005, 6:13am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/14 "2005-03-03T06:13:34Z")
Actually, **Rico** , **Askance** is correct; the probabilities of even numbers of heads and tails after 2 and 4 flips are 1/2 and 6/16, respectively. For example, in four flips, the possibilities are: HHTT HTHT HTTH THTH TTHH THHT What **Askance** missed was that the OP is not interested in the probability of even heads and tails _at_ the nth flip, but the probability of even heads and tails at some point _during the course_ of the n flips. ---
**Author:** ![Rico](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rico/32/3582_2.png) [@Rico](https://boards.straightdope.com/u/Rico)\ **Post date:** [March 3, 2005, 6:24am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/15 "2005-03-03T06:24:12Z")
You are correct, **Cabbage** and **Askance**. The operative phrase there is “even numbers of heads and tails.” Missed that. Then again, I damn near failed high school algebra, so what am I even doing in a thread like this? :eek: 😛 ---
**Author:** ![RM\_Mentock](https://avatars.discourse-cdn.com/v4/letter/r/e274bd/32.png) [@RM\_Mentock](https://boards.straightdope.com/u/RM_Mentock)\ **Post date:** [March 3, 2005, 9:02am UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/16 "2005-03-03T09:02:39Z")
> [@Iamu](#): > > I believe I have more or less found my answer. > > # of flips probability > > 2 .5 > 4 .6875 > 6 .78515625 > 8 .84390259 > > I derived this from the info given on the random walk website given provided by Cabbage. By the time I had bothered to calculate it to 8 flips, I just dropped it into excel and followed the obvious trend on the graph. I believe about 12 or 14 flips should serve my purposes. I think I can feel it out from here based on how much data gets logged. > > I’m not a math person, though, in case you couldn’t tell, so I’d love to hear any and all further thoughts on this. Thanks a ton, guys 🙂 For 4 flips, your answer is .6875, which is 11/16. I believe the right answer is 10/16, but I’m pretty sure that there are are 16 possible outcomes and each has a mirror twin–so the numerator has to be even. Weird, for 6 flips, there are 2^6 outcomes, but .78515625 times 2^6 is 50.25. ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [March 3, 2005, 4:51pm UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/17 "2005-03-03T16:51:14Z")
This is closely related to the so-called “Ballot Problem”: if you’re counting ballots in a two-party election, and Candidate A gets m votes out of a total of N, then how many ways are there to count the ballots in such a way that candidate A is always ahead in the counting? The answer (digging out my old combinatorics textbook) is (N)C(m) \* (N - 2m + 1)/(N - m + 1) where (N)C(m) = N!/((N-m)! m!) is a binomial coefficient. So if you’re looking for the number of possible sequences of length N for which the accumulated number of heads is _always_ ahead of the number of tails, you would just sum over m: (total number of such walks) = 2 \* (Sum from m = 0 to N/2) [(N)C(m) \* (N - 2m + 1)/(N - m + 1)] and the probability of a sequences that “never flips sides” would be this number divided by 2[sup]N[/sup]. (There’s an extra factor of two above to account for the fact that we were only looking at sequences in which “heads” is always in the lead, as opposed to “tails”.) I get that the number of sequences which do _not_ flip sides (plugging this into Mathematica) is: ```auto N number of sequences prob. of such a seq. -------------------------------------- 1 2 1.0 2 4 1.0 3 6 0.75 4 12 0.75 5 20 0.625 6 40 0.625 7 70 0.5469 8 140 0.5469 10 504 0.4922 12 1848 0.4512 ``` This seems to be at odds with what other people have said above, so maybe I’m misintepreting the question. ---
**Author:** ![aahala](https://avatars.discourse-cdn.com/v4/letter/a/a88e4f/32.png) [@aahala](https://boards.straightdope.com/u/aahala)\ **Post date:** [March 3, 2005, 6:37pm UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/18 "2005-03-03T18:37:36Z")
What you need to do is calculate the probabilities of “first even appearance” for flips 2, 4, . . .n and see if the sum equals .9. I don’t believe they will, but I’m uncertain. Calculating first appearance quickly becomes very involved and complicated. For 2 flips, it’s .5 For 4, it’s .125 For 6, it’s .0625 But my calculation for 8 is .0390625. This result surprised me as I would have anticipted the figure to have been .03125, based on the previous numbers, but I can’t find a mistake in my math. If the correct figure for 8 is actually .03125, it seems reasonable to believe the probability for each two additional flips will continue to be hallfed and the sum will never reach .9. As a side note, while the ratio of tails and heads is likely to become more and more even as the number of flips increase, the absolute difference is likely to grow. ---
**Author:** ![Freddy\_the\_Pig](https://avatars.discourse-cdn.com/v4/letter/f/a587f6/32.png) [@Freddy\_the\_Pig](https://boards.straightdope.com/u/Freddy_the_Pig)\ **Post date:** [March 3, 2005, 7:37pm UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/19 "2005-03-03T19:37:29Z")
> [@aahala](#): > > But my calculation for 8 is .0390625. Your calculation is exactly correct. The general formula for determining whether the **first** occurrence of equal heads and tails is after 2n flips is: (2n choosing n) \* (0.5^2n) / (2n - 1) The OP asks when the sum of the above probabilities reaches 0.9. The answer is when n=32, or after 64 flips. This is indeed a variation on the “Ballot Counting Problem”, where one candidate has to lead by one vote after (2n - 1) flips, and have led from the beginning, with the 2n’th flip creating the first tie. It’s discussed on page 122 of Introduction to Probability Models (7th edition) by Sheldon Ross. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 3, 2005, 8:33pm UTC](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687/20 "2005-03-03T20:33:07Z")
> [@aahala](#): > > If the correct figure for 8 is actually .03125, it seems reasonable to believe the probability for each two additional flips will continue to be hallfed and the sum will never reach .9. That’s a geometric series with common ratio 1/2, and it does converge. [Next page](https://boards.straightdope.com/t/statistical-coin-flipping-question/292687.md?page=2)