Coupling Lemma Coupling Lemma 1.(X,Y)is a coupling of p,q>Pr[X≠Y]≥lp-qlrv 2.3 a coupling (X,Y)of p,g s.t.Pr[XY]=llp-allrv p() g(x) x
Coupling Lemma 1. (X,Y) is a coupling of p,q Pr[X 6= Y ] kp qkT V 2. ∃ a coupling (X,Y) of p,q s.t. Pr[X 6= Y ] = kp qkT V Coupling Lemma
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: