Dirk P. Kroese
Many difficult counting and estimation problems can be formulated in terms of estimating the cost of a tree. A simple estimation algorithm by Donald Knuth estimates this cost by running a single random path through the tree. The late Reuven Rubinstein, not being aware of Knuth's work, suggested running multiple random paths through the graph in a parallel fashion, and coined the method Stochastic Enumeration. I will explain how Stochastic Enumeration can be viewed as a generalization of Knuth's method, and can achieve a formidable increase in accuracy compared to Knuth's algorithm, in certain situations. I will demonstrate how the method can be applied to a variety of scenarios, including counting paths in a graph, independent sets, and truth assignments in the satisfiability problem, as well as estimating the reliability of a network.
This was joint work with Slava Vaisman.