PERFORMANCE OF THE METROPOLIS ALGORITHM ON A DISORDERED TREE: THE EINSTEIN RELATION

• 成果类型: Article
• 署名作者: Maillard, Pascal; Zeitouni, Ofer
• 署名单位: Weizmann Institute of Science
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/13-AAP972
• 发表日期: 2014
• 页码: 2070-2090
• 关键词: reversible markov-processes; central-limit-theorem; biased random-walks; random environment; particle

摘要

Consider a d-ary rooted tree (d >= 3) where each edge e is assigned an i.i.d. (bounded) random variable X (e) of negative mean. Assign to each vertex v the sum S(v) of X (e) over all edges connecting v to the root, and assume that the maximurn S-n* of S(v) over all vertices v at distance n from the root tends to infinity (necessarily, linearly) as n tends to infinity. We analyze the Metropolis algorithm on the tree and show that under these assumptions there always exists a temperature 1/beta of the algorithm so that it achieves a linear (positive) growth rate in linear time. This confirms a conjecture of Aldous [Algorithmica 22 (1998) 388-412]. The proof is obtained by establishing an Einstein relation for the Metropolis algorithm on the tree.