Hitting time of large subsets of the hypercube. (English) Zbl 1147.60029
Summary: 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 article is the study of the so-called aging phenomenon in the Random Energy Model, 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.
MSC:
| 60G50 | Sums of independent random variables; random walks |
References:
| [1] | Abramowitz, Handbook of mathematical functions with formulas, graphs, and mathematical tables, National Bureau of Standards Applied Mathematics Series 55 (1972) · Zbl 0543.33001 |
| [2] | Bertin, Dynamical ultrametricity in the critical trap model, J Phys A: Math Gen 35 pp 3039– (2002) · Zbl 1053.82509 |
| [3] | Ben Arous, Glauber dynamics of the random energy model. I. Metastable motion on the extreme states, Comm Math Phys 235 pp 379– (2003) · Zbl 1037.82038 |
| [4] | Ben Arous, Glauber dynamics of the random energy model. II. Aging below the critical temperature, Comm Math Phys 236 pp 1– (2003) · Zbl 1037.82039 |
| [5] | Ben Arous, The arcsine law as a universal aging scheme for trap models, Comm Pure Appl Math 61 pp 289– (2008) · Zbl 1141.60075 |
| [6] | Ben Arous, ”Dynamics of trap models,” École d’été de physique des Houches, Session LXXXIII, Mathematical Statistical Physics pp 331– (2006) |
| [7] | Bovier, Metastability in stochastic dynamics of disordered mean field models, Prob Theory Related Fields 119 pp 99– (2001) |
| [8] | Bovier, Metastability and low lying spectra in reversible Markov chains, Comm Math Phys 228 pp 219– (2002) · Zbl 1010.60088 |
| [9] | G. Ben Arous and V. Gayrard, Elementary potential theory on the hypercube, Electron J Probab (2008), in press. · Zbl 1187.82105 |
| [10] | Diaconis, Group representations in probability and statistics, IMS Lecture Notes–Monograph Series 11 (1988) |
| [11] | Dembo 38 (1998) |
| [12] | Feller II (1971) |
| [13] | Kemperman, The passage problem for a stationary markov chain, Satistical Reseach Monographs I (1961) |
| [14] | Matthews, Covering problems for Markov chains, Ann Probab 16 pp 1215– (1988) · Zbl 0712.60076 |
| [15] | Matthews, Some sample path properties of a random walk on the cube, J Theoret Probab 2 pp 129– (1989) · Zbl 0671.60071 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
