# A unfair coin is tossed until $A$ heads or $A$ tails are observed

"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?

EDIT:

For each of the cases $(A,p) \in \{3,5,10\} \times \{0.5,0.6.0.7\}$, 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.

## 2 Answers

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*}