无向图随机游走理论

定义7.9 图上的随机游走是指一个粒子在图上的一列移动. 某个时间点，粒子在图中所处的位置即为此时系统所处状态. 如果粒子处于顶点$i$并且$i$的出度为$d(i)$，则该粒子从边$(i,j)$移动到邻居$j$的概率是$1/d(i)$

定理7.12 无向图$G$上的随机游走是非周期的当且仅当$G$不是二分图.

定理7.13 无向图上的随机游走收敛于平稳分布$\bar{\pi}$，且满足$\pi_v=\frac{d(v)}{2|E|}$.
证明：直接带入$\bar{\pi}=\bar{\pi}P$验证即可.

定义 图$G=(V,E)$中两顶点$u,v$间的往返时间定义为$h_{u,v}+h_{v,u}$.代表从顶点$u$出发到达$v$并再返回$u$的总时间期望，具有对称性.

定义7.10 图$G=(V,E)$的覆盖时间（cover time）是指从图中任一顶点出发，通过随机游走访问图中所有顶点的最大时间期望. 一般将图$G$的覆盖时间记为$C_G$，也称其为图$G$的命中时间.

尝试寻找图$G$覆盖时间上限：

定理7.14 如果$(u,v)\in E$，则$h_{u,v}+h_{v,u}\leq 2|E|$.

定理7.15 图$G=(V,E)$的覆盖时间满足$C_G\leq 2|E|(|V|-1)$.

定义 $H(n)=\sum_{i=1}^n 1/i\approx \ln{n}$

定理7.16 对于有$n$个顶点的图$G=(V,E)$，有$C_G\leq H(n-1)\underset{u,v\in V:u\neq v}\max h_{u,v}$.
同样也可以得到$C_G\geq H(n-1)\underset{u,v\in V:u\neq v}\min h_{u,v}$ . 但是这个命中时间下限一般很小，缺少使用价值.