论文标题
马尔可夫连锁链在有限的领域，具有确定性的跳跃
Markov chains on finite fields with deterministic jumps
论文作者
论文摘要
我们在$ \ mathbf {f} _p $上研究Markov链，通过应用功能$ f $并以同样的概率添加$ \pmγ$获得。当$ f $是线性函数时，这是经过良好研究的chung-diaconis-graham过程。我们考虑两种情况：当$ f $是一种有理函数的扩展时，当$ f（x）= x^2 $时。在后一种情况下，固定分布不统一，当$ p = 3 \ pmod {4} $时，我们将其表征。在这两种情况下，我们都在混合时间上给出了几乎线性的结合，表明确定性函数急剧加快了混合加速。证明涉及建立与短时间间隔的指数总和的界限。
We study the Markov chain on $\mathbf{F}_p$ obtained by applying a function $f$ and adding $\pmγ$ with equal probability. When $f$ is a linear function, this is the well-studied Chung--Diaconis--Graham process. We consider two cases: when $f$ is the extension of a rational function which is bijective, and when $f(x)=x^2$. In the latter case, the stationary distribution is not uniform and we characterize it when $p=3\pmod{4}$. In both cases, we give an almost linear bound on the mixing time, showing that the deterministic function dramatically speeds up mixing. The proofs involve establishing bounds on exponential sums over the union of short intervals.
