论文标题
Chung-diaconis-Graham随机过程的多重对称版本
A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process
论文作者
论文摘要
本文考虑了$ x_ {n+1}表格的随机过程$ p（a_n = 2）= p（a_n =（p+1）/2）= 1/2 $和$ p（b_n = 1）= p（b_n = 0）= p（b_n = -1）= 1/3 $。这可以看作是Chung，Diaconis和Graham的随机过程的多重对称版本。本文表明，对于$ x_n $的订单$（\ log p）^2 $台阶就足以接近所有奇数$ p $的整数上的均匀分布，而订单$（\ log p）^2 $ step对于$ x_n $来说是必要的，即可在整数上均匀分布在整数mod $ p $上。
This paper considers random processes of the form $X_{n+1}=a_nX_n+b_n \pmod p$ where $p$ is odd, $X_0=0$, $(a_0,b_0), (a_1,b_1), (a_2,b_2),...$ are i.i.d., and $a_n$ and $b_n$ are independent with $P(a_n=2)=P(a_n=(p+1)/2)=1/2$ and $P(b_n=1)=P(b_n=0)=P(b_n=-1)=1/3$. This can be viewed as a multiplicatively symmetrized version of a random process of Chung, Diaconis, and Graham. This paper shows that order $(\log p)^2$ steps suffice for $X_n$ to be close to uniformly distributed on the integers mod $p$ for all odd $p$ while order $(\log p)^2$ steps are necessary for $X_n$ to be close to uniformly distributed on the integers mod $p$.
