Hitting time of large subsets of the hypercube

DOI10.1002/RSA.20217MaRDI QIDQ3522838zbMATH OpenOpenAlexFDO

Authors Jiří Černý, V. Gayrard

Publication date 4 September 2008

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

aginghitting timehypercuberandom walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Abstract: We study the simple random walk on the $n$-dimensional hypercube, in particular its hitting times of large (possibly random) sets. We give simple conditions on these sets ensuring that the properly-rescaled hitting time is asymptotically exponentially distributed, uniformly in the starting position of the walk. These conditions are then verified for percolation clouds with densities that are much smaller than $(nlogn{)}^{-1}$. A main motivation behind this paper is the study of the so-called aging phenomenon in the Random Energy Model (REM), the simplest model of a mean-field spin glass. Our results allow us to prove aging in the REM for all temperatures, thereby extending earlier results to their optimal temperature domain.

Recommendations

• Elementary potential theory on the hypercube.
• Metastability for the Ising model on the hypercube
• Hitting times, commute times, and cover times for random walks on random hypergraphs
• A non-local random walk on the hypercube
• Asymptotic analysis of a random walk on a hypercube with many dimensions

Cites work

• Covering problems for Markov chains
• Dynamical ultrametricity in the critical trap model
• Elementary potential theory on the hypercube.
• Glauber dynamics of the random energy model. I: Metastable motion on the extreme states
• Glauber dynamics of the random energy model. II: Aging below the critical temperature.
• scientific article; zbMATH DE number 3863589 (Why is no real title available?)
• Metastability and low lying spectra in reversible Markov chains
• Some sample path properties of a random walk on the cube
• The arcsine law as a universal aging scheme for trap models

Cited in

(5)

• Asymptotic behavior and aging of a low temperature cascading 2-GREM dynamics at extreme time scales
• Convergence of clock processes and aging in Metropolis dynamics of a truncated REM
• Universality and extremal aging for dynamics of spin glasses on subexponential time scales
• Dynamic phase diagram of the REM
• Aging of the Metropolis dynamics on the random energy model

This page was built for publication: Hitting time of large subsets of the hypercube

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