Eric’s Coin Flip Lemmas

Path: Eric's Site / Math / Pi From Coin Flips / Lemmas

Lemma 0 for coin-flip page:

We want to prove the probability there are at least i+1 pairs of flips before heads equals tails is:

(2i)!
—————.
4ⁱi!²

Because web browsers do not yet support mathematical notation, I write C(m, n) for the number of ways to select n things from m things, which is:

   m!
————————.
n!(m-n)!

In this notation, the above probability is C(2i, i)/4ⁱ. From the statement of the problem, there are at least i+1 pairs of flips if the number of heads has not equaled the number of tails at any point during the first i flips. We will prove the number of ways that can happen is C(2i, i). Obviously, there are 4ⁱ ways for i pairs of coin flips to turn out, so that will make the probability C(2i, i)/4ⁱ, as we desire to prove.

Let us visualize the coin flips as movement in a plane with coordinates. The point (x, y) represents the situation where there have been x flips and there are y more heads than tails flipped so far. (y may be negative.) So we start at (0, 0). If a head is flipped first, we move to (1, 1), and a tail would have taken us to (1, -1).

Consider two sets of sequences:

the sequences that go from (1, 1) to (2i, y) for a positive y and intersect the x-axis at some point, and
the sequences that go from (1, -1) to (2i, y) for a positive y.

From the visualization, we can learn there are the same number of sequences in each set. We see this by matching up each sequence in the first set 1-to-1 with a sequence in the second set. Just take the part of a path from its start to the first point where it touches the axis and reflect that part over the axis. This reflection is the same as changing each head to a tail and each tail to a head. Reflecting like this will change each path in the first set to a path in the second set and vice-versa.

Remember, these are the paths that intersect the axis, the ones that have heads equaling tails at some point, so they are paths we do not want to count in the end. We will subtract them from the total paths later to get the paths we do want to count. First, we have to figure out how many of these paths there are. There are 2^2i-1 sequences going from (1, -1) to (2i, y) for any y. Half of them end where y is negative, and half end where y is positive or zero. This is true by symmetry: Starting from -1, half will end up above -1 and half will end up below -1. (None end up exactly at -1 because you cannot end up with an odd difference after 2i flips.)

So 2^2i-2 sequences end up positive or zero. Ending at zero after the first tail requires getting i heads and i-1 more tails, and the number of ways to do this is C(2i-1, i). Therefore, 2^2i-2-C(2i-1, i) sequences from (1, -1) end up positive. So that is also the number of sequences that do intersect the axis while going from (1, 1) to a positive result.

Next we have to figure out how many sequences from (1, 1) end up at a positive result whether they touch the axis or not, and then we will subtract the sequences that do touch the axis. Well, just as 2^2i-2 sequences from (1, -1) end up negative, the same number from (1, 1) end up positive. So from that we will subtract 2^2i-2-C(2i-1, i), which gives C(2i-1, i).

That is how many sequences from (1, 1) end up positive without touching the axis. There are the same number of sequences from (1, -1) that end up negative without touching the axis, so the total number of sequences of 2i coin flips that never have the number heads equaling the number of tails is twice that, 2C(2i-1, i), which equals C(2i, i).

In summary:

2^2i-2 Number of sequences from (1, -1) to positive or zero.

C(2i-1, i) Number of sequences from (1, -1) to zero.

2^2i-2-C(2i-1, i) Number of sequences from (1, -1) to positive.

2^2i-2-C(2i-1, i) Number of sequences from (1, 1) to positive that do intersect axis.

2^2i-2 Number of sequences from (1, 1) to positive.

C(2i-1, i) Number of sequences from (1, 1) to positive that do not intersect axis.

C(2i, i) Number of sequences from (1, 1) or (1, -1) that do not intersect axis.

C(2i, i)/4²ⁱ Probability that sequence does not intersect axis.

Return to the coin-flip page where this lemma is used.

Path: Eric's Site / Math / Pi From Coin Flips / Lemmas

(Site Map)

2^2i-2	Number of sequences from (1, -1) to positive or zero.
C(2i-1, i)	Number of sequences from (1, -1) to zero.
2^2i-2-C(2i-1, i)	Number of sequences from (1, -1) to positive.
2^2i-2-C(2i-1, i)	Number of sequences from (1, 1) to positive that do intersect axis.
2^2i-2	Number of sequences from (1, 1) to positive.
C(2i-1, i)	Number of sequences from (1, 1) to positive that do not intersect axis.
C(2i, i)	Number of sequences from (1, 1) or (1, -1) that do not intersect axis.
C(2i, i)/4²ⁱ	Probability that sequence does not intersect axis.