Mixing time of the Chung–Diaconis–Graham random process

Sean Eberhard; Péter P. Varjú

doi:10.1007/s00440-020-01009-1

Mixing time of the Chung–Diaconis–Graham random process

Sean Eberhard
, Péter P. Varjú^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

Abstract

Define (X_n) on Z/ qZ by X_n₊₁= 2 X_n+ b_n, where the steps b_n are chosen independently at random from - 1 , 0 , + 1. The mixing time of this random walk is known to be at most 1.02 log ₂q for almost all odd q (Chung, Diaconis, Graham in Ann Probab 15(3):1148–1165, 1987), and at least 1.004 log ₂q (Hildebrand in Proc Am Math Soc 137(4):1479–1487, 2009). We identify a constant c= 1.01136 ⋯ such that the mixing time is (c+ o(1)) log ₂q for almost all odd q. In general, the mixing time of the Markov chain X_n₊₁= aX_n+ b_n modulo q, where a is a fixed positive integer and the steps b_n are i.i.d. with some given distribution in Z, is related to the entropy of a corresponding self-similar Cantor-like measure (such as a Bernoulli convolution). We estimate the mixing time up to a 1 + o(1) factor whenever the entropy exceeds (log a) / 2.

Original language	English
Pages (from-to)	317-344
Number of pages	28
Journal	Probability Theory and Related Fields
Volume	179
Issue number	1-2
Early online date	10 Oct 2020
DOIs	https://doi.org/10.1007/s00440-020-01009-1
Publication status	Published - Feb 2021
Externally published	Yes

Bibliographical note

Funding Information:
Sean Eberhard and Péter P. Varjú have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 803711). PV was supported by the Royal Society.

Publisher Copyright:
© 2020, Springer-Verlag GmbH Germany, part of Springer Nature.

ASJC Scopus subject areas

Analysis
Statistics and Probability
Statistics, Probability and Uncertainty

Access to Document

10.1007/s00440-020-01009-1Licence: Unspecified

Cite this

@article{8d1d69b487fc47a3930a615141bed8d1,

title = "Mixing time of the Chung–Diaconis–Graham random process",

abstract = "Define (Xn) on Z/ qZ by Xn+1= 2 Xn+ bn, where the steps bn are chosen independently at random from - 1 , 0 , + 1. The mixing time of this random walk is known to be at most 1.02 log 2q for almost all odd q (Chung, Diaconis, Graham in Ann Probab 15(3):1148–1165, 1987), and at least 1.004 log 2q (Hildebrand in Proc Am Math Soc 137(4):1479–1487, 2009). We identify a constant c= 1.01136 ⋯ such that the mixing time is (c+ o(1)) log 2q for almost all odd q. In general, the mixing time of the Markov chain Xn+1= aXn+ bn modulo q, where a is a fixed positive integer and the steps bn are i.i.d. with some given distribution in Z, is related to the entropy of a corresponding self-similar Cantor-like measure (such as a Bernoulli convolution). We estimate the mixing time up to a 1 + o(1) factor whenever the entropy exceeds (log a) / 2.",

author = "Sean Eberhard and Varj{\'u}, \{P{\'e}ter P.\}",

note = "Funding Information: Sean Eberhard and P{\'e}ter P. Varj{\'u} have received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (Grant Agreement No. 803711). PV was supported by the Royal Society. Publisher Copyright: {\textcopyright} 2020, Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2021",

month = feb,

doi = "10.1007/s00440-020-01009-1",

language = "English",

volume = "179",

pages = "317--344",

journal = "Probability Theory and Related Fields",

issn = "0178-8051",

publisher = "Springer New York",

number = "1-2",

}

TY - JOUR

T1 - Mixing time of the Chung–Diaconis–Graham random process

AU - Eberhard, Sean

AU - Varjú, Péter P.

N1 - Funding Information: Sean Eberhard and Péter P. Varjú have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 803711). PV was supported by the Royal Society. Publisher Copyright: © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2021/2

Y1 - 2021/2

N2 - Define (Xn) on Z/ qZ by Xn+1= 2 Xn+ bn, where the steps bn are chosen independently at random from - 1 , 0 , + 1. The mixing time of this random walk is known to be at most 1.02 log 2q for almost all odd q (Chung, Diaconis, Graham in Ann Probab 15(3):1148–1165, 1987), and at least 1.004 log 2q (Hildebrand in Proc Am Math Soc 137(4):1479–1487, 2009). We identify a constant c= 1.01136 ⋯ such that the mixing time is (c+ o(1)) log 2q for almost all odd q. In general, the mixing time of the Markov chain Xn+1= aXn+ bn modulo q, where a is a fixed positive integer and the steps bn are i.i.d. with some given distribution in Z, is related to the entropy of a corresponding self-similar Cantor-like measure (such as a Bernoulli convolution). We estimate the mixing time up to a 1 + o(1) factor whenever the entropy exceeds (log a) / 2.

AB - Define (Xn) on Z/ qZ by Xn+1= 2 Xn+ bn, where the steps bn are chosen independently at random from - 1 , 0 , + 1. The mixing time of this random walk is known to be at most 1.02 log 2q for almost all odd q (Chung, Diaconis, Graham in Ann Probab 15(3):1148–1165, 1987), and at least 1.004 log 2q (Hildebrand in Proc Am Math Soc 137(4):1479–1487, 2009). We identify a constant c= 1.01136 ⋯ such that the mixing time is (c+ o(1)) log 2q for almost all odd q. In general, the mixing time of the Markov chain Xn+1= aXn+ bn modulo q, where a is a fixed positive integer and the steps bn are i.i.d. with some given distribution in Z, is related to the entropy of a corresponding self-similar Cantor-like measure (such as a Bernoulli convolution). We estimate the mixing time up to a 1 + o(1) factor whenever the entropy exceeds (log a) / 2.

U2 - 10.1007/s00440-020-01009-1

DO - 10.1007/s00440-020-01009-1

M3 - Article

AN - SCOPUS:85092340572

SN - 0178-8051

VL - 179

SP - 317

EP - 344

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

IS - 1-2

ER -

Mixing time of the Chung–Diaconis–Graham random process

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this