Deterministic random walks on finite graphs
Deterministic random walks on finite graphs
复制标题
有限图上的确定性随机游走
DOI：
10.1002/rsa.20533
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Kazuhisa Makino
中科院分区：
文献类型：
--
作者：
Shuji Kijima;Kentaro Koga;Kazuhisa Makino
转子-路由器模型，也被称为Propp机器，是一个类似于图上随机游走的确定性过程。Propp机器不是将令牌分配给随机选择的邻居，而是通过将每个顶点关联到指向其邻居之一的“转子路由器”，以固定的顺序确定地为邻居提供服务。对于一般有限图，本文研究了转子-路由器模型中单个顶点的令牌数与随机游走中期望令牌数之间的差异。我们证明，对于任意初始配置，如果相应的随机漫步是惰性的和可逆的，在任何时间，差异以O （mn）为界，其中n和m分别表示节点和边的数量。对于下界，我们展示了在任意时刻（> 0）单个顶点处的差异为Ω(m)的图和初始配置示例。对于一些特殊的图，即超立方体骨架和Johnson图，我们给出了一个多对数上界，根据节点的数量，对于差异。©2014 Wiley期刊公司随机结构。Alg。中文信息学报，46,739-761,2015
The rotor‐router model, also known as the Propp machine, is a deterministic process analogous to a random walk on a graph. Instead of distributing tokens to randomly chosen neighbors, the Propp machine deterministically serves the neighbors in a fixed order by associating to each vertex a “rotor‐router” pointing to one of its neighbors. This paper investigates the discrepancy at a single vertex between the number of tokens in the rotor‐router model and the expected number of tokens in a random walk, for finite graphs in general. We show that the discrepancy is bounded by O (mn) at any time for any initial configuration if the corresponding random walk is lazy and reversible, where n and m denote the numbers of nodes and edges, respectively. For a lower bound, we show examples of graphs and initial configurations for which the discrepancy at a single vertex is Ω(m) at any time (> 0). For some special graphs, namely hypercube skeletons and Johnson graphs, we give a polylogarithmic upper bound, in terms of the number of nodes, for the discrepancy. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,739–761, 2015