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?
Best Answer
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} } $$