I need help for b) please:
In a game we lose one unit of money with probability p, and gain 1 unit with probability q = 1 − p. We start with x units of money. The game stops if we have either 0 or N units (0 < x < N).
a) Compute the probability of losing.
b) How long does it take on average until the game terminates?
For a) I got:
$x_k$ = probability of reaching n when gamblers fortune is k. So probability of loosing is 1-$x_k$ which is: 1 - $\frac{1-(\frac{q}{p})^k}{1-(\frac{q}{p})^n}$
For b) I don't know how to calculate the average number of steps it takes until the game terminates (either by winning or losing)? What is the distribution of steps?
Can anybody help, please?
Thanks!
Let $P_i$ be the probability of winning given we start with $i$ units. Then by definition $P_0=0$ and $P_N=1$, and for $1\leqslant i\leqslant N-1$ we have the recursion $P_i=pP_{i+1}+(1-p)P_{i-1}$. Rewriting this as $pP_i + (1-p)P_i=pP_{i+1}+(1-p)P_{i-1}$, we find that $$ P_{i+1}-P_i = \frac{1-p}p(P_i-P_{i-1}). $$ From the above we find that $P_{i+1}-P_i=\left(\frac{1-p}p\right)^iP_1, 0<i<N$, and hence $$ P_{i+1}-P_1 = \sum_{j=1}^i (P_{j+1}-P_J) =\sum_{j=1}^i \left(\frac{1-p}p\right)^jP_1, $$ so that $$ P_{i+1} = P_1\sum_{j=0}^i \left(\frac{1-p}p\right)^j=\begin{cases} P_1\frac{1-\left(\frac{1-p}p\right)^{i+1}}{1-\frac{1-p}p},& p\ne\frac12\\ P_1(i+1),& p=\frac12. \end{cases} $$ Choosing $i=N-1$ and observing that $P_N=1$ we have $$ P_1 = \begin{cases} \frac{1-\left(\frac{1-p}p\right)^N}{1-\left(\frac{1-p}p\right)},&p\ne\frac12\\ \frac1N,&p=\frac12, \end{cases} $$ and hence $$ P_i = \begin{cases} \frac{1-\left(\frac{1-p}p\right)^i}{1-\left(\frac{1-p}p\right)^N},& p\ne\frac12\\ \frac iN,& p=\frac12. \end{cases} $$ Assuming that $p\ne\frac12$, the probability of losing when starting with $i$ units is thus $$ 1-\frac{1-\left(\frac{1-p}p\right)^i}{1-\left(\frac{1-p}p\right)^N}. $$ As for the expected time the game lasts, let $X_n$ be our wealth at time $n$ and $T=\min\{n\geqslant 0: X_n\{0,N\}$ the time the game ends. Define $\tau_i=\mathbb E[T\mathsf 1_{\{X_T=n\}} \mid X_0=i]$ and $\sigma_i=\mathbb E[T\mathsf 1_{\{X_T=0\}} \mid X_0=i]$, then we have the recursion $\tau_i=P_i+p\tau_{i+1}+(1-p)\tau_{i-1}$. As shown here, Expected time for winning in biased Gambler's Ruin we can derive the expected value of $\tau_i$, $\sigma_i$, and $\tau_i+\sigma_i$ by some computations with the two above recurrences.
Such computations can be avoided by the use of martingales. See this question: Gambler's ruin and martingale
Here $a=i$ and $b=N$ so the expected time the game lasts is
$$ \frac{\left(\frac{1-\left(\frac{1-p}p\right)^i}{1-\left(\frac{1-p}p\right)^N}\right)N-i}{2p-1}. $$