Abstract
A class of families of Markov chains defined on the vertices of the n-dimensional hypercube, Ω n ={0,1}n, is studied. The single-step transition probabilities P n,ij , with i,j∈Ω n , are given by \(P_{n,ij}=\frac{(1-{\alpha})^{d_{ij}}}{(2-{\alpha})^{n}}\), where α∈(0,1) and d ij is the Hamming distance between i and j. This corresponds to flip independently each component of the vertex with probability \(\frac{1-{\alpha}}{2-{\alpha}}\). The m-step transition matrix \(P_{n,ij}^{m}\) is explicitly computed in a close form. The class is proved to exhibit cutoff. A model-independent result about the vanishing of the first m terms of the expansion in α of \(P_{n,ij}^{m}\) is also proved.
Article PDF
Avoid common mistakes on your manuscript.
References
Aldous, D., Diaconis, P.: Shuffling cards and stopping times. Am. Math. Mon. 93, 333–348 (1986)
Barrera, J., Bertoncini, O., Fernández, R.: Abrupt convergence and escape behavior for birth and death chains. J. Stat. Phys. 137, 595–623 (2009)
Bayer, D., Diaconis, P.: Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2, 294–313 (1992)
Diaconis, P.: The cutoff phenomenon in finite Markov chains. Proc. Natl. Acad. Sci. USA 93, 1659–1664 (1996)
Diaconis, P., Shahshahani, M.: Generating a random permutation with random transpositions. Z. Wahrscheinlichkeitstheor. Verw. Geb. 57(2), 159–179 (1981)
Diaconis, P., Graham, R.L., Morrison, J.A.: Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Struct. Algorithms 1, 51–72 (1990)
Ding, J., Lubetzky, E., Peres, Y.: Total-variation cutoff in birth-and-death chains. Arxiv preprint. arXiv:0801.2625 (2008)
Lancia, C., Scoppola, B.: Entropy driven cutoff phenomenon, in preparation
Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. AMS, Providence (2009)
Levin, D.A., Luczak, M.J., Peres, Y.: Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probab. Theory Relat. Fields 146, 223–265 (2010)
Lubetzky, E., Sly, A.: Cutoff for the Ising model on the lattice. Arxiv preprint. arXiv:0909.4320 (2009)
Lubetzky, E., Sly, A.: Critical Ising on the square lattice mixes in polynomial time. Arxiv preprint. arXiv:1001.1613 (2010)
Martinez, S., Ycart, B.: Decaying rates and cutoff for convergence and hitting times of Markov chains. Adv. Appl. Probab. 33, 188–205 (2001)
Wilson, D.B.: Random walks on \(\mathbf{Z}_{2}^{d}\). Probab. Theory Relat. Fields 108, 441–457 (1997)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Scoppola, B. Exact Solution for a Class of Random Walk on the Hypercube. J Stat Phys 143, 413–419 (2011). https://doi.org/10.1007/s10955-011-0194-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10955-011-0194-y