 |
|
|
| | | | | |
|
|
|
|
|
Elementary potential theory on the hypercube.
|
Véronique Gayrard, CNRS
Gérard Ben Arous, Courant Institute for mathematical Sciences, NYU
|
Abstract
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⊂{-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→∞$.
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≤ a_0 (N/log N) for some constant 0
|
Full text: PDF
Pages: 1726-1807
Published on: October 4, 2008
|
Bibliography
- 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)
- 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)
- Aldous, David; Diaconis, Persi. Strong uniform times and finite random walks. Adv. in Appl. Math. 8 (1987), no. 1, 69--97. MR0876954 (88d:60175)
- Aldous, David; Diaconis, Persi. Shuffling cards and stopping times. Amer. Math. Monthly 93 (1986), no. 5, 333--348. MR0841111 (88a:60021)
- Ben Arous, G.; Bovier, A.; Gayrard,V. ``Aging in the random energy model'', Phys. Rev. Letts. 88, 087201 (2002).
- 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)
- 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)
- 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
- 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)
- 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)
- 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)
- 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)
- Gayrard, V. ``Glauber dynamics of the 2-GREM. 1. Metastable motion on the extreme states.'', preprint (2007).
- Burke, C. J.; Rosenblatt, M. A Markovian function of a Markov chain. Ann. Math. Statist. 29 1958 1112--1122. MR0101557 (21 #367)
- Comtet, Louis. Analyse combinatoire. Tomes I, II.(French) Collection SUP: ``Le Mathématicien'', 4, 5 Presses Universitaires de France, Paris 1970 Vol. I: 192 pp.; Vol. II: 190 pp. MR0262087 (41 #6697)
- 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)
- 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)
- 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)
- 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)
- W. Feller, An Introduction to Probability Theory and Its Applications, Volume 2, John Wiley and Sons, Inc. New York, 1970.
- 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)
- 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)
- 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)
- Matthews, Peter. ``Covering problems for Markov chains'' Ann. Probab. 16, 1215--1228 (1988).
- 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)
- 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)
- 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)
- 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)
- Voit, Michael. Asymptotic distributions for the Ehrenfest urn and related random walks. J. Appl. Probab. 33 (1996), no. 2, 340--356. MR1385344 (97g:60014)
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context