[Math] expected winning time in fair gambler’s ruin problem using martingale

Question

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

Answer 1

Oh, at last, I got the solution for myself, I hope by sharing it, it will help other people in the future

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}$.