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.


Dirk P. Kroese

Research Area

The University of Queensland


Mon, 07/08/2017 - 2:00pm


M020, The Red Centre, UNSW