7
$\begingroup$

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.

$\endgroup$
16
  • 2
    $\begingroup$ @Alexis In your Heads Heads example, I think you stop after the first so never reach the second. Similarly with Tails Heads Heads you would stop after the third $\endgroup$
    – Henry
    Mar 25 at 19:50
  • 1
    $\begingroup$ There will be an expression for $P(X=x)$ involving Catalan numbers $\endgroup$
    – Henry
    Mar 25 at 19:52
  • 1
    $\begingroup$ In particular $P(X=2k+1)=\frac3{5(k+1)}{2k \choose k}\left (\frac6{25}\right)^k$ and the expected number is indeed $5$ $\endgroup$
    – Henry
    Mar 25 at 19:58
  • 2
    $\begingroup$ In general, if the probability of Heads is $p$ then $P(X=2k+1)= \frac1{k+1}{2k \choose k}p^{k+1}(1-p)^k$ $\endgroup$
    – Henry
    Mar 25 at 20:03
  • 2
    $\begingroup$ @Henry could you add this as an answer with an explanation, or a reference to an explanation, of why the Catalan numbers show up? $\endgroup$
    – mhdadk
    Mar 27 at 15:27

2 Answers 2

4
$\begingroup$

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$.
$\endgroup$
0
$\begingroup$

I found another solution on Quora which ingeniously avoids the labour of finding out the PMF.

$\displaystyle \mathbb E[X] = p\cdot \mathbb E[H|X] + (1-p)\cdot \mathbb E[T|X] \tag{1}\label 1$

where,

  1. $\mathbb E[T|X]$ denotes the expected number of flips given that the first flip has been a tail.
  2. $\mathbb E[H|X]$ denotes the expected number of flips given that the first flip has been a heads.

In case the first flip is a heads, heads is already leading, so $\mathbb E[H|X]=1.$

Think about the case where the first flip is a tail. $$\begin{cases}F_1(T)&= 1 \\ F_1(H)&=0\end{cases}$$ where $F_i$ represents the $i^{\texttt{th}}$ cumulative frequency.

Further $\mathbb E[X]$ flips, it is expected that it'll add $n$ heads and $n+1$ tails.

$$\begin{cases}F_{\mathbb E[X]+1}(T) &=1+n \\ F_{\mathbb E[X]+1}(H) &=0+(n+1)\end{cases}$$

Now that, heads and tails are at par, it's expected that flipping further $\mathbb E[X]$ times more, heads will finally lead! (Say this time, it adds $m$ tails and $m+1$ heads)

$$\begin{cases}F_{2\mathbb E[X]+1}(T) &=1+n+m \\ \\ F_{2\mathbb E[X]+1}(H) &=0+(n+1)+(m+1)\end{cases}$$

Thus, we have: $$\mathbb E[T|X]=2\mathbb E[X]+1.$$

Substituting these results in $\eqref 1$, $$\mathbb E[X]=p+(1-p)(2\mathbb E[X]+1)\\ \implies \boxed{\mathbb E[X] = \frac{1}{2p-1}}$$

This makes sense only if $1\geqslant p>1/2$.

$\endgroup$
2
  • 2
    $\begingroup$ I have edited the formatting; please check it. Also note for display format, use $$ $$ in place of $ $. Best wishes. $\endgroup$ Mar 30 at 12:48
  • $\begingroup$ Thank you. This was my first answer on this site. I didn't know about \eqref. $\endgroup$ Mar 30 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.