# Gambler’s Ruin and the ICM

Persi Diaconis111Departments of Mathematics and Statistics, Stanford
University. Research supported by NSF grant DMS 1954042. Stewart N.
Ethier222Department of Mathematics, University of Utah. Research supported by
Simons Foundation grant 429675.

###### Abstract

Consider gambler’s ruin with three players, 1, 2, and 3, having initial
capitals $A$, $B$, and $C$ units. At each round a pair of players is chosen
(uniformly at random) and a fair coin flip is made resulting in the transfer
of one unit between these two players. Eventually, one of the players is
eliminated and play continues with the remaining two. Let $\sigma\in S_{3}$ be
the elimination order (e.g., $\sigma=132$ means player 1 is eliminated first
and player 3 is eliminated second, leaving player 2 with $A+B+C$ units).

We seek approximations (and exact formulas) for the elimination order
probabilities $P_{A,B,C}(\sigma)$. Exact, as well as arbitrarily precise,
computation of these probabilities is possible when $N:=A+B+C$ is not too
large. Linear interpolation can then give reasonable approximations for large
$N$. One frequently used approximation, the independent chip model (ICM), is
shown to be inadequate. A regression adjustment is proposed, which seems to
give good approximations to the elimination order probabilities.

Keywords: gambler’s ruin problem, tower problem, linear interpolation,
independent chip model (ICM), Plackett–Luce model, linear regression.

“In the case where there are three players with limited fortunes, the various
problems appear to be of quite a different order of difficulty than in the
case of two players.” Louis Bachelier (1912)

##  1 Introduction

As motivation, first consider gambler’s ruin with two players, 1 and 2, who
initially have 1 and $N-1$ units. At each round a fair coin flip is made
resulting in the transfer of one unit from one player to the other.
Eventually, one of the players goes broke. It is a classical result that

$P_{1,N-1}(\text{player 2 goes broke})=\frac{1}{N}.$

Consider next the game with three players having initial fortunes 1, 1, $N-2$.
At each round a pair of players is chosen (uniformly at random) and a fair
coin flip is made resulting in the transfer of one unit between these two
players. What is

$P_{1,1,N-2}(\text{player 3 goes broke first})\,?$

This basic problem has had little study. A first thought is, “Consider player
3 versus $\\{1,2\\}$.” This is like gambler’s ruin with two players. Perhaps

$P_{1,1,N-2}(\text{player 3 goes broke
first})\approx\frac{\text{constant}}{N}.$

A well-studied scheme, the independent chip model (ICM), explained in
Subsection 2.7 below, suggests

$P_{1,1,N-2}(\text{player 3 goes broke first})=\frac{2}{N(N-1)}.$

We prove below that both of these are off. Indeed,

$P_{1,1,N-2}(\text{player 3 goes broke
first})\approx\frac{\text{constant}}{N^{3}}.$

It does not seem easy to give a simple heuristic for the $N^{3}$, and for
$k\geq 4$ players, the correct order of decay is open.

Let the initial capitals be $A$, $B$, and $C$ units, and put $N:=A+B+C$. Let
$\sigma\in S_{3}$ be the elimination order (e.g., $\sigma=132$ means player 1
is eliminated first and player 3 is eliminated second, leaving player 2 with
$N$ units). Useful approximations to $P_{A,B,C}(\sigma)$ are important in
widely played versions of tournament poker; if, at the final table, three
players remain, the first-, second-, and third-place finishers get fixed
amounts $\alpha$, $\beta$, and $\gamma$, say, not depending on $A$, $B$, and
$C$. Clearly, $P_{A,B,C}(\sigma)$ is crucial in evaluating an equitable split
of the prize pool $\alpha+\beta+\gamma$, should the players decide to
“settle.” Such calculations are also required to evaluate the results of
various actions throughout the game.

######  Example 1.1.

In the 2019 World Series of Poker Main Event, at the time the fourth-place
finisher was eliminated, the three remaining players had chip counts as shown
in Table 1 (WSOP, 2019a).

Table 1: The final three in the 2019 World Series of Poker Main Event. 0000player | chip count | big blinds | actual payoff
---|---|---|---
Dario Sammartino |  0$67{,}600{,}000$ |  033.8 |  0$\$6{,}000{,}000$
Alex Livingston | $120{,}400{,}000$ |  060.2 |  0$\$4{,}000{,}000$
Hossein Ensan | $326{,}800{,}000$ | 163.4 | $\$10{,}000{,}000$
0000total | $514{,}800{,}000$ | 257.4 |

At this stage of the tournament, the standard unit bet — the big blind — was
$2{,}000{,}000$ chips. Initial capital, in big blinds, is shown for the three
players in Table 1, but to avoid fractions we multiply these numbers by 5 to
get $A=169$, $B=301$, and $C=817$. In the ensuing competition, the elimination
order turned out to be 213, leaving Hossein Ensan with all $514{,}800{,}000$
chips and the $10 million first-place prize. The methods developed below (see
Examples 2.3 and 3.2) give the chances shown in Table 2 for the six possible
elimination orders, assuming our random walk is a reasonable model for a no-
limit Texas hold’em tournament. Thus, the second most likely elimination order
is what actually occurred.

Table 2: The approximate probabilities of the six possible elimination orders in the scenario of Table 1, assuming chip counts (in units of $400{,}000$ chips, or 1/5 of the big blind) equal to $A=169$, $B=301$, and $C=817$. $\sigma$ | 123 | 132 | 213 | 231 | 312 | 321
---|---|---|---|---|---|---
$P_{A,B,C}(\sigma)$ | 0.4196 | 0.2079 | 0.2152 | 0.1062 | 0.0260 | 0.0251

Section 2 contains background on gambler’s ruin and the independent chip
model. We review the connections with absorbing Markov chain theory. This
allows exact computation for $N$ up to at least 200. Another approach, Jacobi
iteration, allows virtually exact computation for $N$ up to at least 300.

We also observe that the $N=300$ data can be linearly interpolated to give
reasonable approximations for arbitrary $N$. One other method of
approximation, based on a Monte Carlo technique, is described.

Recent results for “nice” absorbing Markov chains (see Diaconis, Houston-
Edwards, and Saloff-Coste, 2020) allow crude but useful approximations of
$P_{A,B,C}(\sigma)$ uniformly. The $\text{constant}/N^{3}$ result is proved as
a consequence of that work.

A new approximation approach is introduced in Section 3. The ratio

$P_{A,B,C}^{\text{GR}}(\sigma)/P_{A,B,C}^{\text{ICM}}(\sigma)$

appears to be a smooth function of $A$, $B$, and $C$. A sixth-degree
polynomial regression is fit to this ratio and seen to give good
approximations to $P_{A,B,C}^{\text{GR}}(\sigma)$. In the sequel, superscripts
GR (“gambler’s ruin”) and ICM (“independent chip model”) will be used only
when there is a chance of confusion. (No superscript implicitly means GR.)

Section 4 gives some results for the gambler’s ruin problem with $k\geq 4$
players as well as a conjecture, namely the scaling conjecture

$P_{A^{\prime},B^{\prime},C^{\prime}}(\sigma)\doteq
P_{A,B,C}(\sigma)\quad\text{whenever}\quad\frac{A^{\prime}}{A}=\frac{B^{\prime}}{B}=\frac{C^{\prime}}{C},$

where $\doteq$ denotes approximate equality. (The symbol $\approx$ has a
different meaning; see Theorem 2.4 below.) An equivalent formulation,

$P_{nA,nB,nC}(\sigma)\doteq P_{A,B,C}(\sigma),\qquad n\geq 2,$ (1.1)

may be preferable because it is closely related to the provable result that
$\lim_{n\to\infty}P_{nA,nB,nC}(\sigma)$ exists; indeed, the limit can be
expressed in terms of standard two-dimensional Brownian motion. A conjecture
that is mathematically sharper than (1.1) appears in Subsection 4.1.

Finally, Section 5 summarizes the various methods of evaluating and
approximating the elimination order probabilities. In all, six methods of
approximation are studied, including a Brownian motion approximation along
with the methods mentioned above.

## Acknowledgments

We thank Laurent Saloff-Coste, Laurent Miclo, Gene Kim, Sangchul Lee, Sourav
Chatterjee, Guanyang Wang, Thomas Bruss, Pat Fitzsimmons, Bruce Hajek, Denis
Denisov, Steve Stigler, Bernard Bru, Mason Malmuth, and Tom Ferguson for their
help. We are particularly indebted to Chris Ferguson for emphasizing the
utility and mathematical depth of the problem.

##  2 Background

This section contains background on gambler’s ruin — in two and higher
dimensions (three or more players). Exact computation of the Poisson kernel
(harmonic measure) using absorbing Markov chains is taken up in Subsection
2.2, and arbitrarily precise computation by Jacobi iteration is the subject of
Subsection 2.3. The use of barycentric coordinates to linearly interpolate
these exact values is taken up in Subsection 2.4. Another approaches to
approximate computation, Monte Carlo methods, is described in Subsection 2.5.

The asymptotics of the Poisson kernel are treated in Subsection 2.6, which
includes a proof of $P_{1,1,N-2}(\text{player 3 goes broke
first})\approx\text{constant}/N^{3}$. Finally, the ICM is introduced and its
relation to the Plackett–Luce model is developed in Subsection 2.7.

###  2.1 Gambler’s ruin

With two players, gambler’s ruin is a classical topic, well developed in
Feller (1968, Chap. XIV) and Ethier (2010, Chap. 7). Important extensions to
unfair coin flips and more-general step sizes are also well developed. See
Song and Song (2013) for a historical survey.

For $k=3$ players, the subject was first studied by Bachelier (1912). The
first post-Bachelier reference we have found is the Brownian motion in a
triangle due to Cover (1987). This was solved by conformally mapping the
triangle to a disk and using classical results for the Poisson kernel of the
disk, by Hajek (1987) and later, independently, by Ferguson (1995). Further
results for $k=3$, including the poker connection, are in Kim (2005).

Martingale theory can be used to get information about the time to absorption.
For three players, let $T_{1}$ be the first time one of the three players is
eliminated. Bachelier (1912, §204), Engel (1993), and Stirzaker (1994) proved

$E(T_{1})=\frac{3ABC}{A+B+C}.$ (2.1)

Thus, if $A=B=C=100$, then $E(T_{1})=10{,}000$. If $A=B=1$ and $C=298$, then
$E(T_{1})=2.98$. Bruss, Louchard, and Turner (2003) and Stirzaker (2006)
evaluated $\text{Var}(T_{1})$. Let $T_{2}$ be the first time two players are
eliminated. Bachelier (1912, §209), Engel (1993), and Stirzaker (1994) showed
that

$E(T_{2})=AB+AC+BC.$ (2.2)

Thus, if $A=B=C=100$, then $E(T_{2})=30{,}000$. If $A=B=1$ and $C=298$, then
$E(T_{2})=597$.

Actually, Bachelier and Engel used first-order linear partial difference
equations, while Stirzaker used martingales. Bachelier’s (1912, §209) proof of
(2.2) is very much worth rereading.

A standard theorem (Bachelier 1912, §14) is

$P(\text{player 3 wins all})=\frac{C}{A+B+C}.$ (2.3)

The results (2.2) and (2.3) generalize to $k$ players. There is a related
development in the language of the “Towers of Hanoi” problem (Bruss, Louchard,
and Turner, 2003; Ross, 2009). None of this literature addresses the position
at the first absorption time.

###  2.2 Exact computation by Markov chain methods

The gambler’s ruin model is an example of an absorbing Markov chain in the
state space

$\mathscr{X}:=\\{(x_{1},x_{2},x_{3})\in\textbf{Z}^{3}:x_{1},x_{2},x_{3}\geq
0,\,x_{1}+x_{2}+x_{3}=N\\}.$

