# Coin Flipping Game - Expected Number of Tails

Can someone help me with this problem?

In this game, let $S_{t}$ denote your earnings at time $t$. Your initial earnings is one dollar ($S_{0} = 1$). For each subsequent time, $t = 1, 2, ..$, flip a coin (probability of heads = $p$ and probability of tails = $1-p$). If the result is heads, you gain one dollar ($S_{t} = S_{t-1} + 1$). If the result is tails, you lose everything except your initial earnings ($S_{t} = 1$). For instance, suppose the following sequence of coin flips occurs: $\{HTHHHHTT\}$. Then your fortune at times $t = 0, 1, 2,.., 8$ will be: $\{1, 2, 1, 2, 3, 4, 5, 1, 1\}$.

Let $T_{N}$ be the first time at which your fortune is $N$ dollars, i.e.,

$T_{N} = min\{t \geq 1 | S_{t} = N\}$

Find the expected number of tails before time $T_{N}$.

To get started, I considered $T_{1}$. $T_{1}$ can take values $1, 2, 3, 4,..$ and so on. But in order for $T_{1} = k$, the sequence of coin flips must be all heads except for a tail at the $k^{th}$ flip. This can be seen if looking at a tree diagram. Thus, $P(T_{1} = k) = p^{k-1}(1-p)$, or $T_{1} \sim$Geom$(1-p)$ distribution. I was hoping that this would generalize for all $T_{N}$, but unfortunately, it does not. Is there a better way to approach this problem?

The $T_1$ case is different to $T_N,\; N\geq 2$, which can be solved as follows.

Let $A_{N,k} = \text{"#Tails before reaching time$T_N$if we start with fortune$N-k$"}$. So we want $E(A_{N,N-1})$. Conditioning on the result of the next flip,

\begin{eqnarray*} E(A_{N,k}) &=& E(A_{N,k}\mid H)P(H) + E(A_{N,k}\mid T)P(T) \\ &=& p E(A_{N,k-1}) + (1-p)(1+E(A_{N,N-1})). \end{eqnarray*}

This is a non-homogeneous, first-order recurrence relation in $k$, so the general solution is, for some constants $\alpha,\beta$,

$$E(A_N,k) = \alpha p^k + \beta\qquad\qquad\qquad\qquad(1)$$

We have boundary conditions:

\begin{eqnarray*} E(A_{N,0}) &=& 0 \\ E(A_{N,1}) &=& pE(A_N,0) + (1-p)(1+E(A_{N,N-1})) \;=\; (1-p)(1+E(A_{N,N-1})). \end{eqnarray*}

So in (1) with $k=0 :\quad 0 = \alpha + \beta \implies \beta = -\alpha$.

With $k=1 :\quad (1-p)(1+E(A_{N,N-1})) = p\alpha -\alpha \implies \alpha = - 1 - E(A_{N,N-1})$.

Therefore, (1) gives: $$E(A_{N,k}) = (1+E(A_{N,N-1})) (1-p^k).$$

Setting $k=N-1$ : \begin{eqnarray*} E(A_{N,N-1}) &=& (1+E(A_{N,N-1})) (1-p^{N-1}) \\ && \\ \therefore\quad E(A_{N,N-1}) &=& \dfrac{1 - p^{N-1}}{p^{N-1}}. \end{eqnarray*}