Explicit Expressions for Moments of the Duration of a 3-Player (Fair) Gambler’s Ruin

Shalosh B. EKHAD and Doron ZEILBERGER

Dedicated to Jean-Paul Delahaye, the French analog of Martin Gardener

How It All Started: Jean-Paul Delahaye’s Wonderful Monthly Column

We are lucky to be on the emailing-list of Jean-Paul Delahaye, who sends us each month his fascinating Logique et Calcul column for the French analog of Scientific American, called Pour la Science. The August piece [De] was dedicated to the Gambler’s Ruin problem, that is one of our favorites. We naively believed that we already knew everything about it, and wrote a paper[Z], fifteen years ago. But that was about the classical two-player case, that goes back to 1657, when Christiaan Huygens discussed and solved it. It is covered extensively in Feller’s probability bible [F].

Thanks to Delahaye’s column, we learned about exciting new extensions by Persi Diaconis and Stewart Ethier, and earlier ones [E] [BLT] [S] [R].

Warm-Up: On the Duration of The 2-player Gambler’s Ruin

Alice and Bob start out with A dollars and B dollars, respectively. A fair coin is tossed, and it lands on Heads, Alice gives Bob a dollar, so now their capitals are A − 1 and B + 1 respectively. On the other hand, if it lands on Tails, Bob gives Alice a dollar, and now their respective capitals are A+1 and B −1. Sooner or later, with probability one, one of them goes broke, and the other one goes home with A + B dollars. The duration of the game is a certain random variable, let’s call is D. Huygnes (probably) proved (see [F]) the famous result

E[D] = AB .

Less well known is an explicit expression for the variance (probably in [F])

V ar(D) = \frac{AB (A^{2} + B^{2} − 2)}{3} .

In [Z] we computed the first ten moments (about the mean), but now we have forty(!) of them, and can easily compute more. Let’s state a few of them here. Let m_{r} be the r-th moment about the mean. We have

m_{3}(D) = \frac{AB (3A^{4} + 10A^{2}B^{2} + 3B^{4} − 10A^{2} − 10B^{2} + 4)}{15} .

m_{4}(D) = \frac{AB}{105} ·

(17A^{6} + 35A^{5}B + 119A^{4}B^{2} + 70A^{3}B^{3} + 119A^{2}B^{4} + 35A B^{5} + 17B^{6} − 84A^{4} − 140A^{3}B − 280A^{2}B^{2}

−140A B^{3} − 84B^{4} + 84A^{2} + 140AB + 84B^{2} + 8) .

m_{5}(D) = \frac{AB}{945} ·

(155A^{8} +630A^{7}B +1860A^{6}B^{2} +2730A^{5}B^{3} +3906A^{4}B^{4} +2730A^{3}B^{5} +1860A^{2}B^{6} +630A B^{7} +155B^{8}

−1020A^{6} − 3360A^{5}B − 7140A^{4}B^{2} − 8400A^{3}B^{3} − 7140A^{2}B^{4} − 3360A B^{5} − 1020B^{6} + 1764A^{4}

+5040A^{3}B + 5880A^{2}B^{2} + 5040A B^{3} + 1764B^{4} − 440A^{2} − 1680AB − 440B^{2} − 144) .

m_{6}(D) = \frac{AB}{10395}·

(2073A^{10}+12573A^{9}B+43780A^{8}B^{2}+95040A^{7}B^{3}+154143A^{6}B^{4}+172326A^{5}B^{5}+154143A^{4}B^{6}+95040A^{3}B^{7}

+43780A^{2}B^{8}+12573A B^{9}+2073B^{10}−17050A^{8}−86130A^{7}B−239250A^{6}B^{2}−418110A^{5}B^{3}−498960A^{4}B^{4}−

418110A^{3}B^{5} − 239250A^{2}B^{6} − 86130A B^{7} − 17050B^{8} + 42636A^{6} + 182028A^{5}B

+367752A^{4}B^{2} + 489720A^{3}B^{3} + 367752A^{2}B^{4} + 182028A B^{5} + 42636B^{6} − 29040A^{4} − 116160A^{3}B

−143000A^{2}B^{2} − 116160A B^{3} − 29040B^{4} − 3344A^{2} − 528AB − 3344B^{2} − 1440) .

