论文标题
混合时间的时间 - diaconis- graham随机过程
Mixing time of the Chung--Diaconis--Graham random process
论文作者
论文摘要
在$ \ mathbf {z}/q \ mathbf {z} $上定义$（x_n）$ by $ x_ {n +1} = 2x_n +b_n $，其中步骤$ b_n $是从$ -1、0、0、 +1 $中独立选择的步骤$ b_n $。众所周知，此随机步行的混合时间最多为$ 1.02 \ log_2 q $，几乎所有奇数$ q $（chung-diaconis-graham，1987）和至少$ 1.004 \ log_2 q $（Hildebrand，2008年）。我们确定一个常数$ c = 1.01136 \ dots $，使混合时间为$（c+o（1））\ log_2 q $几乎所有奇数$ q $。 通常，马尔可夫链的混合时间$ x_ {n + 1} = a x_n + b_n $ modulo $ q $，其中$ a $是固定的正整数，而步骤$ b_n $是i.i.d. $ \ Mathbf {z} $中的一些给定分布与相应的类似类似cantor的度量（例如Bernoulli卷积）的熵有关。每当熵超过$（\ log a）/2 $时，我们将混合时间估计为$ 1+O（1）$。
Define $(X_n)$ on $\mathbf{Z}/q\mathbf{Z}$ by $X_{n+1} = 2X_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_2 q$ for almost all odd $q$ (Chung--Diaconis--Graham, 1987), and at least $1.004 \log_2 q$ (Hildebrand, 2008). We identify a constant $c = 1.01136\dots$ such that the mixing time is $(c+o(1))\log_2 q$ for almost all odd $q$. In general, the mixing time of the Markov chain $X_{n+1} = a X_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 $\mathbf{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$.
