Limiting behavior for the distance of a random walk

Nathanael Berestycki (University of Cambridge)
Rick Durrett (Cornell University)

Abstract


In this paper we study some aspects of the behavior of random walks on large but finite graphs before they have reached their equilibrium distribution. This investigation is motivated by a result we proved recently for the random transposition random walk: the distance from the starting point of the walk has a phase transition from a linear regime to a sublinear regime at time $n/2$. Here, we study the examples of random 3-regular graphs, random adjacent transpositions, and riffle shuffles. In the case of a random 3-regular graph, there is a phase transition where the speed changes from 1/3 to 0 at time $3log_2 n$. A similar result is proved for riffle shuffles, where the speed changes from 1 to 0 at time $log_2 n$. Both these changes occur when a distance equal to the average diameter of the graph is reached. However in the case of random adjacent transpositions, the behavior is more complex. We find that there is no phase transition, even though the distance has different scalings in three different regimes.

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

Pages: 374-395

Publication Date: March 10, 2008

DOI: 10.1214/EJP.v13-490

References

  1. Aldous, David. Random walks on finite groups and rapidly mixing Markov chains. Seminar on probability, XVII, 243--297, Lecture Notes in Math., 986, Springer, Berlin, 1983. MR0770418 (86j:60156)
  2. Angel, Omer; Holroyd, Alexander E.; Romik, Dan. Directed random walk on the permutahedron. In preparation.
  3. Angel, Omer; Holroyd, Alexander E.; Romik, Dan; Vir·g, B·lint. Random sorting networks. Adv. Math. 215 (2007), no. 2, 839--868. MR2355610
  4. Bayer, Dave; Diaconis, Persi. Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2 (1992), no. 2, 294--313. MR1161056 (93d:60014)
  5. Berestycki, NathanaÎl. The hyperbolic geometry of random transpositions. Ann. Probab. 34 (2006), no. 2, 429--467. MR2223947 (2007h:60039)
  6. Berestycki, NathanaÎl; Durrett, Rick. A phase transition in the random transposition random walk. Probab. Theory Related Fields 136 (2006), no. 2, 203--233. MR2240787 (2007i:60009)
  7. Bollob·s, BÈla. Random graphs. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. xvi+447 pp. ISBN: 0-12-111755-3; 0-12-111756-1 MR0809996 (87f:05152)
  8. Bollob·s, BÈla. The isoperimetric number of random regular graphs. European J. Combin. 9 (1988), no. 3, 241--244. MR0947025 (89e:05180)
  9. Bollob·s, B.; Fernandez de la Vega, W. The diameter of random regular graphs. Combinatorica 2 (1982), no. 2, 125--134. MR0685038 (84c:05075)
  10. Chung, Fan; Lu, Linyuan. The diameter of sparse random graphs. Adv. in Appl. Math. 26 (2001), no. 4, 257--279. MR1826308 (2002c:05138)
  11. Diaconis, Persi. Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes---Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. vi+198 pp. ISBN: 0-940600-14-5 MR0964069 (90a:60001)
  12. Diaconis, Persi; Graham, R. L. Spearman's footrule as a measure of disarray. J. Roy. Statist. Soc. Ser. B 39 (1977), no. 2, 262--268. MR0652736 (58 #31575)
  13. Diaconis, Persi; Graham, R. L.; Morrison, J. A. Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures Algorithms 1 (1990), no. 1, 51--72. MR1068491 (91g:60078)
  14. Diaconis, Persi; Shahshahani, Mehrdad. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159--179. MR0626813 (82h:60024)
  15. Durrett, Rick. Shuffling chromosomes. J. Theoret. Probab. 16 (2003), no. 3, 725--750. MR2009200 (2004j:92045)
  16. Durrett, Rick. Genome rearrangement. Statistical methods in molecular evolution, 307--323, Stat. Biol. Health, Springer, New York, 2005. MR2161835 (2006f:92021)
  17. Durrett, R.; Neuhauser, C. Particle systems and reaction-diffusion equations. Ann. Probab. 22 (1994), no. 1, 289--333. MR1258879 (95d:60159)
  18. Eriksen, Niklas. Expected number of inversions after a sequence of random adjacent transpositions---an exact expression. Discrete Math. 298 (2005), no. 1-3, 155--168. MR2163446 (2006b:05008)
  19. H. Eriksson, K. Erikkson, and J. Sjostrand Expected number of inversions after k random adjacent transpositions. Formal power series and algebraic combinatorics. Proceedings of the 12th International Conference (FPSAC'00) held in Moscow, June 26--30, 2000. Edited by Daniel Krob, Alexander A. Mikhalev and Alexander V. Mikhalev. Springer-Verlag, Berlin, 2000. xiv+808 pp. ISBN: 3-540-67247-8 MR1798196 (2001f:05002)
  20. Fulman, Jason. Stein's method and descents after riffle shuffles. Electron. J. Probab. 10 (2005), no. 26, 901--924 (electronic). MR2164033 (2007b:60046)
  21. Kendall, David. Rank Correlation Methods, 1970, 4th edn. London: Griffin.
  22. Knuth, Donald. The Art of Computer Programming, Vol. 2. Reading, Mass.: Addison-Wiley.
  23. Saloff-Coste, Laurent. Random Walks on Finite Groups. In: Probability on discrete structures. Edited by Harry Kesten. Encyclopaedia of Mathematical Sciences, 110. Probability Theory, 1. Springer-Verlag, Berlin, 2004. x+351 pp. ISBN: 3-540-00845-4 MR2023649 (2004g:60003)
  24. N.C. Wormald. Models of random regular graphs (survey), 2005. Available at http://www.ms.unimelb.edu.au/$sim$nick/papers/regsurvey.pdf
Bookmark and Share


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