A Metropolis-type optimization algorithm on the infinite tree

Let S(v) be a function defined on the vertices v of the infinite binary tree. One algorithm to seek large positive values of S is the Metropolis-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 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 xi(e) = S(w) - S(v) along parent-child 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 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 p(crit) below which the problem is infeasible; we study the behavior of algorithms as p down arrow p(crit). This provides a novel analogy between optimization algorithms and statistical physics.