I have a question that is a variant of Gambler's Ruin problem.

Setting: A wins a bet with probability $p\neq \frac{1}{2}$ and loses a bet with probability $q=1-p$. If A wins, A gets 1 dollar. Otherwise, A loses $1.

Suppose A starts with 0 dollar and whenever A has no money to bet (i.e., 0 dollar), A wins the bet with probability 1. The game goes on until the player A has $n$ dollars with him.

I am interested in finding the expected value of number of bets the player A need to play until the end of the game and the number of times the player A hit $0 during the game.

I managed to find the answer when $p=q=0.5$ to be $n^2$ by making the sample space to be $\{-n,...,-1,0,1,....n\}.$ However I don't think the same method can be used when $p\neq0.5$ and I am lost. Could anyone help please?


Let $e_k$ be the expected number of bets starting from $k$ dollars. Then \begin{align} e_{k}&=1+pe_{k+1}+qe_{k-1},\qquad k=1,2,\dots,n-1\\ e_n&=0,\\ e_0&=1+e_1. \end{align} The first equation can be written as $$ e_{k+1}-e_k=(q/p)(e_k-e_{k-1})-1/p $$ Applying this over and over, you get \begin{align} e_{k+1}-e_k &=(q/p)^k(e_1-e_0)-\sum_{i=0}^{k-1}(q^i/p^{i+1}) \\&=(q/p)^k(-1)-\frac{1-(q/p)^k}{p-q} \\e_{k+1}-e_k &=(q/p)^k\frac{2q}{p-q}-\frac1{p-q} \tag{*} \end{align} Now, take equation $(*)$ and sum both sides from $k=1$ to $n-1$. The left hand telescopes to $e_n-e_1=-e_1$, and the right hand side can be simplified. This lets you solve for $e_1$. You can then sum $(*)$ from $k=1$ to $m-1$ to get a formula for $e_m$, for all $m$. The result is $$ -e_1=\frac{2q}{p-q}\cdot\frac{(q/p)^n-q/p}{q/p-1}-\frac{n-1}{p-q} $$ $$ e_1=\frac{n-1}{p-q}+2\cdot \frac{(q/p)^{n+1}-(q/p)^2}{(q/p-1)^2} $$ $$ \bbox[5px, #ddddef, border: solid black 2px] {e_m=\frac{n-m}{p-q}+2\cdot \frac{(q/p)^{n+1}-(q/p)^{m+1}}{(q/p-1)^2}} $$ This is only valid for $m\ge 1$, but $e_0$ is simply $1+e_1$.

If $z_k$ is the expected number of returns to zero starting from $k$, then you instead have

\begin{align} z_{k}&=pz_{k+1}+qz_{k-1},\qquad k=1,2,\dots,n-1\\ z_n&=0,\\ z_0&=1+z_1. \end{align} We are counting the number of times you move from $0$ to $1$, which is the same as the number of visits to zero. This is even easier to solve. You instead have $$ z_{k+1}-z_k=(q/p)^k(z_1-z_0)=(q/p)^k(-1)\tag{**} $$ Therefore, using a telescopic sum with $(**)$, $$ -z_1=-\sum_{k=1}^{n-1}(q/p)^k\implies z_1=\frac{(q/p)^n-q/p}{q/p-1} $$ $$ z_m-z_1=-\sum_{k=1}^{m-1}(q/p)^k\implies \bbox[5px, #ddddef, border: solid black 2px] {z_m=\frac{(q/p)^n-(q/p)^m}{q/p-1}} $$

Again, this assumes $m\ge 0$.

Let $B_{n,m}$ be the probability that starting with $\$m$, you hit $\$0$ before you hit $\$n$. This is the classical gambler's ruin problem, whose solution is well known to be $$ B_{n,m} = \frac{(q/p)^n-(q/p)^m}{(q/p)^n-1} $$ Letting $N$ be the number of times you reach zero before reaching $n$, then $$ \bbox[5px, #ddddef, border: solid black 2px] { P(N=k)= \begin{cases} B_{n,m}\cdot B_{n,1}^{k-1}\cdot (1-B_{n,1}) & k>0 \\ 1-B_{n,m} & k = 0 \end{cases} } $$

  • $\begingroup$ Thank you. If I am interested in p.m.f of the number of times the player hits 0 dollar, how should I modify your answer? So suppose $N$ = the number of times the player hits 0 dollar, and P($N=k$)? $\endgroup$ – jackDanielle Apr 11 '19 at 23:54
  • $\begingroup$ @jackDanielle See edit. $\endgroup$ – Mike Earnest Apr 12 '19 at 0:40

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.