Elementary potential theory on the hypercube.

Véronique Gayrard (CNRS)
Gérard Ben Arous (Courant Institute for mathematical Sciences, NYU)


This work addresses potential theoretic questions for the standard nearest neighbor random walk on the hypercube $\{-1,+1\}^N$. For a large class of subsets $A\subset\{-1,+1\}^N$ we give precise estimates for the harmonic measure of $A$, the mean hitting time of $A$, and the Laplace transform of this hitting time. In particular, we give precise sufficient conditions for the harmonic measure to be asymptotically uniform, and for the hitting time to be asymptotically exponentially distributed, as $N\rightarrow\infty$. Our approach relies on a $d$-dimensional extension of the Ehrenfest urn scheme called lumping and covers the case where $d$ is allowed to diverge with $N$ as long as $d\leq \alpha_0\frac{N}{\log N}$ for some constant $0<\alpha_0<1$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1726-1807

Publication Date: October 4, 2008

DOI: 10.1214/EJP.v13-527


  1. Aldous, David. Random walks on finite groups and rapidly mixing Markov chains. Seminar on probability, XVII, 243--297, Lecture Notes in Math., 986, Springer, Berlin, 1983. MR0770418 (86j:60156)
  2. Aldous, David J. On the time taken by random walks on finite groups to visit every state. Z. Wahrsch. Verw. Gebiete 62 (1983), no. 3, 361--374. MR0688644 (84i:60013)
  3. Aldous, David; Diaconis, Persi. Strong uniform times and finite random walks. Adv. in Appl. Math. 8 (1987), no. 1, 69--97. MR0876954 (88d:60175)
  4. Aldous, David; Diaconis, Persi. Shuffling cards and stopping times. Amer. Math. Monthly 93 (1986), no. 5, 333--348. MR0841111 (88a:60021)
  5. Ben Arous, G.; Bovier, A.; Gayrard,V. ``Aging in the random energy model'' WHERE article_id=Phys. Rev. Letts. 88, 087201 (2002).
  6. Ben Arous, Gérard; Bovier, Anton; Gayrard, Véronique. Glauber dynamics of the random energy model. I. Metastable motion on the extreme states. Comm. Math. Phys. 235 (2003), no. 3, 379--425. MR1974509 (2004g:82122)
  7. Ben Arous, Gérard; Bovier, Anton; Gayrard, Véronique. Glauber dynamics of the random energy model. II. Aging below the critical temperature. Comm. Math. Phys. 236 (2003), no. 1, 1--54. MR1977880 (2004i:82057)
  8. Ben Arous, Gérard; Černý, Jiří. The arcsine law as a universal aging scheme for trap models. Comm. Pure Appl. Math. 61 (2008), no. 3, 289--329. MR2376843
  9. Bovier, Anton; Eckhoff, Michael; Gayrard, Véronique; Klein, Markus. Metastability in stochastic dynamics of disordered mean-field models. Probab. Theory Related Fields 119 (2001), no. 1, 99--161. MR1813041 (2001k:82096)
  10. Bovier, Anton; Eckhoff, Michael; Gayrard, Véronique; Klein, Markus. Metastability and low lying spectra in reversible Markov chains. Comm. Math. Phys. 228 (2002), no. 2, 219--255. MR1911735 (2004g:60102)
  11. Bovier, Anton; Gayrard, Véronique. An almost sure large deviation principle for the Hopfield model. Ann. Probab. 24 (1996), no. 3, 1444--1475. MR1411501 (98g:60055)
  12. Gayrard, V. Thermodynamic limit of the $q$-state Potts-Hopfield model with infinitely many patterns. J. Statist. Phys. 68 (1992), no. 5-6, 977--1011. MR1180270 (93g:82075)
  13. Gayrard, V. ``Glauber dynamics of the 2-GREM. 1. Metastable motion on the extreme states.'' WHERE article_id=preprint (2007).
  14. Burke, C. J.; Rosenblatt, M. A Markovian function of a Markov chain. Ann. Math. Statist. 29 1958 1112--1122. MR0101557 (21 #367)
  15. Comtet, Louis. Analyse combinatoire. Tomes I, II.(French) Collection SUP: ``Le Mathématicien'' WHERE article_id=4, 5 Presses Universitaires de France, Paris 1970 Vol. I: 192 pp.; Vol. II: 190 pp. MR0262087 (41 #6697)
  16. Diaconis, Persi. Applications of noncommutative Fourier analysis to probability problems. École d'Été de Probabilités de Saint-Flour XV--XVII, 1985--87, 51--100, Lecture Notes in Math., 1362, Springer, Berlin, 1988. MR0983372 (90c:60006)
  17. Diaconis, Persi; Graham, R. L.; Morrison, J. A. Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures Algorithms 1 (1990), no. 1, 51--72. MR1068491 (91g:60078)
  18. Kemeny, John G.; Snell, J. Laurie. Finite Markov chains.The University Series in Undergraduate Mathematics D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London-New York 1960 viii+210 pp. MR0115196 (22 #5998)
  19. Kemperman, J. H. B. The passage problem for a stationary Markov chain.Statistical Research Monographs, Vol. I. The University of Chicago Press, Chicago, Ill. 1961 vii+127 pp. MR0119226 (22 #9992)
  20. W. Feller, An Introduction to Probability Theory and Its Applications, Volume 2, John Wiley and Sons, Inc. New York, 1970.
  21. Koch, Hans; Piasko, Jacques. Some rigorous results on the Hopfield neural network model. J. Statist. Phys. 55 (1989), no. 5-6, 903--928. MR1002477 (90i:82047)
  22. Liggett, Thomas M. Interacting particle systems.Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 276. Springer-Verlag, New York, 1985. xv+488 pp. ISBN: 0-387-96069-4 MR0776231 (86e:60089)
  23. Matthews, Peter. Some sample path properties of a random walk on the cube. J. Theoret. Probab. 2 (1989), no. 1, 129--146. MR0981770 (90b:60089)
  24. Matthews, Peter. ``Covering problems for Markov chains'' Ann. Probab. 16, 1215--1228 (1988).
  25. Matthews, Peter. Mixing rates for a random walk on the cube. SIAM J. Algebraic Discrete Methods 8 (1987), no. 4, 746--752. MR0918073 (89a:60030)
  26. Saloff-Coste, Laurent. Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996), 301--413, Lecture Notes in Math., 1665, Springer, Berlin, 1997. MR1490046 (99b:60119)
  27. Soardi, Paolo M. Potential theory on infinite networks.Lecture Notes in Mathematics, 1590. Springer-Verlag, Berlin, 1994. viii+187 pp. ISBN: 3-540-58448-X MR1324344 (96i:31005)
  28. Spitzer, Frank. Principles of random walks.Second edition.Graduate Texts in Mathematics, Vol. 34.Springer-Verlag, New York-Heidelberg, 1976. xiii+408 pp. MR0388547 (52 #9383)
  29. Voit, Michael. Asymptotic distributions for the Ehrenfest urn and related random walks. J. Appl. Probab. 33 (1996), no. 2, 340--356. MR1385344 (97g:60014)

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.