Sampling the Leaves of a Tree with Equal Probabilities
Paul R. Rosenbaum · Journal of the American Statistical Association · 1993
In the computer sciences, trees are among the most common data structures. Knuth proposed a method of sampling the leaves of a tree with known but unequal probabilities; he used the sample to estimate the behavior of backtrack algorithms. This article proposes two methods for sampling leaves with equal probabilities.