Math @ Duke

Publications [#243540] of Richard T. Durrett
Papers Published
 Berestycki, N; Durrett, R, Limiting behavior for the distance of a random walk,
Electronic Journal of Probability, vol. 13
(January, 2008),
pp. 374395, Institute of Mathematical Statistics, ISSN 10836489 [MR2386737 (2009d:60130)], [doi]
(last updated on 2019/04/22)
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 3regular graphs, random adjacent transpositions, and riffle shuffles. In the case of a random 3regular graph, there is a phase transition where the speed changes from 1/3 to 0 at time 3 log2 n. A similar result is proved for riffle shuffles, where the speed changes from 1 to 0 at time log2 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. © 2008 Applied Probability Trust.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

