Efficient Simulation of a Random Knockout Tournament

We consider the problem of using simulation to efficiently estimate the win probabilities for participants in a general random knockout tournament. Both of our proposed estimators, one based on the notion of “observed survivals” and the other based on conditional expectation and post-stratification, are highly effective in terms of variance reduction when compared to the raw simulation estimator. For the special case of a classical 2^n -player random knockout tournament, where each survivor of the previous round plays in the current round, a second conditional expectation based estimator is introduced. At the end, we compare our proposed simulation estimators based on a numerical example and in terms of both variance reduction and the time to complete the simulation experiment. Based on our empirical study, the method of “observed survivals” is the most efficient method