A SYMBOLIC COMPUTATIONAL APPROACH TO THE GENERALIZED GAMBLER’S RUIN PROBLEM IN ONE AND TWO DIMENSIONS

LUCY MARTINEZ

Abstract. The power of symbolic computation, as opposed to mere numerical computation, is illustrated with efficient algorithms for studying the generalized gambler’s ruin problem in one and two dimensions. We also consider a new generalization of the classical gambler’s ruin where we add a third step which we call the mirror step. In this scenario, we provide closed formulas for the probability and expected duration.

1. Introduction

Throughout we let x be some positive integer such that 0 < x < N where N ∈ ℕ = {1, 2, 3, …}. Consider a gambler who starts with x dollars. At each gamble, the gambler either wins a dollar with probability \frac{1}{2} or loses a dollar with probability \frac{1}{2}. The gambler’s goal is to reach N dollars without first running out of money (i.e., hitting 0 dollars). If the gambler reaches N dollars, we say they are a winner. The gambler continues to play until they either run out of money or win. This scenario is known as the gambler’s ruin problem, first posed by Pascal in 1656 in a letter to Fermat, as noted by Edwards [?Edwards1983]. In 1657, Huygens restated the problem and published a solution for the probability of winning [?Huygens]. For additional historical context, we refer the reader to a paper of Seongjoo Song and Jongwoo Song [?Song].

In this paper, we begin by providing an overview of the classical gambler’s ruin problem, recalling results for both the probability of winning and the expected duration of the game. We also summarize analogous results on the generalized 1-dimensional and 2-dimensional versions of the gambler’s ruin problem. Building on the 1-dimensional version, we introduce a new generalization of the classical gambler’s ruin that includes an additional step called the mirror step. For the generalized model, we derive formulas for the probability of winning and expected duration of the game. The objective of this paper is to propose an approach to reduce the running time required to determine the probability of winning, the expected duration and the variance specifically for the generalized 1-dimensional and 2-dimensional versions.

1.1. Classical gambler’s ruin problem. Let f(x) be the probability that the gambler exits the game as a winner starting with x dollars. Then, for 0 < x < N,

f(x) = \frac{1}{2}f(x − 1) + \frac{1}{2}f(x + 1), f(0) = 0, f(N) = 1.  (1)

That is, if the gambler starts with x dollars, then in the next round, the gambler has x − 1 dollars or x + 1 dollars, each with probability \frac{1}{2}. Using this recurrence relation and the boundary conditions, we can find the solution to be f(x) = \frac{x}{N}.

If the gambler starts with x dollars, let g(x) be the expected number of steps (expected duration of the game) the gambler takes to exit the game (either with N dollars or 0 dollars). Similar to the probability, for 1 < x < N,

g(x) = \frac{1}{2}g(x − 1) + \frac{1}{2}g(x + 1) + 1, g(0) = 0, g(N) = 0.

At each round, if the gambler has x dollars, then in the next round, the gambler will have either x − 1 dollars or x+1 dollars, each with probability \frac{1}{2}. However, we add 1 to the count since the gambler has taken one extra step. Using the recurrence relation and the boundary conditions, we can find the solution to be g(x) = x(N − x).

Building upon the expected duration, we can obtain the probability generating function of the duration of the game. For a formal variable t and 0 < x < N,

F (x, t) = t (\frac{1}{2}F (x − 1, t) + \frac{1}{2}F (x + 1, t)) , F (0, t) = 1, F (N, t) = 1.

Taking the derivative of F (x, t) with respect to t, and evaluating at t = 1 recovers the expected duration of the game at x.

Consider extending the game so that the probability of losing one dollar or winning one dollar are not the same. In other words, let p be the probability of winning one dollar, and q = 1 − p be the probability of losing one dollar. Let f(x) be the probability of exiting the game as a winner starting with x dollars. Similarly to Equation (1), we get

f(x) = qf(x − 1) + pf(x + 1), f(0) = 0, f(N) = 1, and p + q = 1.

Edwards gives a conjecture on how Pascal solved the above using a method of recursive formula [?Edwards1983]. We provide Edwards’ solution to f(x). Rewrite f(x + 1) − f(x) and observe the following

f(x + 1) − f(x) = \frac{q}{p} (f(x) − f(x − 1)) = \frac{q^{2}}{p^{2}} (f(x − 1) − f(x − 2)) = ⋯ = \frac{q^{i}}{p^{i}} (f(1) − f(0)) .

Hence,

f(x) = (∑_{j=0}^{x−1} (\frac{q}{p})^{j}) f(1).

Since p = 1 − q then p ≠ q, it follows that \frac{q}{p} ≠ 1. Therefore, by the geometric series, we obtain

1 = f(N) = \frac{1 − (\frac{q}{p})^{N}}{1 − \frac{q}{p}} · f(1).

Thus, we can recover the following

f(1) = \frac{1 − \frac{q}{p}}{1 − (\frac{q}{p})^{N}} and f(x) = \frac{1 − (\frac{q}{p})^{x}}{1 − (\frac{q}{p})^{N}} .

1.2. Generalized 1-dimensional gambler’s ruin. The gambler’s ruin problem can be formulated as follows: A particle starts at a point x on a line of length N where 0 < x < N. The particle moves to the left from x to x − 1 with probability \frac{1}{2}, or to the right from x to x + 1 with probability \frac{1}{2}.

Consider extending the 1-dimensional gambler’s ruin game to include more than two steps on a line of length N. Let r be a positive integer. Let a_{1}, a_{2}, …, a_{r} be distinct integers such that a_{1} < a_{2} < ⋯ < a_{r} where a_{1} < 0 and a_{r} > 0. Let p_{1}, p_{2}, …, p_{r} be probabilities such that p_{1} + p_{2} + … + p_{r} = 1, and let P be the probability table P = [[a_{1}, p_{1}], [a_{2}, p_{2}], …, [a_{r}, p_{r}]] where each pair [a_{i}, p_{i}] represents the outcome a_{i} occurring with probability p_{i}. The generalized 1-dimensional gambler’s ruin problem states that if a particle is currently at some x then the particle moves from x to x + a_{1} with probability p_{1}, or moves from x to x + a_{2} with probability p_{2}, or moves from x to x + a_{3} with probability p_{3}, and so on.

Similar to the method of solving a system of linear equations as in Section 1.1, we can obtain the probability of winning and expected duration for the generalized case for any starting position. However, as N grows, the computation time for solving a system of N linear equations will be slower. In Section 2, we present a faster method to reduce the running time by going from a system of N − 1 linear equations with N − 1 unknowns to a system of a_{r} linear equations with a_{r} unknowns where a_{r} is the maximum of the steps in the probability table P = [[a_{1}, p_{1}], [a_{2}, p_{2}], …, [a_{r}, p_{r}]]. Our method significantly drops the running time and we make comparisons between the direct approach and our strategy in Section 2.3.

1.3. 2-dimensional gambler’s ruin. Let M and N be positive integers. Consider a particle starting at a point (x, y) in the interior of a rectangular grid of size M ×N, where 0 < x < M and 0 < y < N. At each step, the particle moves in one of four directions, each with probability \frac{1}{4}: (x − 1, y), (x, y + 1), (x + 1, y), (x, y − 1). The particle stops moving once it hits one of the four boundaries, defined by x = 0, x = M, y = 0, or y = N. By setting up a recurrence relation for the expected duration, we can obtain a system of (M − 1) × (N − 1) linear equations with (M − 1) × (N − 1) unknowns. Andrej Kmet and Marko Petkovšek gave an explicit formula involving a double sum, enabling direct computation of the expected duration for the 2-dimensional gambler’s ruin game without the need to solve systems of equations or use recursion [?Kmet]. While Kmet and Petkovšek’s formula expresses the expected duration as a double sum, our method reduces the running time by going from a system of (M − 1) × (N − 1) linear equations with (M − 1) × (N − 1) unknowns to a system of N − 1 linear equations and N − 1 unknowns. Our method is significantly faster than the direct approach and Kmet and Petkovšek’ formula. We make comparisons in Section 3.3.

One way to generalize the 2-dimensional game is to change the probabilities of each of the four directions with probabilities p_{L}, p_{U}, p_{R}, and p_{B}, corresponding to left, up, right and down movements, respectively where p_{L} + p_{U} + p_{R} + p_{B} = 1. Although one can generalize the number of steps for either of the four directions, we focus on the case when the set of steps the particle can move is {[0, 1], [0, −1], [1, 0], [−1, 0]}, and remark that one can adapt our strategy for an arbitrary (finite) set of allowed steps, and arbitrary probability distribution.