To see all the moments up to the 40-th, look at the output file

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGR3moms3a.txt .

Arthur Engel’s Beautiful Expression for the Expected Duration of a (fair) 3-player Gambler’s Ruin

In a gambler’s ruin game with three players, the players have initial capitals A, B, C. At each round, one of the players is chosen uniformly at random (i.e. with probability \frac{1}{3}) to give one dollar to one of the other two players (each of whom is equally likely to be the recipient). Sooner or later, one of the players goes broke. How soon?

Equivalently (and that is how Engel thought of it) you have three towers with A, B, C, pegs, and at each round, uniformly at random, you remove a peg from one of the towers and put it (each with probability \frac{1}{2}), on one of the other towers (It is like the Tower of Hanoi, but all pegs have the same diameter). Sooner or later, one of the towers is empty. How soon?

Using simulation, and guessing, Arthur Engel [E] conjectured that the expected duration, E[D], is given by the lovely, explicit formula

E[D] = \frac{3ABC}{A + B + C} .

Once discovered, he had no trouble proving it, since calling this quantity E(A, B, C), it obviously satisfies the equation

E(A, B, C) = 1 + \frac{1}{6} (A(A + 1, B − 1, C) + E(A − 1, B + 1, C)

+E(A + 1, B, C − 1) + E(A − 1, B, C + 1)
+E(A, B + 1, C − 1) + A(A, B − 1, C + 1)) ,

subject to the boundary conditions

E(0, B, C) = 0 , E(A, 0, C) = 0 , E(A, B, 0) = 0 ,

and this is a routine verification. Proving uniqueness is fairly easy, using a maximum principle (see [A], p. 40).

But, in hindsight, there was no need for simulation. Because of the boundary conditions, it is natural to postulate the ansatz

E(A, B, C) = \frac{kABC}{A + B + C}

(Note that the denominator A + B + C is the total number of pegs (dollars) and is an invariant). Here k is an undetermined coefficient, that is to be determined. Plugging it in the equation, one get that indeed k = 3.

Bruss et. al. [BLT] worked pretty hard to find the variance.

V ar(D) = \frac{3ABC (A^{2}B + A^{2}C + A B^{2} − 3ABC + A C^{2} + B^{2}C + B C^{2} − A − B − C)}{2 (A + B + C)^{2}} .

David Stirzaker [S] later gave a simpler proof, using martingales. We will soon describe an even simpler (and much more elementary!) proof, using computer algebra. Using this method, we will also discover, and prove, explicit expressions for many higher moments (and one can keep going indefinitely).

But let’s first state some of these beautiful formulas.

m_{3}(D) = \frac{3ABC}{40(A + B + C)^{3}} ·

(9A^{5}B+9A^{5}C+54A^{4}B^{2}+108A^{4}BC+54A^{4}C^{2}+90A^{3}B^{3}−225A^{3}B^{2}C−225A^{3}B C^{2}+90A^{3}C^{3}+54A^{2}B^{4}

−225A^{2}B^{3}C+1080A^{2}B^{2}C^{2}−225A^{2}B C^{3}+54A^{2}C^{4}+9A B^{5}+108A B^{4}C−225A B^{3}C^{2}−225A B^{2}C^{3}+108AB C^{4}

+9A C^{5}+9B^{5}C+54B^{4}C^{2}+90B^{3}C^{3}+54B^{2}C^{4}+9B C^{5}−90A^{3}B−90A^{3}C−180A^{2}B^{2}+90A^{2}BC−180A^{2}C^{2}

−90A B^{3} + 90A B^{2}C + 90AB C^{2} − 90A C^{3} − 90B^{3}C − 180B^{2}C^{2} − 90B C^{3} + 12A^{2}
+24AB + 24AC + 12B^{2} + 24BC + 12C^{2}) .

m_{4}(D) = \frac{3ABC}{280(A + B + C)^{4}} ·

