Path: Eric's Site
/ Math
/ Pi From Coin Flips
/ Lemmas |
(Site Map) |

Because web browsers do not yet support mathematical notation, I write C((2i)! —————. 4^{i}i!^{2}

In this notation, the above probability is C(2m! ————————.n!(m-n)!

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 (2
*i*,*y*) for a positive*y*and intersect the*x*-axis at some point, and - the sequences that go from (1, -1) to (2
*i*,*y*) for a positive*y*.

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 (2*i*,
*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 2*i*
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(2*i*-1, *i*). Therefore,
2^{2i-2}-C(2*i*-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(2*i*-1,
*i*), which gives C(2*i*-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 2*i* coin
flips that never have the number heads equaling the number of tails is twice
that, 2C(2*i*-1, *i*), which equals C(2*i*, *i*).

In summary:

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

2 ^{2i-2}Number of sequences from (1, -1) to positive or zero. C(2 i-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(2 i-1,i)Number of sequences from (1, 1) to positive that do not intersect axis. C(2 i,i)Number of sequences from (1, 1) or (1, -1) that do not intersect axis. C(2 i,i)/4^{2i}Probability that sequence does not intersect axis.

Path: Eric's Site
/ Math
/ Pi From Coin Flips
/ Lemmas |
(Site Map) |

© Copyright 2000 by Eric Postpischil.