Spectral Theory for Reversible Chains detailed balance equation: π(x)P(c,y)=π(y)P(y,c) 不则 S is symmetry x=y S=ΠPΠ-1 x丰y qPt=q(I-1ST)=qlΠ-1StΠ
Spectral Theory for Reversible Chains detailed balance equation: ⇡(x)P(x, y) = ⇡(y)P(y, x) r⇡x ⇡y P(x, y) = r⇡y ⇡x P(y, x) S(x, y) = r⇡x ⇡y let P(x, y) ) S is symmetry S = ⇧P⇧ ⇧ 1 (x, y) = (p⇡x x = y 0 x 6= y qPt = q(⇧1S⇧) t = q⇧1St ⇧
Spectral Theory for Reversible Chains detailed balance equation: π(x)P(c,y)=π(y)P(y,c) x=y S=IIPII-1 x丰y qPt=q(Π-1STI)t=qlΠI-1StΠ △x(t)=lp克-πlTv=l(ex-π)PtIl1 =l(e-元)Π-1sTml1≤点ax 1-πx 不x whereλmax=max{λ2l,ldnl}
Spectral Theory for Reversible Chains detailed balance equation: ⇡(x)P(x, y) = ⇡(y)P(y, x) S = ⇧P⇧ ⇧ 1 (x, y) = (p⇡x x = y 0 x 6= y qPt = q(⇧1S⇧) t = q⇧1St ⇧ t maxr1 ⇡x ⇡x x(t) = kpt x ⇡kT V = k(ex ⇡)Pt k1 = k(ex ⇡)⇧1St ⇧k1 where max = max{|2|, |n|}
=(2,P)stationary distribution: p:distribution at timewhen initial state isx △x(t)=lp-πlTv △(t)=max△z(t) x∈2 Tr(e)=min{t|△x(t)≤e}T(e)=max Tx(e) x∈2 Theorem (2,P)is reversible,with eigenvalues入1≥·≥入n Let Amax=max{lλ2l,l入n} T(e)≤ ln是+n是 max x∈2 1-入max
M = (⌦, P) x(t) = kp(t) x ⇡kT V (t) = max x2⌦ x(t) ⌧x(✏) = min{t | x(t) ✏} ⌧ (✏) = max x2⌦ ⌧x(✏) stationary distribution: ⇡ p(t) x : distribution at time t when initial state is x (Ω, P) is reversible, with eigenvalues Let Theorem max = max{|2|, |n|} 1 ··· n ⌧ (✏) max x2⌦ 1 2 ln 1 ⇡x + ln 1 2✏ 1 max
Lazy Random Walk undirected d-regular graph G(V,E) lazy random walk:flip a coin to decide whether to stay u=V P(u,v)= 2d u V (0 otherwise adjacency matrix A d=λ1≥λ2≥·≥λn≥-d P=(I+A) ）is symmetric 山吃=2(1+清入) eigenvalues::1=v1≥v2≥·≥vn≥0
Lazy Random Walk • undirected d-regular graph G(V, E) • lazy random walk: flip a coin to decide whether to stay P(u, v) = 8 >< >: 1 2 u = v 1 2d u ⇠ v 0 otherwise adjacency matrix A P = 1 2 (I + 1 dA) is symmetric 1 = ⌫1 ⌫2 ··· ⌫n 0 d = 1 2 ··· n d eigenvalues: ⌫i = 1 2 (1 + 1 d i)
adjacency matrix A d=x1≥λ2≥.≥入m≥-d P=(I+A) is symmetric 山%=(1+a入) eigenvalues:1=v≥v2≥·≥vn≥0 Vmax =V2 Theorem P is symmetric,with eigenvalues v≥v2≥··≥vn Let vmax max{v2,Un r(e)≤ 血n+m是 1-Vmax
adjacency matrix A P = 1 2 (I + 1 dA) is symmetric 1 = ⌫1 ⌫2 ··· ⌫n 0 d = 1 2 ··· n d eigenvalues: ⌫i = 1 2 (1 + 1 d i) P is symmetric, with eigenvalues Let Theorem ⌫1 ⌫2 ··· ⌫n ⌫max = max{|⌫2|, |⌫n|} ⌧ (✏) 1 2 ln n + ln 1 2✏ 1 ⌫max ⌫max = ⌫2