(6A^{8}B + 6A^{8}C + 54A^{7}B^{2} + 108A^{7}BC + 54A^{7}C^{2} + 195A^{6}B^{3} + 354A^{6}B^{2}C + 354A^{6}B C^{2} + 195A^{6}C^{3}

+357A^{5}B^{4} + 63A^{5}B^{3}C − 588A^{5}B^{2}C^{2} + 63A^{5}B C^{3} + 357A^{5}C^{4} + 357A^{4}B^{5} − 378A^{4}B^{4}C +3423A^{4}B^{3}C^{2} + 3423A^{4}B^{2}C^{3} − 378A^{4}B C^{4} + 357A^{4}C^{5} + 195A^{3}B^{6} + 63A^{3}B^{5}C + 3423A^{3}B^{4}C^{2} −8505A^{3}B^{3}C^{3}+3423A^{3}B^{2}C^{4}+63A^{3}B C^{5}+195A^{3}C^{6}+54A^{2}B^{7}+354A^{2}B^{6}C−588A^{2}B^{5}C^{2}+3423A^{2}B^{4}C^{3} +3423A^{2}B^{3}C^{4}−588A^{2}B^{2}C^{5}+354A^{2}B C^{6}+54A^{2}C^{7}+6A B^{8}+108A B^{7}C +354A B^{6}C^{2}+63A B^{5}C^{3}

−378A B^{4}C^{4} + 63A B^{3}C^{5} + 54B^{2}C^{7} + 6B C^{8} + 354A B^{2}C^{6} + 108AB C^{7} + 6A C^{8} + 6B^{8}C +54B^{7}C^{2} + 195B^{6}C^{3} + 357B^{5}C^{4} + 357B^{4}C^{5} + 195B^{3}C^{6} − 63A^{6}B − 63A^{6}C − 441A^{5}B^{2} − 882A^{5}BC

−441A^{5}C^{2} − 1008A^{4}B^{3} − 819A^{4}B^{2}C − 819A^{4}B C^{2} − 1008A^{4}C^{3} − 1008A^{3}B^{4}

−3150A^{3}B^{2}C^{2} − 1008A^{3}C^{4} − 441A^{2}B^{5} − 819A^{2}B^{4}C − 3150A^{2}B^{3}C^{2} − 3150A^{2}B^{2}C^{3} − 819A^{2}B C^{4} −441A^{2}C^{5}−63A B^{6}−882A B^{5}C−819A B^{4}C^{2}−819A B^{2}C^{4}−882AB C^{5}−63A C^{6}−63B^{6}C−441B^{5}C^{2}

−1008B^{4}C^{3} − 1008B^{3}C^{4} − 441B^{2}C^{5} − 63B C^{6} + 161A^{4}B + 161A^{4}C + 483A^{3}B^{2} + 791A^{3}BC

+483A^{3}C^{2} + 483A^{2}B^{3} + 1260A^{2}B^{2}C + 1260A^{2}B C^{2} + 483A^{2}C^{3} + 161A B^{4} + 791A B^{3}C

+1260A B^{2}C^{2} + 791AB C^{3} + 161A C^{4} + 161B^{4}C + 483B^{3}C^{2} + 483B^{2}C^{3}

+161B C^{4}+16A^{3}+48A^{2}B+48A^{2}C+48A B^{2}+96ABC+48A C^{2}+16B^{3}+48B^{2}C+48B C^{2}+16C^{3}) .

To see the first 20 moments (about the mean), enjoy the following output file:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGR3moms4a.txt .

How Did We do it via Symbol-Crunching? The Two-Player Case Let’s first consider the classical case. Let F (A, B)(y) be the probability generating function of the random variable ‘duration until one of the players goes broke’, if the initial capitals were A and B dollars. Obviously, F (A, B)(y) satisfies the following equation:

F (A, B)(y) = \frac{y}{2} (F (A + 1, B − 1)(y) + F (A − 1, B + 1)(y)) ,  (1)

subject to the boundary conditions F (A, 0)(y) = 1 , F (0, B)(y) = 1 .

Let’s expand F (A, B)(y) as a Taylor series around y = 1,

F (A, B)(y) = ∑_{i=0}^{∞} f_{i}(A, B)(y − 1)^{i} .  (2)

f_{i}(A, B) is equal to the binomial moment

E [\binom{D(A, B)}{i}] .