The first two coordinates determine things and the state space can be pictured
(when $N=6$) as in Figure 1. The classical stars and bars argument shows that

$|\mathscr{X}|=\binom{N+2}{2},$

and $\mathscr{X}$ has $\binom{N-1}{2}$ interior states, $3(N-1)$ nonabsorbing
boundary states, and 3 absorbing states. The Markov chain stopped at time
$T_{1}$ is itself a Markov chain whose transition matrix can be written in
block form as

$\bordermatrix{&\text{boundary}&\text{interior}\cr\text{boundary}&\bm{I}&\bm{0}\cr\text{interior}&\bm{S}&\bm{Q}\cr},$

and elementary arguments yield the following theorem (Kemeny and Snell, 1976,
Theorem 3.3.7).

Figure 1: When $N=6$, the state space $\mathscr{X}$ is represented by 28 dots,
of which 10 are interior states (open dots), 15 are nonabsorbing boundary
states (solid dots), and 3 are absorbing states (larger solid dots). Line
segments show possible transitions. There are six from each interior state and
two from each nonabsorbing boundary state.

######  Theorem 2.1.

For $\bm{x}\in\text{Int}(\mathscr{X})$ and $\bm{y}$ in the set of nonabsorbing
boundary states of $\mathscr{X}$, define

$P(\bm{x},\bm{y}):=P_{\bm{x}}(\text{chain first reaches boundary at }\bm{y}),$

so that $\bm{P}$ is a $\binom{N-1}{2}\times 3(N-1)$ matrix. Then

$\bm{P}=(\bm{I}-\bm{Q})^{-1}\bm{S}.$

The function $P(\bm{x},\bm{y})$ is called the Poisson kernel or harmonic
measure.

######  Example 2.2.

When $N=6$, $|\mathscr{X}|=\binom{6+2}{2}=28$, with the $\binom{6-1}{2}=10$
interior states ordered $114$, $123$, $132$, $141$, $213$, $222$, $231$,
$312$, $321$, $411$, and the $3(6-1)=15$ nonabsorbing boundary states ordered
$015$, $024$, $033$, $042$, $051$, $105$, $204$, $303$, $402$, $501$, $150$,
$240$, $330$, $420$, $510$. The Poisson kernel is given by Figure 2.

Figure 2: The Poisson kernel for $N=6$. Rows are labeled by initial interior
states ($114$, $123$, $132$, $141$, $213$, $222$, $231$, $312$, $321$, $411$),
and columns by nonabsorbing boundary states ($015$, $024$, $033$, $042$,
$051$, $105$, $204$, $303$, $402$, $501$, $150$, $240$, $330$, $420$, $510$).

From this we have the chance that the first absorption occurs at a given
boundary point. For the two remaining players, classical gambler’s ruin gives
the probability of the final outcome. Summing over the appropriate part of the
boundary gives the chances of the various elimination orders. For $N=6$, these
are given in Figure 3. Here the row ordering is as before, whereas the column
ordering is $123$, $132$, $213$, $231$, $312$, $321$.

Figure 3: The probabilities of the six elimination orders for $N=6$. Rows are
labeled by initial interior states ($114$, $123$, $132$, $141$, $213$, $222$,
$231$, $312$, $321$, $411$) and columns by elimination orders ($123$, $132$,
$213$, $231$, $312$, $321$).

Mathematica code, for arbitrary $N$, is provided in the supplementary
materials (see Section 6). The only computationally difficult part of the
program is inverting an $\binom{N-1}{2}\times\binom{N-1}{2}$ matrix. When
$N=200$ (the largest $N$ for which we have results), this matrix is
$19{,}701\times 19{,}701$ and the program runtime (in double precision) was
about 97 hours. A faster alternative is described in Subsection 2.3.

A very interesting paper by Swan and Bruss (2006) suggests that much larger
problems might be tackled. Their ideas apply to more general absorbing chains,
but let us specialize to the three-player gambler’s ruin. They partition the
transient states into disjoint “levels” and observe that the transition matrix
can be written as a block tridiagonal matrix (up to “corner effects”) with
considerably smaller blocks. Their second idea is to derive a “folded” chain
on the even blocks. This has the same block tridiagonal form and so recursion
can be used. Finally the absorption probabilities for the chain started in the
odd blocks can be filled in. They do an order of magnitude calculation of the
number of operations involved (along the lines of “it takes order $n^{3}$
steps to invert an $n\times n$ matrix”) and conclude that the new algorithm
would run a factor of $N^{2}$ steps faster than the straightforward matrix
inversion we have used above. The indexing is fairly sophisticated and we have
not attempted to implement their fine ideas.

Using weighted directed multigraphs, David (2015) was able to reduce the
number of transient states by about a factor of two. His results, with $N$ as
large as 192, are consistent with ours. For application of this approach to
four-player gambler’s ruin, see Marfil and David (2020).

Gilliland, Levental, and Xiao (2007) found a way to avoid the inversion of
large matrices in a one-dimensional gambler’s ruin problem, but we have not
been able to adapt their approach to the present setting.

These same techniques work for general absorbing Markov chains. We have used
them (supplementary materials, Section 6) to compute the elimination order
probabilities for $k=4$ players, requiring the inverse of an
$\binom{N-1}{3}\times\binom{N-1}{3}$ matrix. When $N=50$ (the largest $N$ for
which we have results), this matrix is $18{,}424\times 18{,}424$ and the
program runtime (in single precision) was about 84.5 hours. Here the walk
takes place in a discrete 4-simplex. Initial absorption is on one of the four
triangular faces, and from there to final absorption one can apply the three-
player results.

These examples are extremely instructive, but it would be prohibitively time-
intensive to derive exact results for numbers of practical interest in the
poker context. In Example 1.1, $N=257.4$ (big blinds), but to avoid fractional
capital, we chose $N=1287$ (big blinds times 5).

###  2.3 Arbitrarily precise computation by Jacobi iteration

Fix an elimination order $\sigma\in S_{3}$ and total capital $N$. Let
$P_{A,B}$ be short for $P_{A,B,N-A-B}(\sigma)$. Then, for $A,B\geq 1$ with
$A+B\leq N-1$,

$P_{A,B}=\frac{1}{6}(P_{A-1,B+1}+P_{A+1,B-1}+P_{A-1,B}+P_{A+1,B}+P_{A,B-1}+P_{A,B+1})$

with boundary conditions determined by $\sigma$. This may be used in two ways.
Start with any values for the $P_{A,B}$ agreeing with the boundary conditions,
say all $P_{A,B}=\frac{1}{6}$ except when $A=0$, $B=0$, or $A+B=N$. Then
repeatedly iterate this recurrence. Again this may be done in two ways, either
using (at stage $n$) $P^{n+1}$ in terms of $P^{n}$ or using updated values as
they become available. This method was used by Kim (2005) and seen to converge
well for small values of $N$ (e.g., $N=16$).

A second approach harnesses a monotonicity property of the recurrence. Let
$P_{A,B}^{*}$ be the true gambler’s ruin probabilities. If $P_{A,B}^{n}\leq
P_{A,B}^{*}$ for all $A,B$, then $P_{A,B}^{n+1}\leq P_{A,B}^{*}$ for all
$A,B$. Similarly for $P_{A,B}^{n}\geq P_{A,B}^{*}$. Thus, starting the
recurrence off with the correct boundary values and all other
$P_{A,B}^{0,-}\equiv 0$ and $P_{A,B}^{0,+}\equiv 1$ gives

$P_{A,B}^{n,-}\leq P_{A,B}^{*}\leq P_{A,B}^{n,+}\text{ for all }A,B\text{ and
}n.$

When the lower and upper bounds are suitably close, this gives sharp control
of $P_{A,B}^{*}$. For a proof of convergence and further development, history,
and references, see Ethier (2010, Theorem 7.2.4).

We adopt the latter approach, and we find that we can ensure the desired
accuracy (18 significant digits) with $2N^{2}$ iterations. Mathematica code
(for arbitrary $N$) is provided in the supplementary materials. No matrix
inversion is needed, so the program runs faster and uses much less memory than
the one based on Markov chain methods. When $N=200$, the program runtime (in
double precision) was about 19 hours. When $N=300$ (the largest $N$ for which
we have results) it was about 98.5 hours.

The output of this program is a list of $P_{A,B,C}(123)$ for all $A,B,C\geq 1$
with $A+B+C=N$. If, for example, we want $P_{1,1,N-2}(321)$, we simply look up
$P_{N-2,1,1}(123)$ instead. Thus, there is no real loss of information in this
condensed form of the output.

While this method allows for a larger $N$ in evaluating the three-player
elimination order probabilities than the Markov chain method does ($N=300$ vs.
$N=200$), the improvement is more significant in the four-player setting. Here
we generate the probabilities $P_{A,B,C,D}(1234)$ for all $A,B,C,D\geq 1$ with
$A+B+C+D=N$ and again find that $2N^{2}$ iterations suffice to ensure the
desired accuracy (9 significant digits). When $N=100$ (the largest $N$ for
which we have results), the runtime was about 36 hours. Mathematica code is
provided in the supplementary materials, but C++ code would run substantially
faster.

###  2.4 Linear interpolation from exact probabilities

The virtually exact results for $N=300$ can be used to get useful
approximations for other $N$. Given positive integers $A$, $B$, and $C$, let
$N:=A+B+C$ and

$A_{0}:=A\,\frac{300}{N},\quad B_{0}:=B\,\frac{300}{N},\quad
C_{0}:=C\,\frac{300}{N}.$

Typically, these are not integers. Therefore, consider the four points

$\displaystyle\bm{v}_{00}$ $\displaystyle:=(\lfloor A_{0}\rfloor,\lfloor
B_{0}\rfloor,300-\lfloor A_{0}\rfloor-\lfloor B_{0}\rfloor),$
$\displaystyle\bm{v}_{01}$ $\displaystyle:=(\lfloor A_{0}\rfloor,\lceil
B_{0}\rceil,300-\lfloor A_{0}\rfloor-\lceil B_{0}\rceil),$
$\displaystyle\bm{v}_{10}$ $\displaystyle:=(\lceil A_{0}\rceil,\lfloor
B_{0}\rfloor,300-\lceil A_{0}\rceil-\lfloor B_{0}\rfloor),$
$\displaystyle\bm{v}_{11}$ $\displaystyle:=(\lceil A_{0}\rceil,\lceil
B_{0}\rceil,300-\lceil A_{0}\rceil-\lceil B_{0}\rceil),$

belonging to $\mathscr{X}$, and discard the one ($\bm{v}_{00}$ or
$\bm{v}_{11}$) whose third coordinate is neither $\lfloor C_{0}\rfloor$ nor
$\lceil C_{0}\rceil$. The remaining three points, call them
$(A_{1},B_{1},C_{1})$, $(A_{2},B_{2},C_{2})$, and $(A_{3},B_{3},C_{3})$, form
a triangle with $(A_{0},B_{0},C_{0})$ belonging to its interior, and we can
estimate $P_{A,B,C}(\sigma)$ by linear interpolation from the three values of
$P_{A_{i},B_{i},C_{i}}(\sigma)$ ($i=1,2,3$).

The key idea is to represent $(A_{0},B_{0},C_{0})$ in barycentric coordinates.
The relevant weights are

$\binom{\lambda_{1}}{\lambda_{2}}:=\begin{pmatrix}A_{1}-A_{3}&A_{2}-A_{3}\\\
B_{1}-B_{3}&B_{2}-B_{3}\end{pmatrix}^{-1}\binom{A_{0}-A_{3}}{B_{0}-B_{3}}\quad\text{and}\quad\lambda_{3}:=1-\lambda_{1}-\lambda_{2},$

so that

$(A_{0},B_{0},C_{0})=\lambda_{1}(A_{1},B_{1},C_{1})+\lambda_{2}(A_{2},B_{2},C_{2})+\lambda_{3}(A_{3},B_{3},C_{3}),$

