Probability Theory – Problem with Gambler’s Ruin

Question

Consider a gambler who has $k$ coins when he enters a casino. The gambler plays a game in which he wins $1$ coin if he wins a round and loses $1$ coin if he loses a round. He wins a round with probability $\displaystyle \frac{1}{2}$ and loses a round with probability $\displaystyle \frac{1}{2}$. The gambler is considered to win the game if he ends with $n$ coins ($n \gt k$) at some point of time and is considered to lose a game if he ends with $0$ coins.

What is the probability that the gambler wins the game on the $m^{th}$ round(where $m\gt n-k$ and $m=n-k+2r $ for some $r\in\Bbb{N}$ ) such that he does not end with $0$ coins or $n$ coins in any of the earlier $m-1$ rounds.

$\color{green}{\text{My try:}}$

Due to a lot of restrictions on the parameters and the event, I tried to work out the problems for some small values of $n,m,k$ to get an idea on how the probability might be. On obtaining some sequences of numbers I tried searching the sequence on OEIS to get an idea over the explicit form for the probability.

But even after trying a lot of values for $n,m,k$ I couldn't conjecture an explicit form for the probability.

If we denote the probability that the gambler wins in the $m^{th} $ round by $p_m$ then I could only conjecture that
$$p_m=\displaystyle f_{n,k,m} \left(\frac{1}{2}\right)^{m}$$

For some natural numbers $f_{n,k,m}$ which depend on the values of $n,k,m$. It is quite easily noticeable that $$f_{n,k,n-k}=1$$ but other than this I couldn't find a general pattern for the $f_{n,k,m}$'s.

