Skip to main content

Limiting behavior for the distance of a random walk

Publication ,  Journal Article
Berestycki, N; Durrett, R
Published in: Electronic Journal of Probability
January 1, 2008

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

Duke Scholars

Published In

Electronic Journal of Probability

DOI

EISSN

1083-6489

Publication Date

January 1, 2008

Volume

13

Start / End Page

374 / 395

Related Subject Headings

  • Statistics & Probability
  • 0105 Mathematical Physics
  • 0104 Statistics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Berestycki, N., & Durrett, R. (2008). Limiting behavior for the distance of a random walk. Electronic Journal of Probability, 13, 374–395. https://doi.org/10.1214/EJP.v13-490
Berestycki, N., and R. Durrett. “Limiting behavior for the distance of a random walk.” Electronic Journal of Probability 13 (January 1, 2008): 374–95. https://doi.org/10.1214/EJP.v13-490.
Berestycki N, Durrett R. Limiting behavior for the distance of a random walk. Electronic Journal of Probability. 2008 Jan 1;13:374–95.
Berestycki, N., and R. Durrett. “Limiting behavior for the distance of a random walk.” Electronic Journal of Probability, vol. 13, Jan. 2008, pp. 374–95. Scopus, doi:10.1214/EJP.v13-490.
Berestycki N, Durrett R. Limiting behavior for the distance of a random walk. Electronic Journal of Probability. 2008 Jan 1;13:374–395.

Published In

Electronic Journal of Probability

DOI

EISSN

1083-6489

Publication Date

January 1, 2008

Volume

13

Start / End Page

374 / 395

Related Subject Headings

  • Statistics & Probability
  • 0105 Mathematical Physics
  • 0104 Statistics