Dr Ian Plummer
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.
For the purposes of this study, we define an n-tournament to be a function T (the draw) which assigns a player Ti to every index i in the index set [1,2, ..,n].
Example. The functions S and T given by
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.
We need only consider n-tournaments such that N is a power of 2 i.e. N = 2, 4, 8, 16, ..., because any tournament can effectively be reduced to one like that. For example, a tournament of 13 players can be filled up to 16 with dummies named Bye1, Bye2, Bye3, destined to lose all their matches.
Let T be the draw for an n-tournament. For i,j = 1,2,..,n, we put
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).
For a 2-tournament, given by T1 = A, T2 = B, the solution to the problem is obvious, namely
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)
X_Y (final)
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
prob(A reaches final) = P(1,2) = W2(1,L)
prob(B reaches final) = P(2,1) = W2(2,L)
prob(C reaches final) = P(3,4) = W2(1,R)
prob(D reaches final) = P(4,3) = W2(2,R)
prob(X wins final) = prob(X beats C) * prob(C reaches final) + prob(X beats D) * prob(D reaches final),
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) ))
and similarly
W4(2,T) = W2(2,L) * ( P(2,3) * W2(1,R) + P(2,4) * W2(2,R) )
W4(3,T) = W2(1,R) * ( P(3,1) * W2(1,L) + P(3,2) * W2(2,L) )
W4(4,T) = W2(2,R) * ( P(4,1) * W2(1,L) + P(4,2) * W2(2,L) ).
Thus we have arrived at the desired calculation method for W4(i,T).
A key ingredient in this derivation is that
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.
Let T be the draw of an n-tournament, L and R respectively the associated draws of its left and right subtournaments i.e.
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.
For an index i greater than s (so Ti is in the right half) there is a unique index j = i - s such that Ti = Rj. In terms of this j we have
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).
Then
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 0.5 < p < 1 we have P5 > P3 > p.
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
26 January 2003