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

DOI10.1214/13-AAP972zbMATH Open1327.60139arXiv1304.0552OpenAlexW3103036057WikidataQ128213495 ScholiaQ128213495MaRDI QIDQ744385FDOQ744385

Ofer Zeitouni, P. Maillard

Publication date: 25 September 2014

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

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^{*}$ 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.

Full work available at URL: https://arxiv.org/abs/1304.0552

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

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)

Cites Work

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

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)