ON "GO WITH THE WINNERS "A LGORITHM
Sudeepa Roy · 2006
Aldous and Vazirani proposed the “Go With The Winners” algorithm [AV94] to boost the success probability in searching for a leaf at the deepest level of a search tree, by introducing interactions between simulations. They claim high probability of success using only polynomial (in ) number of simulations (as against the naive exponential bound) on search trees satisfying certain criteria quantified by a parameter . This search tree model abstracts the behaviour of Simulated Annealing on a continuous function where a particle moves down to the leaves as the temperature is lowered making irrevocable choices at branch points of the tree. In this work, we propose a simple condition which intends to capture precisely the set of search trees for which the “Go With The Winners” algorithm will find a deepest node with high probability using only a polynomial number of particles. We show that our condition is both necessary and sufficient for a restricted class of search trees. We conjecture that the same condition precisely captures the set of all search trees for which the “Go With The Winners” algorithm is efficient. Since our condition is weaker than the sufficient condition as provided in [AV94] for the “Go With The Winners” algorithm to work, our conjecture, if true, will identify a larger class of search trees, than what the [AV94] condition suggests, on which the algorithm works well. Further, if the conjecture holds, it will give a tighter bound on the number of particles that will suffice for the algorithm to work. As an evidence, we construct a search tree satisfying our condition and on which “Go With The Winners” works, but the tree does not satisfy the sufficient condition as given in [AV94].