and our interpolation estimate is then

$\bar{P}_{A,B,C}(\sigma):=\lambda_{1}P_{A_{1},B_{1},C_{1}}(\sigma)+\lambda_{2}P_{A_{2},B_{2},C_{2}}(\sigma)+\lambda_{3}P_{A_{3},B_{3},C_{3}}(\sigma).$

######  Example 2.3.

As described in Example 1.1, the final three players in the 2019 WSOP Main
Event had chip counts (in units of $400{,}000$ chips, or $1/5$ of the big
blind) equal to $A=169$, $B=301$, and $C=817$. Thus, $N=1287$ and $A$, $B$,
and $C$, multiplied by $300/N$, are $A_{0}\doteq 39.39$, $B_{0}\doteq 70.16$,
and $C_{0}\doteq 190.44$. It follows that $(A_{1},B_{1},C_{1})=(39,70,191)$,
$(A_{2},B_{2},C_{2})=(39,71,190)$, and $(A_{3},B_{3},C_{3})=(40,70,190)$. The
weights can then be evaluated as

$\lambda_{1}=\frac{190}{429},\quad\lambda_{2}=\frac{70}{429},\quad\lambda_{3}=\frac{13}{33},$

and we can look up the probabilities $P_{A_{i},B_{i},C_{i}}(\sigma)$ for
$i=1,2,3$ and each $\sigma$, with results shown in Table 3.

Table 3: Linearly interpolating elimination order probabilities from $N=300$ data. Here $A=169$, $B=301$, and $C=817$ from Example 1.1. $\sigma$ | 123 | 132 | 213 | 231 | 312 | 321
---|---|---|---|---|---|---
$P_{39,70,191}(\sigma)$ | 0.422050 | 0.207786 | 0.214617 | 0.105295 | 0.025547 | 0.024705
$P_{39,71,190}(\sigma)$ | 0.422204 | 0.210495 | 0.211129 | 0.104734 | 0.026172 | 0.025266
$P_{40,70,190}(\sigma)$ | 0.415774 | 0.206898 | 0.217559 | 0.107757 | 0.026436 | 0.025576
$\bar{P}_{A,B,C}(\sigma)$ | 0.419603 | 0.207878 | 0.215207 | 0.106174 | 0.025999 | 0.025139

The scaling conjecture and observed smoothness of $P_{A,B,C}(\sigma)$ in $A$,
$B$, and $C$ suggest that this will be a good approximation. One way to assess
the accuracy of the method is to use it to estimate probabilities that are
already known; we have done so in several cases, and it appears that the
interpolated probabilities are accurate to four or five decimal places. See
Example 3.2 below for an alternative approach.

Note that rounded proportions often do not sum precisely to 1. See Diaconis
and Freedman (1979).

###  2.5 Monte Carlo methods

While the interpolation method of Subsection 2.4 is our method of choice, this
subsection records a further approximation method, Monte Carlo. Guanyang Wang
suggested a straightforward Monte Carlo procedure that approximates
$P_{A,B,C}(\sigma)$ for a given $A,B,C\geq 1$ and all $\sigma\in S_{3}$.
Simply run the Markov chain, starting at $(A,B,C)$, until it first reaches the
boundary. If $N:=A+B+C$ and the Markov chain first reaches the boundary at
$(0,x,N-x)$, for example, then $\sigma=123$ and $\sigma=132$ are counted
$(N-x)/N$ and $x/N$ times, by virtue of the two-player gambler’s ruin formula.
Do this repeatedly, recording the proportion of times each $\sigma\in S_{3}$
occurs, and use these proportions as estimates. A difficulty is that this
procedure is rather slow. For example, the expected number of steps for the
Markov chain to first reach the boundary is given by (2.1), which is
$96{,}876.4$ when using the WSOP data of Examples 1.1 and 2.3 ($A=169$,
$B=301$, and $C=817$).

Wang suggested an optimization method to speed up the process. Starting from
state $(x_{1},x_{2},x_{3})$, let $m=\min(x_{1},x_{2},x_{3})$ and consolidate
the next $m$ steps of the Markov chain into a single step by simulating
$(n_{1},n_{2},n_{3})\sim\text{multinomial}(m,\frac{1}{3},\frac{1}{3},\frac{1}{3})$,
with $n_{i}$ representing the number of matchups in the next $m$ trials not
involving player $i$, and $\zeta_{i}\sim\text{binomial}(n_{i},\frac{1}{2})$
($i=1,2,3$) to tell the full story.

Wang has written R code and shown that it works well for quite large $N$ (and
also for $k=4$). Starting with the just mentioned WSOP data ($A=169$, $B=301$,
and $C=817$), the standard Monte Carlo procedure requires 2.7 seconds per
sample path or 7.5 hours for sample size $10^{4}$, with the optimized
procedure requiring only 0.0182 seconds per sample path or 3 minutes for
sample size $10^{4}$ (148 times faster). Example 3.2 below compares simulation
results (optimized, with sample size $10^{6}$) with other approximations.

###  2.6 Analytic approximation

Some rather sophisticated analysis (John and inner uniform domains, Whitney
covers, parabolic Harnack inequalities, Carlesson estimates) have been applied
to get analytic approximations to the harmonic measure (Diaconis, Houston-
Edwards, and Saloff-Coste, 2020). The results apply to the $k$-player
gambler’s ruin problem, but we will content ourselves with the case $k=3$.
Code things up as in Figure 1 with two coordinates $x_{1}$, $x_{2}$ in the
triangle $x_{1},x_{2}\geq 0$, $x_{1}+x_{2}\leq N$. This corresponds to
$A=x_{1}$, $B=x_{2}$, and $C=N-(x_{1}+x_{2})$. By symmetry, it is enough to
have approximations to

$P(\bm{x},(y,0)):=P_{\bm{x}}(\text{walk first reaches boundary at }(y,0))$

with $\bm{x}=(x_{1},x_{2})$ in the interior of $\mathscr{X}$, satisfying
$2x_{1}+x_{2}\leq N$. The boundary point $(y,0)$ has $0<y<N$.

######  Theorem 2.4 (Diaconis, Houston-Edwards, Saloff-Coste, 2020).

For $x_{1},x_{2},y$ as above,

$P(\bm{x},(y,0))\approx\frac{x_{1}x_{2}(x_{1}+x_{2})(N-(x_{1}+x_{2}))(N-x_{2})y^{2}(N-y)^{2}}{N^{4}(x_{1}+d)^{2}(x_{2}+d)^{2}(x_{1}+x_{2}+2d)^{2}}$
(2.4)

with $d$ being the graph distance from $(x_{1},x_{2})$ to $(y,0)$. Here
$a_{n}\approx b_{n}$ means there exist positive $c$ and $c^{\prime}$
(universal) such that

$c\,a_{n}\leq b_{n}\leq c^{\prime}a_{n}$

for all $n$. The constants implicit in (2.4) are uniform for all $x,y$.

Let us illustrate this result by proving the $1/N^{3}$ result claimed in
Section 1.

######  Theorem 2.5.

$P_{1,1,N-2}(\text{\rm player 3 goes broke first})\approx\frac{1}{N^{3}}.$

###### Proof.

To get things into the notation of Theorem 2.4, take $x_{1}=1$, $x_{2}=N-2$.
Then, for $0<y<N$,

$P(\bm{x},(y,0))=P(\text{player 2 goes broke first at which time player 1 has
}y).$

For any $y$, $d\approx N$ so the denominator in (2.4) is $\approx N^{10}$. The
numerator is $\approx N^{2}y^{2}(N-y)^{2}$. Thus,

$P(\bm{x},(y,0))\approx\frac{y^{2}(N-y)^{2}}{N^{8}}=\frac{1}{N^{4}}\bigg{(}\frac{y}{N}\bigg{)}^{2}\bigg{(}1-\frac{y}{N}\bigg{)}^{2}.$

Summing in $y$ and reversing the roles of players 2 and 3,

$\displaystyle P_{1,1,N-2}(\text{player 3 goes broke first})$
$\displaystyle\quad{}\approx\frac{1}{N^{3}}\,\frac{1}{N}\sum_{y=1}^{N-1}\bigg{(}\frac{y}{N}\bigg{)}^{2}\bigg{(}1-\frac{y}{N}\bigg{)}^{2}\sim\frac{B(3,3)}{N^{3}},$
(2.5)

where $B$ denotes the beta function. ∎

######  Corollary 2.6.

$P_{1,1,N-2}(\text{\rm player 3 goes broke second})\sim\frac{2}{N}.$

###### Proof.

The desired probability is

$\displaystyle{}1-P_{1,1,N-2}(\text{\rm player 3 wins
all})-P_{1,1,N-2}(\text{\rm player 3 goes broke first})$
$\displaystyle\qquad\quad{}=1-\frac{N-2}{N}-O(1/N^{3})=\frac{2}{N}-O(1/N^{3})$

by (2.3) and Theorem 2.5, and the result follows. ∎

######  Remarks.

  1. (1)

The constant $B(3,3)=1/30$ in (2.6) is meaningless because of all the cruder
approximations being used. Now

$P_{1,1,N-2}(\text{player 3 goes broke
first})=P_{1,1,N-2}(312)+P_{1,1,N-2}(321),$

and because of symmetry,

$P_{1,1,N-2}(312)=P_{1,1,N-2}(321),$

so Theorem 2.5 implies

$P_{1,1,N-2}(312)=P_{1,1,N-2}(321)\approx\frac{1}{N^{3}}.$

  2. (2)

A similar calculation shows, for $1\leq i<N/2$,

$P_{i,i,N-2i}(\text{player 3 goes broke first})\approx\frac{i^{3}}{N^{3}},$

uniformly in $i$. This is consistent with the scaling conjecture of Section 4.

  3. (3)

The asymptotics above may be supplemented by the exact computing of
Subsections 2.2 and 2.3. Table 4 gives $P_{1,1,N-2}(321)$ for $N=50$, 100,
150, 200, 250, 300 as well as these values multiplied by $N^{3}$.

Table 4: The exact values of $P_{1,1,N-2}(321)$, rounded to 15 significant digits, suggesting that this quantity is asymptotic to $c/N^{3}$ for $c\doteq 4.5597945$. $N$ |  000$P_{1,1,N-2}(321)$ | $N^{3}P_{1,1,N-2}(321)$
---|---|---
050 | 0.0000364783779008280 | 4.55979723760
100 | 0.00000455979467170448 | 4.55979467170
150 | 0.00000135105023226911 | 4.55979453391
200 | 0.000000569974313837992 | 4.55979451070
250 | 0.000000291826848279112 | 4.55979450436
300 | 0.000000168881277854908 | 4.55979450208
  4. (4)

In unpublished work, Sangchul Lee has used Ferguson’s (1995) Brownian motion
approximation to the discrete gambler’s ruin problem to derive an analytical
closed form expression for the constant $c\doteq 4.5597945$ in Table 4. He
shows

$c=\frac{\sqrt{\pi}}{3\sqrt{3}}\bigg{(}\frac{\Gamma(1/3)}{\Gamma(5/6)}\bigg{)}^{3}\doteq
4.55979449996,$

in remarkable agreement to the numbers in Table 4. The validity of the
Brownian motion approximation has not been rigorously established to this
degree. See Denisov and Wachtel (2015).

  5. (5)

Theorem 2.4 allows proof of similar asymptotics for other values of $A$, $B$,
and $C$. For example, we have proved the following:

     * •

For fixed $A,B\geq 1$ and $C_{N}:=N-A-B$,

$P_{A,B,C_{N}}(321)\approx P_{A,B,C_{N}}(312)\approx\frac{1}{N^{3}}.$

     * •

For $A=1$, $B_{N}=\lfloor\sqrt{N}\rfloor$, and $C_{N}:=N-1-B_{N}$,