Once you have the binomial moments, you can easily compute the moments

E[D(A, B)^{i}] = ∑_{j=0}^{i} j! S(i, j) E [\binom{D(A, B)}{j}] ,

where S(i, j) are the Stirling numbers of the second-kind.

Once you have the moments, in particular, the most important one, μ = E[D(A, B)], you can get the moments about the mean by

E[(D(A, B) − μ)^{i}] = ∑_{j=0}^{i}(−μ)^{i−j} \binom{i}{j}E[D(A, B)]^{j} .

Plugging-in (2) into (1) and writing, for convenience y − 1 = z, we have

∑_{i=0}^{∞} f_{i}(A, B)z^{i} = \frac{1 + z}{2} (∑_{i=0}^{∞} f_{i}(A + 1, B − 1)z^{i} + ∑_{i=0}^{∞} f_{i}(A − 1, B + 1)z^{i}) .  (3)

Comparing the coefficient of z^{i}, we have the equation

f_{i}(A, B) = \frac{1}{2}(f_{i}(A + 1, B − 1) + f_{i}(A − 1, B + 1)) + \frac{1}{2}(f_{i−1}(A + 1, B − 1) + f_{i−1}(A − 1, B + 1)) ,

Implying that

f_{i}(A, B) − \frac{1}{2}(f_{i}(A + 1, B − 1) + f_{i}(A − 1, B + 1)) = \frac{1}{2}(f_{i−1}(A + 1, B − 1) + f_{i−1}(A − 1, B + 1)) .

Assuming that we already know f_{i−1}(A, B) (of course f_{0}(A, B) = 1), we postulate an ansatz for f_{i}(A, B) as a polynomial in A, B of degree 2i, using undetermined coefficients, letting Maple do the tedious high-school algebra, getting a system of linear equations satisfied by these so far undetermined coefficients, and to our delight, get a unique solution. The uniqueness (in general) is easy by a “maximum principle”.

The Three-Player (fair) Gambler’s Ruin Until One Player Goes Broke

Everything is analogous. Letting f_{i}(A, B, C) be the binomial moment of the random variable ‘duration (until one of the players goes broke)’, with initial capitals A, B, C, we have

f_{i}(a, b, c) − \frac{1}{6}(f_{i}(A + 1, B − 1, C) + f_{i}(A − 1, B + 1, C)

+f_{i}(A + 1, B, C − 1) + f_{i}(A − 1, B, C + 1)

+f_{i}(A, B + 1, C − 1) + f_{i}(A, B − 1, C + 1))

= \frac{1}{6}(f_{i−1}(A + 1, B − 1, C) + f_{i−1}(A − 1, B + 1, C)

+f_{i−1}(A + 1, B, C − 1) + f_{i−1}(A − 1, B, C + 1)

+f_{i−1}(A, B + 1, C − 1) + f_{i−1}(A, B − 1, C + 1)) .

Inspired by Engel’s formula for the first moment, Now the ansatz is a polynomial in A, B, C of degree 2i + 1 divided by A + B + C. Since the denominator is inviariant, it is retaioned, and we can look at the numerator and do the linear algebra with undetermined coefficients, like we did for the two-player case.

Duration for a k-Player (fair) Gambler’s Ruin until Only One Player survives

The Expectation is easy, as already pointed out by Sheldon Ross [R] (of the popular probability textbooks fame). If k-players, with initial capitals A_{1}, …, A_{k}, the expected duration until k − 1 drop out, is

∑_{1≤i<j≤k} A_{i} A_{j} .

Alas, the higher moments do not seem to be nice, let alone polynomials (or even rational functions).

Probability of Winning

For the classical, two-player, gambler’s ruin, famously (and trivially) the probability of winning the whole pot for the player whose initial capital was a_{1} dollars (and the other had a_{2} dollars) is \frac{a_{1}}{a_{1}+a_{2}} . There does not seem to be a ‘nice’ (let alone polynomial or rational) formula, but the the fascinating article [DiE] has some very good approximations, and proved asymptotics, in N, for the special case of capitals 1, 1, N. In fact, they prove that it is O(1/N^{3}).

