Total variation distance of probability measures

<h2 id="definition">Definition</h2>
Consider a <a href="/facts/Measurable_space/AJ98lhT4">measurable space</a> 
 
 
 
 (
 Ω
 ,
 
 
 F
 
 
 )
 
 
 {\displaystyle (\Omega ,{\mathcal {F}})}
 
 and <a href="/facts/Probability_measure/8BjhgoPR">probability measures</a> 
 
 
 
 P
 
 
 {\displaystyle P}
 
 and 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 defined on 
 
 
 
 (
 Ω
 ,
 
 
 F
 
 
 )
 
 
 {\displaystyle (\Omega ,{\mathcal {F}})}
 
.
The total variation distance between 
 
 
 
 P
 
 
 {\displaystyle P}
 
 and 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 is defined as<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>

δ
        (
        P
        ,
        Q
        )
        =
        
          sup
          
            A
            ∈
            
              
                F
              
            
          
        
        
          |
          
            P
            (
            A
            )
            −
            Q
            (
            A
            )
          
          |
        
        .
      
    
    {\displaystyle \delta (P,Q)=\sup _{A\in {\mathcal {F}}}\left|P(A)-Q(A)\right|.}

This is the largest absolute difference between the probabilities that the two <a href="/facts/Probability_distribution/EpsKKVRu">probability distributions</a> assign to the same event.

<h2 id="properties">Properties</h2>
The total variation distance is an <a href="/facts/F-divergence/lhL1sMDh">f-divergence</a> and an <a href="/facts/Integral_probability_metric/AmtLakxW">integral probability metric</a>.

<h3>Relation to other distances</h3>
The total variation distance is related to the <a href="/facts/Kullback%25E2%2580%2593Leibler_divergence/nh7SjlPE">Kullback–Leibler divergence</a> by <a href="/facts/Pinsker%2527s_inequality/KRvK9Adk">Pinsker’s inequality</a>:

δ
        (
        P
        ,
        Q
        )
        ≤
        
          
            
              
                1
                2
              
            
            
              D
              
                
                  K
                  L
                
              
            
            (
            P
            ∥
            Q
            )
          
        
        .
      
    
    {\displaystyle \delta (P,Q)\leq {\sqrt {{\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)}}.}

One also has the following inequality, due to <a href="/facts/Bretagnolle%25E2%2580%2593Huber_inequality/SfmWIsrC">Bretagnolle and Huber</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> (see also <a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>), which has the advantage of providing a non-vacuous bound even when 
 
 
 
 
 
 D
 
 
 K
 L
 
 
 
 (
 P
 ∥
 Q
 )
 >
 2
 :
 
 
 
 {\displaystyle \textstyle D_{\mathrm {KL} }(P\parallel Q)>2\colon }

δ
        (
        P
        ,
        Q
        )
        ≤
        
          
            1
            −
            
              e
              
                −
                
                  D
                  
                    
                      K
                      L
                    
                  
                
                (
                P
                ∥
                Q
                )
              
            
          
        
        .
      
    
    {\displaystyle \delta (P,Q)\leq {\sqrt {1-e^{-D_{\mathrm {KL} }(P\parallel Q)}}}.}

The total variation distance is half of the <a href="/facts/L1_norm/gbad0Rv1">L1 distance</a> between the probability functions:
on discrete domains, this is the distance between the <a href="/facts/Probability_mass_function/LhurokRt">probability mass functions</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

δ
        (
        P
        ,
        Q
        )
        =
        
          
            1
            2
          
        
        
          ∑
          
            x
          
        
        
          |
        
        P
        (
        x
        )
        −
        Q
        (
        x
        )
        
          |
        
        ,
      
    
    {\displaystyle \delta (P,Q)={\frac {1}{2}}\sum _{x}|P(x)-Q(x)|,}

and when the distributions have standard <a href="/facts/Probability_density_functions/zvfybna4">probability density functions</a> p and q,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

δ
        (
        P
        ,
        Q
        )
        =
        
          
            1
            2
          
        
        ∫
        
          |
        
        p
        (
        x
        )
        −
        q
        (
        x
        )
        
          |
        
        
        
          d
        
        x
      
    
    {\displaystyle \delta (P,Q)={\frac {1}{2}}\int |p(x)-q(x)|\,\mathrm {d} x}

(or the analogous distance between <a href="/facts/Radon%25E2%2580%2593Nikodym_theorem/uWepNG2B">Radon-Nikodym derivatives</a> with any common <a href="/facts/Absolute_continuity/NPKDt9Qn">dominating measure</a>). This result can be shown by noticing that the supremum in the definition is achieved exactly at the set where one distribution dominates the other.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
The total variation distance is related to the <a href="/facts/Hellinger_distance/nmIlcIGn">Hellinger distance</a> 
 
 
 
 H
 (
 P
 ,
 Q
 )
 
 
 {\displaystyle H(P,Q)}
 
 as follows:<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