1.4. A mirror step variant of gambler’s ruin. We consider a new generalization of the gambler’s ruin problem. A particle starts at some point x on a line of length N where 0 < x < N. At each step, the particle either moves from x to x − 1 with probability q_{1}, or moves from x to x + 1 with probability q_{2}, or moves from x to N − x with probability p where 0 < p < 1 and q_{1} + q_{2} + p = 1. We call this last step the mirror step. The particle continues to walk on the line until it reaches 0 or N. In this paper, we focus on the case when q_{1} = q_{2} = \frac{1−p}{2} and we call this the symmetric case.

We begin with an example where the particle starts at x = 1 and generate data for different p values with fixed N.

Example 1. Let N = 100 and x = 1. We generate data for the probability that if the particle is currently at x = 1, the particle eventually ends at 100. Let p ∈ \{\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, …, \frac{1}{10}\}.

We use the procedure Lk(p,x,N), as described in Appendix A.1.4 in Maple which generates the following data in about 4.765 seconds:

T :=[0.4142135624, 0.3660254038, 0.3333333333, 0.3090169944, 0.2898979486, 0.2742918852, 0.2612038750,
0.2500000000, 0.2402530734].

The sequence T reads as follows. If the particle is currently at x = 1 and p = \frac{1}{2}, the particle moves from x to x − 1 with probability \frac{1−p}{2} = \frac{1}{4}, or moves from x to x + 1 with probability \frac{1−p}{2} = \frac{1}{4}, or moves from x to 100 − x with probability p = \frac{1}{2}. Then, the probability of the particle starting at x = 1 and ending at 100 is T_{1} = 0.4142135624. Similarly, if the particle is currently at x = 1 and p = \frac{1}{3}, the particle moves from x to x − 1 with probability \frac{1−p}{2} = \frac{1}{3}, or moves from x to x + 1 with probability \frac{1−p}{2} = \frac{1}{3}, or moves from x to 100 − x with probability p = \frac{1}{3}. Then, the probability of the particle starting at x = 1 and ending at 100 is T_{2} = 0.3660254038. Thus, T_{i} is the probability of the particle starting at x = 1 and ending at 100 for p = \frac{1}{i+1} where 1 ≤ i ≤ 9.

We then use the function identify in Maple on the sequence T. The function identify is based, in part, on the continued fraction expansion of any given numerical value. Using this function on the values of T, we conjecture that each of the probabilities in T converges to

M := [\sqrt{2} − 1, \frac{\sqrt{3} − 1}{2}, \frac{1}{3}, \frac{\sqrt{5} − 1}{4}, \frac{\sqrt{6} − 1}{5}, \frac{\sqrt{7} − 1}{6}, \frac{2\sqrt{2} − 1}{7}, \frac{1}{4}, \frac{\sqrt{10} − 1}{9}] .

That is, the probability of the particle starting at x = 1 and ending at 100 converges to M_{i} for p = \frac{1}{i+1} where 1 ≤ i ≤ 9.

The previous example illustrates that when the particle starts at x = 1, the probability of ending at N converges fast. Denote this probability by f_{N}^{(p)}(x). We state the following guess for x = 1 and in Corollary 4.4.1 we provide a proof.

Guess 1.1. If the particle starts at x = 1, then

lim_{N→∞} f_{N}^{(p)}(1) = \frac{\sqrt{p} − p}{1 − p}.

In Section 4, we provide other expressions for lim_{N→∞} f_{N}^{(p)}(x) when x = 2 and x = N − 2 with fixed N, and in Corollary 4.4.1 we provide the general formula for the limit.

This paper is structured as follows: In Section 2, we present a symbolic computation approach to compute the probability of winning, the expected duration of the game and the variance that reduces the running time for the generalized 1-dimensional gambler’s ruin. In Section 3, we provide the analogous approach for the generalized 2-dimensional case and compare the running times to a formula provided by Andrej Kmet and Marko Petkovšek. In Section 4, we consider a mirror step variant of gambler’s ruin and provide closed formulas for both the probability of winning and the expected duration of the game. We conclude with future directions in Section 5.

2. Generalized 1-dimensional Gambler’s Ruin

In this section, we introduce the recurrence relation for the probability of winning in the generalized 1-dimensional gambler’s ruin game, and introduce symbolic variables to the recurrence equation of the probability and expected duration. Recall that P = [[a_{1}, p_{1}], [a_{2}, p_{2}], …, [a_{r}, p_{r}]] denotes a probability table, where each pair [a_{i}, p_{i}] represents the outcome a_{i} occurring with probability p_{i}. To set up notation, we start with an example.

Example 2. Let N = 5 and P be the probability table given by P = [[−2, \frac{1}{2}], [1, \frac{1}{4}], [2, \frac{1}{4}]]. If the particle starts at some x where 0 < x < 5 on the line of length 5, then it can move along the line as follows: from x to x − 2 with probability \frac{1}{2}, or from x to x + 1 with probability \frac{1}{4}, or from x to x + 2 with probability \frac{1}{4}.

2.1. Probability. We now establish the recurrence relation for the probability that the particle reaches some position ≥ N starting from an initial position x. We then rewrite this recurrence and introduce new variables for the probabilities at each x.

Define f(x) as the probability that a particle starting at x will eventually reach a position ≥ N. For 0 < x < N, this probability satisfies the recurrence relation

f(x) = ∑_{i=1}^{r} p_{i}f(x + a_{i}),  (2)

where a_{i} ∈ ℤ, a_{1} < a_{2} < ⋯ < a_{r}, a_{1} < 0 and a_{r} > 0. Unlike the classical gambler’s ruin problem, the generalized 1-dimensional scenario has more than two boundary conditions. Certainly f(0) = 0 and f(N) = 1. Since a_{1} < a_{2} < ⋯ < a_{r}, the values a_{1} and a_{r} represent the minimum and maximum of all the integers a_{i}, respectively. For any integer k such that a_{1} + 1 ≤ k ≤ 0, it follows that f(k) = 0. Indeed, if the particle is at x = 1, it may move to x + a_{1} = a_{1} + 1 with probability p_{1}. Given that a_{1} < 0, this movement brings the particle to some position k ≤ 0, implying that f(k) = 0 for k = a_{1} + 1, a_{1} + 2, …, −1, 0. Similarly, for any integer ℓ such that N ≤ ℓ ≤ N + a_{r} − 1, we have f(ℓ) = 1. If the particle is at x = N − 1, it may move to x + a_{r} = N + a_{r} − 1 with probability p_{r}. Since a_{r} > 0, this movement brings the particle to some position ℓ ≥ N, so f(ℓ) = 0 for ℓ = N, N + 1, N + a_{r} − 2, N + a_{r} − 1. Thus, there are a_{r} − a_{1} boundary conditions.

Example 3. (Continuing Example 2) Recall the probability table P = [[−2, \frac{1}{2}], [1, \frac{1}{4}], [2, \frac{1}{4}]] and N = 5. If f(x) denotes the probability that the particle reaches some position ≥ 5, then

f(x) = \frac{1}{2}f(x − 2) + \frac{1}{4}f(x + 1) + \frac{1}{4}f(x + 2)

with initial and final conditions f(−1) = f(0) = 0 and f(5) = f(6) = 1. This setup results in a system of 4 linear equations for 0 < x < 5,

f(1) = \frac{1}{2}f(−1) + \frac{1}{4}f(2) + \frac{1}{4}f(3)
f(2) = \frac{1}{2}f(0) + \frac{1}{4}f(3) + \frac{1}{4}f(4)
f(3) = \frac{1}{2}f(1) + \frac{1}{4}f(4) + \frac{1}{4}f(5)
f(4) = \frac{1}{2}f(2) + \frac{1}{4}f(5) + \frac{1}{4}f(6).

Solving for the unknowns using the boundary conditions yields f(1) = \frac{1}{5}, f(2) = \frac{13}{45}, f(3) = \frac{23}{45}, f(4) = \frac{29}{45}.

Although this direct method works for small values of N, solving the system of N − 1 equations becomes computationally expensive as N grows. To address this, we rewrite the recurrence relation Equation (2) as

f(x) = \frac{1}{p_{r}} f(x − a_{r}) − \frac{1}{p_{r}} ∑_{i=1}^{r−1} p_{i}f(x + a_{i} − a_{r})  (3)

