Mixing time and spectral gap 定理.随机游走的e-混合时间最多为2log(②，其中1=min{1- a2,1 lanl} 当谱间隔((spectral gap)为常数的时候，随机游走在0(1og)步内收敛 ·回忆PageRank,亦可通过随机游走模拟 对于惰性随机游走，谱间隔变为二，其中2为归一化的拉普拉斯矩 阵的第二特征值 直观上看，谱间隔相当于描述了这个图有多么接近不连通的 回顾Cheeger's inequality,有2≥(C 2 因此，Lazy random walk的e混合时间最多为，log 1214 回顾Cheeger’s inequality，有 � & ≥ + , 6 & 因此 ，Lazy random walk 的 � -混合时间最多为 & + , 6 log -