Problem with Gambler's ruin
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$$
Solution 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$.
Solution 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}$.
Solution 3:
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.
Solution 4:
Let me (isomorphically 😀) change the conventions a bit: My gambler starts off with $0$ dollars and looses once he gets $<-l$ dollars. He wins once he gets $r$ dollars. We are looking for all games of length $N$ where the gambler has at least $-l$ dollars and at most $r-1$ dollars at every step (except the last step, at which the gambler has exactly $r$ dollars.)
Note that a game of your gambler can be seen as a path from the origin $(0,0)$ to the point $(N, r)$ using only the steps $(1, \pm 1)$ while always staying between the horizontals $x=r-1$ and $x=-l$ (except for the last step).
Let $F(N, l,r)$ denote the number of al such paths as above. Then we have the following recurrence relation (here, $\land$ denotes the logical and and $\lor$ denotes the logical or):
$$F(N,l,r)=\begin{cases}1, &\text{ if } \min(N,l)\geq0 \land N=r \\ 0, &\text{ if } \min(N,l,r)<0\lor (N\geq 1 \land r\le 0)\lor r >N\\ F(N-1, l-1,r-1)+F(N-1,l+1,r+1), &\text{ otherwise} \end{cases}.$$
The probability of your gambler winning is then simply the number of paths above divided by all possible $N$-step paths, i.e. $$\text{Prob. of winning on the $N$th step}=\frac{1}{2^N} F(N,l,r),$$ where $l$ is the maximum amount of money he can loose (i.e. starting capital) and $r$ is the amount of money he wants to win.
The first case is true because there is (trivially) only one such way from $(0,0)$ to $(N,N)$. The second case is also trivial.
About the third case: If you have a non-degenerate case, then you can either make the step $(1,-1)$ or the step $(1,+1)$. In the first case, you are faced with the same problem but this time everything got shifted down by one (hence the first term). Analogous with the step in the other direction.
Albeit extensive research, I wasn't able to find a nice general expression for $F(N,l,r)$.
A special case: If you choose $l\geq \frac{N-d}2$, then it won't cause any problems (you can never make more than $\frac{N-d}2$ steps of the type $(1,-1)$ anyway.) In that case, the triangular sequence \begin{matrix} F(1,l,1) \\ F(2,l,1) & F(2,l,2) \\ F(3,l,1) & F(3,l,2) & F(3,l,3) \\ \dots & \dots & \dots & \ddots \end{matrix} is simply the Catalan triangle with $0$s.
A nice property of $F$ is that it is very easy to compute it. Here is an implementation in Python:
result = {}
def paths(N, l, r):
if N>=0 and N==r and l>=0:
result[N, l, r] = 1
return 1
if N<0 or N>=1 and r<=0 or r<0 or l<0 or r>N:
return 0
if (N, l, r) in result:
return result[N, l, r]
result[N, l, r] = paths(N-1, l-1, r-1) + paths(N-1, l+1, r+1)
return result[N, l, r]
print(paths(1000, 100, 300))
# prints 80605354977878720386697544162956768753193806712070170371530526246806813519038390664560509330012101808514169139063423697610995947184030159865069668043691199312683326030574149872000469359512164491415986216216002270576795289227598203625600
Solution 5:
Here is another answer based on solving the boundary value problem, equivalent to the discrete Fourier transform, of the difference equation or recursion equation.
This problem can be formulated as a random walk starting from position $k$ on a $1$-d lattice at time $t=0$ and ending on position $y$ at time $t=m$. We want to find the probability $p(t,x)$ of the paths starting from $x$ at time $0\le t\le m$ not ever hitting $n$ or $0$.
$$p(t,x)=\frac12p(t+1,x+1)+\frac12p(t+1,x-1).$$ Assume $p(t,x)=T(t)X(x)$. $$2\frac{T(t)}{T(t+1)}=\frac{X(x-1)+X(x+1)}{X(x)}$$ Since each side depends only on different variables with the left on $t$ and the right on $x$, it has to be a constant, say $2\lambda$, independent of both variables.
We can try $X(x)=a^x$ for some constant $a$ for the difference function $$X(x+1)-2\lambda X(x)+X(x-1)=0$$ leading to $$a^2-2\lambda a+1=0,$$ or $$\begin{cases}a=e^{\pm i\theta} \\ \lambda = \cos(\theta) \end{cases}$$ where $i$ is the pure imaginary number. Thus $$X(x)=c_+ e^{i\theta x}+c_-e^{-i\theta x}.$$ The boundary condition $X(0)=X(n)=0$ dictates that $$X(x)=\sin\Big(\frac {kx}n\pi\Big)$$
(to be continued)