How to Design a Linear Cover Time Random Walk on a Finite Graph
How to Design a Linear Cover Time Random Walk on a Finite Graph
复制标题
如何设计有限图上的线性覆盖时间随机游走
DOI：
10.1007/978-3-642-04944-6_9
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Masafumi Yamashita
中科院分区：
文献类型：
--
作者：
Yoshiaki Nonaka;Hirotaka Ono;Kunihiko Sadakane;Masafumi Yamashita
有限图G =（V，E）上的随机游动是指图G的顶点上的随机记号循环.顶点inV上的标记根据转移概率矩阵P移动到其相邻顶点之一。已知标准随机游动的击中时间和覆盖时间都有界于O（|V| 3），其中令牌以均匀概率随机移动到相邻顶点。这种估计在某种意义上是紧的，即存在标准随机游动的命中时间和覆盖时间为的图。因此，下面的问题自然出现：是否有可能加快随机游走，也就是说，设计一个转移概率为G，实现更快的覆盖时间？或者，G上随机游动的覆盖时间的下界有多大（或多小）？在本文中，我们研究如何我们可以/不能设计一个更快的随机游走的覆盖时间。本文给出了图G具有线性覆盖时间随机游动的必要条件，即，1999年，张晓刚（|V|).我们还提出了一类图，有一个线性覆盖时间。作为副产品，我们得到了树上任意随机游动的覆盖时间的下界。
A random walk on a finite graphG= (V,E) is random token circulation on vertices ofG. A token on a vertex inVmoves to one of its adjacent vertices according to a transition probability matrixP. It is known that both of the hitting time and the cover time of the standard random walk are bounded byO(|V|3), in which the token randomly moves to an adjacent vertex with the uniform probability. This estimation is tight in a sense, that is, there exist graphs for which the hitting time and cover times of the standard random walk are. Thus the following questions naturally arise: is it possible to speed up a random walk, that is, to design a transition probability forGthat achieves a faster cover time? Or, how large (or small) is the lower bound on the cover time of random walks onG? In this paper, we investigate how we can/cannot design a faster random walk in terms of the cover time. We give necessary conditions for a graphGto have a linear cover time random walk, i,e., the cover time of the random walk onGisO(|V|). We also present a class of graphs that have a linear cover time. As a byproduct, we obtain the lower boundof the cover time of any random walk on trees.