Deterministic random walks on the integers
Deterministic random walks on the integers
复制标题
整数上的确定性随机游走
DOI：
10.1016/j.ejc.2007.04.018
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Gábor Tardos
中科院分区：
文献类型：
--
作者：
Joshua N. Cooper;Benjamin Doerr;Joel H. Spencer;Gábor Tardos
吉姆·普罗普（Jim Propp）的P-machine，也被称为“转子路由器模型”，是一个简单的确定性过程，它模拟了图上的随机游走。它不是将芯片随机分配给随机选择的邻居，而是以固定的顺序为邻居提供服务。我们研究这个过程如何很好地模拟随机漫步。对于作为无限路径的图，我们证明，与起始配置无关，在每个时间和每个顶点上，该顶点上的芯片数量与随机行走模型中期望的芯片数量最多偏离一个常数c1，约为2.29。对于长度为L的区间，差值提高到O(logL)，对于连续区间集的L2average，差值甚至提高到O（logL）。所有这些界限都很紧。
Jim Propp’s P-machine, also known as the ‘rotor router model’, is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order. We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant c1, which is approximately 2.29. For intervals of length L, this improves to a difference of O(logL), for the L2average of a contiguous set of intervals even to O(logL). All these bounds are tight.