[Math] Tossing a coin until you have more heads than tails

probability

I toss a coin a many times, each time noting down the result of the toss. If at any time I have tossed more heads than tails I stop.
I.e. if I get heads on the first toss I stop.
Or if toss T-T-H-H-T-H-H I will stop.
If I decide to only toss the coin at most 2n+1 times, what is the probability that I will get more heads than tails before I have to give up?

Best Answer

Let $C_n$ be the $n$-th Catalan number, defined by $\frac{1}{n+1}\binom{2n}{n}$. Let's also say that you keep tossing even after you had more heads than tails, for good measure. Then there are $2^{2n + 1}$ different sequences of tosses you could've made. How many of them will at some point have more heads than tails?

We will divide this by cases in the following way: Any sequence that does at some point have more heads than tails are grouped together according to the number of tosses it took to get more heads for the first time. That means, for instance, that half of all the sequences (the ones starting with head) are in group $0$. The ones that took $3$ coin tosses are in group $1$ and so on. The ones that made it to the more-heads-than-tails-side only on the last coin flip are in group $n$.

How many sequences are in each group? Say we have the group labelled $i$. That means that for any sequence in this group, after $2i$ throws they have exactly as many heads as tails, and at no point before have they had more heads. There are $C_i\cdot 2^{2n-2i}$ tossing sequences like that. $C_i$ because that's how many ways you can reach the spot, and $2^{2n-2i}$ because that's how many ways it can go on after this, provided that the $(2i + 1)$th throw is a heads (which it is; that was the definition of group $i$).

So we're left with calculating the following sum: $$ \sum_{i = 0}^n 2^{2n-2i}C_i = \sum_{i = 0}^n \frac{2^{2n-2i}}{i+1}\binom{2i}{i} $$ and then divide it by $2^{2n + 1}$, and you have your probability.

PS. I don't know how to calculate the sum, but WolframAlpha says it's equal to $$ 2^{2 n+1}-\frac{1}{2} \binom{2(n+1)}{n+1} $$ which suggests there are $\frac{1}{2}\binom{2(n+1)}{n+1}$ sequences of coin tosses that are $2n + 1$ long and that never have more heads than tails in any initial segment.