Q: If you flip a coin forever, are you guaranteed to eventually flip an equal number of heads and tails?

The original question was: Lets say we have a fair coin that is flipped a hundred times and at the end of the trial there have been 40 tails and 60 heads. At this time there have been 20 more heads than tails and it could be said that heads is “dominant”.

Is it inevitable that, given enough time to occur, eventually a “switch-over” in dominance will occur and tails will be dominant, or is it the case that dominance by heads or tails can carry on indefinitely?

If a “self correction” is inevitable, how long, on average, would a correction take (the equalizing of the number of heads and tails)? Is it something you will see by the end of the day or something you won’t see in your lifetime. (on average of course, I accept that both are theoretically possible)?

What is the likely number of flips between each “switch-over” and is a “switch-over” guaranteed?

Physicist: In the very specific case of this question: yes.  In fact (for this very specific case) any given tally (e.g., 7,823 more heads than tails) will happen eventually, regardless of what the imbalance presently is.  Since that includes #-of-heads = #-of-tails, then eventually (in less than infinite time) you’ll always flip the same number of heads as tails.  Even “better”, this will happen an infinite number of times.  If you really keep at it.

However, this is entirely do to the fact that this coin example is the same as the “1 dimensional discrete random walk”.  If you assign “+1″ to heads and “-1″ to tails, then you can keep a running tally with one number.  The fact that, starting with a tally of zero, you’ll eventually return to zero isn’t any kind of “self correcting” property of the universe.  Even slightly different situations (such as one side of the coin being even a tiny, tiny bit more probable) will create “non-recurrent” strings of coin flips.

The tally changes by about the square root of the number of flips (on average), and this can be either an increase or decrease (equal chance).  This is an important part of the “central limit theorem“.  Starting at zero, if you’re flipping 10 coins a minute, then at the end of the day you can expect the difference between the number of heads and tails to be in the neighborhood of \sqrt{10\times60\times24} = 120.

Three days spent filling and counting coins will produce running tallies like this.

Just so you don’t have to do it: Three days spent flipping and counting coins will produce running tallies like this.  The curves are the square root of the number of flips, and most of the time (~64%) the tally will stay between these lines.

Anything between, say, +200 heads or +200 tails is pretty normal, which is a little surprising considering that 200 is pretty small for a full day of coin flipping.  During the course of that day there’s a good chance you’ll “pass zero” several times.

The question of how long it will take for you to get back to the same tally is a little subtle.  If you’re close to zero, then there’s a good chance you’ll hit zero several more times in rapid succession.  But one of those zeros will be the last for a while since inevitably (and completely at random) you’ll get a string of tails or heads that carries you away from zero.  Every possible tally is achieved eventually, and since there are arbitrarily large numbers, there are arbitrarily long return-to-zero times.  That isn’t a rigorous proof, but it turns out that the average return time is infinite.

So basically, if you’re flipping a coin and the total number of heads is equal to the total number of tails, then the same is likely to be true soon.  But if it doesn’t happen soon, then it probably won’t happen again a long time.  Really, the best you can say is that “square root thing”, which is that the tally will usually be within \pm\sqrt{N}, where N is the number of flips.

Answer gravy: For those of you who wanted the details behind that last bit, it turns out to be not too difficult to figure out how long it will take you to get back to zero.

However you get back to zero, you’ll have to flip the coin 2N times (you can’t have an equal number of heads and tails if you flip an odd number of times).  Now say you have a series of tallies that starts at zero, then stays greater than or equal to zero until the 2N flip.  The number of possible ways for this to happen is the Nth Catalan number, CN, which can be described as “the number of ways of arranging N pairs of parenthesis so that they make sense”.  Turns out that C_N = \frac{1}{N+1}{2N \choose N} (this is a choose function).

The probability that the 2Nth coin flip is the first that brings the tally back to zero, P(2N), is the number of paths that didn’t come back to zero before, divided by the total number of paths.

CN is the number of ways for the tally to be greater than or equal to zero.  To be strictly greater than zero, we need a little trick.  Say the first coin flip takes the tally to +1.  If the 2Nth coin flip brings the tally to zero (for the first time), then on the 2N-1th coin flip the tally was +1 as well.  So, the total number of paths starting with “heads” that makes 2N the first return to zero is CN-1 (the number of paths greater than or equal to one, between the first flip and the second to last flip).  Same thing works if the first flip is tails, which means we need to multiply the number of paths by two: 2CN-1.

The total number of possible paths is easy: 22N.  So,

