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: