Random walk on graphs 这个随机过程的“长期表现”是怎么样的呢？ 1.重复t步之后，当前顶点是某个顶点u的概率是多少？ 2.是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？（混合时间，mixing time) 4. 从点s出发，多久才会到达点t?(hitting time) 5. 多久才会遍历每个顶点至少一次？（遍历时间，cover time) 前3个问题可以通过纯概率的方法(coupling)来研究；我们将讨 论如何利用与幂迭代的联系，通过马尔可夫链(Markov chains)转 移矩阵的特征值来研究。 后2个问题我们将留到之后讨论“图与电阻电路网络”的时候 11 Random walk on graphs 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？(混合时间，mixing time) 4. 从点s出发，多久才会到达点t? (hitting time) 5. 多久才会遍历每个顶点至少一次？(遍历时间，cover time) 前3个问题可以通过纯概率的方法(coupling)来研究；我们将讨 论如何利用与幂迭代的联系，通过马尔可夫链(Markov chains)转 移矩阵的特征值来研究。 后2个问题我们将留到之后讨论“图与电阻电路网络”的时候 11