Any help would be greatly appreciated. Also if it would be possible to create a generating function for $f_{n,k,m}$ then that generating function would also suffice to solve the problem ( I tried to form a generating function for the $f_{n,k,m}$'s but failed miserably).

* Edit *

Some values I tried are ("assuming I have counted them correctly"):

$$f_{6,2,4}=f_{6,3,3}=f_{5,2,3}=f_{6,4,2}=f_{5,1,4}=1$$
$$f_{6,2,6}=4$$
$$f_{6,2,8}=13$$
$$f_{6,3,5}=3$$
$$f_{6,3,7}=9$$
$$f_{6,3,9}=27$$
$$f_{5,2,5}=3$$
$$f_{5,2,7}=8$$
$$f_{5,2,9}=21$$
$$f_{5,2,11}=55$$
$$f_{6,4,4}=2$$
$$f_{6,4,6}=5$$
$$f_{6,4,8}=14$$
$$f_{5,1,6}=3$$
$$f_{5,1,8}=8$$
$$f_{5,1,10}=21$$
$$f_{5,1,12}=55$$

Answer 1

We provide an answer and link it with already given answers which might help to see connections.

Some observations:

• We can reduce the problem to a combinatorial one by counting all paths starting from $(0,k)$ to $(m-1,n-1)$ using steps $(1,1)$ and $(1,-1)$ which do not reach the lines $y=0$ and $y=n$.

• The starting point represents the $k$ coins of the gambler he has right at the beginning. Winning a round increases his coins by one which is represented by a step $(1,1)$ and loosing a round means also going in $x$-direction by one, but decreasing $y$ by one, so we make a step $(1,-1)$.

• Each valid path from $(0,k)$ to $(m-1,n-1)$ has length $m-1$ and is realised with probability $\frac{1}{2^{m-1}}$. In order to reach $(m,n)$ this can only be done in one step from $(m-1,n-1)$ to $(m,n)$ with probability $\frac{1}{2}$, so that the number of valid paths from $(0,k)$ to $(m-1,n-1)$ has finally to be divided by $2^m$ to find the wanted probability.

We start with an example confirming the approach of @GCab.

Example (part 1): k=2, m=14, n=6

We count the number of valid paths from $(0,2)$ to $(14,6)$, which is the number of lattice paths from $(0,2)$ to $(13,5)$ which do not touch the lines $y=0$ and $y=6$, followed by an $m$-th step from $(13,5)$ to $(14,6)$.

We see in accordance with the table presented by @GCab that we have $\color{red}{364}$ valid paths which is marked red in the graphic below.

We can normalise the situation by shifting $(0,k)$ to $(0,0)$ and consider the equivalent problem to count the number of lattice paths from $(0,0)$ to $(m-1,n-1-k)$ using steps $(1,1)$ and $(1,-1)$ without reaching the boundaries $y=n-k$ and $y=-k$. We denote this number of valid paths by \begin{align*} L_{m-1,n-1-k;n-k,k} \end{align*}

Formula:

The formula above in the form $L_{m,n;r,s}$ counting valid paths from $(0,0)$ to $(m,n)$ which do not reach the boundaries $y=r$ and $y=-s$ is established in this post. It can be written as

\begin{align*} L_{m,n;r,s}&=\binom{m}{\frac{m+n}{2}}-\sum_{j\geq1}\left[\binom{m}{\frac{m+n}{2}-r+j(r+s)} +\binom{m}{\frac{m+n}{2}+s-j(r+s)}\right]\\ &\qquad\qquad\qquad+\sum_{j\geq1}\left[\binom{m}{\frac{m+n}{2}+j(r+s)} +\binom{m}{\frac{m+n}{2}-j(r+s)}\right]\tag{1}\\ \end{align*}

In the current situation we obtain from (1) the number of valid paths for OP's problem:

\begin{align*} &\color{blue}{L_{m-1,n-1-k;n-k,k}}=\binom{m-1}{\frac{m+n-k}{2}-1}\\ &\quad\qquad-\sum_{j\geq1}\left[\binom{m-1}{\frac{m+n-k}{2}-1-n+k+jn}+\binom{m-1}{\frac{m+n-k}{2}-1+k-jn}\right]\\ &\quad\qquad+\sum_{j\geq1}\left[\binom{m-1}{\frac{m+n-k}{2}-1+jn}+\binom{m-1}{\frac{m+n-k}{2}-1-jn}\right]\tag{2}\\ &\quad=-\sum_{j\geq0}\binom{m-1}{\frac{m+n-k}{2}-1+k+jn}-\sum_{j\geq1}\binom{m-1}{\frac{m+n-k}{2}-1+k-jn}\\ &\quad\qquad+\sum_{j\geq0}\binom{m-1}{\frac{m+n-k}{2}-1+jn}+\sum_{j\geq1}\binom{m-1}{\frac{m+n-k}{2}-1-jn}\tag{3}\\ &\quad\,\,\color{blue}{=\sum_{j=-\infty}^{\infty}\left[\binom{m-1}{\frac{m+n-k}{2}-1+jn}-\binom{m-1}{\frac{m+n+k}{2}-1+jn}\right]}\tag{4} \end{align*}

Comment:

• In (3) we shift in the left-most series the index by one to start with $j=0$. In the third series we merge the single left-most term from (2).

• In (4) we combine the two-right most series as well as the two left-most series.

The resulting probability is \begin{align*} \color{blue}{\frac{1}{2^m}L_{m-1,n-1-k;n-k,k}} \end{align*}

The sums in (2) are a consequence of applying the principle of inclusion-exclusion to reflected paths. This is necessary in order to compensate double counting as indicated in the answer from @Hans.

.

Example (part 2): k=2, m=14, n=6

In order to check (2) we calculate the number of valid paths from the example above.

We obtain

\begin{align*} \color{blue}{L_{13,3;4,2}}&=\binom{13}{8}-\left[\binom{13}{10}+\binom{13}{4}\right]+\left[\binom{13}{2}\right]\tag{3}\\ &=1\,287-(286+715)+78\\ &\,\,\color{blue}{=364} \end{align*}

in accordance with the first part of the example. Note the number of reflected paths in the brackets in (3) are indicated in the graphic by $A_1, B_1$ and $B_2$.