Problem with Gambler's ruin

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

This is solved by repeated application of the reflection principle.

We only need to enumerate the number of profit-loss paths satisfying the condition which then divided by $2^m$ to obtain the probability. The number of paths starting from $0$ coins and ending in $y$ coins on the $x$'th round is $$y\choose l \tag1$$ where $l=\frac{x-y}2$ is the number of losses on this path.

We first solve the partial problem of starting from $k$ coins and ending with $n$ coins on round $m$ for the first time (so dropping below $0$ coin is allowed). Each admissible path gives one unique path of $m-1$ rounds that reaches $n-1$ coins on round $m-1$ without ever possessing $n$ coins before. Each such path of $m-1$ rounds generates one unique required $m$ rounds path by winning one more round. Due to this ono-one correspondence, we just need to compute the number of such $m-1$ rounds paths $N_1(m,k,n)$. By the reflection principle applied to the reflecting line of $n$ coins, and Equation $(1)$ $$f_1(n,k,m)={m-1\choose \frac{m-n+k}2}-{m-1\choose \frac{m-n-2+k}2}.$$

Now we add in the condition that the path should never touch the $0$ coin line. By the reflection principle applied to coin line $0$, the paths that satisfy the condition in the previous paragraph but does not touch the $0$ coin line one-to-one corresponds to

$$f_2(n,k,m)={m-1\choose \frac{m-n+k}2}-{m-1\choose \frac{m-n-2+k}2}-{m-1\choose \frac{m+n-2+k}2}+{m-1\choose \frac{m+n+k}2}.$$

We need to reflect the path ad infinitum around the lines $\{ni\}_{i=0}^\infty$ until the length of the path for such reflection is exhausted. By mathematical induction, we can obtain the final enumeration saught $$f(n,k,m)=\sum_{i=-\infty}^\infty \Bigg({m-1\choose \frac{m-(2i+1)n+k}2}-{m-1\choose \frac{m-(2i+1)n-2+k}2}\Bigg)$$ where ${a\choose b}:=0,\,\forall b\not\in[0,a]$, or integer $i\in\big[-\frac12\big(\frac{m-k}n+1\big),\,\frac12\big(\frac{m+k}n-1\big)\big]$. The probability sought is simply $\frac{f(n,k,m)}{2^m}$.

The standard approach would be through Markov matrix.
The transition matrix , denoting the probability of changes in the capital at each run, is simple. For $n=4$ for example, it is $$ {\bf T}(4) = \left( {\matrix{ 1 & 0 & 0 & 0 & 0 \cr {1/2} & 0 & {1/2} & 0 & 0 \cr 0 & {1/2} & 0 & {1/2} & 0 \cr 0 & 0 & {1/2} & 0 & {1/2} \cr 0 & 0 & 0 & 0 & 1 \cr } } \right) $$ and computationally it works pretty well. Taking the various powers of the matrix (${\bf T}^m$) the $k$-th row will give the probability to get the capital corresponding to the column index.
Since at $0$ and $n$ we have an absorbing barrier, those columns will give the cumulative probability of losing or winning.
In this way we get for example, for $n=5,6$, the following tables for $f(n,k,m)$

which correspond with yours. However the results are difficult to render in analitical terms, because the Jordan canonical form is complicated and possible splittings into simpler components leads to non commutative terms.

So we take a different approach.

If we reach to round $q$ with a capital $1 \le c \le n-1$, then the number of ways to proceed from here and win at round $m$ ($w_n(q,m,c)$) is clearly equal to the number of ways of reaching that goal starting from the previous round ($q-1$) with a capital $c-1$ plus those with a capital $c+1$, since the probability of winning and losing is the same. That is $$ w_{\,n} (q,m,c) = \left[ {1 \le c \le n - 1} \right]\left( {w_{\,n} (q - 1,m,c - 1) + w_{\,n} (q - 1,m,c + 1)} \right) $$ where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$ and the condition $\left[ {1 \le k \le n - 1} \right]$ is to assure that we remain in game.

Going backwards from the point $(m,n)$ and complementing the capital, it is easy to transform the above into a recursion for $f$, starting from the point$(n,0)$ $$ \bbox[lightyellow] { \eqalign{ & f_n (k,m) = \cr & = \left[ {1 \le k \le n - 1} \right]\left( {f_n (k - 1,m - 1) + f_n (k + 1,m - 1)} \right) + \left[ {0 = m} \right]\left[ {n = k} \right] = \cr & = \left[ {0 \le k - 1 \le n - 2} \right]f_n (k - 1,m - 1) + \left[ {2 \le k + 1 \le n} \right]f_n (k + 1,m - 1) + \left[ {0 = m} \right]\left[ {n = k} \right] \cr} }$$ this checks with the tables above ad provides a more efficient tool for computation.