Elementary potential theory on the hypercube. (English) Zbl 1187.82105

Gayrard, Véronique; Ben Arous, Gérard

Electron. J. Probab. 13, 1726-1807 (2008).

Summary: 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\to \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 a_0 (N/\log N)\) for some constant \(0<a_0<1\).

MSC:

82C44	Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics
60K35	Interacting random processes; statistical mechanics type models; percolation theory

Keywords:

random walk on hypercubes; lumping