Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T09:39:33.569Z Has data issue: false hasContentIssue false
  • English
  • Français

A non-local random walk on the hypercube

Part of: Combinatorial probability Markov processes

Published online by Cambridge University Press:  17 November 2017

Evita Nestoridi
Evita Nestoridi*
Affiliation:
Stanford University
*
* Current address: Department of Mathematics, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544-1000, USA. Email address: exn@princeton.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we study the random walk on the hypercube (ℤ / 2ℤ)n which at each step flips k randomly chosen coordinates. We prove that the mixing time for this walk is of the order (n / k)logn. We also prove that if k = o(n) then the walk exhibits cutoff at (n / 2k)logn with window n / 2k.

Keywords

Hypercubecouplingrandom walkEhrenfest urn model

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60C05: Combinatorial probability

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 4 , December 2017 , pp. 1288 - 1299
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Aldous, D. (1983). Minimization algorithms and random walk on the d-cube. Ann. Prob. 11, 403–413. Google Scholar
[2] Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. In Seminar on Probability, XVII (Lecture Notes Math. 986), Springer, pp. 243–297. Google Scholar
[3] Aldous, D. and Diaconis, P. (1986). Shuffling cards and stopping times. Amer. Math. Monthly 93, 333–348. Google Scholar
[4] Andersen, H. C. and Diaconis, P. (2007). Hit and run as a unifying device. J. Soc. Fr. Statist. Rev. Statist. Appl. 148, 5–28. Google Scholar
[5] Bubley, R. and Dyer, M. (1997). Path coupling: a technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, IEEE, pp. 223–231. Google Scholar
[6] Diaconis, P. (1988). Group Representations in Probability and Statistics (Inst. Math. Statist. Lecture Notes Monogr. Ser. 11). Institute of Mathematical Statistics, Hayward, CA. Google Scholar
[7] Diaconis, P. and Saloff-Coste, L. (1993). Comparison techniques for random walk on finite groups. Ann. Prob. 21, 2131–2156. Google Scholar
[8] Diaconis, P. and Shahshahani, M. (1987). Time to reach stationarity in the Bernoulli–Laplace diffusion model. SIAM J. Math. Anal. 18, 208–218. Google Scholar
[9] Diaconis, P., Graham, R. L. and Morrison, J. A. (1990). Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures Algorithms 1, 51–72. Google Scholar
[10] Ehrenfest, P. and Ehrenfest, T. (1907). Über zwei bekannte einwände gegen das Boltzmannsche H-theorem. Phys. Z. 8, 311–314. Google Scholar
[11] Kac, M. (1947). Random walk and the theory of Brownian motion. Amer. Math. Monthly 54, 369–391. Google Scholar
[12] Koekoek, R. and Swarttouw, R. F. (1996). The Askey-scheme of hypergeometric orthogonal polynomials and its q-analogue. Preprint. Available at https://arxiv.org/abs/maths/9602214. Google Scholar
[13] Saloff-Coste, L. (2004). Random walks on finite groups. In Probability on Discrete Structures, Springer, Berlin, pp. 263–346. Google Scholar
[14] Saloff-Coste, L. (2004). Total variation lower bounds for finite Markov chains: Wilson's lemma. In Random Walks and Geometry, De Gruyter, Berlin, pp. 515–532. Google Scholar
[15] Sinclair, A. (2009). Markov chain Monte Carlo: foundations & applications. Available at https://people.eecs.berkeley.edu/~sinclair/cs294/f09.html. Google Scholar
[16] Wilson, D. B. (2003). Mixing time of the Rudvalis shuffle. Electron. Commun. Prob. 8, 77–85. Google Scholar