The power of two choices for random walks
The power of two choices for random walks
复制标题
随机游走的两种选择的威力
DOI：
10.1017/s0963548321000183
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Georgakopoulos A
中科院分区：
文献类型：
--
作者：
Georgakopoulos A
我们将两次选择的幂范式应用于图上的随机漫步：而不是在每一步移动到均匀随机邻居，控制器被允许从两个独立的均匀随机邻居中进行选择。我们证明了这允许控制器在几个自然图类中显著加速命中和覆盖时间。特别地，我们证明了在某个稀疏连接区域的Erdős-Rényi随机图上，在离散环面和有界度树上的n阶顶点的覆盖时间是线性的。我们还考虑了计算最优策略的算法问题，并证明了命中和掩护时间计算策略之间的效率二分法。
We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two independent uniform random neighbours. We prove that this allows the controller to significantly accelerate the hitting and cover times in several natural graph classes. In particular, we show that the cover time becomes linear in the number n of vertices on discrete tori and bounded degree trees, of order on the Erdős–Rényi random graph in a certain sparsely connected regime. We also consider the algorithmic question of computing an optimal strategy and prove a dichotomy in efficiency between computing strategies for hitting and cover times.