回顾 上节课： ·电路电阻网络 ·“等效电阻”距离 这节课： 。f 随机游走的碰撞时间(Hitting time)和返程时 间(commute time). 0 线性规划LP 2
回顾 上节课: • 电路电阻网络 • “等效电阻”距离 这节课： • 随机游走的碰撞时间(Hitting time)和返程时 间(commute time) • 线性规划 LP 2
回顾：随机游走 1. f碰撞时间(Hitting time):Hu,v=min{t≥1|X1=u and X:=} and huv E[Huv]. 2. 返程时间(Commute time):Cuv=hu,v+hv,u 3.遍历时间(Cover time):covery定义为：从v出发的随机游走访 问每个节点至少一次需要的期望时间；coverg=max coverv 3
回顾：随机游走 1. 碰撞时间 (Hitting time): �!,# ≔ min � ≥ 1 | �$ = � ��� �% = � and ℎ!,# = �[�!,#]. 2. 返程时间 (Commute time): �!,# ≔ ℎ!,# + ℎ#,!. 3. 遍历时间 (Cover time): cover# 定义为：从�出发的随机游走访 问每个节点至少一次需要的期望时间；cover& ≔ max ' cover# 3
Commute time 定理.对任意的节点s和t,Cs,t=2mRer(s,t),其中m=|E(G)儿. 证明： 固定节点t,记hut为从点u节点t的hitting time,满足vu≠t R=1+:=d:-aou=心 102 考虑h*t这一向量，它满足 D-A (To be cont'd..) 4
Commute time 定理. 对任意的节点� 和 �, �(,% = 2��)** �,� , 其中� = � � . 证明：固定节点 � ，记ℎ!,#为从点 �节点 �的hitting time，满足∀� ≠ � ℎ!,% = 1 + 1 �! E #∼! ℎ#,% ⇒ �!ℎ!,% − E #∼! ℎ#,% = �! 考虑ℎ∗,%这一向量，它满足 � − � ℎ!,# ℎ#,# = �! �# − 2� (To be cont’d..) 4
Commute time 定理.对任意的节点s和t,Cst=2mRef(s,t),其中m=|E(G)儿. 证明：固定节点s,记hu.s为从点u节点s的hitting time,满足Vu≠s hg=1+∑：3dh:-∑A:=d 考虑九*S这一向量，它满足 ds -2m D-A du (To be cont'd..) 5
Commute time 定理. 对任意的节点� 和 �, �(,% = 2��)** �,� , 其中� = � � . 证明：固定节点 �，记ℎ!,$为从点 �节点 �的hitting time，满足∀� ≠ � ℎ!,( = 1 + 1 �! E #∼! ℎ#,( ⇒ �!ℎ!,( − E #∼! ℎ#,( = �! 考虑ℎ∗,(这一向量，它满足 � − � ℎ$,$ ℎ!,$ ℎ#,$ = �$ − 2� �! �# (To be cont’d..) 5
Commute time 定理、对任意的节点s和t,Cs,t=2mRef(s,t),其中m= E(G)儿. 证明(cont'd): ds-2m 2m L(h.,t-h.s)= u 0 d:-2m 2m 因此h-九 2m 2=bst。回顾L中=bt,有解，且解空间是一维的 令中= -, 有 2m Refr(S,t)=φ(s)-中(t)= hst-hss hithts hstt hts Cst 2m 2m 2m 2m 6
Commute time 定理. 对任意的节点� 和 �, �!,# = 2��$%% �,� , 其中� = � � . 证明(cont’d)： � ℎ∗,# − ℎ∗,$ = �! �" ⋮ �# − 2� − �! − 2� �" ⋮ �# = 2� 0 ⋮ −2� 因此 & '∗,&('∗,' )* = �!,#。回顾�� = �$#，有解，且解空间是一维的 令� = &∗,#'&∗,$ () ，有 �*++ �,� = � � − � � = ℎ$,# − ℎ$,$ 2� − ℎ#,# − ℎ#,$ 2� = ℎ!,# + ℎ#,! 2� = �$,# 2� 6