obtained by the change of variables x ↦ x − a_{r}. The boundary conditions remain, f(a_{1} + 1) = 0, f(a_{1} + 2) = 0, …, f(−1) = 0, f(0) = 0 and f(N) = 1, f(N + 1) = 1, …, f(N + a_{r} − 2) = 1, f(N + a_{r} − 1) = 1. For each 1 ≤ j ≤ a_{r} define d_{j} = f(j) and construct the set S = {d_{1}, d_{2}, …, d_{j}} where a_{r} is the maximum of the a_{i}’s. Using these variables, we express

f(a_{r} + 1), f(a_{r} + 2), …, f(N + a_{r} − 1)  (4)

as linear combinations of the elements in S.

Observe that a_{1} < a_{2} < ⋯ < a_{r} implies a_{i}−a_{r} < 0 for any 1 ≤ i ≤ r−1. Hence, x+a_{i}−a_{r} < x ≤ N+a_{r}−1 for all x ∈ {a_{r} + 1, a_{r} + 2, …, N + a_{r} − 1} since 0 < a_{r} + 1 < a_{r} + 2 < ⋯ < N + a_{r} − 1. Thus, x + a_{i} − a_{r} < N + a_{r} − 1 for all x ∈ {a_{r} + 1, a_{r} + 2, …, N + a_{r} − 1} and any 1 ≤ i ≤ r − 1.

Also, x + a_{i} − a_{r} > x + a_{1} − a_{r} since a_{i} > a_{1} for any 1 ≤ i ≤ r − 1. Now, x + a_{i} − a_{r} > x + a_{1} − a_{r} ≥ a_{r} +1+a_{1} −a_{r} = a_{1} +1 for all x ∈ {a_{r} +1, a_{r} +2, …, N +a_{r} −1} since 0 < a_{r} +1 < a_{r} +2 < ⋯ < N +a_{r} −1. Hence, x + a_{i} − a_{r} > a_{1} + 1 for all x ∈ {a_{r} + 1, a_{r} + 2, …, N + a_{r} − 1}.

Therefore, a_{1} + 1 < x + a_{i} − a_{r} < N + a_{r} − 1. This implies that f(x + a_{i} − a_{r}) depends only on the following

f(a_{1} + 1), f(a_{1} + 2), …, f(0),
f(N), f(N + 1), f(N + 2), …, f(N + a_{r} − 1),
f(1), f(2), …, f(a_{r}),
f(a_{r} + 1), f(a_{r} + 2), …, f(N − 1).

We know 0 = f(a_{1}+1) = f(a_{1}+2) = ⋯ = f(0), 1 = f(N) = f(N+1) = f(N+2) = ⋯ = f(N+a_{r}−1) and f(1) = d_{1}, f(2) = d_{2}, …, f(j) = d_{j} where j = a_{r}. For any a_{r}+1 ≤ x ≤ N−1, f(a_{r}+1) is a linear combination of f(1) and f(a_{1} + 1), f(a_{2}) + 1, …, f(a_{r−1} + 1). But we know a_{1} + 1 ≤ a_{2}, a_{2} + 1 ≤ a_{3}, …, a_{r−1} + 1 ≤ a_{r} since a_{1} < a_{2} < ⋯ < a_{r−1} < a_{r}. Hence, f(a_{r} + 1) depends on at most the expression f(a_{r}), which is known. Thus, f(a_{r} + 1) depends on the variables {d_{1}, d_{2}, …, d_{j}}. Since f(x) is a recursive formula, for any x > a_{r} + 1, f(x) will be a linear combination of the variables {d_{1}, d_{2}, …, d_{j}}.

Furthermore, when f(x) is evaluated in Equation (3), f(x) will be a linear combination of {d_{1}, d_{2}, …, d_{j}} while simultaneously we have f(N) = f(N + 1) = … = f(N + a_{r} − 2) = f(N + a_{r} − 1) = 1. Therefore, these a_{r} equations are linear combinations of {d_{1}, d_{2}, …, d_{j}} where j = a_{r} and are all equal to 1. It follows that this is a system of a_{r} equations with a_{r} unknowns. Solving for this system yields solutions for {d_{1}, d_{2}, …, d_{j}} which provides solutions for the rest of the expressions, namely f(a_{r} + 1), f(a_{r} + 2), …, f(N − 1).

Example 4. (Continuing Example 3) Let N = 5 and P = [[−2, 1/2], [1, 1/4], [2, 1/4]] as in Example 3. Recall the boundary conditions: f(−1) = f(0) = 0 and f(5) = f(6) = 1. Note that a_{3} = 2, the maximum of {−2, 1, 2}, introduces the new variables {d_{1}, d_{2}} such that f(1) = d_{1}. Using the recurrence relation f(x) = 4f(x−2)−2f(x−4)−f(x−1), we construct the equations for f(3), f(4), f(5), and f(6), with r = 3:

f(−1) = f(0) = 0
f(1) = d_{1}
f(2) = d_{2}
f(3) = 4f(1) − 2f(−1) − f(2) = 4d_{1} − d_{2}
f(4) = 4f(2) − 2f(0) − f(3) = 5d_{2} − 4d_{1}
f(5) = 4f(3) − 2f(1) − f(4) = 18d_{1} − 9d_{1}
f(6) = 4f(4) − 2f(2) − f(5) = 27d_{2} − 34d_{1}.

Since f(5) = f(6) = 1, the system of equations 1 = 18d_{1} − 9d_{1} and 1 = 27d_{2} − 34d_{1} has the solution d_{1} = \frac{1}{5} and d_{2} = \frac{13}{45}. Substituting these values gives

f(1) = \frac{1}{5}, f(2) = \frac{13}{45}, f(3) = \frac{23}{45}, f(4) = \frac{29}{45}.

These results agree with Example 3.

2.2. Expected duration. In the previous section, we considered the probability for the particle to reach some position ≥ N. In this section, we consider the expected duration for the particle to end at a position ≤ 0 or a position ≥ N. Since this is analogous to the probability case, we omit the details.

Define g(x) as the expected number of steps that a particle starting at x will eventually reach a position ≤ 0 or a position ≥ N. For 0 < x < N, this expected duration satisfies the recurrence relation

g(x) = ∑_{i=1}^{r} p_{i}g(x + a_{i}) + 1,  (5)

where a_{i} ∈ ℤ, a_{1} < a_{2} < ⋯ < a_{r}, a_{1} < 0, a_{r} > 0 and boundary conditions 0 = g(a_{1} + 1) = g(a_{1} + 2) = ⋯ = g(−1) = g(0) and 0 = g(N) = g(N + 1) = ⋯ = g(N + a_{r} − 2) = g(N + a_{r} − 1).

Similar to the probability case, we rewrite Equation (5) to

g(x) = \frac{1}{p_{r}} g(x − a_{r}) − \frac{1}{p_{r}} ∑_{i=1}^{r−1} p_{i}g(x + a_{i} − a_{r}) − \frac{1}{p_{r}}  (6)

where 0 = g(a_{1} + 1) = g(a_{1} + 2) = ⋯ = g(−1) = g(0) and 0 = g(N) = g(N + 1) = ⋯ = g(N + a_{r} − 2) = g(N + a_{r} − 1).

Using Equation (6) reduces the running time for the expected duration of the game as we will see in the next section.

2.3. Comparison between the slower method and the faster method. In this section, we compare the running times in Maple between the classical approach of solving for N − 1 linear equations and the faster method from Section 2.2.

Let P = [[−1, \frac{1}{3}], [1, \frac{1}{3}], [2, \frac{1}{3}]] and N ∈ \{100, 110, 120, 130, 140, 150\}. Using GR1dLG and NewGR1dLG as described in Appendix A.1.2, we run time(GR1dLG) and time(NewGR1dLG). We get the following times in Maple:

N System of N − 1 linear equations Symbolic Computation
(seconds)  (seconds)
100  0.015  0.015
110  97.953  0.015
120  501.484  0.046
130  0.062
140  0.078
150  0.062

The data in the table suggests that introducing symbolic variables in Equation (6) dramatically reduces the running time for computing the expected durations of the game starting at all starting locations.

2.4. Variance. In this section, we consider the variance of the duration of the generalized 1-dimensional gambler’s ruin game. The computation builds up the expected duration discussed in Section 2.2.

