No CrossRef data available.
Article contents
Fast mixing of a randomized shift-register Markov chain
Published online by Cambridge University Press: 02 September 2022
Abstract
We present a Markov chain on the n-dimensional hypercube
$\{0,1\}^n$
which satisfies
$t_{{\rm mix}}^{(n)}(\varepsilon) = n[1 + o(1)]$
. This Markov chain alternates between random and deterministic moves, and we prove that the chain has a cutoff with a window of size at most
$O(n^{0.5+\delta})$
, where
$\delta>0$
. The deterministic moves correspond to a linear shift register.
MSC classification
- Type
- Original Article
- Information
- Copyright
- © The Author(s), 2022. Published by Cambridge University Press on behalf of Applied Probability Trust
References
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20230208165938590-0012:S0021900222000377:S0021900222000377_inline442.png?pub-status=live)