UC Berkeley

Let S(υ) be a function defined on the vertices υ of the infinite binary tree. One algorithm to seek large positive values of S is the Metropolis-type Markov chain (Xn) defined by P(Xn+1 = w|Xn = υ) = 1/3 eb(S(w)-S(υ))/1 + eb(S(w)-S(υ)) for each neighbor w of υ, where b is a parameter ("1/temperature") which the user can choose. We introduce and motivate study of this algorithm under a probability model for the objective function S, in which S is a "tree-indexed simple random walk," that is, the increments ξ(e) = S(w) - S(υ) along parent-child edges e = (υ, w) are independent and P(ξ = 1) = p, P(ξ = -1) = 1 - p. This algorithm has a "speed" r(p, b) = limn n-1 ES(Xn). We study the speed via a mixture of rigorous arguments, nonrigorous arguments, and Monte Carlo simulations, and compare with a deterministic greedy algorithm which permits rigorous analysis. Formalizing the nonrigorous arguments presents a challenging problem. Mathematically, the subject is in part analogous to recent work of Lyons et al. [19], [20] on the speed on random walk on Galton-Watson trees. A key feature of the model is the existence of a critical point pcrit below which the problem is infeasible; we study the behavior of algorithms as p ↓ pcrit. This provides a novel analogy between optimization algorithms and statistical physics. © 1998 Springer-Verlag New York Inc.