A non-local random walk on the hypercube

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In this paper we study the random walk on the hypercube (ℤ / 2ℤ)n which at each step flips k randomly chosen coordinates. We prove that the mixing time for this walk is of the order (n / k)logn. We also prove that if k = o(n) then the walk exhibits cutoff at (n / 2k)logn with window n / 2k.

Original languageEnglish (US)
Pages (from-to)1288-1299
Number of pages12
JournalAdvances in Applied Probability
Volume49
Issue number4
DOIs
StatePublished - Dec 1 2017

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Applied Mathematics

Keywords

  • Ehrenfest urn model
  • Hypercube
  • coupling
  • random walk

Fingerprint Dive into the research topics of 'A non-local random walk on the hypercube'. Together they form a unique fingerprint.

Cite this