P(2N) = \frac{2C_{N-1}}{2^{2N}} = \frac{1}{N 2^{2N-1}}{2(N-1) \choose N-1} = \frac{1}{2^{2N-1}}\frac{(2N-2)!}{(N-1)!(N-1)!}

Just to double check: notice that P(2) = 1/2, which is exactly what you’d expect (“TH” and “HT”, but not “HH” and “TT”).  If you’re close to, or at zero, then there’s a good chance you’ll be there again in short order, and you’re guaranteed to come back eventually.

The average number of flips to return to zero is:

\sum_{N=1}^\infty 2N \,P(2N) = \sum_{N=1}^\infty \frac{2N(2N-2)!}{2^{2N}(N-1)!(N-1)!}

However!  This is what folk in the math biz call a “divergent series” because it “adds up to infinity”.  Each term in the summation are about equal to \frac{2N(2N-2)!}{2^{2N}(N-1)!(N-1)!} \approx \frac{2}{\sqrt{\pi}}\sqrt{\frac{1}{N}} (using Stirling’s approximation).  While these do add up slower and slower (because you’re more likely to return to zero sooner than later), they still add up to infinity.

So, in a very technical/mathematical sense, if you flip a coin forever, then eventually you’ll get the same number of heads as tails.  Technically the average return time is infinite.  In practice 90% of the time you’ll get an equal number within 64 flips (fact!), and if you don’t then stop anyway.

This entry was posted in -- By the Physicist, Math, Probability. Bookmark the permalink.

