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

  • $\begingroup$ You want to use the fact that $E[X_\tau] = E[X_0]$, from the optimal stopping theorem, and start from there. $\endgroup$ – harvey Aug 16 '16 at 14:39
  • $\begingroup$ @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 $\endgroup$ – Rizky Reza Fujisaki Aug 16 '16 at 21:21

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

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 13 '19 at 23:45

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.