# Tossing a coin until you have more heads than tails

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?

-
I think you can use the distribution of the first time you hit 1 in a simple random walk (that is known). If you call that r.v. T, you want $P(T \leq 2 n + 1)$ –  Kolmo Aug 30 '13 at 19:12

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.

-
Thank you for the detailed answer, but when you split it into groups based on how many tosses it took to reach more heads than tails, aren't you assuming all sequences at some point will have more heads than tails? The sequence of T-T-T-T-T.... does exist and it wouldn't be counted. Are we allowed to assume every sequence will always have more heads than tails at some point? If we are allowed to assume this, what happens if we consider rolling a die instead of using a coin, counting rolls of 6 against not rolls of 6. I don't think you could make the assumption that eventually 6's>not6's. –  James Aug 30 '13 at 16:53
@James You do raise a valid point, however, at this point I'm only counting the number of sequences that at some point have more heads than tails, so there is no problem. –  Arthur Aug 31 '13 at 7:52

I will expand my comment.

Set $N=2 n+1$ and $S_k= \sum_{i=1}^k X_i$, where the $X_i$ are i.i.d.r.v. assuming values $+1, -1$ with equal probability ($S_0=0$ a.s.). This is the simple random walk. The idea is that we associate to head a +1 and to tail a -1.

What you are looking for is the probability of the event $A=\max_{1 \leq k \leq N} S_k \geq 1$; that is before $N$ the random walk passed 1 which means you had 1 more head than tails.

For $l$ positive integer define $T_l$ as the first time the random walk hits the level $l$ (the event $A$ corresponds to $T_1 \leq N$); the reflection principle implies $P(T_l \leq r) = 2 P(S_r \geq l) - P(S_r = l)$. I think you can find a proof of that on the internet, if you need it I will write it.

Coming back to you case you have: $$P(T_1 \leq N) = 2 P(S_N \geq 1 ) - P(S_N=1)=$$

$$=1- \binom {2n+1}{n+1} \ 2^{-(2n+1)} .$$

EDIT.

One version of the reflection principle says that $$P(T_l \leq r \cap S_r < l ) = P(T_l \leq r \cap S_r > l ).$$ Note that $(S_r>l) \subset (T_l \leq r)$, so the R.H.S is equal to $P(S_r >l)$. Note also that $(T_l = r \cap S_r < l) = (T_l = r \cap S_r > l) = \emptyset$.

Then:

$$P(T_l < r \cap S_r <l) = \sum_{k=1}^{r-1} P(T_l=k \cap S_r<l) = \sum_{k=1}^{r-1} P(T_l=k \cap S_r-S_k<0)$$

The last step is because $T_l=k$ implies $S_k=l$.

The event $(T_l=k) \in \sigma\{X_1,...,X_k\}$, while $S_r-S_k <0 \in \sigma \{X_{k+1},...,X_r\}$ and those sigma-algebras are independent.

So

$$P(T_l=k \cap S_r-S_k<0) = P(T_l=k)P(S_r-S_k<0)=P(T_l=k)P(S_r-S_k>0)$$ where last equality follow from the symmetry of $S_r-S_k$.

Proceeding backwards, the result follows.

This implies:

$$P(T_l \leq r) = P(T_l \leq r \cap S_r \geq l) + P(T_l \leq r \cap S_r < l)=$$

$$=P(S_r \geq l) + P(S_r > l )=2 P(S_r \geq l) - P(S_r = l ).$$

-
Do you know where I can find this version of the reflection principle for random walks? Thanks. –  user84413 Sep 1 '13 at 23:27
Try to google it, I don't have an immediate link now. If you need it i will write the proof but on the weekend. –  Kolmo Sep 2 '13 at 18:05
Okay, thanks -- I will see if I can find it. –  user84413 Sep 2 '13 at 18:27

There is no harm in imagining that we toss the coin $2n+1$ times and simply look to see whether at some point we got a success (meaning more heads than tails at that point).

Say that a finite string of H’s and T’s is balanced if it contains an equal number of H’s and T’s, and that it is completely unbalanced if it has no balanced initial segment. Let $U$ be the set of completely unbalanced strings of length $2n+2$; the lemma in this proof and the remarks preceding it show that $|U|=\binom{2n+2}{n+1}$.

Let $U_T$ be the set of completely unbalanced strings of length $2n+2$ that start with T; these are the ones that have an excess of T’s over H’s in every non-empty initial segment. There is clearly a bijection between $U_T$ and $U_H$, the set of $\sigma\in U$ that start with H, and $U_T\cap U_H=\varnothing$, so $|U_T|=\frac12\binom{2n+2}{n+1}$.

Let $\sigma\in U_T$. If you delete the initial T from $\sigma$, you get a string of length $2n+1$ whose non-empty initial segments all have at least as many T’s as H’s, i.e., strings that are not successes. Conversely, prepending a T to any unsuccessful string of length $2n+1$ produces a string in $U_T$. Thus, exactly $\frac12\binom{2n+2}{n+1}$ of the $2^{n+1}$ strings of length $2n+1$ are failures, and there must therefore be

$$2^{n+1}-\frac12\binom{2n+2}{n+1}$$

successes.

-

As in some previous answers, assume that you continue tossing the coin even if you get more heads than tails at some point, so you have a total of $2n+1$ tosses and $2^{2n+1}$ possible outcomes of the tosses.

To count the number of sequences of tosses in which we never get more heads than tails, we can use Andre's reflection principle:

The number of tails t must be larger than the number of heads h, so $n+1\le t\le 2n+1$, and the number of tosses in which tails never falls behind heads is given by

$\displaystyle\sum_{t=n+1}^{2n+1} \bigg[\binom{2n+1}{t}-\binom{2n+1}{t+1}\bigg]=$ $\big[\binom{2n+1}{n+1}-\binom{2n+1}{n+2}\big]+\big[\binom{2n+1}{n+2}-\binom{2n+1}{n+3}\big]+\big[\binom{2n+1}{n+3}-\binom{2n+1}{n+4}\big]+\cdots+\big[\binom{2n+1}{2n+1}-\binom{2n+1}{n+2}\big]$ $=\binom{2n+1}{n+1}$, so the probability of getting more heads than tails at some point in the tosses is equal to

$1-\binom{2n+1}{n+1}/2^{2n+1}$.

-