# Given enough time, what are the chances I can come out ahead in a coin toss contest?

Assuming I can play forever, what are my chances of coming out ahead in a coin flipping series?

Let's say I want "heads"...then if I flip once, and get heads, then I win, because I've reached a point where I have more heads than tails (1-0). If it was tails, I can flip again. If I'm lucky, and I get two heads in a row after this, this is another way for me to win (2-1).

Obviously, if I can play forever, my chances are probably pretty decent. They are at least greater than 50%, since I can get that from the first flip. After that, though, it starts getting sticky.

I've drawn a tree graph to try to get to the point where I could start see the formula hopefully dropping out, but so far it's eluding me.

Your chances of coming out ahead after 1 flip are 50%. Fine. Assuming you don't win, you have to flip at least twice more. This step gives you 1 chance out of 4. The next level would be after 5 flips, where you have an addtional 2 chances out of 12, followed by 7 flips, giving you 4 out of 40.

I suspect I may be able to work through this given some time, but I'd like to see what other people think...is there an easy way to approach this? Is this a known problem?

-
 Here's a hint: "Forever" is a really, really long time. – Justin L. Jul 23 '10 at 21:51 The answers are (reasonably) assuming that the coin is fair, but note that the question becomes more interesting -- and more relevant to real-world gambling -- if you consider the more general case of a biased coin which comes up heads with probability $p < .5$. – Pete L. Clark Aug 7 '10 at 20:23

100%, for the same reason as the 1-D walk

In fact (again for the same reason), your chances are 100% of eventually reaching X-greater heads than tails (or tails than heads), where X is any non-negative integer.

-

The question can be answered using Catalan numbers. Let C_n denote the number of sequences of 2n coin tosses in which you are never ahead. Formally, we count sequences in which every prefix has no less T's than H's. We call this property A.

The number of total sequences of length 2n is $2^{2n}$. We then show that as n→∞, the ratio $C_n / 2^{2n}$ tends to 0. This means that in almost every sequence you will eventually be ahead (the chances of a random sequence having property A tend to 0 as the sequence gets longer).

Indeed,

$C_n = \frac{(2n)!}{(n+1)!n!}$

so

$C_n / 2^{2n} = \frac{(2n)!}{2^{2n}} \cdot \frac{1}{(n+1)!n!}$

and it can be shown that this tends to 0 by Stirling's approximation (multiply and divide by $(2n/e)^{2n}$).

-