G(V,E)of max degree△ proper q-coloring with g≥△+l sampling:sample a uniform random proper g-coloring Markov Chain: at each step: ·randomly pick a vertex veV and a color c∈[q]; change the color of v to c if it is proper; aperiodic; q2△+2 irreducible; uniform stationary distribution;
proper q-coloring G(V,E) of max degree ∆ sampling: sample a uniform random proper q-coloring with q≥∆+1 • randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: Markov Chain: aperiodic; irreducible; uniform stationary distribution; q≥∆+2
at each step: ·randomly pick a vertex veV and a color c∈[g; change the color of v to c if it is proper; Coupling: there is a coupling (X,Y)(X',Y)such that 廿proper coloringsx,y∈[q]V Eld(X',Y'X=x,Y=y a≥ gn
∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that • randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: for some α∈[0,1] ⌧mix = O 1 ↵ log n Coupling: q≥4∆+1 ↵ 1 qn E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵)d(x, y)
at each step: ·randomly pick a vertex veV and a color c∈[g; change the color of v to c if it is proper; Path Coupling(Bubley-Dyer 1997): there is a coupling (X,)-(X',Y)such that V proper colorings x,ye[g]y that disagree at 1 vertex Eld(X',Y)X=z,Y=y]<(1-a)d(x,y) for some a∈[0,1] Tmix =O(i logn)
∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that • randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: for some α∈[0,1] ⌧mix = O 1 ↵ log n Path Coupling (Bubley-Dyer 1997): that disagree at 1 vertex E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵)d(x, y)
at each step: ·randomly pick a vertex veV and a color c∈[g]; change the color of v to c if it is proper; X,Y disagree at vo coupling (X,)(X',Y): randomly pick the same vertex vev .if v=vo,pick the same color celg]d(X',Y)=0 ·ifv≠vo and v-vo,same color c∈[q]>dX',Y)=1 ·ifv~vo:pick(cx,cY) so that E[d(X',Y'】=1+Pr[X≠Yw]is minimized
• randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: v0 v0 coupling (X,Y)→(X’,Y’): X,Y disagree at v0 : • randomly pick the same vertex v∊V • if v=v0, pick the same color c∊[q] • if v≠v0 and v≁v0, same color c∊[q] • if v∼v0: d(X’,Y’)=0 d(X’,Y’)=1 pick (cX,cY) so that E[d(X is minimized 0 , Y 0 )] = 1 + Pr[X0 v 6= Y 0 v ]
at each step: ·randomly pick a vertex veV and a color c∈[g; change the color of v to c if it is proper; X,Y disagree at vo 。 coupling (X,Y)(X',Y): randomly pick the same vertex vev E[d(X',Y)]=d(vo)/g if v=vo,pick the same color ce[g]0 ●ifv≠vo and vvo,,same color ce[ql>dX',Y)=l ·ifv~vo:pick(cx,CY) Cx=X(vo)+Cy=Y(vo) Cx=Y(vo) cy=Xo) DPrX≠YW= otherwise cx cy
• randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: v0 v0 coupling (X,Y)→(X’,Y’): X,Y disagree at v0 : • randomly pick the same vertex v∊V • if v=v0, pick the same color c∊[q] • if v≠v0 and v≁v0, same color c∊[q] • if v∼v0: d(X’,Y’)=0 d(X’,Y’)=1 pick (cX,cY) cX = X(v0) ⇔ cY = Y(v0) cX = Y(v0) ⇔ cY = X(v0) otherwise cX = cY Pr[X0 v 6= Y 0 v ] = 1 q E[d(X’,Y’)]=d(v0)/q
at each step: ·randomly pick a vertex veV and a color c∈[q]; change the color of v to c if it is proper; X,Y disagree at vo 01 coupling (X,Y(X',Y): E0X,y1xy-n=m+D++(+） n q =1-g-2d(o) ≤1、9-24 nq nq q≥2A+1> Tmix =O(gnlogn)
• randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: v0 v0 coupling (X,Y)→(X’,Y’): X,Y disagree at v0 : q 2 + 1 ⌧mix = O(qn log n) E[d(X0 , Y 0 ) | X, Y ] = n (d(v0) + 1) n + 1 n d(v0) q + d(v0) n ✓ 1 + 1 q ◆ = 1 q 2d(v0) nq 1 q 2 nq
Path Coupling (Bubley-Dyer 1997): there is a coupling (X,)(X',Y)such that V proper colorings x,ye[g]y that disagree at 1 vertex Eld(X',Y)X=x,Y=y] Tmix=O(log n)
∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that for some α∈[0,1] ⌧mix = O 1 ↵ log n Path Coupling (Bubley-Dyer 1997): that disagree at 1 vertex E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵)d(x, y)
there is a coupling (X,Y(X',Y)such that V proper colorings x,ye[g]y that disagree at 1 vertex Eld(X',YX=x,Y=y(,Y)such that V proper colorings x,ye[g]v Eld(X',Y)X=x,Y=yTmix=0(3logn）
∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that for some α∈[0,1] ⌧mix = O 1 ↵ log n ∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that for some α∈[0,1] E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵) d(x, y) that disagree at 1 vertex E[d(X0 , Y 0 ) | X = x, Y = y] (1 ↵)d(x, y)
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 ciivi q = X n i=1 8q 2 R civi n qP = X n i=1 civiP