$P_{1,B_{N},C_{N}}(\text{player 3 goes broke first})\approx\frac{1}{N^{2}}.$

Exact computations suggest that in the first case $N^{3}P_{A,B,C_{N}}(321)$
and in the second case $N^{2}P_{A,B_{N},C_{N}}(\text{player 3 goes broke
first})$ rapidly approach limits.

  6. (6)

Similarly, $P_{1,B_{N},C_{N}}(321)\approx P_{1,B_{N},C_{N}}(312)\approx
1/N^{2}$. This is a bit surprising. Of course, the event that the player with
the big stack is eliminated first is a rare event but then the advantage that
player 2 had over player 1 disappears. Indeed, numerical computations show
that, for this case, given player 3 is eliminated first, the conditional
gambler’s ruin probability that 1 is eliminated second is 1/2 to remarkable
approximation. For example, $P_{1,14,185}(321)\doteq 0.000059822$ and
$P_{1,14,185}(312)\doteq 0.000059872$.

  7. (7)

The results of Diaconis, Houston-Edwards, and Saloff-Coste (2020) were not
intended to give good numerics. We hope that comparing them to data will allow
better choices of omitted constants as in item (3) above. The following
results are examples.

  8. (8)

For any $N$,

$\displaystyle P_{1,1,N-2}(123)=P_{1,1,N-2}(213)$
$\displaystyle=\frac{1}{2}P_{1,1,N-2}(\text{player 3 wins all})$
$\displaystyle=\frac{1}{2}\,\frac{N-2}{N}=\frac{1}{2}\bigg{(}1-\frac{2}{N}\bigg{)}.$

When $N=200$, the right side is 0.495. Using Theorem 2.4,

$P_{1,1,N-2}(123)\approx\frac{1}{2}\sum_{y=1}^{N-1}\frac{(1-y/N)^{3}}{y^{4}}=\frac{\zeta(4)}{2}(1+o(1))\doteq
0.5412.$

Similarly, if $1\leq i<N/2$,

$P_{i,i,N-2i}(123)=P_{i,i,N-2i}(213)=\frac{1}{2}\,\frac{N-2i}{N}=\frac{1}{2}\bigg{(}1-\frac{2i}{N}\bigg{)},$

confirming the scaling conjecture in this case. So perhaps not all hope is
lost for using Theorem 2.4.

  9. (9)

Similarly, taking $x_{1}=x_{2}=1$,

$\displaystyle P_{1,1,N-2}(132)$
$\displaystyle=P_{1,1,N-2}(231)\approx\frac{1}{2}\sum_{y=1}^{N-1}\frac{(1-y/N)^{2}}{y^{4}}\,\frac{y}{N}$
$\displaystyle=\frac{1}{2N}\sum_{y=1}^{N-1}\frac{(1-y/N)^{2}}{y^{3}}\sim\frac{1}{2N}\,\zeta(3).$

By Corollary 2.6, these probabilities are asymptotic to $1/N$, so this
estimate is off by a factor of $\zeta(3)/2\doteq 0.6010$.

###  2.7 The independent chip model (ICM)

There are a variety of reasons for wanting to compute the chances of the
various elimination orders. The most classical one, “The Problem of Points,”
has to do with splitting the capital in a $k$-player game when the game must
be called off early. This is one of the problems that got Fermat and Pascal in
correspondence — the start of modern probability theory. In tournament poker,
we have seen three players decide to “settle,” dividing the final prize money
in proportion to their current chip totals. (As we will see, this is not the
right way to do it.) Of course, calculating expectations for various decisions
(mentioned earlier) is a key application.

The independent chip model (ICM), a popular scheme, originated in a 1986
article by Mason Malmuth in Poker Player Newspaper, which was reprinted in
Malmuth (1987, 2004). Although the name came later, the concept was used to
argue that rebuying in a percentage-payback poker tournament is mathematically
correct, contrary to conventional wisdom at the time. Other implications of
the ICM for poker tournaments were discussed by Gilbert (2009). See Aguilar
(2016) for its use in “chopping” the prize pool in poker tournaments, using a
poker ICM calculator (ICMizer, 2020).

ICM builds on a solid foundation: In the two-player gambler’s ruin problem for
fair coin-tossing, if player 1 starts with $A$ and player 2 starts with $B$,
the chance that player 1 (respectively, player 2) wins all is $A/(A+B)$
(resp., $B/(A+B)$). Now a heuristic step: Consider three players with initial
capitals $A$, $B$, and $C$. The chance that a given player wins all is
(rigorously) proportional to his initial capital (so the chance that player 1
wins all is $A/N$, where $N:=A+B+C$). The ICM calculation conditions on this,
uses the relative initial capitals of the two nonwinners to calculate the
chance of being second eliminated, and then multiplies. This results in the
chances shown in Table 5 assigned to the six elimination orders.

Table 5: The ICM with three players. $\sigma$ | 123 | 132 | 213 | 231 | 312 | 321
---|---|---|---|---|---|---
$P_{A,B,C}^{\text{ICM}}(\sigma)$ | $\frac{C}{N}\,\frac{B}{A+B}$ | $\frac{B}{N}\,\frac{C}{A+C}$ | $\frac{C}{N}\,\frac{A}{A+B}$ | $\frac{A}{N}\,\frac{C}{B+C}$ | $\frac{B}{N}\,\frac{A}{A+C}$ | $\frac{A}{N}\,\frac{B}{B+C}$

The probabilities for $k\geq 4$ players are determined similarly.

We can now be more explicit about how the prize pool is chopped when the last
three players decide to settle. First, apportioning it in proportion to
current chip totals does not take prize money into account and is
unsupportable. For example, in Example 1.1, the chip leader would get about
$12.696 M, more than he would get by finishing first, and the player in third
place would get about $2.626 M, less than he would get by finishing third. So
let $P(\sigma)$ be the probability of elimination order $\sigma$. Let
$\alpha$. $\beta$, and $\gamma$ be the payouts for first, second, and third
place. Then the expression for the amounts apportioned to players 1, 2, and 3
should be

$\displaystyle(\gamma,\beta,\alpha)P(123)+(\gamma,\alpha,\beta)P(132)+(\beta,\gamma,\alpha)P(213)$
$\displaystyle\qquad{}+(\alpha,\gamma,\beta)P(231)+(\beta,\alpha,\gamma)P(312)+(\alpha,\beta,\gamma)P(321).$

It is standard practice to use $P_{A,B,C}^{\text{ICM}}(\sigma)$ in place of
$P(\sigma)$. Alternatively, one could use
$\bar{P}_{A,B,C}^{\text{GR}}(\sigma)$. Of course, both are approximations.

######  Example 2.7.

Let us return to Example 1.1 with $A=169$, $B=301$, and $C=817$; also
$\alpha=\$10$ M, $\beta=\$6$ M, and $\gamma=\$4$ M. Using the ICM
probabilities from Table 5, we get
$(\$5.325\,\text{M},\$6.287\,\text{M},\$8.388\,\text{M})$, which is consistent
with ICMizer (2020), whereas using the interpolated gambler’s ruin
probabilities from Example 2.3, we get
$(\$5.270\,\text{M},\$6.293\,\text{M},\$8.437\,\text{M})$. The player with
third-largest chip total gets about $54 K more from an ICM chop than from a GR
chop.

######  Remarks.

  1. (1)

ICM is different from gambler’s ruin. Consider $N=6$ and initial capital
$A=1$, $B=2$, and $C=3$. What is the chance the elimination order is 321?
Using the exact calculation in Table 3 and the ICM formula yields

$P_{1,2,3}^{\text{GR}}(321)=\frac{569}{9456}\doteq 0.06017,\qquad
P_{1,2,3}^{\text{ICM}}(321)=\frac{1}{6}\,\frac{2}{5}\doteq 0.06667.$

  2. (2)

The results can be of different orders of magnitude. With starting capitals
$1,1,N-2$,

$P_{1,1,N-2}^{\text{GR}}(321)\approx\frac{1}{N^{3}},\qquad
P_{1,1,N-2}^{\text{ICM}}(321)=\frac{1}{N}\,\frac{1}{N-1}\sim\frac{1}{N^{2}}.$

  3. (3)

Sometimes they agree. With starting capitals $i,i,N-2i$, where $1\leq i<N/2$,

$P_{i,i,N-2i}^{\text{GR}}(123)=P_{i,i,N-2i}^{\text{ICM}}(123)=\frac{N-2i}{N}\,\frac{1}{2}=\frac{1}{2}\bigg{(}1-\frac{2i}{N}\bigg{)}.$

  4. (4)

They are often quite different. In the next section we calculate of the ratios

$P_{A,B,C}^{\text{GR}}(\sigma)/P_{A,B,C}^{\text{ICM}}(\sigma)$

for all $A,B,C\geq 1$ with $A+B+C=300$ and all $\sigma\in S_{3}$. The ratios
vary considerably, ranging from about 0.015 to about 1.15.

  5. (5)

But poker is a complicated game, particularly no limit where the bets can be
arbitrary. The gambler’s ruin model is based on single-unit bets. Why is this
relevant? Some variants of the $\pm 1$ transfer have been studied.

     * •

All in: After two players out of the remaining $k$ are chosen, if they have
$A$ and $B$ respectively, the bet size is $\min(A,B)$. The player with the
smaller chip count is eliminated or doubles up.

     * •

Occasionally all in: This is a compromise between unit bets and all-in bets.
After two players out of the remaining $k$ are chosen, if they have $A$ and
$B$ respectively, the bet size is chosen uniformly at random from
$\\{1,2,\ldots,\min(A,B)\\}$.

     * •

Compulsive gambler (Aldous, Lanoue, and Salez, 2015): After two players out of
the remaining $k$ are chosen, one gets the other’s money with probabilities
given by the two-player gambler’s ruin formula. That is, if the respective
amounts are $A$ and $B$, the player with $A$ wins (and then has $A+B$) with
probability $A/(A+B)$, or loses (and is eliminated) with probability
$B/(A+B)$.

A fascinating effort at finding an optimal strategy for $k$-player gambler’s
ruin with all-in betting is in Ganzfried and Sandholm (2008). Interestingly,
they use ICM as a starting evaluation of the value function and then sharpen
this using fictitious play and value iteration.

These variants will (almost surely) result in different elimination order
probabilities. The ICM assignment is different yet again. Thus, there are many
distinct models. It would be worthwhile to look at some of the available data
for tournament poker and compare. We wouldn’t be surprised if all these models
are inadequate.

The next section salvages something from these differences, using the ratios
and regression to give a useful approximation to the gambler’s ruin
probabilities.

To finish this section, let us note that ICM is well studied as the
Plackett–Luce model. This is a model allowing non-uniform distributions on
$S_{k}$, the set of permutations of $k$ distinct items, labeled
$1,2,\ldots,k$. Each item $i$ is assigned a weight $w_{i}>0$ with
$w_{1}+w_{2}+\cdots+w_{k}=w$. Now imagine these weights placed in an urn and
the weights removed sequentially, each time with probability proportional to
its size among the remaining weights. Thus,

$P(\sigma):=\frac{w_{\sigma(1)}}{w}\,\frac{w_{\sigma(2)}}{w-w_{\sigma(1)}}\,\frac{w_{\sigma(3)}}{w-w_{\sigma(1)}-w_{\sigma(2)}}\cdots.$

The model was introduced in perception psychology by R. Duncan Luce (1959,
1977). It has a variety of derivations: via the elimination by aspect axiom;
as the distribution of the order statistics of independent exponential
variables (the $i$th having mean $w_{i}$); and as the stationary distribution
of the Tsetlin library. See Diaconis (1988, pp. 174–175) for further
references.