H
          
            2
          
        
        (
        P
        ,
        Q
        )
        ≤
        δ
        (
        P
        ,
        Q
        )
        ≤
        
          
            2
          
        
        H
        (
        P
        ,
        Q
        )
        .
      
    
    {\displaystyle H^{2}(P,Q)\leq \delta (P,Q)\leq {\sqrt {2}}H(P,Q).}

These inequalities follow immediately from the inequalities between the <a href="/facts/Lp_space/gbad0Rv1">1-norm</a> and the <a href="/facts/Lp_space/gbad0Rv1">2-norm</a>.

<h3>Connection to transportation theory</h3>
See also: <a href="/facts/Transportation_theory_(mathematics)/DRoHNtde">Transportation theory (mathematics)</a>
The total variation distance (or half the norm) arises as the optimal transportation cost, when the cost function is 
 
 
 
 c
 (
 x
 ,
 y
 )
 =
 
 
 
 1
 
 
 
 x
 ≠
 y
 
 
 
 
 {\displaystyle c(x,y)={\mathbf {1} }_{x\neq y}}
 
, that is,

1
            2
          
        
        ‖
        P
        −
        Q
        
          ‖
          
            1
          
        
        =
        δ
        (
        P
        ,
        Q
        )
        =
        inf
        
          
            {
          
        
        
          P
        
        (
        X
        ≠
        Y
        )
        :
        
          Law
        
        (
        X
        )
        =
        P
        ,
        
          Law
        
        (
        Y
        )
        =
        Q
        
          
            }
          
        
        =
        
          inf
          
            π
          
        
        
          E
          
            π
          
        
        ⁡
        [
        
          
            
              1
            
          
          
            x
            ≠
            y
          
        
        ]
        ,
      
    
    {\displaystyle {\frac {1}{2}}\|P-Q\|_{1}=\delta (P,Q)=\inf {\big \{}\mathbb {P} (X\neq Y):{\text{Law}}(X)=P,{\text{Law}}(Y)=Q{\big \}}=\inf _{\pi }\operatorname {E} _{\pi }[{\mathbf {1} }_{x\neq y}],}

where the expectation is taken with respect to the probability measure 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 on the space where 
 
 
 
 (
 x
 ,
 y
 )
 
 
 {\displaystyle (x,y)}
 
 lives, and the infimum is taken over all such 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 with marginals 
 
 
 
 P
 
 
 {\displaystyle P}
 
 and 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
, respectively.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Total_variation/tyY5fTz9">Total variation</a></li>
<li><a href="/facts/Kolmogorov%25E2%2580%2593Smirnov_test/Kr5MqpfH">Kolmogorov–Smirnov test</a></li>
<li><a href="/facts/Wasserstein_metric/r0tB6sXm">Wasserstein metric</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Chatterjee, Sourav. "Distances between probability measures" (PDF). UC Berkeley. Archived from the original (PDF) on July 8, 2008. Retrieved 21 June 2013. <a href="/wiki/Sourav_Chatterjee" target="_blank">/wiki/Sourav_Chatterjee</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bretagnolle, J.; Huber, C, Estimation des densités: risque minimax, Séminaire de Probabilités, XII (Univ. Strasbourg, Strasbourg, 1976/1977), pp. 342–363, Lecture Notes in Math., 649, Springer, Berlin, 1978, Lemma 2.1 (French). <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Tsybakov, Alexandre B., Introduction to nonparametric estimation, Revised and extended from the 2004 French original. Translated by Vladimir Zaiats. Springer Series in Statistics. Springer, New York, 2009. xii+214 pp. ISBN 978-0-387-79051-0, Equation 2.25. <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">David A. Levin, Yuval Peres, Elizabeth L. Wilmer, Markov Chains and Mixing Times, 2nd. rev. ed. (AMS, 2017), Proposition 4.2, p. 48. <a href="/wiki/Yuval_Peres" target="_blank">/wiki/Yuval_Peres</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Tsybakov, Aleksandr B. (2009). Introduction to nonparametric estimation (rev. and extended version of the French Book ed.). New York, NY: Springer. Lemma 2.1. ISBN 978-0-387-79051-0. <a href="978-0-387-79051-0" target="_blank">978-0-387-79051-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Devroye, Luc; Györfi, Laszlo; Lugosi, Gabor (1996-04-04). A Probabilistic Theory of Pattern Recognition (Corrected ed.). New York: Springer. ISBN 978-0-387-94618-4. <a href="978-0-387-94618-4" target="_blank">978-0-387-94618-4</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Harsha, Prahladh (September 23, 2011). "Lecture notes on communication complexity" (PDF). <a href="https://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/lectures/l12.pdf" target="_blank">https://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/comm/lectures/l12.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Villani, Cédric (2009). Optimal Transport, Old and New. Grundlehren der mathematischen Wissenschaften. Vol. 338. Springer-Verlag Berlin Heidelberg. p. 10. doi:10.1007/978-3-540-71050-9. ISBN 978-3-540-71049-3. <a href="978-3-540-71049-3" target="_blank">978-3-540-71049-3</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Total variation distance of probability measures open-in-new

Total variation distance of probability measures