Asymptotic analysis of a random walk on a hypercube with many dimensions.

*(English)*Zbl 0723.60085Authors’ abstract: In nearest neighbor random walk on an n-dimensional cube a particle moves to one of its nearest neighbors (or stays fixed) with equal probability. The particle starts at 0. How long does it take to reach its stationary distribution? In fact, this occurs surprisingly rapidly. Previous analysis has shown that the total variation distance to stationarity is large if the number of steps N is \(\ll 4^{-1}n \log n\) and close to 0 if \(N\gg 4^{-1}n \log n\). This paper derives an explicit expression for the variation distance as \(n\to \infty\) in the transition region \(N\sim 4^{-1}n \log n\). This permits the first careful evaluation of a cutoff phenomenon observed in a wide variety of Markov chains. The argument involves Fourier analysis to express the probability as a contour integral and saddle point approximation. The asymptotic results are in good agreement with numerical results for n as small as 100.

Reviewer: S.Asmussen (Gothenburg)

##### MSC:

60G50 | Sums of independent random variables; random walks |

82C41 | Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics |

##### Keywords:

saddle point method; nearest neighbor random walk; stationary distribution; evaluation of a cutoff phenomenon; Fourier analysis
PDF
BibTeX
XML
Cite

\textit{P. Diaconis} et al., Random Struct. Algorithms 1, No. 1, 51--72 (1990; Zbl 0723.60085)

Full Text:
DOI

##### References:

[1] | and , Handbook of Mathematical Functions, National Bureau of Standards, Washington, DC, 1964, p. 886. |

[2] | (a) Random walk on finite groups and rapidly mixing Markov chains, in Seminaire de Probabilities XVII. Lecture Notes in Mathematics 986, Springer, New York, 1983, pp. 2113–2297. |

[3] | Aldous, Ann. Prob. 11 pp 403– (1983) |

[4] | Aldous, Amer. Math. Monthly 93 pp 333– (1986) |

[5] | Group Representations in Probability and Statistics, Institute of Mathematical Statistics, Hayward, CA, 1988. |

[6] | Diaconis, SIAM J. Math. Anal. 18 pp 208– (1987) |

[7] | Asymptotic Expansions, Dover, New York, 1956. · Zbl 0071.34702 |

[8] | An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd. ed., Wiley, New York, 1950, p. 52. |

[9] | Friedman, J. Soc. Indust. Appl. Math. 7 pp 280– (1959) |

[10] | Kac, Amer. Math. Monthly 54 pp 369– (1947) |

[11] | Probability and Related Topics in Physical Sciences, American Mathematical Society, Providence, RI. 1959. |

[12] | Letac, J. Reine Angew. Math. 310 pp 187– (1979) |

[13] | and , The Theory of Error Correcting Codes, North-Holland, Amsterdam, The Netherlands, 1977 |

[14] | , and , Formulas and Theorems for the Special Functions of Mathematical Physics, Springer-Verlag, New York, 1966. · doi:10.1007/978-3-662-11761-3 |

[15] | Mathews, SIAM J. Alg. Disc. Meth. 8 pp 746– (1987) |

[16] | Mathews, Theoretical Prob. (1988) |

[17] | (personal communication). |

[18] | (personal communication). |

[19] | Siegert, Phys. Rev. 76 pp 1708– (1949) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.