ORIGINAL ARTICLE: Persi Diaconis, Stewart N. Ethier, Gambler’s Ruin and the ICM, Statist. Sci. 37(3): 289-305 (2022). DOI: https://doi.org/10.1214/21-STS826
Article Abstract: Consider gambler’s ruin with three players, 1, 2, and 3, having initial capitals , , and 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 be the elimination order (e.g., means player 1 is eliminated first and player 3 is eliminated second, leaving player 2 with units). We seek approximations (and exact formulas) for the elimination order probabilities (σ). Exact, as well as arbitrarily precise, computation of these probabilities is possible when is not too large.
A
B
C
σ∈
S
3
σ132
A+B+C
P
A,B,C
N:A+B+C
Three-player elimination order probabilities
Three-player elimination order probabilities
Here are two Mathematica programs for computing the elimination order probabilities in double precision; the first program allows infinite precision if time and memory permit. First, is a reserved symbol in Mathematica, so we use instead for , where is a state of the gambler’s ruin Markov chain with , , and being nonnegative integers.In the first program, which computes the elimination order probabilities directly, can be as large as 200. The program computes the harmonic measure and the elimination order probabilities , in terms of the transition matrix of the Markov chain, and its submatrices and . For example, . The harmonic measure is the distribution on the boundary of the state space at the time of first elimination. Using the two-player gambler’s ruin formula, is easily derived from . The only tricky part is the labeling of the rows and columns of and . The interior states are ordered lexicographically.In the second program, which computes lower and upper bounds for the elimination order probabilities by iteration, can be as large as 300, maybe larger. It computes lower bounds and upper bounds for the elimination order probabilities, and one can verify that they are equal to about 18 decimal places.
N
n
i+j+k
(i,j,k)
i
j
k
n
H
K
P
Q
S
HS
-1
(I-Q)
K
H
Q
S
(i,j,k)
n
Pmin
Pmax
N = 200
N = 200
Compute three-player elimination order probabilities in double precision by Markov chain methods (N arbitrary), and output when N = 200.
In[]:=
Print[DateList[]];n=200;Q=ConstantArray[0,{(n-1)(n-2)/2,(n-1)(n-2)/2}];S=ConstantArray[0,{(n-1)(n-2)/2,3(n-1)}];R=ConstantArray[0,{3(n-1),6}];For[k=1,k≤n-1,k++,q=N[k/n,12];(*replaceby"q=k/n;"ifinfiniteprecisionisdesired*)R[[k,1]]=1-q;R[[k,2]]=q;R[[n-1+k,3]]=1-q;R[[n-1+k,4]]=q;R[[2(n-1)+k,5]]=1-q;R[[2(n-1)+k,6]]=q];num[r_,s_]:=Sum[n-j,{j,2,r}]+s;(*numberofstate(r,s,n-r-s)underlexicographicalordering*)p=N[1/6,12];(*replaceby"p=1/6;"ifinfiniteprecisionisdesired*)row=0;For[i=1,i≤n-2,i++,For[j=1,j≤n-1-i,j++,row++;(*row=(i,j,n-i-j)*)(*col+-.*)If[j>1,Q[[row,num[i+1,j-1]]]=p,S[[row,n-1+i+1]]=p];(*col+.-*)If[n-i-j>1,Q[[row,num[i+1,j]]]=p,S[[row,2(n-1)+i+1]]=p];(*col-+.*)If[i>1,Q[[row,num[i-1,j+1]]]=p,S[[row,j+1]]=p];(*col.+-*)If[n-i-j>1,Q[[row,num[i,j+1]]]=p,S[[row,2(n-1)+i]]=p];(*col-.+*)If[i>1,Q[[row,num[i-1,j]]]=p,S[[row,j]]=p];(*col.-+*)If[j>1,Q[[row,num[i,j-1]]]=p,S[[row,n-1+i]]=p]]];M=Inverse[IdentityMatrix[(n-1)(n-2)/2]-Q];H=M.S;(*harmonicmeasure*)K=H.R;(*eliminationorderprobabilities*)K1=ConstantArray[0,{(n-1)(n-2)/2,9}];(*eliminationorderprobabilitieswithrowlabels*)row=0;For[i=1,i≤n-2,i++,For[j=1,j≤n-1-i,j++,row++;K1[[row,1]]=i;K1[[row,2]]=j;K1[[row,3]]=n-i-j]];For[i=1,i≤(n-1)(n-2)/2,i++,For[j=1,j≤6,j++,K1[[i,j+3]]=N[K[[i,j]],9]]];(*replaceby"K1[[i,j+3]]=K[[i,j]]]];"ifinfiniteprecisionisdesired*)Print[K1];Print[DateList[]];
Output is available at http://www.math.utah.edu/~ethier/3ruin200-output
N = 300
N = 300
Compute three-player elimination order probabilities in double precision by iteration (N arbitrary), and output when N = 300.
Print[DateList[]];n=300;(*123orderprobability*)iterations=4n^2;Pmin0=ConstantArray[0,{n-2,n-2}];Pmax0=ConstantArray[1,{n-2,n-2}];Pmin1=ConstantArray[0,{n-2,n-2}];Pmax1=ConstantArray[1,{n-2,n-2}];Pmin=ConstantArray[0,{(n-1)(n-2)/2,4}];Pmax=ConstantArray[0,{(n-1)(n-2)/2,4}];num[r_,s_]:=Sum[n-j,{j,2,r}]+s;p=N[1/6,21];For[m=1,m≤iterations,m++,For[i=1,i≤n-2,i++,For[j=1,j≤n-i-1,j++,Pmax1[[i,j]]=(If[i>1,Pmax0[[i-1,j+1]],1-(j+1)/n]+If[j>1,Pmax0[[i+1,j-1]],0]+If[i>1,Pmax0[[i-1,j]],1-j/n]+If[n-i-j>1,Pmax0[[i+1,j]],0]+If[j>1,Pmax0[[i,j-1]],0]+If[n-i-j>1,Pmax0[[i,j+1]],0])p;Pmin1[[i,j]]=(If[i>1,Pmin0[[i-1,j+1]],1-(j+1)/n]+If[j>1,Pmin0[[i+1,j-1]],0]+If[i>1,Pmin0[[i-1,j]],1-j/n]+If[n-i-j>1,Pmin0[[i+1,j]],0]+If[j>1,Pmin0[[i,j-1]],0]+If[n-i-j>1,Pmin0[[i,j+1]],0])p]];For[i=1,i≤n-2,i++,For[j=1,j≤n-i-1,j++,Pmax0[[i,j]]=Pmax1[[i,j]];Pmin0[[i,j]]=Pmin1[[i,j]]]]];For[i=1,i≤n-2,i++,For[j=1,j≤n-i-1,j++,Pmin[[num[i,j],1]]=i;Pmin[[num[i,j],2]]=j;Pmin[[num[i,j],3]]=n-i-j;Pmin[[num[i,j],4]]=N[Pmin0[[i,j]],18];Pmax[[num[i,j],1]]=i;Pmax[[num[i,j],2]]=j;Pmax[[num[i,j],3]]=n-i-j;Pmax[[num[i,j],4]]=N[Pmax0[[i,j]],18]]];Print[Pmin];Print[Pmax];Print[DateList[]];
Output is available at http://www.math.utah.edu/~ethier/3iteration300-output
Four-player elimination order probabilities
Four-player elimination order probabilities
The above programs for the three-player elimination order probabilities can be extended to four players using the same methods. In the first program, which computes the elimination order probabilities directly, can be as large as 50. In the second program, which uses the iteration method, can be as large as 100.
n
n
N = 50
N = 50
Compute four-player elimination order probabilities in single precision by Markov chain methods (N arbitrary), and output when N = 50.
Output is available at http://www.math.utah.edu/~ethier/4ruin50-output
N = 100
N = 100
Compute four-player elimination order probabilities in single precision by iteration (N arbitrary), and output when N = 100.
Output is available at http://www.math.utah.edu/~ethier/4iteration100-output
In the three-player gambler’s ruin model, there are nice formulas (discovered by Bachelier in 1912) for the mean time to first elimination and the mean time to second elimination. There are no such nice formulas for the elimination-order probabilities, which get more and more complicated as increases. For that reason, much of the paper is concerned with approximations to these probabilities, based on linear interpolation, regression analysis, Monte-Carlo simulation, or two-dimensional Brownian motion. Linear interpolation extends easily to four players, but the other methods have not yet been tried.
The ICM of the title is the independent chip model, which gives yet another approximation to the elimination-order probabilities. It is widely used in the setting of tournament poker, but is not a particularly good approximation to the elimination-order probabilities. On the other hand, the random walk model is probably unsatisfactory for tournament poker, given the frequency of all-in betting.
n
The ICM of the title is the independent chip model, which gives yet another approximation to the elimination-order probabilities. It is widely used in the setting of tournament poker, but is not a particularly good approximation to the elimination-order probabilities. On the other hand, the random walk model is probably unsatisfactory for tournament poker, given the frequency of all-in betting.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Gambler's Ruin and the ICM
by Persi Diaconis, Stewart Ethier
Wolfram Community, STAFF PICKS, September 8, 2023
https://community.wolfram.com/groups/-/m/t/3009112
by Persi Diaconis, Stewart Ethier
Wolfram Community, STAFF PICKS, September 8, 2023
https://community.wolfram.com/groups/-/m/t/3009112