Later reinventions of the model were published by Harville (1973) and Plackett
(1975), both of whom applied it to horse racing, and it seems to have a life
of its own for this application (Stern, 2008). There is good available code
for fitting this model to data (Turner et al., 2017) and many applications.
Although the model is referred to in the literature as the Plackett–Luce
model, perhaps Luce–Harville–Plackett–Malmuth would be chronologically more
correct.

Finally, we note that enumerative combinatorics for the Plackett–Luce model
can be interesting and challenging; What is the approximate distribution of
the number of fixed points or cycles, and how does it depend on the weights?

##  3 ICM and regression for gambler’s ruin

Here we show how to use the easy-to-compute ICM probabilities
$P_{A,B,C}^{\text{ICM}}(\sigma)$ to get surprisingly good approximations to
the gambler’s ruin probabilities $P_{A,B.C}^{\text{GR}}(\sigma)$. Throughout,
we work with $k=3$ players, fair coin flips, and $\pm 1$ transfers at each
stage.

We can base the analysis on the $N=300$ data, which gives $P_{A,B,C}(123)$ (in
double precision) for all $A,B,C\geq 1$ with $A+B+C=300$. There are
$\binom{300-1}{2}=44{,}551$ such points. Notice that, for
$\sigma=\sigma(1)\,\sigma(2)\,\sigma(3)$,

$P_{A_{1},A_{2},A_{3}}(\sigma)=P_{A_{\sigma(1)},A_{\sigma(2)},A_{\sigma(3)}}(123),$

so there is no loss of information by restricting to $\sigma=123$.

As efficient as this data set is, there is still some redundancy in the data,
as has already been alluded to in (2.3) and elsewhere, namely

$\displaystyle P_{A,B,C}(123)+P_{A,B,C}(213)$ $\displaystyle=\frac{C}{A+B+C},$
$\displaystyle P_{A,B,C}(132)+P_{A,B,C}(312)$ $\displaystyle=\frac{B}{A+B+C},$
(3.1) $\displaystyle P_{A,B,C}(231)+P_{A,B,C}(321)$
$\displaystyle=\frac{A}{A+B+C},$

a consequence of the optional stopping theorem. The result is that it suffices
to consider only one of the two probabilities in each row of (3).
Incidentally, the equations in (3) hold trivially with superscript ICM.

We begin by evaluating, for $N=300$, the ratios

$R_{123}(A,B,C):=P_{A,B,C}^{\text{GR}}(123)/P_{A,B,C}^{\text{ICM}}(123)$ (3.2)

for all $A,B,C\geq 1$ with $A+B+C=N$. As already noted, there are $44{,}551$
such ratios and all of them belong to $(0.015,1.15)$. The function $R_{123}$
is plotted in Figure 4.

Figure 4: A plot of $R_{123}$ defined in (3.2) as a function of $(A,B)$ when
$N=300$. (The domain of $R_{123}$ is restricted to $A,B\geq 1$ with $A+B\leq
N-1$.). The second figure is a rotation of the first that reveals the
singularity near $(1,1)$.

Notice that $R_{123}$ appears smooth as a function of $(A,B)$ ($C=N-A-B$),
except for a singularity near $(1,1)$. We can mitigate the effect of the
singularity by considering $R_{\sigma}$ over $1\leq A\leq B\leq C$ with
$A+B+C=N$ for $\sigma=213$, 312, and 321. (The number of such triples
$(A,B,C)$ is $N^{2}/12$ if $N$ is divisible by 6, hence 7500 if $N=300$.) In
each case we fit a sextic polynomial in

$x:=\frac{A}{N}\quad\text{and}\quad y:=\frac{B}{N}$

to the function $R_{\sigma}$. A quadratic approximation does not give very
good results, while a quartic approximation is quite good, and a sextic is
even better. At the same time, the higher the degree, the closer the design
matrix is to being less than full rank. An octic approximation results in some
disturbingly large estimated regression coefficients, so we have settled on a
sextic polynomial approximation. Thus, we want to approximate $R_{\sigma}$ by
the polynomial with 28 terms

$p_{\sigma}(x,y):=\sum_{i,j\geq 0,\,i+j\leq 6}\beta_{ij}x^{i}y^{j}.$

Let $\bm{Y}$ be the column vector of values of $R_{321}$ (with $N=300$),
indexed by the vectors $(A,B,C)$ (with $1\leq A\leq B\leq C$ and $A+B+C=N$)
ordered lexicographically, let $\bm{X}$ be the matrix whose rows are indexed
as the entries of $\bm{Y}$, and with row $(A,B,C)$ containing $1$, $x$, $y$,
$x^{2}$, $xy$, $y^{2}$, $x^{3}$, $x^{2}y$, …, $y^{6}$, where $x=A/N$ and
$y=B/N$. Note that $\bm{Y}$ has length 7500 and $\bm{X}$ is 7500 by 28. To
quantify the claim that $\bm{X}^{\prime}\bm{X}$ becomes closer to being
singular as the degree of the approximating polynomial increases, we note
that, with $N=300$, $\det(\bm{X}^{\prime}\bm{X})$ is $1.68\times 10^{6}$ for
quadratic approximation, $3.90\times 10^{-29}$ for quartic, $1.14\times
10^{-136}$ for sextic, and $1.10\times 10^{-415}$ for octic.

The estimated regression coefficients are

$\hat{\bm{\beta}}=(\bm{X}^{\prime}\bm{X})^{-1}\bm{X}^{\prime}\bm{Y},$

and the values of the fitted polynomial $\hat{p}_{321}$ are the entries of
$\bm{X}\hat{\bm{\beta}}$. Table 6 lists the estimated regression coefficients,
and additional detail is given in the supplementary materials (Section 6).

This gives the approximation

$\hat{P}_{A,B,C}^{\text{GR}}(321):=P_{A,B,C}^{\text{ICM}}(321)\;\hat{p}_{321}\bigg{(}\frac{A}{N},\frac{B}{N}\bigg{)}=\frac{C}{N}\,\frac{B}{A+B}\;\hat{p}_{321}\bigg{(}\frac{A}{N},\frac{B}{N}\bigg{)},$
(3.3)

and the cases $\sigma=312$ and $\sigma=213$ are treated in the same way. The
derivation assumed $N=300$ throughout. We did the same computation for
$N=200$, and the estimated regression coefficients did not change much,
indicating stability. We expect that the approximation to be reasonable for
other (perhaps much larger) values of $N$. That is, for general $N$ use the
approximation (3.3) in which the function $\hat{p}_{321}$ is determined by the
coefficients in Table 6 computed from the $N=300$ data. We investigate this in
two examples below.

######  Example 3.1.

Table 7 compares exact values of $P_{A,B,C}(\sigma)$ with its interpolation
approximation $\bar{P}_{A,B,C}(\sigma)$ and its regression-corrected ICM
$\hat{P}_{A,B,C}(\sigma)$. In the two examples, which are representative, we
find that, for $\sigma=321$ and $\sigma=312$ (and their “complements”
$\sigma=231$ and $\sigma=132$), the regression approximation is often accurate
to six significant digits (except near the boundary of $\mathscr{X}$). But
with $\sigma=213$ (and $\sigma=123$) the regression approximation is not as
good, perhaps only three or four significant digits. In the latter case, we
see from Table 6 that the estimated regression coefficients are substantially
larger, which is indicative of a poorer fit. On the other hand, the
interpolation approximation is typically accurate to four or five decimal
places.

Table 6: The estimated regression coefficients in fitting a sextic polynomial in $x:=A/N$ and $y:=B/N$ to $P_{A,B,C}^{\text{GR}}(\sigma)/P_{A,B,C}^{\text{ICM}}(\sigma)$, when $1\leq A\leq B\leq C$ and $A+B+C=N$. Here $N=300$. | $\sigma=321$ | $\sigma=312$ | $\sigma=213$
---|---|---|---
$\hat{\beta}_{00}$ | $-0.00000716459$ | $-0.00000434510$ |  $-$0000.951694
$\hat{\beta}_{10}$ |  $-$2.27836000 |  $-$02.2797800 |  $-$0007.072670
$\hat{\beta}_{01}$ |  $-$2.28004000 |  $-$02.2802800 |  000$-3.74069$0
$\hat{\beta}_{20}$ |  $-2.25895$000 |  $-$00.0295644 |  00$-85.5467$00
$\hat{\beta}_{11}$ |  $-2.24587$000 |  0$-2.30603$00 |  00$-23.1325$00
$\hat{\beta}_{02}$ | $-0.00740617$ |  0$-2.28407$00 |  $-$0037.761200
$\hat{\beta}_{30}$ |  $-$0.07930100 |  0$-0.618044$0 |  $-$0336.603000
$\hat{\beta}_{21}$ |  $-0.581954$00 |  $-$00.2854840 |  $-$0646.261000.
$\hat{\beta}_{12}$ |  $-0.191389$00 |  $-$00.2416720 |  0$-111.109$000
$\hat{\beta}_{03}$ |  $-$0.06308140 |  $-$00.0171583 |  0$-197.597$000
$\hat{\beta}_{40}$ |  $-$1.48069000 |  $-$00.5334920 |  0$-557.212$000
$\hat{\beta}_{31}$ |  $-$7.41061000 |  0$-3.71135$00 |  $-2327.47$0000
$\hat{\beta}_{22}$ |  $-$3.41508000 |  0$-4.35883$00 |  $-1723.69$0000
$\hat{\beta}_{13}$ |  $-5.89118$000 |  $-$05.7938200 |  $-$0874.263000
$\hat{\beta}_{04}$ |  $-2.67189$000 |  $-$02.4999700 |  $-$0540.005000
$\hat{\beta}_{50}$ |  $-0.55614$00 |  0$-4.34151$00 |  $-$0401.498000
$\hat{\beta}_{41}$ |  $-3.73983$000 |  $-14.9318$000 |  $-$2829.270000
$\hat{\beta}_{32}$ |  $-5.73258$000 |  $-$14.4755000 |  $-$5167.690000
$\hat{\beta}_{23}$ |  $-$$0.0461851$00 |  $-$13.5284000 |  $-$1655.900000
$\hat{\beta}_{14}$ |  $-$1.48366000 |  0$-7.28960$00 |  $-1925.03$0000
$\hat{\beta}_{05}$ |  $-0.274686$00 |  0$-2.71321$00 |  0$-746.323$000
$\hat{\beta}_{60}$ |  $-0.0378116$0 |  $-$02.4837200 |  0$-100.681$000
$\hat{\beta}_{51}$ |  $-1.05892$000 |  $-$21.5551000 |  $-1101.29$0000
$\hat{\beta}_{42}$ |  $-4.84129$000 |  $-$06.4850200 |  $-3408.10$0000
$\hat{\beta}_{33}$ |  $-5.77799$000 |  $-35.4065$000 |  $-3643.9$0000
$\hat{\beta}_{24}$ |  $-$1.08693000 |  $-12.3409$000 |  0$-213.799$000
$\hat{\beta}_{15}$ |  $-$5.19094000 |  $-$05.4446600 |  $-$1420.660000
$\hat{\beta}_{06}$ |  $-$1.88817000 |  $-$01.0799700 |  $-$0410.303000

######  Example 3.2 (Example 2.3 continued).

Recall that, in Example 2.3, we estimated $P_{A,B,C}(\sigma)$ when $A=169$,
$B=301$, and $C=817$. We did so using linear interpolation based on the
$N=300$ data. Results are restated in Table 8 (row (b)), so that we can
compare them with the ICM (row (a)) and the regression approximation (row
(c)), which used (3.3) (and $\hat{p}_{312}$ and $\hat{p}_{213}$) with $A$,
$B$, and $C$ as above and $N=1287$.

We find that linear interpolation and linear regression match to four or more
decimal places, Monte Carlo to three, and ICM to one or two.

