Performance of the Metropolis algorithm on a disordered tree: the Einstein relation

DOI10.1214/13-AAP972MaRDI QIDQ744385zbMATH OpenOpenAlexWikidataFDO

Authors P. Maillard, Ofer Zeitouni

Publication date 25 September 2014

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.0552, https://projecteuclid.org/euclid.aoap/1403812370

zbMATH Keywords

Metropolis algorithmrandom environmentEinstein relationbranching random walkdisordered tree

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Sums of independent random variables; random walks (60G50) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Processes in random environments (60K37) Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics (82C41)

Abstract: Consider a $d$-ary rooted tree ($dgeq3$) 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 maximum $S_n^{\ast }$ 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 $$ 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.

Recommendations

• A Metropolis-type optimization algorithm on the infinite tree
• Automata, Languages and Programming
• scientific article; zbMATH DE number 1263187
• What do we know about the Metropolis algorithm?
• scientific article; zbMATH DE number 431548

Cites work

• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 2070282 (Why is no real title available?)
• A Metropolis-type optimization algorithm on the infinite tree
• A central limit theorem for biased random walks on Galton-Watson trees
• An invariance principle for reversible Markov processes. Applications to random motions in random environments
• Asymptotics for the survival probability in a killed branching random walk
• Biased random walks on Galton-Watson trees
• Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions
• Chernoff's theorem in the branching random walk
• Einstein relation for a tagged particle in simple exclusion processes
• Einstein relation for biased random walk on Galton-Watson trees
• Einstein relation for random walks in random environments
• Einstein relation for reversible diffusions in a random environment
• Fluctuations in Markov processes. Time symmetry and martingale approximation.
• Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty
• On mobility and Einstein relation for tracers in time-mixing random environments
• Probability. Theory and examples.
• Random walk in a random environment and first-passage percolation on trees
• Small Deviations in a Space of Trajectories
• The Einstein relation for the displacement of a test particle in a random environment
• Transient random walks in random environment on a Galton-Watson tree
• Weighted sums of certain dependent random variables

Cited in

(1)

• Einstein relation and linear response in one-dimensional Mott variable-range hopping

This page was built for publication: Performance of the Metropolis algorithm on a disordered tree: the Einstein relation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744385)