The 2+2 Archive Forums: Tournament Finish Probability (long)

The following is a summeray of what I have found/done to accurately calculate probability of finishing in a given place as a function of the stack sizes.

Notation: P(i,x)=probability that player i finishes in xth place
P(w|z)=probability that w occurs given that z occurs
I=i's stack
T=SUM[I]
Base: P(i,1)=I/T

1) conditional probability methods:
It is unequivaocally true that (a) P(i,2)=SUM(j!=i)[P(j,1)*P(i,2|j,1)]
or one could use (b) P(i,n-1)=SUM(j!=i)[P(j,n)*P(i,n-1|j,n)] (that is, start from last place and work up)
Unfortunately, it seems that all the reasonable choices for the conditional probabilities are incorrect to varying degrees.

2) random walk methods:
These results are are valid for their induvidual constraints. The results depend somewhat on the size of the step used in the random walk. For large step sizes, they also depend somewhat on the way in which steps are taken:
Large (~1): enumeration (Wiedeman method) (a)
Medium(~0.1): simulation (b)
Small(infinitesimal): complex analysis (Ferguson method) (c)

All the decent models appear to fall into these categories, here are some, together with their errors/limitations (in rough order from worst to best):
(For each model I have given results for stacks of relative size 2,1,1 and payoff for 1st=0.5,2nd=0.3,3rd=0.2)

McEvoy model for threeway split (1a). Tom only wrote this as a money split algorithm, but one could derive finish probabilities from his results. Everyone gets 3rd place plus (1st-3rd + 2nd-3rd)*I/T. This is equivalent to saying that P(i,2)=P(i,1). Thus this is a model of type 1a, using some very awkward assumptions about the conditional probabilities. Big advantage for large stacks, in fact, very large stacks could get more than 1st place money (and finish probabilities that do not sum to one). For the 2,1,1 case:
Code:

Weitzman model (1b) from Malmith's GTaOT. Assumes P(i,last) inversely proportional to I/T. In order to get P(i,1)=I/T, P(i,2|j,3)= (I+J/2)/T, that is, as each player is eliminated, their chips are evenly distributed to the remaining players. This massively favors the small stacks.
Code:

Malmuth model (1a), this is the model I have been promoting, in GTaOT 4th edition, but predates Mason as well (anyone have an original citation?). Uses P(i,2|j,1)=I/(T-J). This reasonable seeming assumption favors the small stacks (though considerably less than the Weitzman model).
Code:

Surprisingly enough, this is equivalent to the (2) method where each players stack is divided into m(i) stacks such that all stacks are equal and there is now a SUM[m(i)] player freezeout. Each player finishes as the best of his substacks, with the caveat that the loweer player move up to fill any resulting vacancies in the top n. I didn't explain this too well, but it is just the result if each player's stack of (I) chips acts like (I) independent players. This is equivalent to modelling poker as a raffle with several prizes, but no matter how many tickets you buy, you can only win one prize (and all prizes will be awarded). Apparently, it is the non-independence of the larger stack's many small stacks that gives him an advantage (over the Malmuth model).

By solving ~T^2 simultaneous equations, you can do the random walk exactly (2a), the Weideman model. Results depend on the size of the triangle (for 3 players) you use. However, results do not change much for larger triangles as you will see in the next scheme. Results depend somewhat on the way the random walk is done exactly; the Weideman model uses a series of random head-to-head matchups (one chip each, no ties).
Code:

I hate solving 10+ equations for 10+ unknowns, so I just simulated this. With 10 milliono trials, results are good to 3.5 significant figures. I used two style of walk, the h2h one chip each (h2h), and the rotating 1 chip blind, that a random player (possibly the one who put it up) then fights for (blind). Here I give result for several sizes (2,1,1 4,2,2 6,4,4 ...).
Code:

(h2h) 2 1 1
1 0.499849 0.250198 0.249953
2 0.357230 0.321502 0.321268
3 0.142921 0.428301 0.428779
$ 0.385678 0.307209 0.307113
4 2 2
1 0.500092 0.249894 0.250014
2 0.357726 0.321089 0.321185
3 0.142182 0.429017 0.428801
$ 0.385800 0.307077 0.307123
6 3 3
1 0.500094 0.249970 0.249936
2 0.357835 0.321080 0.321084
3 0.142071 0.428949 0.428980
$ 0.385812 0.307099 0.307089

(blind) 2 1 1
2 0.500017 0.250056 0.249927
2 0.361369 0.318985 0.319646
3 0.138614 0.430959 0.430426
$ 0.386142 0.306915 0.306943
4 2 2
2 0.500074 0.249823 0.250104
2 0.358331 0.319862 0.321807
3 0.141595 0.430316 0.428089
$ 0.385855 0.306933 0.307212
6 3 3
2 0.499990 0.250070 0.249939
2 0.358004 0.320569 0.321428
3 0.142006 0.429361 0.428633
$ 0.385798 0.307078 0.307125

I found the unpublished article by Thomas Ferguson (father of "Jesus"), which solved the threeway random walk in the diffusion limit. Alas, it is some complicated complex analysis, and the answer is not in a functional form, and it requires beta functions. Still, this gives the infinite size limit that previous two are approaching. Anyone want to work this into a more usable form, or solve it for 4 players?
Code:

2 1 1
1 1/2 1/4 1/4
2 0.3579 0.3211 0.3211
3 0.1421 0.4289 0.4289
$ 0.3858 0.3071 0.3871

Note that the simulation results converge to the small step result very quickly (by 2-4 decrease in stakes from largest possible). So reasonable simulations may not be very time intensive.

Unfortunately, only the random walk simulation and the Malmuth method appear to be generalizable to larger tournaments.

The Malmuth model typically gives errors of 1-2% for the large stack's chances of 2nd and 3rd. The large blind variation is always small (<~.1%).

Craig

PS Note that whether large stakes is an advantage or disadvantage to the big stack can depend on the exact style of blinds. In fact, I found an unusual type of game (where the blind never wins unless no one else fights for it), where there is a large affect of relative position (wrt the large stack), even though the button position to start is decided randomly.

PPS In this case (after subtracting off the guaranteed third money), the large stack is worth 87% of twice a small stack.