How to Calculate Winning Probabilities for Knock-Out Tournaments
by Louis Nel
If four players A,B,C,D play in a tournament (i.e. a knock-out tournament in this discussion), there is more than one possible draw for the first round. For example
A_D C_B is one possibility,
A_B C_D is another.
The probability for A to win the tournament under the first draw is different in general from what it is under the second. Our purpose here is to provide a method for the numerical calculation of the winning probability of each player under a particular draw.
S1 = A, S2 = D, S3 = C, S4 = D,
T1 = A, T2 = B, T3 = C, T4 = D
are 4-tournaments with the same player population A,B,C,D. In fact, S and T represent the two tournaments mentioned in the opening paragraph.
P(i,j) = the probability that Ti will beat Tj ,
Wn(i,T) = the probability that Ti will win the n-tournament T.
The probabilities P(i,j) can readily be calculated for players with known Grades who play consistently in accordance with their Grades (see Winning Percentages associated with Grade Differences. The calculations are precise for such players and are approximate for ordinary players. With the above notation in place, let us begin to develop the promised method for calculation of Wn(i,T).
W2(1,T) = P(1,2),
W2(2,T) = P(2,1).
So let us move to the case of a 4-tournament with draw given by
T1 = A, T2 = B, T3 = C, T4 = D
We have only two rounds:
A_B C_D (semifinal round)
where X is the winner of A_B and Y the winner of C_D. We can regard this 4-tournament as a succession of two 2-tournaments, namely its LEFT 2-tournament L and and its RIGHT 2-tournament R, where
L1 = A, L2 = B, R1 = C, R2 = D.
Let prob(Event X) denote the probability that Event X will take place. We have
where * denotes multiplication. It follows that
W4(1,T) = prob(A reaches final) * prob(A wins final)
= W2(1,L)* ( P(1,3) * W2(1,R) + P(1,4) * W2(2,R) ))
Thus we have arrived at the desired calculation method for W4(i,T).
W4(i,T) becomes expressed in terms of W2(i,L) and W2(i,R)
i.e. the solutions for its left and right 2-tournaments. This gives the clue for handling larger tournaments: the solution of the 8-tournament problem needs merely to be expressed similarly in terms of the solutions for its left and right 4-tournament problems. Likewise, a 16-tournament problem reduces to 8-tournament problems and so on for any power of 2. Let us write it up for the general case.
Lj = Tj for j = 1,2,..,s where s = n/2
Rj = Ts+j for j = 1,2,..,s.
Our task is to express Wn(i,T) in terms of the solutions of the left and right s-tournament problems, namely Ws(j,L) and Ws(k,R).
For an index i not greater than s (so Ti is in the left half of the draw) we have
Wn(i,T) = Ws(i,L) * (Probability Sum).
where (Probability Sum) denotes the sum of all terms of the form
P(i,k) * Ws(k,R)
where k runs through the index set 1,2,...,s.
Wn(i,T) = Ws(j,R) * ( P(i,1) * Ws(1,L) + ..+ P(i,s) * Ws(s,L) ).
Thus we have established a recursive numerical scheme for calculating the winning probabilites for an n-tournament. For a given n one could write out all the terms explicitly, but for large n this becomes very tedious. Fortunately, it is also unnecesary, because the scheme as given is adequate to serve as basis for a computer program.
Remark on Best-of-3 Knock-Outs.
Whether a knock-out is based on best-of-3 matches or single game matches, makes no difference to the above method for calculating tournament winning probabilities. It is only the pairwise winning probabilities P(i,j) that change and that changes as follows. Let
p = prob( A will beat B in a single game), P3 = prob( A will beat B in a best-of-3 match) ,
P5 = prob( A will beat B in a best-of-5 match).
P3 = p2(3 -2p),
P5 = p3(10 - 15p + 6p2).
It can be verified that the three probabilites coincide when
p = 0 or p = 0.5 or p = 1.
When 0 < p < 0.5 we have P5 < P3 < p and
When Bo3 Changes to Bo5 During the KO
Some KO events, like 32-tournament in the World Championships, start with bo3 and from the semifinal on it becomes best-of-5. In such a case, the above algorithm cannot be applied on the KO as a whole. It can be applied, with P3(i,j) for the pairwise win probabilities, to the four 8-tournaments formed by the four quarters of the draw, whose winners will be the semifinalists. The application will give for each player the probability that he becomes a semifinalist. Then a separate application to the 4-tournament formed by semifinalists can be made, this time with P5(i,j) used for the pairwise win probabilities. By combining the two steps, one can again compute, for each player his win probability in the 32-tournament as product of the probability that he reaches the semifinal and the probability that he wins the final once there. These two factors are analogous to "blue" and "red" sums explained above.
Enhancement of the 2000 version
All rights reserved © 2000-3