# expected winning time in fair gambler's ruin problem using martingale

In fair gambler's ruin problem, we already knew that the expected time of winning is $E(\tau_n|\tau_n<\tau_0)=\frac{n^2-k^2}{3}$, where $k$ is how much money we have in the beginning and $\tau_i$ is the first hitting time at $i$. I know how to solve it by using first step analysis in markov chain, but my teacher wants me to use martingale instead, he said it is much easier. I think I have to use optional stopping time theorem, but I don't know how to use it in this problem. Any idea? Thank you so much

• You want to use the fact that $E[X_\tau] = E[X_0]$, from the optimal stopping theorem, and start from there. – harvey Aug 16 '16 at 14:39
• @harvey thank you for replying my question, I know I have to start with $E(X_\tau)=E(X_0)$, but I dont know how to add the condition $\tau_n<\tau_0$, it is easy to use the theorem when we just want to calculate $E(\tau)$ (expected time to finish the game), but I dont have any idea for this problem – Rizky Reza Fujisaki Aug 16 '16 at 21:21

Let $\{S_t\}$ be a fair simple random walk started at $k\in\{0,1,...,n\}$ (this is a martingale), $\tau_a$ be first hitting time at $a$, and $\tau=\min\{\tau_0,\tau_n\}$. Define $E_k(.)=E(.|S_0=k)$, $P_k(.)=\Pr(.|S_0=k)$, and $M_t=S_t^3-3tS_t$, it is obvious that $\{M_t\}$ is a martingale,
By Optional Stopping Theorem, we know that \begin{eqnarray*} E_k(M_\tau)=E_k(M_0)=E_k(S_0^3-3.0.S_0)=k^3, \end{eqnarray*} but \begin{eqnarray*} E_k(M_\tau)&=&E_k(M_\tau|\tau_n<\tau_0)P_k(\tau_n<\tau_0)+E_k(M_\tau|\tau_n\geq\tau_0)P_k(\tau_n\geq\tau_0)\\ &=&E_k(M_{\tau_n}|\tau_n<\tau_0)\frac{k}{n}+E_k(M_{\tau_0}|\tau_n\geq\tau_0)P_k(\tau_n\geq\tau_0)\\ &=&E_k(S_{\tau_n}^3-3\tau_n S_{\tau_n}|\tau_n<\tau_0)\frac{k}{n}+E_k(S_{\tau_0}^3-3\tau_0 S_{\tau_0}|\tau_n\geq\tau_0)P_k(\tau_n\geq\tau_0)\\ &=&[n^3-3E_k(\tau_n|\tau_n<\tau_0)n]\frac{k}{n}+[0^3-3E_k(\tau_0|\tau_n\geq\tau_0)0]P_k(\tau_n\geq\tau_0)\\ &=&[n^2-3E_k(\tau_n|\tau_n<\tau_0)]k. \end{eqnarray*} Hence, we have $E_k(\tau_n|\tau_n<\tau_0)=\frac{n^2-k^2}{3}$.
• Thanks for sharing. To apply the Optional Stopping Theorem, you need a bounded stopping time $\tau$. How do you know that its bounded almost surely? – GNUSupporter 8964民主女神 地下教會 Jan 13 '19 at 23:45