"A game is played by tossing an unfair coin ($P(head) = p$) until $A$ heads or $A$ tails (not necessarily consecutive) are observed. What is the expected number of tosses in one game?"

My approach is the following:

Let's represent represent a head by $H$ and a tail by $T$, and call $H_n$ the event "the game ends with $A$ heads when the coin is tossed for the n-th time" and $T_n$ the event "the game ends with $A$ tails when the coin is tossed for the n-th time".

First, I analyse $H_n$.

For $n<A$, $P(H_n) = 0$ because at least $A$ tosses are needed. For $n>2A-1$, $P(H_n) = 0$ because by then we will surely have at least $A$ heads or tails.

$$P(H_A) = p^A$$

$$P(H_{A+1}) = \left(\binom{A+1}{A} -1 \right) p^A(1-p)$$ $$P(H_{A+2}) = \left(\binom{A+2}{A} -\binom{A+1}{A} \right) p^A(1-p)^2$$

We can generalize it to: $$P(H_{A+i}) = \left(\binom{A+i}{A} -\binom{A+i-1}{A} \right) p^A(1-p)^{i}$$

The expression for $T_n$ is analogous: $$P(T_{A+i}) = \left(\binom{A+i}{A} -\binom{A+i-1}{A} \right) p^i(1-p)^{A}$$

And the expectation for the number of tosses in one game is: $$\sum_{i=0}^{A-1} P(H_{A+i}) (A+i) + \sum_{i=0}^{A-1} P(T_{A+i}) (A+i)$$

Is it correct? Is there a more elegant way of doing it?


For each of the cases $(A,p) \in \{3,5,10\} \times \{0.5,\}$, I simulated $10^7$ games. The maximum relative difference between the simulated average and the expectation given by the formula above was $0.013%$. I am assuming the formula is correct.


The approach seems correct. There are a couple of different ways to get to the terms in the sum, and rearrange the sum, but no significantly more elegant method that I see.


A closed form may not exist, but we can write it as summations, which can be easily evaluated by computer algera systems

1. \begin{align*} f(a,0) &= p^a \\ f(0,b) &= (1-p)^b \\ f(a,b) &= p\cdot f(a-1,b) + (1-p)\cdot f(a,b-1) \\ E(A,p) &= A\times \sum_{i=0}^{A-1} f(A,i) + f(i,A) \end{align*} 2. \begin{align*} E(A,p) &= \sum_{i=0}^{A-1} \left(A+i\right) \binom{A+i-1}{i} \left((1-p)^A p^i + p^A (1-p)^i\right) \\ \end{align*}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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