Explicit expanders with cutoff phenomena

Eyal Lubetzky, Allan Sly

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

The cutoff phenomenon describes a sharp transition in the convergence of an ergodic finite Markov chain to equilibrium. Of particular interest is understanding this convergence for the simple random walk on a bounded-degree expander graph. The first example of a family of bounded-degree graphs where the random walk exhibits cutoff in total-variation was provided only very recently, when the authors showed this for a typical random regular graph. However, no example was known for an explicit (deterministic) family of expanders with this phenomenon. Here we construct a family of cubic expanders where the random walk from a worst case initial position exhibits total-variation cutoff. Variants of this construction give cubic expanders without cutoff, as well as cubic graphs with cutoff at any prescribed time-point.

Original languageEnglish (US)
Pages (from-to)419-435
Number of pages17
JournalElectronic Journal of Probability
Volume16
DOIs
StatePublished - Jan 1 2011

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Cutoff phenomenon
  • Expander graphs
  • Explicit constructions
  • Random walks

Fingerprint Dive into the research topics of 'Explicit expanders with cutoff phenomena'. Together they form a unique fingerprint.

Cite this