Table 7: Two examples comparing the exact value of $P_{A,B,C}(\sigma)$ (to six significant digits) with its interpolation approximation $\bar{P}_{A,B,C}(\sigma)$ and its regression approximation $\hat{P}_{A,B,C}(\sigma)$. 000$\sigma$ | 123 | 132 | 213 | 231 | 312 | 321
---|---|---|---|---|---|---
$P_{23,45,67}(\sigma)$ | 0.342769 | 0.264802 | 0.153527 | 0.108430 | 0.0685310 | 0.0619406
$\bar{P}_{23,45,67}(\sigma)$ | 0.342763 | 0.264801 | 0.153533 | 0.108430 | 0.0685326 | 0.0619404
$\hat{P}_{23,45,67}(\sigma)$ | 0.342744 | 0.264802 | 0.153552 | 0.108430 | 0.0685311 | 0.0619404
$P_{10,40,90}(\sigma)$ | 0.532690 | 0.268542 | 0.110167 | 0.0553389 | 0.0171721 | 0.0160897
$\bar{P}_{10,40,90}(\sigma)$ | 0.532702 | 0.268540 | 0.110155 | 0.0553369 | 0.0171744 | 0.0160917
$\hat{P}_{10,40,90}(\sigma)$ | 0.532773 | 0.268542 | 0.110084 | 0.0553389 | 0.0171721 | 0.0160897

Table 8: Approximations to $P_{A,B,C}^{\text{GR}}(\sigma)$ when $A=169$, $B=301$, and $C=817$. Row (a) uses ICM, row (b) uses linear interpolation, row (c) uses linear regression, and row (d) uses Monte Carlo. | $\sigma$ | 123 | 132 | 213 | 231 | 312 | 321
---|---|---|---|---|---|---|---
(a) | $P_{A,B,C}^{\text{ICM}}(\sigma)$ | 0.406548 | 0.193791 | 0.228261 | 0.095960 | 0.040086 | 0.035354
| rounded | 0.4065 | 0.1938 | 0.2283 | 0.0960 | 0.0401 | 0.0354
(b) | $\bar{P}_{A,B,C}^{\text{GR}}(\sigma)$ | 0.419603 | 0.207878 | 0.215207 | 0.106174 | 0.025999 | 0.025139
| rounded | 0.4196 | 0.2079 | 0.2152 | 0.1062 | 0.0260 | 0.0251
(c) | $\hat{P}_{A,B,C}^{\text{GR}}(\sigma)$ | 0.419633 | 0.207879 | 0.215177 | 0.106174 | 0.025998 | 0.025139
| rounded | 0.4196 | 0.2079 | 0.2152 | 0.1062 | 0.0260 | 0.0251
(d) | $\widehat{P}_{A,B,C}^{\text{GR}}(\sigma)$ | 0.419345 | 0.207492 | 0.215650 | 0.106286 | 0.026120 | 0.025107
| rounded | 0.4193 | 0.2075 | 0.2157 | 0.1063 | 0.0261 | 0.0251

##  4 A conjecture and more than three players

This section treats two further topics, the scaling conjecture and $k\geq 4$
players (in particular, $k=4$).

###  4.1 Scaling conjecture

The scaling conjecture says, for all $A,B,C\geq 1$, $\sigma\in S_{3}$, and
$n\geq 2$,

$P_{nA,nB,nC}(\sigma)\doteq P_{A,B,C}(\sigma).$ (4.1)

As noted in Section 1, this is closely related to the result, provable as a
consequence of Donsker’s theorem, that $\lim_{n\to\infty}P_{nA,nB,nC}(\sigma)$
exists and can be expressed in terms of standard two-dimensional Brownian
motion.

To formulate such a theorem, we adopt the setup used by Ferguson (1995). Let
$\Delta$ be the equilateral triangle with vertices $(-1,0)$, $(1,0)$, and
$(0,\sqrt{3})$, and let $V_{3}$ be the edge that lies on the $x$-axis. Let
$A$, $B$, and $C$ be positive integers and $N:=A+B+C$. Then the barycentric
coordinates $(A/N,B/N,C/N)$ correspond to the initial state
$\bm{x}:=((B-A)/N,\sqrt{3}\,C/N)$.

######  Theorem 4.1.

Let $\\{\bm{B}(t),\;t\geq 0\\}$ be standard two-dimensional Brownian motion,
and let $T_{1}$ be the exit time of $\bm{x}+\bm{B}$ from $\Delta$. Then

$\lim_{n\to\infty}[P_{nA,nB,nC}(321)+P_{nA,nB,nC}(312)]=P(\bm{x}+\bm{B}(T_{1})\in
V_{3}).$ (4.2)

Furthermore,

$\lim_{n\to\infty}P_{nA,nB,nC}(321)=E\bigg{(}\frac{|\bm{x}+\bm{B}(T_{1})-(1,0)|}{2};\;\bm{x}+\bm{B}(T_{1})\in
V_{3}\bigg{)}.$ (4.3)

The integrand in (4.3) is the proportion of the length of the edge $V_{3}$
that lies between the exit position $\bm{x}+\bm{B}(T_{1})$ and the corner
$(1,0)$ corresponding to player 2 winning all. This amounts to applying the
two-player gambler’s ruin formula to the exit position.

Ferguson (1995) (see also Bruss, Louchard, and Turner, 2003) and Hajek (1987)
used conformal mapping to give complicated expressions for the right sides of
(4.2) and (4.3), respectively. It remains to massage their formulas into
computable form. In a special case this can easily be done for Ferguson’s
formula. If the initial state $(A,B,C)$ satisfies $A=B$, or equivalently, if
the initial state in barycentric coordinates has the form $(a,a,1-2a)$, then
the Mathematica function defined in Figure 5 gives the exit probability in
(4.2).

Figure 5: Mathematica code for the right side of (4.2) when the initial state,
in barycentric coordinates, is $(a,a,1-2a)$.

Ferguson (1995) showed that standard two-dimensional Brownian motion starting
at $(0,\sqrt{3}/2)$ exits the equilateral triangle with vertices $(-1,0)$,
$(1,0)$, and $(0,\sqrt{3})$ along the $x$-axis with probability about 0.1421.
Now $(0,\sqrt{3}/2)$ has barycentric coordinates
$(\frac{1}{4},\frac{1}{4},\frac{1}{2})$, so Figure 5 shows that Ferguson’s
probability, evaluated to 12 decimal places, is 0.142154976126. On the other
hand, the corresponding gambler’s ruin probability with $N=300$ is

$\displaystyle P_{75,75,150}(\text{player 3 goes broke first})$
$\displaystyle\qquad\qquad{}=P_{75,75,150}(312)+P_{75,75,150}(321)\doteq
0.142154976161,$ (4.4)

which we have computed to 18 decimal places, the first ten of which agree with
Ferguson’s number!

In support of the scaling conjecture we present evidence in Table 9. We have
looked at many other examples. Scaling to good approximation seems to hold
always.

Table 9: $P_{A,B,C}(\sigma)$ for $(A,B,C)=(2n,3n,5n)$ ($1\leq n\leq 15$ and $n=20,25,30$), rounded to 12 significant digits, in support of the scaling conjecture. Here we include only three choices of $\sigma$. Results for the others can be deduced from (3). $A,B,C$ | $\sigma=213$ | $\sigma=312$ | $\sigma=321$
---|---|---|---
$2,3,5$ | 0.190419015064 | 0.0704242611225 | 0.0662121426098
$4,6,10$ | 0.190374670083 | 0.0704067672263 | 0.0662043067857
$6,9,15$ | 0.190371967724 | 0.0704057817695 | 0.0662038677034
$8,12,20$ | 0.190371502992 | 0.0704056143412 | 0.0662037932082
$10,15,25$ | 0.190371375036 | 0.0704055684270 | 0.0662037727906
$12,18,30$ | 0.190371328913 | 0.0704055519070 | 0.0662037654463
$14,21,35$ | 0.190371309103 | 0.0704055448186 | 0.0662037622955
$16,24,40$ | 0.190371299477 | 0.0704055413763 | 0.0662037607656
$18,27,45$ | 0.190371294349 | 0.0704055395436 | 0.0662037599511
$20,30,50$ | 0.190371291418 | 0.0704055384960 | 0.0662037594855
$22,33,55$ | 0.190371289645 | 0.0704055378624 | 0.0662037592040
$24,36,60$ | 0.190371288521 | 0.0704055374610 | 0.0662037590256
$26,39,65$ | 0.190371287781 | 0.0704055371968 | 0.0662037589082
$28,42,70$ | 0.190371287279 | 0.0704055370172 | 0.0662037588284
$30,45,75$ | 0.190371286927 | 0.0704055368917 | 0.0662037587726
$40,60,100$ | 0.190371286171 | 0.0704055366216 | 0.0662037586526
$50,75,125$ | 0.190371285964 | 0.0704055365478 | 0.0662037586198
$60,90,150$ | 0.190371285890 | 0.0704055365213 | 0.0662037586080

A second piece of evidence comes from

$P_{i,i,N-2i}(123)=P_{i,i,N-2i}(213)=\frac{1}{2}\bigg{(}1-\frac{2i}{N}\bigg{)},\qquad
1\leq i<N/2.$ (4.5)

These are exactly invariant under scaling. Indeed, they match the ICM.

A third piece of evidence comes from the Brownian motion approximation of the
random walk. As we have already seen for $k=3$, the gambler’s ruin walk
converges to Brownian motion on the $k$-simplex (Denisov and Wachtel, 2015).
It follows that the first hitting probabilities converge to those of Brownian
motion. Finally, the Brownian motion extinction probabilities are scale
invariant via properties of Brownian motion.

A fourth piece of evidence comes from the asymptotic approximation (2.4)
above. This is (approximately) scale invariant.

The rapid convergence of rescaled probabilities (as seen in Table 9) is
surprising. Theorem 4.1 shows that these approach limits expressible in terms
of standard two-dimensional Brownian motion. We might denote the limit of
$P_{nA,nB,nC}(\sigma)$ as $n\to\infty$ by $P_{A,B,C}^{\text{BM}}(\sigma)$,
where the superscript refers to Brownian motion. For example, if $\sigma=321$,
this limit is given by (4.3). Usually, Gaussian approximation of features of
random walk converge at rate $1/\sqrt{N}$. The numerics would be explained by
the following conjecture, which may be regarded as a more precise version of
the scaling conjecture (4.1).

######  Conjecture 4.2.

$(a)$ For each $A,B,C\geq 1$, $\sigma\in S_{3}$, and $n\geq 2$,

$|P_{nA,nB,nC}(\sigma)-P_{A,B,C}(\sigma)|<0.0004.$

$(b)$ For each $A,B,C\geq 1$ and $\sigma\in S_{3}$, let $N:=A+B+C$. Then

$|P_{nA,nB,nC}(\sigma)-P_{A,B,C}^{{\rm
BM}}(\sigma)|=O\bigg{(}\frac{1}{(nN)^{4}}\bigg{)}\quad\text{as }n\to\infty.$

In the case of (a), we have found differences as large as 0.000383. As for
(b), the ten-digit match seen in (4.1) is consistent with this because
$1/(300)^{4}\doteq 1.235\times 10^{-10}$.

In practical problems scale invariance and smoothness (so fine details don’t
matter much) can reduce things to “manageable numbers” within the range of
computer calculation.

###  4.2 Gambler’s ruin with more than three players

The questions above make sense for $k$ players with initial capitals
$A_{1},A_{2},\ldots,A_{k}$. The exact calculations of Subsection 2.2 are
(potentially) available. We have carried them out to give exact results for
$k=4$ and $N:=A_{1}+A_{2}+A_{3}+A_{4}$ as large as 100. The results for
$N=100$ are in the supplementary materials (Section 6). By analogy with (4.5),

$P_{i,i,i,N-3i}(1234)=\frac{1}{6}\bigg{(}1-\frac{3i}{N}\bigg{)},\qquad 1\leq
i<N/3.$

