Tournament Finish Probability (long)

[Bozeman]

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:
<font class="small">Code:</font><hr /><pre> 2 1 1
1st 0.5 0.25 0.25
2nd 0.5 0.25 0.25
3rd 0 0.5 0.5
$ 0.4 0.3 0.3</pre><hr />

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.
<font class="small">Code:</font><hr /><pre> 2 1 1
1st 0.5 0.25 0.25
2nd 0.3 0.35 0.35
3rd 0.2 0.4 0.4
$ 0.38 0.31 0.31</pre><hr />

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).
<font class="small">Code:</font><hr /><pre> 2 1 1
1st 0.5 0.25 0.25
2nd 1/3 1/3 1/3
3rd 1/6 5/12 5/12
$ 0.383_ 0.3083_ 0.3083_</pre><hr />

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).
<font class="small">Code:</font><hr /><pre> 2 1 1
1st 1/2 1/4 1/4
2nd 5/14 9/28 9/28
3rd 1/7 3/7 3/7
$~ 0.3857 .3071 .3071</pre><hr />

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 ...).
<font class="small">Code:</font><hr /><pre> (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
</pre><hr />

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?
<font class="small">Code:</font><hr /><pre> 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</pre><hr />

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 (&lt;~.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.

[Legato]

Wow, great work. Unfortunately it would take hours for me to understand it all (if even that would be enough). Recently I played a tourney where we wanted to do a split I always used the McEvoy model (which I believe Pokerstars uses in the big one as well), but was informed about the big problem with large stacks potentially getting more than 1st prize which I never thought about before, and which clearly makes the model inadequate.

You seem to know alot about this and I trust your work enough to start using the Malmuth model. Unfortunately I do not understand how it works from your description. Would you please detail it a bit more.

The formula given is:

P(i,2|j,1)=I/(T-J)

My (incorrect) translation:
Probability of player i ending up 2nd granted that player j ends up 1st is equal to player i:s stack divided by the total number of chips minus player js stack.

And using your example 2/1/1:

P(i,2|j,1)=I/(T-J) =&gt;
P(i,2|j,1)=1/(4-2) = 0.5 which you calculate to 0,33.

Would you care to show how u got the figures you got for 2/1/1 stacks?

[Bozeman]

You need to do a sum:

If A has 2, B has 1, C has 1,

P(A,2)=P(B,1)*P(A,2|B,1)+P(C,1)*P(A,2|C,1)
= 1/4 * 2/(4-1) + 1/4 * 2/(4-1)
= 1/3

P(B,2)=P(A,1)*P(B,2|A,1)+P(C,1)*P(B,2|C,1)
= 1/2 * 1/(4-2) + 1/4 * 1/(4-1)
= 1/4 + 1/12
= 1/3

In general, P(i,m)=SUM[P(j,1)*P(k,2|j,1)...P(w,m-1|....)*P(i,m|j,1&amp;k,2&amp;..&amp;w,m-1)]{for all w!=k!=j!=i}
where P(i,m|j,1&amp;k,2&amp;..&amp;w,m-1)=I/(T-J-K-...-W) in the Malmuth model.

For threeway the math isn't too hard (also you can use lots of x+y+z=1 identities once you have an answer). For larger numbers of players, one pretty much needs a computer to compute it, so it may be better to use a random walk simulation.

Craig

[Legato]

Thanks! Really appreciate it.

[thylacine]

[ QUOTE ]

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.


[/ QUOTE ]

I agree completely. But I don't see how you could really find these conditional probabilities without solving the whole problem. If you start with players A,B,C having chip distribution vector (a,b,c), then in the case that C busts, you cannot assume any particular chip distribution for A,B since there would really be a probability distribution of chip distributions.

Also any method that gives a formula for prize equity that is a rational function (ratio of ploynomials) is not correct, though it may be a good approximation. The two (different) formulas in Malmulth's book are rational functions.

[Bozeman]

"I agree completely. But I don't see how you could really find these conditional probabilities without solving the whole problem."

Well, you are correct. The actual results (random walk), show problems with all the guesses for the conditional probabilities. However, it is useful to see what sorts of errors (and how large) are made by various approximations.

"If you start with players A,B,C having chip distribution vector (a,b,c), then in the case that C busts, you cannot assume any particular chip distribution for A,B since there would really be a probability distribution of chip distributions. "

This, however, doesn't seem to be a real issue, since the two player solution is simple, so the integral over the probability distribution should be doable. Care to find the chip distribution probability?

It would be very interesting to find a closed form solution to the random walk problem, and then extract conditional probabilities from it. Perhaps there is a more logical (simpler form?) way to separate into conditional probabilities than the two I have given. In any case, it was very useful to conceptually divide the various extant approaches.

Craig

PS The closest rational approximation I have found (tried only in a few cases, and not sure about how to generalize) is to take the divide into equal stacks approach, but to also allow a few strange exceptional outcomes (such as 1134 to be an allowed 4 stack finish).

PPS I am surprised that I have not seen a closed form solution (for anything larger than 2 players). Is this because I don't read enough obscure mathematics, because it is uninteresting, or because it is ~impossible?

[Copernicus]

I wonder (and I do mean wonder, since its an area us applied guys never had to trifle with) whether (in the absence of a reasonable simulation) there isnt a topological approach to the problem.

The potential orders of finish for n players would seem to be representable as figures in n-space, and gaining or losing chips distortions of either the figure or a dimension. Perhaps you wind up with the same conditional probability froblem, but those topology guys are pretty tricky.

[thylacine]

In the starting post to this thread Bozeman posted a link to "Ferguson method". (By the way, how do you do this, and what is the address of the link?) From this you get file gamblersruin.pdf, unpublished article by Thomas Ferguson.

I regard this as an exact solution (for the infinitesimal random walk, i.e. Brownian motion) for 3 players, although the solution is somewhat obscure and indirect. It finds the probability of a player coming third, and since the probability of a player coming first is easy to find, it gives prob of each position for each player for any given chip distribution.

I don't know if you'd call it "closed form".

It does not do n&gt;3, and in any case for n&gt;3, knowing P(first) and P(last) for each player would not tell you prob of other positions.

This general case is random walk on a regular n-vertex simplex. (n=2 line segment, n=3 triangle, n=4 tetrahedron etc)

For general n Ferguson does an outline for random walk in positive octant of n-dimensional space. This is equivalent to n+1 players, where one player has an infinite stack, so the totals for the others will vary but they will eventually all bust, and the question is, in what order? But it appears that this method would only give P(last) for each player and would not tell you prob of other positions.

[Bozeman]

Also, while the problem of time to diffusion accross a plane (or general n-1 dimensional subspace) (which corresponds to one player being eliminated) is quite doable, the problem of interest involves the very difficult computation of the probability of crossing one such boundary before crossing another. In addition, you would need to find the probability of exit at each point along that plane, and finding the n-1th finisher would be an integral of the results of all possible n-1 player chip distributions * prob. that such distribution is reached (this integral then being the exact conditional probability in the 1(b) case). (As thylacine said, just finding out who finishes last with what probability only solves the entire problem in the 3 player case.) But the solution to the n-1 player problem and the probability of getting to each possible boundary point together solve the n player problem.

Craig

[thylacine]

But I don't think you have to do this integral. For n players you want prob P( x ,i j) the prob that player i comes in position j given starting stack distribution x=(x_1,x_2,...,x_n). These will be the solutions of some differential equation for these functions of x in an n-vertex simplex, with boundary conditions coming by induction from the (n-1)-player case.