Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 14 open journal systems 


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: PDF

Pages: 374-395

Published on: March 10, 2008
Bibliography
  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
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489