# Gambler's Ruin variant: Play until the player earns target money

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

• 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$)? – jackDanielle Apr 11 at 23:54
• @jackDanielle See edit. – Mike Earnest Apr 12 at 0:40