Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T08:14:20.014Z Has data issue: false hasContentIssue false
  • English
  • Français

A non-local random walk on the hypercube

Part of: Markov processes Combinatorial probability

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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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
Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 4 , December 2017 , pp. 1288 - 1299
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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