Let P = [[a_{1}, p_{1}], [a_{2}, p_{2}], …, [a_{r}, p_{r}]] such that p_{1} + … + p_{r} = 1 and define F (x, t) as the probability generating function of the duration of the generalized 1-dimensional gambler’s ruin game. For 0 < x < N, this functions satisfies the recurrence relation

F (x, t) = t(p_{1}F (x + a_{1}, t) + p_{2}F (x + a_{2}, t) + ⋯ + p_{r}F (x + a_{r}, t)),

where F (0, t) = 1 and F (N, t) = 1. Making the substitution t ↦ z + 1 yields

F (x, z) = (z + 1)(p_{1}F (x + a_{1}, z) + p_{2}F (x + a_{2}, z) + ⋯ + p_{r}F (x + a_{r}, z),  (7)

with F (0, z) = 1 and F (N, z) = 1. We derive an expression to estimate the second factorial moment. Expanding F (x, z) as a Taylor series gives

F (x, z) = 1 + g(x)z + \frac{h(x)}{2!}z^{2} + ⋯  (8)

where g(x) is the expected duration as defined as in Section 2.2, and h(x) represents the second factorial moment at x. Substituting Equation (8) into Equation (7) results in

1 + g(x)z + \frac{h(x)}{2}z^{2} + … = (1 + z) (p_{1} (1 + g(x + a_{1})z + \frac{h(x + a_{1})}{2}z^{2} + ⋯))

+ (1 + z) (p_{2} (1 + g(x + a_{2})z + \frac{h(x + a_{2})}{2}z^{2} + ⋯))

⋮

+ (1 + z) (p_{r} (1 + g(x + a_{r})z + \frac{h(x + a_{r})}{2}z^{2} + ⋯)) .

From the previous expression, we extract the coefficient of z^{2} to get an expression for h(x). Hence,

h(x) − (p_{1}h(x + a_{1}) + p_{2}h(x + a_{2}) + ⋯ + p_{r}h(x + a_{r})) = 2(p_{1}g(x + a_{1}) + p_{2}g(x + a_{2}) + ⋯ + p_{r}g(x + a_{r}))

where 0 = g(a_{1} + 1) = g(a_{1} + 2) = ⋯ = g(−1) = g(0) and 0 = g(N) = g(N + 1) = ⋯ = g(N + a_{r} − 2) = g(N + a_{r} − 1). The sum g(x) + h(x) gives the second moment for 0 < x < N. The variance at x, denoted V (x), is computed as

V (x) = g(x) + h(x) − (g(x))^{2}

where g(x) and h(x) are defined as follows

g(x) = \frac{1}{p_{r}} g(x − a_{r}) − \frac{1}{p_{r}} ∑_{i=1}^{r−1} p_{i}g(x + a_{i} − a_{r}) − \frac{1}{p_{r}}

and

h(x) − ∑_{i=1}^{r} p_{i}h(x + a_{i}) = 2 ∑_{i=1}^{r} p_{i}g(x + a_{i}).

We conclude this section with a table comparing the expected duration and the standard deviation when the particle starts at x = \frac{N}{2} for various N and probability table P = [[−2, \frac{1}{3}], [1, \frac{1}{3}], [2, \frac{1}{3}]] .

N x Expected Duration Standard Deviation
10 5  8.613479400  6.321808669
20 10  25.23344696  18.44137538
30 15  42.94261730  29.22243692
40 20  59.58246747  37.26482832
50 25  75.36543964  43.30155080
60 30  90.70157954  48.13687964
70 35  105.8379590  52.27336865
80 40  120.8913756  55.98253147
90 45  135.9117966  59.40593597
100 50  150.9194653  62.61931702

3. 2-Dimensional Gambler’s Ruin

In this section, we consider the 2-dimensional gambler’s ruin and provide analogous results to the probability, expected duration and variance discussed in Section 2. We introduce symbolic variables to the recurrence equation of the probability and expected duration. We then compare the running times between symbolic computation and the formula provided by Kmet and Petkovšek. We conclude this section with a detailed analysis of the variance.

We begin by recalling the setup for the 2-dimensional case as described in Section 1.3. Consider a particle starting at a point (x, y) in the interior of a rectangular grid of size M ×N, where 0 < x < M and 0 < y < N. At each step, the particle moves in one of four directions, with probabilities p_{L}, p_{U}, p_{R}, and p_{B}, corresponding to left, up, right and down movements, respectively. The particle stops moving once it hits one of the four boundaries, defined by x = 0, x = M, y = 0, or y = N.

3.1. Probability. We begin by considering the recurrence relation for the probability that the particle reaches some position at one of the four boundaries. We then rewrite this recurrence and introduce new variables for the probabilities at each x and y.

Define f(x, y) = f_{L}(x, y)L + f_{R}(x, y)R + f_{U}(x, y)U + f_{D}(x, y)D, where f_{L}(x, y) is the probability that the particle, starting at (x, y) will exit the rectangle on the left side, and analogously for f_{R}(x, y), f_{U}(x, y), f_{D}(x, y), and L, R, U, D are formal variables. For 0 < x < M and 0 < y < N, this probability satisfies the recurrence relation

f(x, y) = p_{L}f(x − 1, y) + p_{U}f(x, y + 1) + p_{R}f(x + 1, y) + p_{B}f(x, y − 1)  (9)

with boundary conditions f(0, y) = L, f(x, N) = U, f(M, y) = R and f(x, 0) = B for all 0 < x < M and 0 < y < N. Thus, the coefficients of L, U, R, and B in f(x, y) represent the respective probabilities that a particle starting at (x, y) will end on each boundary. For any 0 < x < M and 0 < y < N, f(x, y) can be determined by solving a system of (M − 1) × (N − 1) linear equations with (M − 1) × (N − 1) unknowns.

In the next subsection, we will introduce symbolic variables into the recurrence relation for the expected duration, as outlined in Section 2. This method, applied to Equation 9 , but the same approach works for efficient computations of probabilities. This is further detailed in Appendix A.1.3.

3.2. Expected duration. We now consider the expected duration until the particle reaches some position at one of the four boundaries. We focus on the case when p_{W} = p_{N} = p_{E} = p_{S} = \frac{1}{4}, and remark that one can adapt our strategy for p_{W} ≠ p_{N} ≠ p_{E} ≠ p_{S} as described in Appendix A.1.3.

Define g(x, y) as the expected number of steps that a particle starting at (x, y) will eventually take to reach a position at one of the boundaries. For 0 < x < M and 0 < y < N, this expected duration satisfies the recurrence relation

g(x, y) = \frac{1}{4}g(x − 1, y) + \frac{1}{4}g(x, y + 1) + \frac{1}{4}g(x + 1, y) + \frac{1}{4}g(x, y − 1) + 1  (10)

with boundary conditions g(0, y) = g(M, y) = g(x, 0) = g(x, N) = 0 for all 0 < x < M and 0 < y < N. Similarly to the probability case, g(x, y) can be determined by solving a system of (M − 1) × (N − 1) linear equations with (M − 1) × (N − 1) unknowns.

Orr and Zeilberger provided a solution that reduces the number of linear equations from (M −1)×(N −1) to O(N + M). Their approach exploits symmetry by solving g(0, y) = g(M − 1, y) for 0 < y < N, and g(x, 1) = g(x, N − 1) for 0 < x < M [?OrrDoron]. Kmet and Petkovšek gave an explicit solution involving a double sum, enabling direct computation of the expected duration without the need to solve systems of equations or use recursion [?Kmet]. For the special case where M = N, they established the following result.

Theorem 3.1 ([?Kmet], Equation (11)). Consider the 2-dimensional gambler’s ruin problem as stated in this section. Then, the expected duration of the game when the particle starts at (x, y) is given by

g(x, y) = \frac{4}{M^{2}} ∑_{\begin{matrix}k=1 \\ k odd \end{matrix}}^{M−1} (sin (\frac{jkπ}{M} ) cot (\frac{kπ}{2M} ) ∑_{\begin{matrix}ℓ=1 \\ ℓ odd \end{matrix}}^{M−1} \frac{sin (\frac{iℓπ}{M}) cot (\frac{ℓπ}{2M})}{sin^{2} (\frac{kπ}{2M}) + sin^{2} (\frac{ℓπ}{2M})})

for any 0 ≤ x, y ≤ M.

We propose an alternative approach to those of Orr and Zeilberger, and Kmet and Petkovšek. By rewriting Equation (10), we obtain the recurrence

g(x, y) = 4g(x − 1, y) − g(x − 1, y − 1) − g(x − 1, y + 1) − g(x − 2, y) − 4  (11)

where x → x − 1. The boundary conditions remain g(0, y) = g(M, y) = g(x, 0) = g(x, N) = 0 for all x, y. For each 1 ≤ j ≤ N − 1 define d_{j} = g(1, j) and construct the set S = {d_{1}, d_{2}, …, d_{N−1}}. Using these variables, we reduce the system of equations. Initially, g(x, y) is solved by constructing a system of (M −1)×(N −1) linear equations with (M −1)×(N −1) unknowns. By using S, we reformulate the system into:

• N − 1 equations for x = 1,

• (M − 2) × (N − 1) equations for 2 ≤ x ≤ M − 1, and

• N − 1 boundary equations for x = M.

The boundary equations, derived using Equation (11), are expressed in terms of the variables in S and reduce the system to N −1 boundary equations with N −1 unknowns. Once these N −1 variables are solved, the remaining (M − 2) × (N − 1) equations can be determined. We illustrate this process in Example 5.

Example 5. Let M = N = 3. This system consists of 4 linear equations with 2 unknowns: d_{1} = g(1, 1) and d_{2} = g(1, 2). The boundary conditions are g(0, y) = g(M, y) = g(x, 0) = g(x, N) = 0 for all 0 ≤ x, y ≤ 3. Using the recurrence in Equation (11), we derive

d_{1} = g(1, 1)
d_{2} = g(1, 2)
g(2, 1) = 4d_{1} − d_{2} − 4
g(2, 2) = 4d_{2} − d_{1} − 4
g(3, 1) = 0 = 16d_{1} − 8d_{2} − 16
g(3, 2) = 0 = 16d_{2} − 8d_{1} − 16.

Solving the last two equations yields d_{1} = 2 and d_{2} = 2. Substituting these values into the earlier equations gives g(1, 1) = g(1, 2) = g(2, 1) = g(2, 2) = 2.

3.3. Comparison between Kmet and Petkovšek formula and faster method. We compare the computational running times in Maple between Kmet and Petkovšek’s formula for the expected duration and the faster method introduced in the previous section. Specifically, we evaluate the performance of NewGR2dL and KmetPetkovsek, as described in Appendix A.1.3. Using the commands time(evalf(NewGR2dL(M,M))) and time(KmetPetkovsek(M))), we measure the execution time for varying values of M. The results provide a direct comparison of the efficiency of the two methods. The measured times in Maple are summarized below:

