Hitting time of large subsets of the hypercube

2006/11/08 by Cerny, Jiri, Véronique Gayrard, Gayrard, Veronique
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.math/0611242

openalex publication_date 2006/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 (n log n)^-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.

Related

• Elementary potential theory on the hypercube
• Hitting time of connectedness in the random hypercube process
• Stopping Times of Random Walks on a Hypercube
• The local time of a random walk on growing hypercubes
• A note on random walks in a hypercube