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


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.