An introduction to covering problems for random walks on graphs
An introduction to covering problems for random walks on graphs
复制标题
介绍图上随机游走的问题
DOI：
10.1007/bf01048271
复制
发表时间：
1989
影响因子：
0.8
通讯作者：
D. Aldous
中科院分区：
文献类型：
--
作者：
D. Aldous
在有限连通无向图G=(VG)上，有一个自然的简单随机游走的概念：马氏链从它的当前顶点v以均匀的概率跳到Dv相邻的顶点之一。文献中从几个角度对这种随机游动进行了研究。文献[1]讨论了经典马尔可夫链理论的一些结果。1；与电网络的类比在参考文献[1]中讨论。2；参考文献23描述了与流形理论的联系。我们的主题是由Broder和Karlin调查的某些计算机科学问题间接引发的，写T w表示顶点w上的第一次命中时间，C=Maxw Tw表示覆盖时间，即访问每个顶点所需的步数。C的典型大小取决于图的大小：人们可以研究特定图的C，并且可以根据图G的图论参数来寻找C的界限，一个明显的参数是点数i VI。期望E~，C取决于起始顶点v，在不同的位置，我们考虑了极值情况max，E~C，min~E~C和平均情况E~C，其中~是平稳分布
On a finite connected undirected graph G=(Vg) there is a natural notion of simple random walk: the Markov chain which from its current vertex v, jumps to one of the dv neighboring vertices with uniform probability. Such random walks have been studied in the literature from several viewpoints. Some consequences of classical Markov chain theory are discussed in Ref. 1; the analogy with electrical networks is treated in Ref. 2; and Ref. 3 describes connections with manifold theory. Our topic is motivated indirectly by certain computer science problems, surveyed by Broder and Karlin, below.Write T w for the first hitting time on vertex w, and C= maxw Tw for the covering time, that is, the number of steps taken to visit every vertex. The typical size of C depends on the graph: one can study C for specific graphs, and one can seek bounds on C in terms of graph-theoretic parameters of the graph G, an obvious parameter being the number of vertices I VI. The expectation E~, C depends on the starting vertex v, and at different places we consider the extreme cases max,, E~ C, min~ E~ C and the" average" case E~ C, where~ is the stationary distribution