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.

When several users simultaneously transmit over a shared communication channel, the messages are lost and must be retransmitted later. Various protocols specifying when to retransmit have been proposed and studied in recent years. One protocol is “binary exponential back-off,” used in the local area network Ethernet. A mathematical model with several idealizations (discrete time slots, infinite users, no deletions) is shown to be unstable in that the asymptotic rate of successful transmissions is zero, however small the arrival rate. © 1987 IEEE

In a famous paper [8] Hammersley investigated the length L n of the longest increasing subsequence of a random n-permutation. Implicit in that paper is a certain one-dimensional continuous-space interacting particle process. By studying a hydrodynamical limit for Hammersley's process we show by fairly "soft" arguments that lim n ′1/2 EL n =2. This is a known result, but previous proofs [14, 11] relied on hard analysis of combinatorial asymptotics. © 1995 Springer-Verlag.