Total Variation Distance two probability measures p,g over p,9∈[0,1]0 ∑p(x)=1∑q(c)=1 x∈2 x∈2 total variation distance between p and g: Ilp-allrv jllp-all >lp(z)-a(s) x∈2 equivalent definition: ID-grv=Rlp(A）-g(A 4/10 3/10 D 2/10 1/10 0 2 3 4Total Variation Distance • two probability measures p, q over Ω: • total variation distance between p and q: • equivalent definition: p, q 2 [0, 1]⌦ X x2⌦ p(x)=1 X x2⌦ q(x)=1 kp ￾ qkT V = 1 2 kp ￾ qk1 = 1 2 X x2⌦ |p(x) ￾ q(x)| COUPLING OF MARKOV CHAINS 4/10 r-----. I I I I I I r----- I I I - + - -:- --- -{ -- I I I ____ -' L __________ I 3/10 2/10 1/10 o 2 3 4 x Figure 11.1: Example of variation distance. The areas shaded by upward diagonal lines correspond to values x where DI (x) < D2 (x); the areas shaded by downward diagonal lines correspond to val￾ues x where DI(x) > D 2(x). The total area shaded by upward diagonal lines must equal the total area shaded by downward diagonal lines, and the variation distance equals one of these two areas. we run the chain for a finite number of steps. If we want to use this Markov chain to shuffle the deck, how many steps are necessary before we obtain a shuffle that is to uniformly distributed? To quantify what we mean by "close to uniform", we must introduce a distance measure. Definition 11.1: The variation distance between two distributions D, and D2 on (f countable state space S is given by 1 liD, - D211 = 2: LID,(x) - D2(x)l. XES A pictorial example of the variation distance is given in Figure 11.1. The factor 1/2 in the definition of variation distance guarantees that the variation dis￾tance is between 0 and l. It also allows the following useful alternative characterization. Lemma 11.1: Foran), A S, let Di(A) = LXEA Di(x)jori = 1,2. Then A careful examination of Figure 11.1 helps make the proof of this lemma transparent. Proof: Let S+ S be the set of states such that D,(x) D2(X), and let S- S the set of states such that D2 (x) > D, (x). Clearly, and But since D,(S) = D2(S) = 1, we have D,(S+) + D,(S-) = D2(S+) + D2(S-) = 1, 272 kp ￾ qkT V = max A✓⌦ |p(A) ￾ q(A)|