有向图上的随机游动

Random Walks on Directed Graph

中文关键词:  概率  马尔科夫链  图  随机游动.

英文关键词:probability  Markov chain  graph  random walk.

中文摘要:

      设G=(V,Г)是有向图,G上的随机游动X(G)定义如下:位于某个顶点上的一个粒子将以等概率转移到该顶点的所有后继顶点.令M(j,n)表示随机游动X(G)在前n步内访问顶点j的平均次数,用W(j)表示随机游动X(G)到达顶点j所需要的平均步效.我们对M(j,n)和W(j)的值进行了估计,证明了M(j,n)=O(n),并给出了W(j)的上界.

英文摘要:

      A random walk on a digraph is defined in which a particle moves from one vertex to any successor of this vertex with equal probability. Detailed results are given on the expectation of first passage time and the expected number of times to be in some vertex during the first n steps.