M Faster Method Kmet and Petkovšek M Faster Method Kmet and Petkovšek
(seconds)  (seconds)  (seconds)  (seconds)
10  0.015  0.015  90  9.843  181.953
20  0.015  0.500  100  14.765  301.906
30  0.093  1.859  110  21.171  451.625
40  0.343  5.703  120  36.187  641.609
50  0.468  15.171  130  57.281  872.015
60  1.171  35.125  140  80.140  1155.281
70  2.640  63.062  150  133.109  1564.515
80  5.062  114.234  160  226.312  2023.125

While Kmet and Petkovšek’s formula expresses the expected duration as a double sum, it is computationally less efficient compared to our method.

3.4. Variance. In this subsection, we analyze the variance of the duration of the 2-dimensional gambler’s ruin game under the condition p_{W} = p_{N} = p_{E} = p_{S} = \frac{1}{4}. The computation builds upon the expected duration discussed Section 3.2.

Define F (x, y, t) as the probability generating function of the duration of the 2-dimensional gambler’s ruin game. For 0 < x < M and 0 < y < N, this function satisfies the recurrence relation

F (x, y, t) = \frac{t}{4}(F (x − 1, y, t) + F (x + 1, y, t) + F (x, y − 1, t) + F (x, y + 1, t))  (12)

where F (0, 0, t) = 1 and F (M, N, t) = 1. Making the substitution t ↦ z + 1 yields

F (x, y, z) = \frac{1 + z}{4} (F (x − 1, y, z) + F (x + 1, y, z) + F (x, y − 1, z) + F (x, y + 1, z)),  (13)

with F (0, 0, z) = 1 and F (M, N, z) = 1. We derive an expression to estimate the second factorial moment. Expanding F (x, y, z) as a Taylor series gives

F (x, y, z) = 1 + g(x, y)z + \frac{h(x, y)}{2!}z^{2} + ⋯  (14)

where g(x, y) is the expected duration as defined in Section 3.2, and h(x, y) represents the second factorial moment at (x, y). Substituting Equation (14) into Equation (12) and extracting the coefficient of z^{2} yields an expression for h(x, y):

4h(x, y)−h(x−1, y)−h(x+1, y)−h(x, y−1)−h(x, y+1) = 2(g(x−1, y)+g(x+1, y)+g(x, y−1)+g(x, y+1))

where g(0, y) = g(M, y) = g(x, 0) = g(x, N) = 0 for all x, y. The sum g(x, y) + h(x, y) gives the second moment for 0 < x < M and 0 < y < N.

The variance at (x, y), denoted by V (x, y), is computed as

V (x, y) = g(x, y) + h(x, y) − (g(x, y))^{2}

where g(x, y) and h(x, y) are defined by

g(x, y) = 4g(x − 1, y) − g(x − 1, y − 1) − g(x − 1, y + 1) − g(x − 2, y) − 4

and

4h(x, y)−h(x−1, y)−h(x+1, y)−h(x, y−1)−h(x, y+1) = 2(g(x−1, y)+g(x+1, y)+g(x, y−1)+g(x, y+1)).

We conclude this section with a table comparing the expected duration and the standard deviation when the particle starts at (x, y) = (\frac{M}{2} , \frac{M}{2} ) for various M under probabilities P = [\frac{1}{6}, \frac{1}{3}, \frac{1}{6}, \frac{1}{3}].

M (x, y) Expected Duration Standard Deviation
2 (1, 1)  1  0
4 (2, 2)  4.470588235  2.891342524
6 (3, 3)  10.3030  7.102295958
8 (4, 4)  18.47746573  12.97689858
10 (5, 5)  28.99020033  20.52455308
12 (6, 6)  41.84019550  29.74741677
14 (7, 7)  57.02707373  40.64621816
16 (8, 8)  74.55067222  53.22126050
18 (9, 9)  94.41091165  67.47268859
20 (10, 10)  116.6077497  83.40057864

4. A Mirror Step Variant of Gambler’s Ruin

In this section, we begin by formulating a new generalization of the gambler’s ruin problem in 1-dimension. A particle starts at some point x on a line of length N where 0 < x < N. At each step, the particle moves from x to x − 1 with probability q_{1}, or moves from x to x + 1 with probability q_{2}, or moves from x to N − x with probability p where 0 < p < 1 and q_{1} + q_{2} + p = 1. We call this last step the mirror step. The particle continues to walk on the line until it reaches 0 or N. We focus on the case when q_{1} = q_{2} = \frac{1−p}{2} and we call this the symmetric case.

4.1. Probability. Define f(x) = f_{N}^{(p)}(x) as the probability that a particle starting at x will eventually reach N. For 0 < x < N, this probability satisfies the recurrence relation

f(x) = \frac{1 − p}{2}f(x − 1) + \frac{1 − p}{2}f(x + 1) + pf(N − x)  (15)

where f(0) = 0 and f(N) = 1. Before providing the solution to Equation (15), we will try to guess the limit as N goes to infinity of the probability when the particle starts at some x and ends at N, by using a fixed, large, N as discussed in Section 1.4. We are interested in

lim_{N→∞} f_{N}^{(p)}(x)  (16)

and we hope to get expressions for when x = 2 and x = N − 2. First, we describe the approach that will generate data for fixed values of N and x. Using the data, we can make some guesses for the limit in Equation (16).

• Fix N as large as possible and use Maple to generate N − 1 linear equations with Equation (15).

• Solve for the N − 1 linear equations.

• Generate data for f_{N}^{(p)}(x) for different p values with fixed N and a fixed location x.

• We use the function identify in Maple to try to identify the numerical values given by f_{N}^{(p)}(x). The function identify is based, in part, on the continued fraction expansion of the numerical values. As N grows the numerical value will converge to some number.

• Guess a formula for the number with fixed x and varying p. We begin with an example on how to generate data in Maple using the code accompanying this article.

Example 6. Let N = 100 and x = 2. We generate data for the probability that if the particle starts at x = 2, the particle eventually ends at 100. Let p ∈ \{\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, …, \frac{1}{10}\}.

