Random walks supported on random points ofZ/nZ
Random walks supported on random points ofZ/nZ
复制标题
Z/nZ 随机点支持随机游走
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
M. Hildebrand
中科院分区：
文献类型：
--
作者：
M. Hildebrand
本文考虑了整数模上的随机游动，并询问这些游动需要多长时间才能接近均匀分布。Ifk是一个常数，Greenhalgh证明了至少有一些固定的时间n2/(k−1)步长是使随机游动与均匀分布的距离变小所必需的；这里我们证明了干扰素是质数，一些固定的时间n2/(k−1)步长足以使这个距离对于几乎所有的K点选择都很小。该证明利用Diaconis和Shahshahani的上界引理和一些平均技巧。本文还探讨了k随n变化的几种情况。特别地，如果k=⌊(Logn)a⌋，对于不同的a值，我们得到了不同类型的结果，这些结果推翻了Aldous和Diaconis的一个猜想。
SummaryThis paper considers random walks on the integers modn supported onk points and asks how long does it take for these walks to get close to uniformly distributed. Ifk is a constant, Greenhalgh showed that at least some constant timesn2/(k−1) steps are necessary to make the distance of the random walk from the uniform distribution small; here we show that ifn is prime, some constant timesn2/(k−1) steps suffice to make this distance small for almost all choices ofk points. The proof uses the Upper Bound Lemma of Diaconis and Shahshahani and some averaging techniques. This paper also explores some cases wherek varies withn. In particular, ifk=⌊(logn)a⌋, we find different kinds of results for different values ofa, and these results disprove a conjecture of Aldous and Diaconis.