Explicit Expanders with Cutoff Phenomena

Eyal Lubetzky (Microsoft Research)
Allan Sly (Microsoft Research)

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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 419-435

Publication Date: February 24, 2011

DOI: 10.1214/EJP.v16-869

References

  1. M. Ajtai, Recursive construction for 3-regular expanders, Combinatorica 14 (1994), no. 4, 379–416.
  2. D. Aldous, Random walks on finite groups and rapidly mixing Markov chains, Seminar on probability, XVII, 1983, pp. 243–297.
  3. D. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 ( 1986 ), 333–348.
  4. D. Aldous and J. A. Fill, Reversible Markov Chains and Random Walks on Graphs. In preparation, http://www.stat.berkeley.edu/~aldous/RWG/book.html.
  5. N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96.
  6. N. Alon and V. D. Milman, λ1, isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88.
  7. N. Berestycki, Phase transitions for the distance of random walks and applications to genome rearrangement, Ph.D. dissertation, Cornell University (2005).
  8. G.-Y. Chen and L. Saloff-Coste, The cutoff phenomenon for ergodic Markov processes, Electronic Journal of Probability 13 (2008), 26–78.
  9. P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1659–1664.
  10. P. Diaconis and M. Shahshahani, Generating a random permutation with random Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179.
  11. J. Ding, E. Lubetzky, and Y. Peres, Total-variation cutoff in birth-and-death chains, Probab. Theory Related Fields 146 (2010), no. 1, 61–85.
  12. J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794.
  13. R. Durrett, Random graph dynamics, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2007.
  14. S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), no. 4, 439–561.
  15. E. Lubetzky and A. Sly, Cutoff phenomena for random walks on random regular graphs, Duke Math. J. 153 (2010), no. 3, 475–510.
  16. Y. Peres, American Institute of Mathematics (AIM) research workshop “Sharp Thresholds for Mixing Times” (Palo Alto, December 2004).
  17. Y. Peres and D. B. Wilson. Private communication.
  18. O. Reingold, S. Vadhan, and A. Wigderson, Entropy waves, the zig-zag graph product and new constant-degree expanders, Ann. of Math. (2) 155 (2002), no. 1, 157–187.
  19. L. Saloff-Coste, Random walks on finite groups, Probability on discrete structures, 2004, pp. 263–346.
  20. A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82 (1989), no. 1, 93–133.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.