We use the procedure Lk(p,x,N), as described in Appendix A.1.4, in Maple which generates the following data in about 8.390 seconds:

T :=[0.48528137423857029281, 0.46410161513775458705, 0.444, 0.42705098312484227231,
0.41171425595857973499, 0.39811169380648470689, 0.38595282133533513790, 0.375,
0.36506306819388080622].

The sequence T reads as follows. If the particle starts at x = 2 and p = \frac{1}{2}, the particle moves from x to x − 1 with probability \frac{1−p}{2} = \frac{1}{4}, or moves from x to x + 1 with probability \frac{1−p}{2} = \frac{1}{4}, or moves from x to 100 − x with probability p = \frac{1}{2}. Then, the probability of the particle starting at x = 2 and ending at 100 is T_{1} = 0.48528137423857029281. Similarly, if the particle starts at x = 2 and p = \frac{1}{3}, the particle moves from x to x − 1 with probability \frac{1−p}{2} = \frac{1}{3}, or moves from x to x + 1 with probability \frac{1−p}{2} = \frac{1}{3}, or moves from x to 100 − x with probability p = \frac{1}{3}. Then, the probability of the particle starting at x = 2 and ending at 100 is T_{2} = 0.46410161513775458705. Thus, T_{i} is the probability of the particle starting at x = 2 and ending at 100 for p = \frac{1}{i+1} where 1 ≤ i ≤ 9.

Using identify in Maple for the sequence T, we conjecture that each of the probabilities in T converge to

M := [−8 + 6\sqrt{2}, −3 + 2\sqrt{3}, \frac{4}{9}, \frac{−5 + 3\sqrt{5}}{4}, \frac{−24 + 14\sqrt{6}}{25}, \frac{−7 + 4\sqrt{7}}{9}, \frac{−32 + 36\sqrt{2}}{49}, \frac{3}{8}, \frac{−40 + 22\sqrt{10}}{81}] .

That is the probability of the particle starting at x = 2 and ending at N as N grows converges to M_{i} for p = \frac{1}{i+1} where 1 ≤ i ≤ 9.

The previous example illustrates that when the particle starts at x = 2, {f_{N}^{(p)}(2)} converges fast. We state the following guess for the expression of the limit when x = 2 and in Corollary 4.4.1 we provide a proof.

Guess 4.1. If the particle starts at x = 2, then

lim_{N→∞} f_{N}^{(p)}(2) = \frac{2\sqrt{p}(1 + p − 2\sqrt{p})}{(1 − p)^{2}}.

Using the same approach from above, we can obtain data for x = N −2. We guess the following expression of the limit when x = N − 2 and provide a proof in Corollary 4.4.1.

Guess 4.2. If the particle starts at x = N − 2, then

lim_{N→∞} f_{N}^{(p)}(N − 2) = \frac{(1 + p)(1 + p − 2\sqrt{p})}{(1 − p)^{2}}.

We were able to guess more expressions for lim_{N→∞} f_{N}(x) with other x values. After we made these guesses, we established the following key lemma which provides a relation between f(x) and f(N − x) for any 0 ≤ x ≤ N. We stress that this is only true for the symmetric case when the probability of the particle moving from x to x − 1 is the same as the probability of the particle moving from x to x + 1.

Lemma 4.3. Consider the symmetric case when f(x) = \frac{1−p}{2}f(x − 1) + \frac{1−p}{2}f(x + 1) + pf(N − x) with boundary conditions f(0) = 0, f(N) = 1 for some 0 < p < 1. For any 0 ≤ x ≤ N, the following identity holds

f(x) + f(N − x) = 1.

Proof. Call g(x) = 1 − f(N − x). We will show that f(x) + f(N − x) = 1 by proving that g(x) = f(x). Note that g(0) = 0 and g(N) = 1, and f(x) = 1 − g(N − x). Using the recurrence in Equation (15), we substitute 1 − g(N − x) for f(x) and obtain:

g(N − x) = \frac{1 − p}{2}g(N − (x − 1)) + \frac{1 − p}{2}g(N − (x + 1)) + pg(x).

That is,

g(x) = \frac{1 − p}{2}g(x + 1)) + \frac{1 − p}{2}g(x − 1) + pg(N − x)

which has boundary conditions g(0) = 0 and g(N) = 1. Therefore, g(x) = f(x) as desired. □

Lemma 4.3 establishes that the sums of the probabilities when the particle starts at x and when the particle starts at N − x equals to 1. Using this identity, we rewrite Equation (15) to

f(x) = \frac{p}{1 + p} + \frac{1}{2} (\frac{1 − p}{1 + p}) f(x − 1) + \frac{1}{2} (\frac{1 − p}{1 + p}) f(x + 1), f(0) = 0, f(N) = 1.  (17)

We can now derive the probability of the particle ending at N if it starts at some x, for general N, x and p.

Theorem 4.4. Consider the generalization of the gambler’s ruin problem when we add a mirror step. Then, the probability of ending at N starting at x is given by

f(x) = \frac{1}{2} \frac{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} + 1}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}} (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} + \frac{1}{2} \frac{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} + 1}{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} − (\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N}} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x} + \frac{1}{2}

whenever we restrict the particle moves by either moving from x to x − 1 with probability q_{1}, or from x to x + 1 with probability q_{2}, or from x to N − x with probability p where q_{1} = q_{2} = \frac{1−p}{2}.

Proof. We can solve for Equation (17) because it is an inhomogeneous recurrence relation. Hence, we find a homogeneous and an inhomogeneous solution. The general solution to the homogeneous equation f(x) = \frac{1}{2} (\frac{1−p}{1+p}) f(x − 1) + \frac{1}{2} (\frac{1−p}{1+p}) f(x + 1) is

f(x) = A (\frac{1 + p + 2\sqrt{p}}{1 − p})^{x} + B (\frac{1 + p − 2\sqrt{p}}{1 − p})^{x}

for some numbers A and B. Next, we find the particular solution to the inhomogeneous relation by setting f^{∗}(x) = C for some constant C. Then,

f^{∗}(x) = \frac{p}{1 + p} + \frac{1}{2} (\frac{1 − p}{1 + p}) f^{∗}(x − 1) + \frac{1}{2} (\frac{1 − p}{1 + p}) f^{∗}(x + 1)

becomes

C = \frac{p}{1 + p} + \frac{1}{2} (\frac{1 − p}{1 + p}) C + \frac{1}{2} (\frac{1 − p}{1 + p}) C

which has solution C = \frac{1}{2}.

Therefore, f^{∗}(x) = \frac{1}{2} is the particular solution, and the general inhomogeneous solution is

f(x) = A (\frac{1 + p + 2\sqrt{p}}{1 − p})^{x} + B (\frac{1 + p − 2\sqrt{p}}{1 − p})^{x} + \frac{1}{2}.  (18)

Using Maple, we find A and B by using the boundary conditions to get a system of two linear equations. Namely,

0 = A + B + \frac{1}{2}

and

\frac{1}{2} = A (\frac{1 + p + 2\sqrt{p}}{1 − p})^{N} + B (\frac{1 + p − 2\sqrt{p}}{1 − p})^{N} .

Solving for the above linear equations gives

A = \frac{1}{2} \frac{(\frac{1+p−2\sqrt{p}}{1−p})^{N} + 1}{(\frac{1+p+2\sqrt{p}}{1−p})^{N} − (\frac{1+p−2\sqrt{p}}{1−p})^{N}}  (19)

and

B = \frac{1}{2} \frac{(\frac{1+p+2\sqrt{p}}{1−p})^{N} + 1}{(\frac{1+p−2\sqrt{p}}{1−p})^{N} − (\frac{1+p+2\sqrt{p}}{1−p})^{N}} .  (20)

Rewriting Equations 18, 19 and 20 gives

f(x) = A (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} + B (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x} + \frac{1}{2}

with

A = \frac{1}{2} \frac{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} + 1}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}} ,
B = \frac{1}{2} \frac{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} + 1}{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} − (\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N}} .

This completes the proof. □

Theorem 4.4 provides a formula for lim_{N→∞} f_{N}(x) for any x where 0 < x < N. Corollary 4.4.1. If the particle starts at some x where 0 < x < N, then

lim_{N→∞} f_{N}^{(p)}(x) = \frac{1}{2} − \frac{1}{2} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x}

whenever we restrict the particle moves by either moving from x to x − 1 with probability q_{1}, or from x to x + 1 with probability q_{2}, or from x to N − x with probability p where q_{1} = q_{2} = \frac{1−p}{2}. Proof. Let