Recall that the scaled moments (about the mean) are m_{i}/m_{2}^{i/2}.

The limit of the scaled moments with equal capitals for two players

If both players start out with the same capital a, then, of course

m_{1} = E[D] = a^{2} , σ^{2} = m_{2} = \frac{2}{3}a^{4} + O(a^{3}) ,

and the limits of the scaled moments (about the mean), from the third to the 20^{th}, as a goes to infinity, expressed in decimals are as follows. 1.9595917942265424786, 8.8285714285714285714, 42.737763893131259770, 255.69610389610389610, 1775.6935988640577894, 14103.678121878121878, 126010.34642879135344, 1250957.5292367075649, 13660640.862506747726, 162737708.10778675241, 2100232711.7489454497, 29189813843.019299016,

434668787296.09441079, 6904215035796.8421121, 116519631313642.16450,

2082128256599445.4176, 39273259761289810.763, 779763346464591374.25 .

In particular, the limiting skewness (scaled third-moment about the mean) is 1.9595917942265424786, and the limiting kurtosis (scaled fourth-moment about the mean) is 8.8285714285714285714, as already computed in [Z]. For the exact values, see the output file

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGR3moms5.txt .

The Limit of the Scaled moments with equal capitals for three players If all three players start out with the same capital a, then, of course

m_{1} = E[D] = a^{2} , σ^{2} = m_{2} = \frac{1}{2}a^{4} + O(a^{3}) ,

and the limits of the scaled moments (about the mean), from the third to the 15^{th}, as a goes to infinity, in decimals are 1.8384776310850235634, 8.2714285714285714286, 38.719147032686238015, 226.13701298701298701,

1529.4150671558283928, 11835.953251748251748, 103028.09771971592326,

996496.58001633815101, 10601990.334510850051, 123051719.84505166456,
1547212853.2328220329, 20950631863.915761840, 303953682939.86889196 .

In particular, the limiting skewness is 1.8384776310850235634,a little less than the two-player case, and the limiting kurtosis is 8.2714285714285714286, also a little less than its counterpart. For the exact values, see the output file

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGR3moms6.txt .

More than Three-Players? With the exception of Ross’s formula (mentioned above), that only handles the expectation, for the k-player game until only one survives, this approach does not seem to work with more than three players. Of course, perhaps there is yet-another ansatz, and perhaps one can get, by symbolcrunching at least asymptotic results, but this remains to be seen. Again we strongly recommend the very interesting Diaconis-Ethier article [DiE], whose existence we learned thanks to Jean-Paul Delahaye’s engaging column.

References

[A] Jiri Andrei, “Mathematics and Chance”, Wiley, 2001.

[BLT] F.T. Bruss, G. Louchard, and J.W. Turner, On the N-tower problem and related problems. Adv. Appl. Probab. 35 (2003), 278-294.

[De] Jean-Paul Delahaye, Ruiner le casino ou se ruiner, Pour la Science 550 (August 2023), p. 80.

https://medias.pourlascience.fr/api/v1/files/64b5166b903f8e26c07a14f5?alt=file

[DiE] Persi Diaconis and Stewart N. Ethier, Gamblers Ruin and the ICM, Statist. Sci. 3, 289-305, August 2022.

https://arxiv.org/abs/2011.07610 .

[E] Arthur Engel, The computer solves the three tower problem, Amer. Math. Monthly 100 (1993), 62-64.

[F] William Feller, “An Introduction to Probability Theory and Its Application”, volume 1, three editions. John Wiley and sons. First edition: 1950. Second edition:1957. Third edition: 1968. Volume 2: two editions.

[R] Sheldon M. Ross, A simple solution to a multiple player gambler’s ruin problem, Amer. Math. Monthly 116 (2009), 77-81.

[S] David Stirzaker, Three-handed gambler’s ruin, Adv. Appl. Probab. 38 (2006), 284-286.

[Z] Doron Zeilberger, Symbol-crunching with the gamblers ruin problem, in: “Tapas in Experimental Mathematics”, Contemporary Mathematics 457 (2008), 285-292, (Tewodros Amdeberhan and Victor Moll, eds.)

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/ruin.html .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Sept. 13, 2023. 9