南京大学：《随机算法 Randomized Algorithms》课程教学资源（课件讲稿）Mixing

Mixing Why should a uniform random walk on a graph be rapidly mixing? Why should a Markov chain be rapidly mixing?

Mixing • Why should a uniform random walk on a graph be rapidly mixing? • Why should a Markov chain be rapidly mixing?

Sample Matchings G(V,E matching: MCE Ve1,e2∈M no common vertex input:G(V,E) sampling a uniform random matching in G

Sample Matchings input: G(V,E) matching: M ✓ E 8e1, e2 2 M no common vertex sampling a uniform random matching in G G(V,E)

the Jerrum-Sinclair random walk of matchings at each step:M with probability 1/2,do nothing; pick a uniform random edge e=uveE; ·(个)if none of u,v is matched,add e to M; (if eeM,remove e from M; (>if one of u,v is matched by some e'eM, replace e'by e;

• with probability 1/2, do nothing; • pick a uniform random edge e=uv∊E; • (↑) if none of u, v is matched, add e to M; (↓) if e∊M, remove e from M; (↔) if one of u, v is matched by some e’∊M, replace e’ by e; at each step: M the Jerrum-Sinclair random walk of matchings

Mixing Why should a uniform random walk on a graph be rapidly mixing? Why should a Markov chain be rapidly mixing? initial distribution g the decreasing rate of gpe-

Mixing • Why should a uniform random walk on a graph be rapidly mixing? • Why should a Markov chain be rapidly mixing? kqPt ￾ ⇡k1 initial distribution q the decreasing rate of

Spectral Decomposition Spectral Theorem P:symmetric nxn matrix eigenvalues:d≥2≥.≥λn the corresponding eigenvectors v1,v2,...,v are orthonormal m g∈Rm q=>civi where ci=qTvi i=1 qP=∑cP=∑c入 2=1 i=1

Spectral Decomposition P : eigenvalues : symmetric n×n matrix the corresponding eigenvectors v1, v2, ..., vn are orthonormal ￾1 ￾ ￾2 ￾ ··· ￾ ￾n Spectral Theorem where ci = qT vi = X n i=1 ci￾ivi q = X n i=1 8q 2 R civi n qP = X n i=1 civiP

Mixing of Symmetric Chain =(n,P)P is symmetric stationary=(元…是 eigenvalues:1=λ1≥2≥··≥入n(Perron-Frobenius)) orthonormal eigenbasis v1,v2,...Vn gE[0,1]is a distribution=1 qz= 9= c=T+∑ Civi where ci-gTv; 2=1 2=2 qPt=πPt+∑cPt=T+caXu 2=2 2三2

Mixing of Symmetric Chain M = ([n], P) P is symmetric eigenvalues : orthonormal eigenbasis : v1, v2, ..., vn 1 = ￾1 ￾ ￾2 ￾ ··· ￾ ￾n (Perron-Frobenius) q 2 [0, 1]n is a distribution kqk1 = 1 where ci = qT q = vi X n i=1 civi ￾1 = 1 1P = 1 o v1 = 1 k1k2 = ✓ 1 pn ,..., 1 pn ◆ ) c1 = qT v1 = 1 pn = ⇡ +X n i=2 civi c1v1 = ✓ 1 n ,..., 1 n ◆ = ⇡ qPt = ⇡Pt +X n i=2 civiPt = ⇡ +X n i=2 ci￾t ivi ⇡ = ✓ 1 n ,..., 1 n ◆ stationary

=(n,P)P is symmetric stationary=(（元…是 eigenvalues:1=1≥λ2≥··≥λn orthonormal eigenbasis v1,v2,...V q∈[0，l]is a distribution where ci=qTv; qPt=πPt+cPt=元+cX i=2 2=2

M = ([n], P) P is symmetric eigenvalues : orthonormal eigenbasis : v1, v2, ..., vn 1 = ￾1 ￾ ￾2 ￾ ··· ￾ ￾n ⇡ = ✓ 1 n ,..., 1 n ◆ stationary q 2 [0, 1]n is a distribution where ci = qT vi qPt = ⇡Pt +X n i=2 civiPt = ⇡ +X n i=2 ci￾t ivi

=(n,P)P is symmetric stationary-(元是 eigenvalues:1=λ1≥λ2≥·≥入n orthonormal eigenbasis V1,v2,...,Vn q∈[0，1is a distribution where ci=gTv; o-t-②sv唇ew (Cauchy-Schwarz) sv define 入max≌max{lλ2l,|Xn} ≤VnXinaxllal2≤V冗λimax > r(g)sn+血是 1-入max

M = ([n], P) P is symmetric eigenvalues : orthonormal eigenbasis : v1, v2, ..., vn 1 = ￾1 ￾ ￾2 ￾ ··· ￾ ￾n ⇡ = ✓ 1 n ,..., 1 n ◆ stationary q 2 [0, 1]n is a distribution where ci = qT vi kqPt ￾ ⇡k1 = ￾ ￾ ￾ ￾ ￾ X n i=2 ci￾t ivi ￾ ￾ ￾ ￾ ￾ 1  pn ￾ ￾ ￾ ￾ ￾ X n i=2 ci￾t ivi ￾ ￾ ￾ ￾ ￾ 2 (Cauchy-Schwarz) = pn vuutX n i=2 c2 i ￾2t i  pn￾t max vuutX n i=2 c2 i  pn￾t maxkqk2  pn￾t max ￾(t)  pn 2 ￾t max  pn 2 e￾t(1￾￾max) ⌧ (✏)  1 2 ln n + ln 1 2✏ 1 ￾ ￾max define ￾max , max{|￾2|, |￾n|}

=(2,P)stationary distribution: p:distribution at time when initial state isx △x(t)=lp-πlTv △(t)=max△z(t) x∈2 Tr(e)=min{t|△x(t)≤}T(e)=max Ta(e) x∈2 Theorem P is symmetric,with eigenvaluesλ1≥λ2≥·≥入n Let Amax max{A2l,An} T(e)≤ 2Inn+In zc 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 ⌧ (✏)  1 2 ln n + ln 1 2✏ 1 ￾ ￾max P is symmetric, with eigenvalues ￾1 ￾ ￾2 ￾ ··· ￾ ￾n Let Theorem ￾max = max{|￾2|, |￾n|}

Reversibility ergodic detailed balance equation: flow T(x)P(x,y)=T(y)P(y,x) time-reversible Markoy chain: 3π，廿，x,y∈2，π(c)P(xc,y)=π(y)P(y,x) stationary distribution: (πP)y=π(c)P(x,)=π(g)P(,)=π(g) C C time-reversible: when start fromπ (X0,X1,,Xn)~(Xn,Xn-1,,X0)

Reversibility detailed balance equation: time-reversible Markov chain: 9⇡, 8, x, y 2 ⌦, ⇡(x)P(x, y) = ⇡(y)P(y, x) stationary distribution: (⇡P)y = X x ⇡(x)P(x, y) = X x ⇡(y)P(y, x) = ⇡(y) time-reversible: (X0, X1,...,Xn) ￾ (Xn, Xn￾1,...,X0) when start from ⇡ ⇡(x)P(x, y) = ⇡(y)P(y, x) ergodic flow