▣顾：Random walk on graphs 给定图G=(V,E) 图上的随机游走： ·从一个给定的顶点出发 接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？（混合时间，mixing time) 4. 从点s出发，多久才会到达点t?(hitting time) 多久才会遍历每个顶点至少一次？（遍历时间，cover time) 回顾：Random walk on graphs 给定图� = (�, �) 图上的随机游走: • 从一个给定的顶点出发 • 接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 • 不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？(混合时间，mixing time) 4. 从点s出发，多久才会到达点t? (hitting time) 5. 多久才会遍历每个顶点至少一次？(遍历时间，cover time) 4