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 .

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 , 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, C_N, which can be described as “the number of ways of arranging N pairs of parenthesis so that they make sense”.  Turns out that (this is a choose function).

The probability that the 2N^th 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.

C_N 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 2N^th coin flip brings the tally to zero (for the first time), then on the 2N-1^th 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 C_N-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: 2C_N-1.

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

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:

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 (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.