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∈2Markov 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: