The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off


  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,
  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.

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