19 Responses to Q: If you flip a coin forever, are you guaranteed to eventually flip an equal number of heads and tails?

  1. LarryD says:

    But even maths must give way to physics. If a plain coin(no marks on either side) is perfectly balanced with one identified with a cross and the other with two lines. If the starting position is the same each time and the number of mid air spins are the same what will the result be?

  2. Scott Owen says:

    Hmmm… my intuition says that the mathematics involved are not a law, but a statistical model, and it is in theory possible for a fair coin to be tossed an infinite number of times and always come up heads.

  3. John Cabbage says:

    If I can nitpick, I feel I should point out that this answer uses the colloquial definition of “inevitable” rather than the mathematical definition. 90% probability isn’t actually inevitable – just very very likely.

    Even 100% probability isn’t truly inevitable (because there could be a 0% probability it doesn’t happen – which is still a possibility when you talk about infinite series). Math is weird.

    I like this answer, I think you responded to the spirit of the question. But I think it should be pointed out there is no guarantee. All I can actually say is that given a certain dominance in heads or tails and a number of coin flips there is a probability that the dominance will switch at some point that rapidly approaches 100% as the number of flips grows large. But there is never truly a “guarantee” because you could always just get really unlucky (or lucky?) with your coin flips.

    Similarly the assertion that any given tally will happen eventually is actually one of the fundamental assumptions of probability (the large number theorem if you want to look it up), not a proven result. To say that any given tally will happen in a finite number of flips seems wrong or at least misleading to me, because for any given finite number of flips there is a non-zero probability that it doesn’t happen.

    Sorry to rant like this, but I feel like you are using some very strict terms a little loosely here.

  4. kopernik says:

    “Flipping a coin, equal heads and tails.’
    Well reasoned. Thanks.

    Allow me to take a metaphysical approach – We would not have the present universe, if chances for the development of a particular morphology was the same as that for another contrary to this one.
    Could say that the universe we have is the result of an early flip of coin. The circumstances of that very early flip have been playing out, even though there have been many flips since then. The result of that first flip ‘colors’ all that has come since.
    E.g., galaxy formation must follow a very proscribed pattern for development. The four physical forces have defined characteristics that are limited. Electromagnetic radiation can behave only in a certain manner.
    Still, the accumulating weight of uncountable flips very likely will lead to a ‘flip-flop’ that will bring an end to this universe, and set the stage for another.
    What think you all?

  5. Émile Essent says:

    You are wrong. It is possible to get only heads, forever. Probability is zero, but it is possible. Zero probability is not impossibility.

  6. Hernán says:

    @Émile I thought that a probability of zero == impossible (as in “will never happen, ever”)

  7. Miske50 says:

    I do not consider this as a (mathematical) probability problem at all as, in real world, it is a typical example of the chaos theory. Flipping a coin with whatever means, in real world, let us say with an arm and a hand and a thumb involves, unavoidably, a complex system of levers (i.e. bones, tendons and muscles), so, as a pendulum with large motions, it is bound to move chaotically. So, in the chaos theory, lies the answer on the description of coin flipping. The system is non-linear.
    Infinitely small changes in initial conditions result in finite differences in the result. It is called sensitive dependence on initial conditions.
    Statistics may help in “interpreting” the results but do not contribute to the understanding of the problem.

  8. Paul Czerner says:

    There is no guarantee, only percent likelyhood.

  9. Émile says:

    @Hernán zero-probability = impossible only when the number of things that can happen is finite. Here, the number sequences of H and T is finite as long as you restrict yourself to a limited number of trials, and then all sequences have the same probability (which is 1/(number of such sequences) = 1/2^n, where n is the number of trials).

    Now, if you play “forever”, the number of possible sequences is infinite and they still have equal probability… thus intuitively that probability is 1/(number of sequences)=1/infinity=0.

    Strange things happen around infinity !

  10. Pingback: Somewhere else, part 110 | Freakonometrics

  11. Mariano Quiroga says:

    There seems to be a problem with the very concept of the question. Assuming an infinite amount of flippings, would mean that every possible result should also be infinite. Can you speak of such a thing as “half infinite”? Would a sharp 50 % of infinity make any sense? May be we can consider a Limit that tends to infinite regarding the number of events, and a probability distribution of either states of a coin that infinitesimally tends to the 50th percentile

  12. webmail says:

    Thanks a bunch to the Physicist for answering this in such detail. That 90pc of all trials equalize within 64 flips is fascinating.

    @Miske50 That isnt the spirit of the question, its meant much like the monkeys writing Shakespeare, a debate of random number generation, not actual coins and monkeys.

  13. Dan says:

    I’m in an undergraduate probability class where we’ve talked about this.
    Technically, there is a difference between a probability of zero and impossibility. The reason is that if you throw a dart at a dartboard, the infinitely small point that is the exact center of your dart (assuming it’s perfectly round, etc.) will land on exactly one infinitely small point. But there is an infinite number of such points, and since the point is infinitely small, there is a probability zero of hitting exactly that same point again. In fact, for any given point on the dartboard, there is a probability zero that you will hit it, and yet you are guaranteed to hit one of those points. It sounds paradoxical, but it’s just an example of an infinite number of zeroes adding up to a finite value.
    In essence, I think you can get away with saying it is impossible for something to happen if it has probability zero, but if you want to do so, you have to keep in mind what your definition of impossibility is. In my mind, I define impossibility as anything that has a probability zero. It may not be totally robust, but it works well enough, because for any event in the future, once you’ve defined the event, it simply will not occur if its probability is actually zero. I would bet my life on it.

  14. Mr. Facetious says:

    If you flip a coin forever (infinitely), how can you “eventually” ever determine the total number of flips landing on heads or tails? Somewhere you will eventually have to stop flipping to sum the tally? Suppose you stopped on an odd number of flips; would there be more flips of heads or more flips of tails?

  15. Pseudoego says:

    90% probability of return to zero within 64 flips ignores that the other 10% of the time includes extremely long intervals of time during which the numbers *never* even out.

    All you need to do is think about all the possible combinations, and you will realize that there are some combinations which will simply keep pushing the number of heads (for example) further and further away from the number of tails.

    William Feller explained all of this over 50 years ago…there is no necessity that you will ever catch up once you are behind…that is another version of the Gambler’s Fallacy.

  16. Orien Rigney says:

    U.S. coins are as far as I know; not perfectly balanced. The head side in all instances is supposedly lighter then the tail side due to displacement of metal as the coin is struck. Best bet! Take a coin and flip it a hundred times. Which side comes up most in those flips is the one to choose throughout eternity.

  17. Orien Rigney says:

    Mathematicians calculate Dark Matter and Dark Energy to make up approx. 97% of the universe. Is this factual, or has physical matter as we know it, spread itself so thin that we only consider the vast distances between vector divergence of these pieces and parts? And will we continue to explain such divergence as, more dark matter and dark energy and a less % of matter?

  18. Will says:

    By saying the probability of an event what you’re formally stating, within the field of statistics, is the likelihood of an event occurring as the number of events (flips) tends towards infinity.
    So by saying the probability of flipping a head = the probability of flipping a tail (P(head) = P(tail) = 0.5), you are stating as you flip a coin close to an infinite number of times, you will see an equal number of heads and tails.

  19. Orien Rigney says:

    Tossing a coin is probably not the best way to look at randomness. The link below explains how the flip can be controlled to produce many variables. http://www.npr.org/templates/story/story.php?storyId=1697475
    Quantum randomness is more like a nine ball rack being broken 10 or a 1,000,000 times, hoping to duplicate the exact same break pattern twice.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>