The scaling conjecture for $k=4$, either in the form

$P_{A^{\prime},B^{\prime},C^{\prime},D^{\prime}}(\sigma)\doteq
P_{A,B,C,D}(\sigma)\quad\text{whenever}\quad\frac{A^{\prime}}{A}=\frac{B^{\prime}}{B}=\frac{C^{\prime}}{C}=\frac{D^{\prime}}{D},$

or in the equivalent form

$P_{nA,nB,nCnD}(\sigma)\doteq P_{A,B,C,D}(\sigma),\qquad n\geq 2,$

seems to hold. Here $A,B,C,D\geq 1$ and $\sigma\in S_{4}$ are arbitrary. Table
11 gives a few data points. These numbers are consistent with those of Marfil
and David (2020). Notice that convergence is slower for four players than for
three.

The ICM formula is available for all $k$. Preliminary investigations
(including Table 13) suggest it is just as unreliable as an approximation to
$P_{A_{1},\ldots,A_{k}}(\sigma)$ as it is when $k=3$. We have tried
interpolation (Subsection 4.3) but not yet regression. Plots such as Figure 4
are not feasible when $k=4$.

One final point: The $\text{constant}/N^{3}$ results described above for $k=3$
should not stir false hope of similar results for $k=4$. There are reasons to
expect that

$P_{1,1,1,N-3}(4321)\sim\frac{\text{constant}}{N^{\kappa}}$

with $\kappa$ an irrational number. This (heuristically) follows from the
connection between gambler’s ruin and the “cops and robbers” problem. See
Ratzkin and Treibergs (2009). Table 10 gives ten data points, which suggest
$\kappa=5.72\cdots$.

Table 10: $P_{1,1,1,N-3}(4321)$ for $N=10,20,\ldots,100$. $N$ | $P_{1,1,1,N-3}(4321)$ |  | $N$ | $P_{1,1,1,N-3}(4321)$
---|---|---|---|---
10 | $2.61956573\times 10^{-4}$ |  |  060 | $9.43556904\times 10^{-9}$
20 | $5.03729359\times 10^{-6}$ |  |  070 | $3.90711745\times 10^{-9}$
30 | $4.96691782\times 10^{-7}$ |  |  080 | $1.82032195\times 10^{-9}$
40 | $9.58966829\times 10^{-8}$ |  |  090 | $9.28008330\times 10^{-10}$
50 | $2.67684672\times 10^{-8}$ |  | 100 | $5.07937120\times 10^{-10}$
Table 11: $P_{A,B,C,D}(\sigma)$ for $(A,B,C,D)=(n,2n,3n,4n)$ ($1\leq n\leq 10$) and four choices of $\sigma\in S_{4}$, rounded to nine decimal places, in support of the scaling conjecture. Notice that the rate of convergence appears to be slower than for the three-player data in Table 9. $A,B,C,D$ | $\sigma=1234$ | $\sigma=2143$ | $\sigma=3412$ | $\sigma=4321$
---|---|---|---|---
$1,2,3,4$ | 0.147755766 | 0.055231830 | 0.012087939 | 0.007499579
$2,4,6,8$ | 0.148462055 | 0.054618468 | 0.012147611 | 0.007459339
$3,6,9,12$ | 0.148582024 | 0.054511807 | 0.012158593 | 0.007452294
$4,8,12,16$ | 0.148621208 | 0.054476628 | 0.012162415 | 0.007449874
$5,10,15,20$ | 0.148638685 | 0.054460859 | 0.012164179 | 0.007448762
$6,12,18,24$ | 0.148647981 | 0.054452450 | 0.012165136 | 0.007448161
$7,14,21,28$ | 0.148653514 | 0.054447436 | 0.012165712 | 0.007447800
$8,16,24,32$ | 0.148657074 | 0.054444206 | 0.012166086 | 0.007447565
$9,18,27,36$ | 0.148659501 | 0.054442002 | 0.012166342 | 0.007447405
$10,20,30,40$ | 0.148661229 | 0.054440432 | 0.012166526 | 0.007447290

###  4.3 Linear interpolation for four players

Just as we could interpolate three-player elimination order probabilities with
arbitrary $N$ from three known such probabilities with $N=300$, we can also
interpolate four-player elimination order probabilities with arbitrary $N$
from four known such probabilities with $N=100$.

Given positive integers $A$, $B$, $C$, and $D$, let $N:=A+B+C+D$ and

$A_{0}:=A\,\frac{100}{N},\quad B_{0}:=B\,\frac{100}{N},\quad
C_{0}:=C\,\frac{100}{N},\quad D_{0}:=D\,\frac{100}{N}.$

Typically, these are not integers. Therefore, consider the eight points

$\displaystyle\bm{v}_{000}$ $\displaystyle:=(\lfloor A_{0}\rfloor,\lfloor
B_{0}\rfloor,\lfloor C_{0}\rfloor,100-\lfloor A_{0}\rfloor-\lfloor
B_{0}\rfloor-\lfloor C_{0}\rfloor),$ $\displaystyle\bm{v}_{001}$
$\displaystyle:=(\lfloor A_{0}\rfloor,\lfloor B_{0}\rfloor,\lceil
C_{0}\rceil,100-\lfloor A_{0}\rfloor-\lfloor B_{0}\rfloor-\lceil
C_{0}\rceil),$ $\displaystyle\bm{v}_{010}$ $\displaystyle:=(\lfloor
A_{0}\rfloor,\lceil B_{0}\rceil,\lfloor C_{0}\rfloor,100-\lfloor
A_{0}\rfloor-\lceil B_{0}\rceil-\lfloor C_{0}\rfloor),$
$\displaystyle\bm{v}_{100}$ $\displaystyle:=(\lceil A_{0}\rceil,\lfloor
B_{0}\rfloor,\lfloor C_{0}\rfloor,100-\lceil A_{0}\rceil-\lfloor
B_{0}\rfloor-\lfloor C_{0}\rfloor),$ $\displaystyle\bm{v}_{011}$
$\displaystyle:=(\lfloor A_{0}\rfloor,\lceil B_{0}\rceil,\lceil
C_{0}\rceil,100-\lfloor A_{0}\rfloor-\lceil B_{0}\rceil-\lceil C_{0}\rceil),$
$\displaystyle\bm{v}_{101}$ $\displaystyle:=(\lceil A_{0}\rceil,\lfloor
B_{0}\rfloor,\lceil C_{0}\rceil,100-\lceil A_{0}\rceil-\lfloor
B_{0}\rfloor-\lceil C_{0}\rceil),$ $\displaystyle\bm{v}_{110}$
$\displaystyle:=(\lceil A_{0}\rceil,\lceil B_{0}\rceil,\lfloor
C_{0}\rfloor,100-\lceil A_{0}\rceil-\lceil B_{0}\rceil-\lfloor C_{0}\rfloor),$
$\displaystyle\bm{v}_{111}$ $\displaystyle:=(\lceil A_{0}\rceil,\lceil
B_{0}\rceil,\lceil C_{0}\rceil,100-\lceil A_{0}\rceil-\lceil
B_{0}\rceil-\lceil C_{0}\rceil),$

and choose four of them for the purpose of linear interpolation, discarding
any whose fourth coordinate is neither $\lfloor D_{0}\rfloor$ nor $\lceil
D_{0}\rceil$. Denote by $\\{a\\}:=a-\lfloor a\rfloor$ the fractional part of
$a$.

If $\\{A_{0}\\}+\\{B_{0}\\}+\\{C_{0}\\}\in(0,1)$, then we choose
$\bm{v}_{000}$, $\bm{v}_{001}$, $\bm{v}_{010}$, and $\bm{v}_{100}$.

If $\\{A_{0}\\}+\\{B_{0}\\}+\\{C_{0}\\}\in(2,3)$, then we choose
$\bm{v}_{011}$, $\bm{v}_{101}$, $\bm{v}_{110}$, and $\bm{v}_{111}$.

If $\\{A_{0}\\}+\\{B_{0}\\}+\\{C_{0}\\}\in(1,2)$, then we choose four of the
six points $\bm{v}_{001}$, $\bm{v}_{010}$, $\bm{v}_{100}$, $\bm{v}_{011}$,
$\bm{v}_{101}$, and $\bm{v}_{110}$ in such a way that the resulting
tetrahedron contains $(A_{0},B_{0},C_{0},D_{0})$ in its interior. The choice
is not unique.

Let us call these four points $(A_{i},B_{i},C_{i},D_{i})$ ($i=1,2,3,4$). We
can estimate $P_{A,B,C,D}(\sigma)$ by linear interpolation from the four
values of $P_{A_{i},B_{i},C_{i},D_{i}}(\sigma)$ ($i=1,2,3,4$). As before, we
represent $(A_{0},B_{0},C_{0},D_{0})$ in barycentric coordinates. The relevant
weights are

$\begin{pmatrix}\lambda_{1}\\\ \lambda_{2}\\\
\lambda_{3}\end{pmatrix}:=\begin{pmatrix}A_{1}-A_{4}&A_{2}-A_{4}&A_{3}-A_{4}\\\
B_{1}-B_{4}&B_{2}-B_{4}&B_{3}-B_{4}\\\
C_{1}-C_{4}&C_{2}-C_{4}&C_{3}-C_{4}\end{pmatrix}^{-1}\begin{pmatrix}A_{0}-A_{4}\\\
B_{0}-B_{4}\\\ C_{0}-C_{4}\end{pmatrix}$

and $\lambda_{4}:=1-\lambda_{1}-\lambda_{2}-\lambda_{3}$, so that

$(A_{0},B_{0},C_{0},D_{0})=\sum_{i=1}^{4}\lambda_{i}(A_{i},B_{i},C_{i},D_{i}),$

and our interpolation estimate is then

$\bar{P}_{A,B,C,D}(\sigma):=\sum_{i=1}^{4}\lambda_{i}P_{A_{i},B_{i},C_{i},D_{i}}(\sigma).$

If one or more of the weights $\lambda_{i}$ is negative, that indicates
$(A_{0},B_{0},C_{0},D_{0})$ lies outside the resulting tetrahedron, and we
must choose the four points differently.

######  Example 4.3.

At the final table of the 2019 World Series of Poker Millionaire Maker Event,
at the time the fifth-place finisher was eliminated, the remaining four
players had chip counts (in units of $100{,}000$, 1/16 of the big blind) equal
to $A=97$, $B=125$, $C=144$, and $D=1839$ (WSOP, 2019b). See Table 12. Thus,
$N=2205$ and $A$, $B$, $C$, and $D$, multiplied by $100/N$, are $A_{0}\doteq
4.40$, $B_{0}\doteq 5.67$, $C_{0}\doteq 6.53$, and $D_{0}\doteq 83.40$. Since
$\\{A_{0}\\}+\\{B_{0}\\}+\\{C_{0}\\}\doteq 1.60$, we must choose four of the
six vertices $\bm{v}_{2}=(4,5,7,84)$, $\bm{v}_{3}=(4,6,6,84)$,
$\bm{v}_{4}=(5,5,6,84)$, $\bm{v}_{5}=(4,6,7,83)$, $\bm{v}_{6}=(5,5,7,83)$, and
$\bm{v}_{7}=(5,6,6,83)$. We choose $\bm{v}_{2}$, $\bm{v}_{3}$, $\bm{v}_{5}$,
and $\bm{v}_{7}$, the four points closest to $(A_{0},B_{0},C_{0},D_{0})$. We
find that

$\lambda_{1}=\frac{146}{441},\quad\lambda_{2}=\frac{31}{441},\quad\lambda_{3}=\frac{88}{441},\quad\lambda_{4}=\frac{176}{441},$

and results are shown in Table 13. For the record, the actual elimination
order turned out to be $\sigma=1243$, the seventh most likely result.

