Explicit Expanders with Cutoff Phenomena
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
- M. Ajtai, Recursive construction for 3-regular expanders, Combinatorica 14 (1994), no. 4, 379–416.
- D. Aldous, Random walks on finite groups and rapidly mixing Markov chains, Seminar on probability, XVII, 1983, pp. 243–297.
- D. Aldous and P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 ( 1986 ), 333–348.
- 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.
- N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96.
- N. Alon and V. D. Milman, λ1, isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88.
- N. Berestycki, Phase transitions for the distance of random walks and applications to genome rearrangement, Ph.D. dissertation, Cornell University (2005).
- G.-Y. Chen and L. Saloff-Coste, The cutoff phenomenon for ergodic Markov processes, Electronic Journal of Probability 13 (2008), 26–78.
- P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A. 93 (1996), no. 4, 1659–1664.
- P. Diaconis and M. Shahshahani, Generating a random permutation with random Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179.
- 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.
- J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794.
- R. Durrett, Random graph dynamics, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2007.
- S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), no. 4, 439–561.
- E. Lubetzky and A. Sly, Cutoff phenomena for random walks on random regular graphs, Duke Math. J. 153 (2010), no. 3, 475–510.
- Y. Peres, American Institute of Mathematics (AIM) research workshop “Sharp Thresholds for Mixing Times” (Palo Alto, December 2004).
- Y. Peres and D. B. Wilson. Private communication.
- 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.
- L. Saloff-Coste, Random walks on finite groups, Probability on discrete structures, 2004, pp. 263–346.
- A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82 (1989), no. 1, 93–133.
This work is licensed under a Creative Commons Attribution 3.0 License.