Technical
How to Calculate Winning Probabilities for KnockOut Tournaments
by Louis Nel If four players A,B,C,D play in a tournament (i.e. a knockout 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. S_{1} = A, S_{2} = D, S_{3} = C, S_{4} = D, T_{1} = A, T_{2} = B, T_{3} = C, T_{4} = D are 4tournaments 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 T_{i} will beat T_{j} , W_{n}(i,T) = the probability that T_{i} will win the ntournament 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 W_{n}(i,T). W_{2}(1,T) = P(1,2), W_{2}(2,T) = P(2,1). So let us move to the case of a 4tournament with draw given by T_{1} = A, T_{2} = B, T_{3} = C, T_{4} = 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 4tournament as a succession of two 2tournaments, namely its LEFT 2tournament L and and its RIGHT 2tournament R, where L_{1} = A, L_{2} = B, R_{1} = C, R_{2} = D. Let prob(Event X) denote the probability that Event X will take place. We have
where * denotes multiplication. It follows that W_{4}(1,T) = prob(A reaches final) * prob(A wins final) = W_{2}(1,L)* ( P(1,3) * W_{2}(1,R) + P(1,4) * W_{2}(2,R) )) and similarly
Thus we have arrived at the desired calculation method for W_{4}(i,T). W_{4}(i,T) becomes expressed in terms of W_{2}(i,L) and W_{2}(i,R) i.e. the solutions for its left and right 2tournaments. This gives the clue for handling larger tournaments: the solution of the 8tournament problem needs merely to be expressed similarly in terms of the solutions for its left and right 4tournament problems. Likewise, a 16tournament problem reduces to 8tournament problems and so on for any power of 2. Let us write it up for the general case. L_{j} = T_{j} for j = 1,2,..,s where s = n/2 R_{j} = T_{s+j} for j = 1,2,..,s. Our task is to express W_{n}(i,T) in terms of the solutions of the left and right stournament problems, namely W_{s}(j,L) and W_{s}(k,R). For an index i not greater than s (so T_{i} is in the left half of the draw) we have W_{n}(i,T) = W_{s}(i,L) * (Probability Sum). where (Probability Sum) denotes the sum of all terms of the form P(i,k) * W_{s}(k,R) where k runs through the index set 1,2,...,s. W_{n}(i,T) = W_{s}(j,R) * ( P(i,1) * W_{s}(1,L) + ..+ P(i,s) * W_{s}(s,L) ). Thus we have established a recursive numerical scheme for calculating the winning probabilites for an ntournament. 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 Bestof3 KnockOuts.Whether a knockout is based on bestof3 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), P_{3} = prob( A will beat B in a bestof3 match) , P_{5} = prob( A will beat B in a bestof5 match). Then P_{3} = p^{2}(3 2p), P_{5} = p^{3}(10  15p + 6p^{2}). 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 P_{5} < P_{3} < p and When Bo3 Changes to Bo5 During the KOSome KO events, like 32tournament in the World Championships, start with bo3 and from the semifinal on it becomes bestof5. In such a case, the above algorithm cannot be applied on the KO as a whole. It can be applied, with P_{3}(i,j) for the pairwise win probabilities, to the four 8tournaments 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 4tournament formed by semifinalists can be made, this time with P_{5}(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 32tournament 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 © 20003
