The-Square-and-Add Markov Chain
The-Square-and-Add Markov Chain
复制标题
平方加马尔可夫链
DOI：
10.1007/s00283-021-10058-w
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Martin Isaacs, I.
中科院分区：
文献类型：
--
作者：
Diaconis, Persi;He, Jimmy;Martin Isaacs, I.
让我们从一个我们无法解决的问题开始开始。如果q是素数幂，我们写Fq来表示有q个元素的域，所以如果p是素数，Fp是整数模p的域。随着时间的推移，这收敛到Fp上的均匀分布。这意味着，经过很长一段时间后，随机游走将在某个a2 Fp处的概率约为1/p。这种收敛大约需要p2步。这很慢：如果p = 101，那么p2 = 10 201。这些非正式的陈述在下面的定理1之后更仔细地解释。一种加快速度的尝试是将确定性加倍与随机的101步相结合。如果Xn表示n步后的行走位置（比如从X 0开始），则这个新行走是
L et us begin with a problem we cannot solve. If q is a prime power, we write Fq to denote the field with q elements, so if p is prime, Fp is the field of integers modulo p. A simple random walk (drunkard’s walk) on Fp goes from j to j þ 1 or j Ā 1 with probability 1/2. As time goes on, this converges to the uniform distribution on Fp. This means that after a long time, the probability that the random walk will be at some a 2 Fp is about 1/p. It takes about p2 steps for this convergence to kick in. This is slow: if p ž 101, then p2 ž 10 201. These informal statements are explained more carefully after Theorem 1 below. One attempt to speed things up intersperses deterministic doubling with the random Æ1 steps. If Xn denotes the position of the walk after n steps (say starting from X0 ž 0), then this new walk is
登录
查看更多内容
影响因子：
2
作者：
S. Chatterjee;P. Diaconis
通讯作者：
S. Chatterjee;P. Diaconis
具有确定性跳跃的有限域上的马尔可夫链
影响因子：
1.4
作者：
Jimmy He
通讯作者：
Jimmy He
影响因子：
0.7
作者：
S. Lenwood;A. L. Nicholas
通讯作者：
A. L. Nicholas
与过去的耦合
影响因子：
0.7
作者：
D. A. Levin;Y. Peres;Elizabeth L. Wilmer
通讯作者：
Elizabeth L. Wilmer
随机数生成中出现的随机游走
影响因子：
2.3
作者：
F. Chung;P. Diaconis;R. Graham
通讯作者：
R. Graham