Table 12: The final four in the 2019 World Series of Poker Millionaire Maker Event. The big blind was $1{,}600{,}000$. 0000player | chip count | big blinds | big blinds | actual payoff
---|---|---|---|---
|  | (rounded) |  ${}\times 16$ (exact) |
Vincas Tamasauskas |  00$9{,}700{,}000$ |  006 |  0097 | $\$464{,}375$
Lokesh Garg |  0$12{,}500{,}000$ |  008 |  0125 | $\$619{,}017$
John Gorsuch |  0$14{,}400{,}000$ |  009 |  0144 | $\$1{,}344{,}930$
Kazuki Ikeuchi | $183{,}900{,}000$ | 115 | 1839 | $\$830{,}783$
0000totals | $220{,}500{,}000$ | 138 | 2205 |
Table 13: For $(A,B,C,D)=(97,125,144,1839)$, row (a) gives $P_{A,B,C,D}^{\text{ICM}}(\sigma)$, and row (b) gives the interpolated approximations $\bar{P}_{A,B,C,D}^{\text{GR}}(\sigma)$. Here $\varepsilon=10^{-5}$. | $\sigma=1234$ | $\sigma=1243$ | $\sigma=1324$ | $\sigma=1342$ | $\sigma=1423$ | $\sigma=1432$
---|---|---|---|---|---|---
| $\sigma=2134$ | $\sigma=2143$ | $\sigma=2314$ | $\sigma=2341$ | $\sigma=2413$ | $\sigma=2431$
| $\sigma=3124$ | $\sigma=3142$ | $\sigma=3214$ | $\sigma=3241$ | $\sigma=3412$ | $\sigma=3421$
| $\sigma=4123$ | $\sigma=4132$ | $\sigma=4213$ | $\sigma=4231$ | $\sigma=4312$ | $\sigma=4321$
(a) | 0.184762 | 0.0328106 | 0.170195 | 0.0299478 | 0.00376238 | 0.00372801
| 0.143375 | 0.0254611 | 0.118324 | 0.0205440 | 0.00287798 | 0.00281381
| 0.114645 | 0.0201732 | 0.102712 | 0.0178333 | 0.00245171 | 0.00241914
| 0.000198451 | 0.000196638 | 0.000195621 | 0.00019126 | 0.000191977 | 0.000189427
(b) | 0.193685 | 0.0365869 | 0.177240 | 0.0338414 | 0.00127429 | 0.00127379
| 0.139180 | 0.0264827 | 0.118035 | 0.0228907 | 0.000947236 | 0.000946428
| 0.107017 | 0.0207477 | 0.0988571 | 0.0193277 | 0.000811526 | 0.000811141
|  0.751143$\,\varepsilon$ |  0.750991$\,\varepsilon$ |  0.750703$\,\varepsilon$ |  0.750331$\,\varepsilon$ |  0.750250$\,\varepsilon$ |  0.750030$\,\varepsilon$

##  5 Summary

In Summary, we have discussed six different methods of approximating the
gambler’s ruin probabilities:

  1. 1.

Exact computation by Markov chain methods (Subsection 2.2)

  2. 2.

Arbitrarily precise computation by Jacobi iteration (Subsection 2.3)

  3. 3.

Linear interpolation from exact probabilities (Subsection 2.4)

  4. 4.

Monte Carlo methods (Subsection 2.5)

  5. 5.

Regression on ICM (Section 3)

  6. 6.

Approximation by Brownian motion (Theorem 4.1)

While exact computation using Markov chain methods and arbitrarily precise
computation using Jacobi iteration are feasible for $N:=A+B+C$ not too large,
it seems impossible for $N$ of practical interest. Linear interpolation is our
preferred method, using the nearly exact results for $N=300$. Monte Carlo
allows computation for a single $A,B,C$ of interest and is useful for two- or
three-digit accuracy. Regression analysis is quite accurate but probably needs
an app to to be “real-time useful.” Brownian approximation changes the problem
into one that requires special function calculations and so probably also
needs an app. Finally, the widely used ICM is roughly useful (say for single-
digit accuracy), and it can be “done in your head.”

##  6 Supplementary materials

Supplementary materials include four Mathematica programs, four output files,
and three regression analyses using Mathematica. Here are the details.

  1. 1.

Mathematica program to compute three-player elimination order probabilities in
double precision by Markov chain methods ($N$ arbitrary), and output when
$N=200$. http://www.math.utah.edu/~ethier/3ruin-program.nb
http://www.math.utah.edu/~ethier/3ruin200-output

  2. 2.

Mathematica program to compute three-player elimination order probabilities in
double precision by iteration ($N$ arbitrary), and output when $N=300$.
http://www.math.utah.edu/~ethier/3iteration-program.nb
http://www.math.utah.edu/~ethier/3iteration300-output

  3. 3.

Mathematica program to compute four-player elimination order probabilities in
single precision by Markov chain methods ($N$ arbitrary), and output when
$N=50$ http://www.math.utah.edu/~ethier/4ruin-program.nb
http://www.math.utah.edu/~ethier/4ruin50-output

  4. 4.

Mathematica program to compute four-player elimination order probabilities in
single precision by iteration ($N$ arbitrary), and output when $N=100$.
http://www.math.utah.edu/~ethier/4iteration-program.nb
http://www.math.utah.edu/~ethier/4iteration100-output

  5. 5.

Mathematica files containing regression analyses for $\sigma=321$, 312, and
213. 5.1 MB each. http://www.math.utah.edu/~ethier/regression213-300.nb
http://www.math.utah.edu/~ethier/regression312-300.nb
http://www.math.utah.edu/~ethier/regression321-300.nb

## References

  * Aguilar, J. (2016) How to negotiate final table deals like a pro. Upswing Poker. https://upswingpoker.com/final-table-deal-making-tournaments/.

  * Aldous, D., Lanoue, D. and Salez, J. (2015) The compulsive gambler process. Electron. J. Probab. 20 (35), 1–18.

  * Bachelier, L. (1912) Calcul des Probabilités, Vol. 1. Gauthier-Villars, Paris.

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

  * Cover, T. M. (1987). Gambler’s ruin: A random walk on the simplex. In Open Problems in Communication and Computation. (T. M. Cover and B. Gopinath, eds.) 155. Springer, New York.

  * David, G. (2015) Markov chain solution to the 3-tower problem. In Information and Communication Technology. (I. Khalil, E. Neuhold, A. Tjoa, L. Xu, and I. You, eds.) ICT-EurAsia 2015. Lecture Notes in Computer Science 9357, 121–128. Springer, Cham.

  * Denisov, D. and Wachtel, V. (2015) Random walks in cones. Ann. Probab. 43 (3), 992–1044.

  * Diaconis, P. (1988) Group Representations in Probability and Statistics. Lecture Notes–Monograph Series 11. Institute of Mathematical Statistics, Hayward, CA.

  * Diaconis, P. and Freedman, D. (1979) On rounding percentages. J. Amer. Statist. Assoc. 74 (366a), 359–364.

  * Diaconis, P., Houston-Edwards, K., and Saloff-Coste, L. (2020) Gambler’s ruin estimates on finite inner uniform domains. Ann. Appl. Probab., to appear.

  * Engel, A. (1993) The computer solves the three tower problem. Amer. Math. Monthly 100 (1), 62–64.

  * Ethier, S. N. (2010) The Doctrine of Chances: Probabilistic Aspects of Gambling. Springer, Berlin and Heidelberg.

  * Feller, W. (1968) An Introduction to Probability Theory and Its Applications, Volume I, Third Edition. John Wiley & Sons, Inc., New York.

  * Ferguson, T. (1995) Gambler’s ruin in three dimensions. Unpublished. https://www.math.ucla.edu/~tom/papers/unpublished/gamblersruin.pdf.

  * Ganzfried, S. and Sandholm, T. (2008) Computing an approximate jam/fold equilibrium for 3-player no-limit Texas hold’em tournaments. AAMAS08: 7th International Conference on Autonomous Agents and Multi Agent Systems (L. Padgham, D. Parkes, J. Müller, and S. Parsons, eds.) 919–926. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC.

  * Gilbert, G. T. (2009) The independent chip model and risk aversion. https://arxiv.org/abs/0911.3100.

  * Gilliland, D., Levental, S., and Xiao, Y. (2007) A note on absorption probabilities in one-dimensional random walk via complex-valued martingales. Statist. Probab. Lett. 77 (11) 1098–1105.

  * Hajek, B. (1987) Gambler’s ruin: A random walk on the simplex. In Open Problems in Communication and Computation. (T. M. Cover and B. Gopinath, eds.) 204–207. Springer, New York.

  * Harville, D. A. (1973) Assigning probabilities to the outcomes of multi-entry competitions. J. Amer. Statist. Assoc. 68 (342), 312–316.

  * ICMizer (2020) Poker ICM calculator for final table deals. https://www.icmpoker.com/icmcalculator/.

  * Kemeny, J. G. and Snell, J. L. (1976) Finite Markov Chains. Springer-Verlag, New York.

  * Kim, M. S. (2005) Gambler’s ruin in many dimensions and optimal strategy in repeated multi-player games with application to poker. Masters thesis, UCLA.

  * Luce, R. D. (1959) Individual Choice Behavior: A Theoretical Analysis. Wiley, New York.

  * Luce, R. D. (1977) The choice axiom after twenty years. J. Math. Psych. 15, 215–233.

  * Malmuth, M. (1987) Gambling Theory and Other Topics. Two Plus Two Publishing, Henderson, NV.

  * Malmuth, M. (2004) Gambling Theory and Other Topics, Sixth Edition. Two Plus Two Publishing, Henderson, NV.

  * Marfil, R. I. D. and David, G. (2020) On the placing probabilities for the four-tower problem using recursions based on multigraphs. J. Math. Soc. Philippines 43 (1), 19–32.

  * Plackett, R. L. (1975) The analysis of permutations. Appl. Statist. 24 (2), 193–202.

  * Ratzkin, J., and Treibergs, A. (2009) A capture problem in Brownian motion and eigenvalues of spherical domains. Trans. Amer. Math. Soc. 361 (1), 391–405.

  * Ross, S. M. (2009) A simple solution to a multiple player gambler’s ruin problem. Amer. Math. Monthly 116 (1), 77–81.

  * Song, S. and Song, J. (2013) A note on the history of the gambler’s ruin problem. Comm. Statist. Applic. Methods 20 (1), 1–12.

  * Stern, H. S. (2008) Estimating the probabilities of the outcomes of a horse race (alternatives to the Harville formulas). In Efficiency of Racetrack Betting Markets, 2008 Edition (D. B. Hausch, V. S. Y. Lo, and W. T. Ziemba, eds.) 225–235. World Scientific Publishing, Singapore.

  * Stirzaker, D. (1994) Tower problems and martingales. Math. Scientist 19 (1), 52–59.

  * Stirzaker, D. (2006) Three-handed gambler’s ruin. Adv. Appl. Probab. 38 284–286.

  * Swan, Y. C. and Bruss, F. T. (2006) A matrix-analytic approach to the $N$-player ruin problem. J. Appl. Probab. 43, 755–766.

  * Turner, H., van Etten, J., Firth, D., and Kosmidis, I. (2017) Introduction to PlackettLuce. Microsoft R Application Network. https://mran.microsoft.com/snapshot/2017-12-15/web/packages/PlackettLuce/vignettes/Overview.html

  * WSOP (2019a) Hossein Ensan wins the 2019 WSOP Main Event ($10,000,000). https://www.wsop.com/tournaments/updates/?aid=2&grid=1622&tid=17298&dayof=7661&rr=5&curpage=4.

  * WSOP (2019b) John Gorsuch completes epic comeback to win 2019 WSOP Millionaire Maker for $1,344,930. https://www.wsop.com/tournaments/updates/?aid=2&grid=1622&tid=17287&dayof=7470&rr=5.