A METROPOLIS-TYPE OPTIMIZATION ALGORITHM ON THE INFINITE TREE

Let S(v) be a function defined on the vertices v of the infinite binar y tree. One algorithm to seek large positive values of S is the Metrop olis-type Markov chain (X-n) defined by P(Xn+1 = w \ X-n = v) = 1/3 e( b(S(w)-S(v)))/1 + e(b(S(w)-S(v))) for each neighbor w of v, where b is a parameter (''1/temperature'') which the user can choose. We introdu ce 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 xi(e) = S(w) - S(v) along parent-chil d edges e = (v, w) are independent and P(xi = 1) = p, P(xi = -1) = 1 - p. This algorithm has a ''speed'' r(p, b) = lim(n)n(-1) ES(X-n). We s tudy the speed via a mixture of rigorous arguments, nonrigorous argume nts, and Monte Carlo simulations, and compare with a deterministic gre edy algorithm which permits rigorous analysis. Formalizing the nonrigo rous arguments presents a challenging problem. Mathematically, the sub ject 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 p(crit) below which the pr oblem is infeasible; we study the behavior of algorithms as p down arr ow p(crit). This provides a novel analogy between optimization algorit hms and statistical physics.