RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2023 Volume 214, Number 6, Pages 136–154 (Mi sm9811)

On the multiplicative Chung-Diaconis-Graham process

I. D. Shkredov

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia

Abstract: We study the lazy Markov chain on $\mathbb{F}_p$ defined as follows: $X_{n+1}=X_n$ with probability $1/2$ and $X_{n+1}=f(X_n) \cdot \varepsilon_{n+1}$, where the $\varepsilon_n$ are random variables distributed uniformly on the set $\{\gamma, \gamma^{-1}\}$, $\gamma$ is a primitive root and $f(x)=x/(x-1)$ or $f(x)=\mathrm{ind}(x)$. Then we show that the mixing time of $X_n$ is $\exp(O(\log p \cdot \log \log \log p/ \log \log p))$. Also, we obtain an application to an additive-combinatorial question concerning a certain Sidon-type family of sets.
Bibliography: 34 titles.

Keywords: Markov chains, Chung-Diaconis-Graham process, mixing time, incidence geometry, Sidon sets.

MSC: Primary 11B13, 60B15, 60G50, 60J10; Secondary 05B10

Received: 13.07.2022 and 09.11.2022

DOI: 10.4213/sm9811


 English version:
Sbornik: Mathematics, 2023, 214:6, 878–895

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025