Mixing time (for d-regular graphs) 定理随机游走的c-混合时间最多为log(②)，其中=minf1-a2,1-lan 证明：取v1,V2,,Vn为A的一组正交正规特征向量的基。 设po=c1v1+c2v2++cnn,则pt=Wtp0=C1iv1,+c2吃v2+…+cna克n 由Cauchy--Schwarz不等式，Ilm,-πl1≤Vp:-πl2元 Ilp:-πl陉=lc2a吃v2+…+Cnatvn3=c吃a经|lv2ll3+…+c2a2 llnll =c吃aα好+…+ca≤(1-02t(c经+…+c) 注意到po本身作为一个概率分布，满足Ilpo陉=∑ipo()2≤ipo()=lpol1=1 因此lp:-π陉≤(1-)2t→lp:-πl1≤Vn1-)'≤vme ,注：非d-regular的情况下v1,v2,,yn需要取作A的正交正规特征向量基，会有额外Vn的损失 当ispectral gap为常数时i.e.入=(1)ル，随机游走在0(1og)步内收敛， 对正则图且λ=2(1)时，我们可以在01ogn)步内，均匀随机采样到一个顶点. 13 Mixing time (for d-regular graphs) 13 定理. 随机游走的�-混合时间最多为# 4 log / 5 , 其中� = min 1 − �*, 1 − |�/| . 证明：取�!, �", … , �#为�的一组正交正规特征向量的基。 设�$ = �!�! + �"�" + … + �#�#，则�% = �%�$ = �!�! %�! + �"�" %�" + ⋯ + �#�# % �# 由Cauchy-Schwarz不等式， �! − � # ≤ � �% − � & �! − � " " = �"�" ! �" + ⋯ + �#�# ! �# " " = �" "�" "% �" " " + ⋯ + �# "�# "! �# " " = �" "�" "! + ⋯ + �$ %�$ %& ≤ 1 − � %& �% % + ⋯ + �$ % 注意到 �$本身作为一个概率分布，满足 �$ * * = ∑. �0 � * ≤ ∑. �0 � = �0 # = 1 因此 �% − � & & ≤ 1 − � "% ⇒ �% − � # ≤ � 1 − � ! ≤ � �%&! • 注：非d-regular的情况下�#, �*, … , �/需要取作�的正交正规特征向量基，会有额外 �的损失 • 当spectral gap为常数时(i.e. � = Ω(1))， 随机游走在� log / 5 步内收敛. • 对正则图且� = Ω(1)时，我们可以在�(log �)步内，均匀随机采样到一个顶点. �