f_{N}^{(p)}(x) = \frac{1}{2} \frac{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} + 1}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}} (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} + \frac{1}{2} \frac{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} + 1}{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} − (\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N}} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x} + \frac{1}{2},  (21)

and

g_{N}^{(p)}(x) = \frac{1}{2} \frac{1}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})N} (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} + \frac{1}{2} − \frac{1}{2} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x} .

We will show that lim_{N→∞} f_{N}^{(p)}(x) − g_{N}^{(p)}(x) = 0. Observe that

f_{N}^{(p)}(x) − g_{N}^{(p)}(x) = \frac{1}{2} \frac{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} + 1}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}} (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} + \frac{1}{2} \frac{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} + 1}{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} − (\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N}} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x}

− \frac{1}{2} \frac{1}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})N} (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} + \frac{1}{2} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x}

= \frac{1}{2} (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} (\frac{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} + 1}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}} − (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{N} )

+ \frac{1}{2} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x} (\frac{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} + 1}{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} − (\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N}} + \frac{1}{2})

= \frac{1}{2} (\frac{1 + \sqrt{p}}{1 − \sqrt{p}})^{x} (\frac{(\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} + (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{2N}}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}} ) − \frac{1}{2} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x} (\frac{1 + (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}} )

= \frac{1}{2} \frac{(1 + (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}) ((\frac{1+\sqrt{p}}{1−\sqrt{p}})^{x} (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{x})}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{N} − (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}}

= \frac{1}{2} \frac{(1 + (\frac{1−\sqrt{p}}{1+\sqrt{p}})^{N}) ((\frac{1+\sqrt{p}}{1−\sqrt{p}})^{x} − 1)}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{2N} − 1}.

Since

lim_{N→∞} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{N} = 0

and

lim_{N→∞} \frac{1}{2} \frac{((\frac{1+\sqrt{p}}{1−\sqrt{p}})^{x} − 1)}{(\frac{1+\sqrt{p}}{1−\sqrt{p}})^{2N} − 1} = 0,

It follows that

lim_{N→∞} f_{N}^{(p)}(x) − g_{N}^{(p)}(x) = 0.

Thus,

lim_{N→∞} f_{N}^{(p)}(x) = \frac{1}{2} − \frac{1}{2} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}})^{x}

as desired.

□

Using Corollary 4.4.1 provides a proof for Guess 1.1. See the following example. Example 7. Setting x = 1,

lim_{N→∞} f_{N}^{(p)}(1) = \frac{1}{2} − \frac{1}{2} (\frac{1 − \sqrt{p}}{1 + \sqrt{p}}) = \frac{\sqrt{p} − p}{1 − p}

as expected.

4.2. Expected duration. We now consider the expected duration of the gambler’s ruin problem with a mirror step. Define g(x) as the expected number of steps that a particle starting at x will eventually reach a position 0 or N. For 0 < x < N, this expected duration satisfies the recurrence relation

g(x) = \frac{1 − p}{2}g(x − 1) + \frac{1 − p}{2}g(x + 1) + pg(N − x) + 1, g(0) = 0, g(N) = 0.  (22)

We use this recurrence relation to find a closed formula for the expected duration of the game.

Theorem 4.5. Consider the generalization of the gambler’s ruin problem when we add a mirror step. Then, the expected duration of ending at 0 or N starting at x is given by

g(x) = \frac{1}{1 − p}x(N − x)

whenever we restrict the particle moves by either moving from x to x − 1 with probability q_{1}, or from x to x + 1 with probability q_{2}, or jumps to N − x with probability p where q_{1} = q_{2} = \frac{1−p}{2}.

Remark: When p = 0, Theorem 4.5 recovers the formula for the expected duration of the classical gambler’s ruin game.

Proof. Let h(x) = \frac{1}{1−p}x(N − x) and observe that h(0) = 0, h(N) = 0. We prove that h(x) satisfies the same recurrence relation as g(x). Applying the recurrence from Equation (22) to h(x) and simplifying yields

\frac{1 − p}{2}h(x − 1) + \frac{1 − p}{2}h(x + 1) + ph(N − x) + 1

= \frac{1 − p}{2} (\frac{1}{1 − p}(x − 1)(N − x + 1)) + \frac{1 − p}{2} (\frac{1}{1 − p}(x + 1)(N − x − 1)) + p (\frac{1}{1 − p}x(N − x)) + 1

= \frac{1}{1 − p}x(N − x).

Hence, h(x) satisfies the following recurrence relation

h(x) = \frac{1 − p}{2}h(x − 1) + \frac{1 − p}{2}h(x + 1) + ph(N − x) + 1, h(0) = 0, h(N) = 0.

Thus, we get that h(x) = g(x) which completes the proof. □

5. Future Work

In Section 4, we consider a generalization of the gambler’s ruin problem where the particle starts at some point x on a line of length N where 0 < x < N. At each step, the particle either moves to the left by one step with probability q_{1}, moves to the right by one step with probability q_{2}, or moves to N − x with probability p where 0 < p < 1 and q_{1} + q_{2} + p = 1. We focus on the case when q_{1} = q_{2} = \frac{1−p}{2}, and we provide formulas for the probability that the particle ends at N and the expected number of steps to finish the game. Thus, it is an open problem to give formulas for general q_{1}, q_{2} and p.

Computational evidence suggests the following conjecture when the probability of moving from x to x − 1 is the same as the probability of moving from x to N − x.

Conjecture 5.1. Consider the generalization of the gambler’s ruin problem when we add a mirror step. If the particle starts at x = 1, then

lim_{N→∞} f_{N}^{(p)}(1) = \frac{\sqrt{(p + 1)(1 − 3p + 4p^{2})} − (1 − 2p)(p + 1)}{2p(p + 1)}

whenever we restrict the particle moves by either moving from x to x − 1 with probability q_{1}, or from x to x + 1 with probability p, or from x to N − x with probability q_{2} where q_{1} = q_{2} = \frac{1−p}{2}.

Acknowledgements

The author thanks her advisor Dr. Doron Zeilberger for the introduction to the problem and feedback on an earlier draft. The author was supported by the NSF Graduate Research Fellowship Program under Grant No. 2233066.

Appendix A. Computational Tools for Analyzing the Gambler’s Ruin Problem

A.1. Method Descriptions. There are four text files accompanying this article: GGR.txt, GGR1d.txt, GGR2d.txt, and GGR1dMirror.txt. In this section, we will describe the functionality of some of the main procedures. These text files should be saved in the same directory. All procedures were written and tested for Maple 20.

A.1.1. GGR.txt. The GGR.txt file contains the following main procedures.

• ProbN(N)

Returns a list L of length N − 1. This function inputs a positive integer N and computes the probability of ending at N for every

1 ≤ x ≤ N − 1.

Example:

 read `GGR.txt`:
 N:=10;
 ProbN(N);

Output:

{[1/10, 1/5, 3/10, 2/5, 1/2, 3/5, 7/10, 4/5, 9/10]}
• ExpN(N)

Returns a list L of length N − 1. This function inputs a positive integer N and computes the expected number of steps of ending

at either 0 or N for every 1 ≤ x ≤ N − 1.

A.1.2. GGR1d.txt. The GGR1d.txt file contains procedures for the classical gambler’s ruin game. In addition, it contains procedures for the 1-dimensional case. We provide the main procedures.

• GR1dPG(N,P)

Returns a list L of length N − 1. This function inputs a positive integer N and a probability table P where P = [[a_{1}, p_{1}], [a_{2}, p_{2}], ..., [a_{r}, p_{r}]]

and computes the probability of the particle ending at some position ≥ N for every 1 ≤ x ≤ N − 1. Remark: This procedures uses the classical approach of solving for N − 1 linear equations. Example:

 read `GGR1d.txt`:
 P:=GR1dPG(10,[[-1,1/2],[1,1/2]]);

Output:

{[1/10, 1/5, 3/10, 2/5, 1/2, 3/5, 7/10, 4/5, 9/10]}
• GR1dLG(N,P)

Returns a list L of length N − 1. This function inputs a positive integer N and a probability table P where P = [[a_{1}, p_{1}], [a_{2}, p_{2}], ..., [a_{r}, p_{r}]]

and computes the expected number of steps for the particle to end at ≤ 0 or ≥ N for every 1 ≤ x ≤ N − 1.

