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?
 A: 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*}
