Flipping an unfair coin until there are more heads

combinatoricsdistributionsprobability

I came across this question on Quora.

You have an unfair coin for which heads turns up with probability $p=\frac 35$. You flip the coin repeatedly until there have been more heads than tails. How many flips on average does this take?

Let $X$ be the random variable denoting number of flips needed to achieve more heads than tails.

I got interested in this question and tried to find the probability distribution of $X$.

It seems to me that $P(X=2n)=0$ i.e, it's not possible to achieve more heads than tails in even number of flips. For odd number of flips i.e, $X=2n+1$, there must be $n+1$ heads and $n$ tails, but I'm pretty confused how many suitable arrangements are possible.

The answers already given on Quora suggest that $\mathbb E[X]=5$ based on simulation programs.

Is there a closed form expression for probability distribution of $X$? Any help would be appreciated.

Edit: From the comments, I learned that the order of outcomes when $X=2n+1$ resembles Dyck words. You can read my Quora answer.

Best Answer

Consolidation of my comments:

  • You stop the first time you have one more Heads than Tails, so you are correct that the probability you stop after an even number of flips is $0$.
  • So let's consider the probability of stopping after $2k+1$ flips. After $2k$ flips you want the same number of Heads and Tails, without ever having had more Heads than Tails, and then finally have an extra Heads. The number of ways of doing this is the number of Dyck words, the Catalan number $\frac{1}{k+1} \binom{2k}k$.
  • If the probability of Heads is $p$ and Tails is $1-p$, since you need $k+1$ Heads and $k$ Tails, the probability of this is $$\mathbb P(X=2k+1)= \frac1{k+1}{2k \choose k}p^{k+1}(1-p)^k$$
  • If $p \ge \frac12$ then the probability of ever stopping is $\sum\limits_{k=0}^\infty\frac1{k+1}{2k \choose k}p^{k+1}(1-p)^k = 1$, so the expected number of flips need to finish is $$\mathbb E[X]=\sum\limits_{k=0}^\infty\frac{2k+1}{k+1}{2k \choose k}p^{k+1}(1-p)^k = \frac{1}{2p-1}$$
  • With $p=\frac35$ this gives $\mathbb E[X]=5$, as suggested by the simulations.
  • With $p=\frac12$ this gives $\mathbb E[X]=+\infty$, so you almost surely finish in finite time but with an infinite expected time.
  • With $p<\frac12$ then the probability of ever stopping is $\frac p{1-p} <1$ and the probability of never stopping is $\frac{1-2p}{1-p}>0$, so there is no expectation. Curiously, if you condition on stopping in finite time, the conditional expectation is $\mathbb E[X \mid X < \infty]=\frac{1}{|2p-1|}$, similar to the result when $p > \frac12$. For example with $p=\frac25$, the probability of ever stopping is $\frac23$ and the expectation of the number of flips conditioned on stopping is again $5$.
Related Question