Markov chains on finite fields with deterministic jumps
Markov chains on finite fields with deterministic jumps
复制标题
具有确定性跳跃的有限域上的马尔可夫链
DOI：
10.1214/22-ejp757
复制
发表时间：
2020
影响因子：
1.4
通讯作者：
Jimmy He
中科院分区：
文献类型：
--
作者：
Jimmy He
研究了$\mathbf{F}_p$上的马氏链，该马氏链是通过应用一个函数$f$并以等概率添加$\pm\gamma$得到的。当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\gamma$ 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.
影响因子：
2
作者：
S. Chatterjee;P. Diaconis
通讯作者：
S. Chatterjee;P. Diaconis
平方加马尔可夫链
DOI：
10.1007/s00283-021-10058-w
发表时间：
2021
期刊：
The Mathematical Intelligencer
影响因子：
--
作者：
Diaconis, Persi;He, Jimmy;Martin Isaacs, I.
通讯作者：
Martin Isaacs, I.