论文标题
时间依赖的偏见随机步行
Time Dependent Biased Random Walks
论文作者
论文摘要
我们研究偏见的随机步行，在随机步行的每个步骤中，“控制器”可以以一定的概率将步行移至任意邻居。该模型由Azar等人引入。 [Stoc'1992];我们将他们的工作扩展到时间依赖的设置，并考虑这次步行的覆盖时间。我们在封面上获得了新的界限和击打时间。 Azar等。猜想控制器可以将顶点的固定概率从$ p $增加到$ p^{1-ε} $;尽管这种猜想在完全的一般性中并非如此，但我们提出了这个猜想的最佳修订版本，并确认了一系列图形。 我们还考虑了计算控制器的最佳策略的问题，以最大程度地减少覆盖时间，并表明确定盖子时间的有向图是Pspace complete。
We study the biased random walk where at each step of a random walk a "controller" can, with a certain small probability, move the walk to an arbitrary neighbour. This model was introduced by Azar et al. [STOC'1992]; we extend their work to the time dependent setting and consider cover times of this walk. We obtain new bounds on the cover and hitting times. Azar et al. conjectured that the controller can increase the stationary probability of a vertex from $p$ to $p^{1-ε}$; while this conjecture is not true in full generality, we propose a best-possible amended version of this conjecture and confirm it for a broad class of graphs. We also consider the problem of computing an optimal strategy for the controller to minimise the cover time and show that for directed graphs determining the cover time is PSPACE-complete.