Remark: This procedures uses the classical approach of solving for N − 1 linear equations.

• NewGR1dPG(N,P)

Returns a list L of length N − 1. This function inputs a positive integer N and a probability table P where P = [[a_{1}, p_{1}], [a_{2}, p_{2}], ..., [a_{r}, p_{r}]]

and computes the probability for the particle to end at ≥ N for every 1 ≤ x ≤ N − 1. Remark: This procedures uses the faster method. Example:

 read `GGR1d.txt`:
 P:=NewGR1dPG(10,[[-1,1/2],[1,1/2]]);

Output:

   {[1/10, 1/5, 3/10, 2/5, 1/2, 3/5, 7/10, 4/5, 9/10]}
• NewGR1dLG(N,P)

Returns a list L of length N − 1.

This function inputs a positive integer N and a probability table P where P = [[a_{1}, p_{1}], [a_{2}, p_{2}], ..., [a_{r}, p_{r}]] and computes the expected number of steps for the particle to end at ≤ 0 or ≥ N for every 1 ≤ x ≤ N − 1.

Remark: This procedures uses the faster method.

A.1.3. GGR2d.txt. The GGR2d.txt file contains procedures for the 2-dimensional gambler’s ruin game. We provide the main procedures.

• GR2dP(M,N,L,U,R,B)

Returns an (M − 1) × (N − 1) matrix whose entries are linear combinations of L,U,R,B.

This function inputs positive integers M, N and symbols L,U,R,B where L is the left edge, U is the top edges, R is the right edge and B is the bottom edge of the M × N rectangle, and computes the probability of the particle starting at some point (a, b) and ending on L, U, R or B for every 1 ≤ a ≤ M − 1 and 1 ≤ b ≤ M − 1.

Remark: This procedures uses the classical approach of solving for (M − 1) × (N − 1) linear equations.

Example:

    read `GGR2d.txt`:
    GR2dP(3,3,L,U,R,B);

Output:

   {[[(3L)/8 + (3B)/8 + U/8 + R/8, (3L)/8 + B/8 + (3U)/8 + R/8], [L/8 + (3B)/8 + U/8 + (3R)/8,
L/8 + B/8 + (3U)/8 + (3R)/8]]}
• GR2dL(M,N)

Returns an (M − 1) × (N − 1) matrix M.

This function inputs positive integers M, N and computes the expected number of steps of the particle starting at some point (a, b) and ending on L, U, R or B for every 1 ≤ a ≤ M − 1 and 1 ≤ b ≤ M − 1.

Remark: This procedures uses the classical approach of solving for (M − 1) × (N − 1) linear equations.

Example:

    read `GGR2d.txt`:
    GR2dL(3,3);

Output:

   {[[2, 2], [2, 2]]}
• NewGR2dP(M,N,L,U,R,B)

Returns an (M − 1) × (N − 1) matrix whose entries are linear combinations of L,U,R,B.

This function inputs positive integers M, N and symbols L,U,R,B where L is the left edge, U is the top edges, R is the right edge and B is the bottom edge of the M × N rectangle, and computes the probability of the particle starting at some point (a, b) and ending on L, U, R or B for every 1 ≤ a ≤ M − 1 and 1 ≤ b ≤ M − 1.

Remark: This procedures uses the faster method.

Example:

    read `GGR2d.txt`:
    NewGR2dP(3,3,L,U,R,B);

Output:

{[[(3L)/8 + (3B)/8 + U/8 + R/8, (3L)/8 + B/8 + (3U)/8 + R/8], [L/8 + (3B)/8 + U/8 + (3R)/8,
L/8 + B/8 + (3U)/8 + (3R)/8]]}
• NewGR2dL(M,N)

Returns an (M − 1) × (N − 1) matrix M. This function inputs positive integers M, N and computes the expected number of steps of the

particle starting at some point (a, b) and ending on L, U, R or B for every 1 ≤ a ≤ M − 1 and 1 ≤ b ≤ M − 1.

Remark: This procedures uses the faster method. Example:

 read `GGR2d.txt`:
 NewGR2dL(3,3);

Output:

{[[2, 2], [2, 2]]}
• NewGR2dPG(M,N,L,U,R,B,P)

Returns an (M − 1) × (N − 1) matrix whose entries are linear combinations of L,U,R,B. This function inputs positive integers M, N, symbols L,U,R,B where L is the left edge, U is the

top edges, R is the right edge and B is the bottom edge of the M × N rectangle, and a probability table P = [p_{L}, p_{U}, p_{R}, p_{B}] such that the particle moves left by one step with probability p_{L}, or moves up by one step with probability p_{U}, or moves right by one step with probability p_{R}, or moves down by one step with probability p_{B}, and computes the probability of the particle starting at some point (a, b) and ending on L, U, R or B for every 1 ≤ a ≤ M − 1 and 1 ≤ b ≤ M − 1.

Remark: This procedures uses the faster method. Example:

 read `GGR2d.txt`:
 NewGR2dPG(3,3,L,U,R,B,[1/4,1/4,1/4,1/4]);

Output:

{[[R/8 + (3L)/8 + U/8 + (3B)/8, R/8 + (3L)/8 + (3U)/8 + B/8], [(3R)/8 + L/8 + U/8 + (3B)/8,
(3R)/8 + L/8 + (3U)/8 + B/8]]}
• NewGR2dLG(M,N,P)

Returns an (M − 1) × (N − 1) matrix. This function inputs positive integers M, N, and a probability table P = [p_{L}, p_{U}, p_{R}, p_{B}] such that

the particle moves left by one step with probability p_{L}, or moves up by one step with probability p_{U}, or moves right by one step with probability p_{R}, or moves down by one step with probability p_{B}, and computes the expected number of steps of the particle starting at some point (a, b) and ending on L, U, R or B for every 1 ≤ a ≤ M − 1 and 1 ≤ b ≤ M − 1.

Remark: This procedures uses the faster method. Example:

 read `GGR2d.txt`:
 NewGR2dLG(3,3,[1/4,1/4,1/4,1/4]);

Output:

{[[2, 2], [2, 2]]}
• KmetPetkovsek(N)

Returns an (N − 1) × (N − 1) matrix. This function inputs a positive integer N and implements Kmet and Petkovsek’s formula for the

expected duration of the 2-dimensional gambler’s ruin game for the M = N case.

Example:

 read `GGR2d.txt`:

    KmetPetkovsek(3);

Output:

   {[[2, 2], [2, 2]]}

A.1.4. GGR1dMirror.txt. The GGR1dMirror.txt file contains the following main procedures for the new generalization of gambler’s ruin where we add a third step.

• ProbN2(N,P)

Returns a list L of length N.

This function inputs a positive integer N and a probability table P where P = [p_{1}, p_{2}, p_{3}] where p_{1} + p_{2} + p_{3} = 1 and outputs a list L of length N such that L[x] is the probability of the particle ending at N when it starts at x where the particle can move from x to x − 1 with probability p_{1}, or x to x + 1 with probability p_{2}, or x to N − x with probability p_{3}.

Example:

    read `GGR1dMirror.txt`:
    ProbN2(5,[1/3,1/3,1/3]);

Output:

   {[7/19, 9/19, 10/19, 12/19, 1]}
• ExpN2(N,P)

Returns a list L of length N.

This function inputs a positive integer N and a probability table P where P = [p_{1}, p_{2}, p_{3}] where p_{1} + p_{2} + p_{3} = 1 and outputs a list L of length N such that L[x] is the expected number of steps that the particle takes to end at N or 0 when it starts at x where the particle can move from x to x − 1 with probability p_{1}, or x to x + 1 with probability p_{2}, or x to N − x with probability p_{3}.

Example:

    read `GGR1dMirror.txt`:
    ExpN2(5,[1/3,1/3,1/3]);

Output:

   {[6, 9, 9, 6, 0]}
• Lk(p,x,N)

Returns a number.

This function inputs a probability value p, 0 < p < 1, and positive integers x, N where 0 < x < N and outputs the exact probability of the particle ending at N when it starts at location x where with probability (1 − p)/2 the particle moves to x − 1, with probability (1 − p)/2 the particle moves to x + 1 and with probability p the particle moves to N − x.

Example:

    read `GGR1dMirror.txt`:
    Lk(1/3,4,100);

Output:

   {0.4974226119}

(L. Martinez) Department of Mathematics, Rutgers University, Piscataway, NJ 08854

E-mail address: lucy.martinez@rutgers.edu