=(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 Markov Chain Coupling Lemma: (X:,Y:)is a coupling of=(,P) △(t)≤max Pr[Xt≠YEXo=x,Yo= x,y∈2 max Pr[Xt≠Y|Xo=x,Y%=列≤e>1 T(e)≤t c,y∈2
(Xt, Yt) is a coupling of M = (⌦, P) (t) max x,y2⌦ Pr[Xt 6= Yt | X0 = x, Y0 = y] Markov Chain Coupling Lemma: max x,y2⌦ Pr[Xt 6= Yt | X0 = x, Y0 = y] ✏ ⌧ (✏) t 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
Markov Chain Coupling Lemma: (X,Y)is a coupling of =(P) △(t)≤max Pr[Xt≠Y|Xo=x,Yo=y r,y∈D max Pr[Xt≠Y:|Xo=x,o=≤e> T(e)≤t c,y∈2
(Xt, Yt) is a coupling of M = (⌦, P) (t) max x,y2⌦ Pr[Xt 6= Yt | X0 = x, Y0 = y] Markov Chain Coupling Lemma: max x,y2⌦ Pr[Xt 6= Yt | X0 = x, Y0 = y] ✏ ⌧ (✏) t ⌦ x y