The Dispersion Time of Random Walks on Finite Graphs
The Dispersion Time of Random Walks on Finite Graphs
复制标题
有限图上随机游走的分散时间
DOI：
10.1145/3323165.3323204
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sylvester
中科院分区：
文献类型：
--
作者：
Rivera;Sauerwald;Stauffer;Sylvester
我们研究了两个随机过程的n-顶点图的启发内扩散有限聚集（IDLA）模型。这些过程也可以被视为在分布式服务器网络中分配作业的协议。在这两个过程中，n个粒子都从一个任意但固定的原点开始。每个粒子执行一个简单的随机游走，直到它第一次遇到一个未被占用的顶点，此时顶点被占用，随机游走终止。在其中一个过程中，称为顺序IDLA，单个颗粒移动直到沉降，然后才开始下一个颗粒，而在第二个过程中，称为顺序IDLA，所有未沉降的颗粒同时移动。第二个过程类似于并行运行第一个过程。我们的主要目标是分析这些过程的所谓分散时间，这是由n个粒子中的任何一个执行的步骤的最大数量。为了比较这两个过程中，我们开发了一个耦合，这表明分散时间的顺序IDLA的顺序IDLA的随机占主导地位，但是，所有粒子进行的步骤的总数在两个过程中具有相同的分布。这种耦合也给我们，序列IDLA的色散时间的预期是有界的序列IDLA的色散时间的乘法的双对数n因子。此外，我们得到了几个图类，如团，圈，二叉树，d-维网格，超立方体和扩张的色散时间的渐近上界和下界。我们的大多数边界都紧到一个乘法常数。
We study two random processes on an n-vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. These processes can also be regarded as protocols for allocating jobs in a distributed network of servers. In both processes n particles start from an arbitrary but fixed origin. Each particle performs a simple random walk until it first encounters an unoccupied vertex, at which point the vertex becomes occupied and the random walk terminates. In one of the processes, called Sequential-IDLA, a single particle moves until settling and only then does the next particle start whereas in the second process, called Parallel-IDLA, all unsettled particles move simultaneously. The second process is akin to running the first in parallel. Our main goal is to analyze the so-called dispersion time of these processes, which is the maximum number of steps performed by any of the n particles. In order to compare the two processes, we develop a coupling which shows the dispersion time of the Parallel-IDLA stochastically dominates that of the Sequential-IDLA; however, the total number of steps performed by all particles has the same distribution in both processes. This coupling also gives us that dispersion time of Parallel-IDLA is bounded in expectation by dispersion time of the Sequential-IDLA up to a multiplicative łog n factor. Moreover, we derive asymptotic upper and lower bound on the dispersion time for several graph classes, such as cliques, cycles, binary trees, d-dimensional grids, hypercubes and expanders. Most of our bounds are tight up to a multiplicative constant.
登录
查看更多内容
动态图上随机游走的覆盖时间和混合时间
DOI：
--
发表时间：
2018
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
C. Avin;M. Koucký;Zvi Lotker
通讯作者：
Zvi Lotker
内部 DLA 需要多长时间才能忘记其初始配置文件？
影响因子：
2
作者：
Lionel Levine;Vittoria Silvestri
通讯作者：
Vittoria Silvestri
DOI：
--
发表时间：
1986
期刊：
影响因子：
--
作者：
P. Meakin;J. Deutch
通讯作者：
J. Deutch
传递图上激活随机游走的临界密度
影响因子：
2.3
作者：
Alexandre O. Stauffer;L. Taggi
通讯作者：
L. Taggi
内部 DLA 的亚对数波动
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
A. Asselah;A. Gaudilliere
通讯作者：
A. Gaudilliere