Elementary potential theory on the hypercube

Gérard Ben Arous, Véronique Gayrard

Research output: Contribution to journalArticlepeer-review

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 ≥ α0N/log N for some constant 0 < α0 < 1.

Original languageEnglish (US)
Pages (from-to)1726-1807
Number of pages82
JournalElectronic Journal of Probability
Volume13
DOIs
StatePublished - Jan 1 2008

Keywords

  • Lumping
  • Random walk on hypercubes

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Elementary potential theory on the hypercube'. Together they form a unique fingerprint.

Cite this