Nonincreasing of Total Variation p):distribution at time t when initial state isx △z(t)=lp-πlrv Theorem: △x(t+1)≤△x(t) consider y~π △(=lp-prv x=X1 X2,....Xn X+1 -Y1,Y2,...YY coupling lemma:3 a coupling (Xi,Y)s.t.Pr[X]=A(t) couple (X1,Y+1)in such a way that:X=YX=Y △x(t)=Pr[X≠Y≥Pr[X+1≠Y+]≥lp+D-πlTv =△x(t+1)
Nonincreasing of Total Variation x(t) = kp(t) x ⇡kT V p(t) x : distribution at time t when initial state is x Theorem: x(t + 1) x(t) consider y ∼ π x(t) = kp(t) x p(t) y kT V coupling lemma: ∃ a coupling (Xt, Yt) s.t. x = X1, X2, ..., Xt, Xt+1, ... π ∼ Y1, Y2, ..., Yt, Yt+1, ... Pr[Xt 6= Yt] = x(t) couple (Xt+1, Yt+1) in such a way that: Xt=Yt ⇒ Xt+1=Yt+1 x(t) = Pr[Xt 6= Yt] Pr[Xt+1 6= Yt+1] kp(t+1) x ⇡kT V = x(t + 1)
Geometric Convergence p):distribution at time twhen initial state isx △(t)=lp-πlTv△(t)=max△x(t) x∈2 Tx(e)=min{t|△x(t)≤e}r(e)=max Ta(e) x∈2 Tmix =T(1/2e) Theorem:△(k,Tmix)≤ek 三X22%w-g9vse x =X1,X2,... 3 coupling Pr[Xt≠YAl≤e-1 couple X=Y,→X+1=Y+l in caseX=r'≠y'=y子coupling P≠Yl=lpg-t-pg-tIlr
Geometric Convergence x(t) = kp(t) x ⇡kT V p(t) x : distribution at time t when initial state is x Theorem: (k · ⌧mix) ek (t) = max x2⌦ x(t) ⌧x(✏) = min{t | x(t) ✏} ⌧ (✏) = max x2⌦ ⌧x(✏) ⌧mix = ⌧ (1/2e) x = X1, X2, ..., Xt, Xt+1, ... , Xkt, ... y = Y1, Y2, ..., Yt, Yt+1, ... , Ykt, ... kp(t) x p(t) y kT V e1 Pr[Xt 6= Yt] e ∃ coupling 1 couple Xt=Yt ⇒ Xt+1=Yt+1 in case Xt=x’ ≠ y’=Yt ∃ coupling Pr[Xkt 6= Ykt] = kp (k1)t x0 p (k1)t y0 kT V
Coupling of Markov Chains a coupling of =(P)is a Markov chain (X,Y) of state space x such that: o l both are faithful copies of the chain Pr[X++1=y Xt=x]=Pr[Yi+1=yYi=x]=P(x,y) once collides,always makes identical moves Xi=Y>Xi+1=Yi+1
• both are faithful copies of the chain • once collides, always makes identical moves Coupling of Markov Chains ⌦ Pr[Xt+1 = y | Xt = x] = Pr[Yt+1 = y | Yt = x] = P(x, y) Xt = Yt Xt+1 = Yt+1 is a Markov chain (Xt, Yt) of state space a coupling of M = (⌦, P) ⌦ ⇥ ⌦ such that:
Markov Chain Coupling Lemma Markov chain:=(,P) stationary distribution: p):distribution at time t when initial state isx △z(t)=lp-πlrv △(t)=max△z(t) x∈2 Markov Chain Coupling Lemma: (X:,Yi)is a coupling of=(2,P) △(t)≤nax Pr[Xt≠Yt|Xo=x,Yo=y x,y∈2
Markov Chain Coupling Lemma Markov chain: M = (⌦, P) x(t) = kp(t) x ⇡kT V (t) = max x2⌦ x(t) stationary distribution: ⇡ p(t) x : distribution at time t when initial state is x (Xt, Yt) is a coupling of M = (⌦, P) (t) max x,y2⌦ Pr[Xt 6= Yt | X0 = x, Y0 = y] Markov Chain Coupling Lemma:
distribution at timewhen initial state isx Markov Chain Coupling Lemma: (X,Y)is a coupling of =(2,P) △(t)≤max Pr[Xt≠Y|Xo=x,Yo=y x,y∈2 △()=竖p-xy ≤max x,y∈2 llsv ≤max Pr[Xt卡Yt|Xo=x,Yo=y c,y∈2 (coupling lemma)
(Xt, Yt) is a coupling of M = (⌦, P) (t) max x,y2⌦ Pr[Xt 6= Yt | X0 = x, Y0 = y] Markov Chain Coupling Lemma: p(t) x : distribution at time t when initial state is x (t) = max x2⌦ kp(t) x ⇡kT V max x,y2⌦ kp(t) x p(t) y kT V max x,y2⌦ Pr[Xt 6= Yt | X0 = x, Y0 = y] (coupling lemma)