Geodesic
On the multiplicative Chung-Diaconis-Graham process
Sbornik. Mathematics, Tome 214 (2023) no. 6, pp. 878-895

Voir la notice de l'article provenant de la source Math-Net.Ru

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: Chung-Diaconis-Graham process, mixing time, incidence geometry
Mots-clés : Markov chains, Sidon sets. 
@article{SM_2023_214_6_a5,
     author = {I. D. Shkredov},
     title = {On the multiplicative {Chung-Diaconis-Graham} process},
     journal = {Sbornik. Mathematics},
     pages = {878--895},
     publisher = {mathdoc},
     volume = {214},
     number = {6},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2023_214_6_a5/}
}
TY  - JOUR
AU  - I. D. Shkredov
TI  - On the multiplicative Chung-Diaconis-Graham process
JO  - Sbornik. Mathematics
PY  - 2023
SP  - 878
EP  - 895
VL  - 214
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SM_2023_214_6_a5/
LA  - en
ID  - SM_2023_214_6_a5
ER  - 
%0 Journal Article
%A I. D. Shkredov
%T On the multiplicative Chung-Diaconis-Graham process
%J Sbornik. Mathematics
%D 2023
%P 878-895
%V 214
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SM_2023_214_6_a5/
%G en
%F SM_2023_214_6_a5
I. D. Shkredov. On the multiplicative Chung-Diaconis-Graham process. Sbornik. Mathematics, Tome 214 (2023) no. 6, pp. 878-895. http://geodesic.mathdoc.fr/item/SM_2023_214_6_a5/