Let μ i , ν i \mu_i, \nu_i μ i , ν i ( Ω i , 2 Ω i ) (\Omega_i, 2^{\Omega_i} ) ( Ω i , 2 Ω i ) i ∈ [ n ] i \in [n] i ∈ [ n ] μ = ∏ i ∈ [ n ] μ i \mu = \prod_{i \in [n]} \mu_i μ = ∏ i ∈ [ n ] μ i ν = ∏ i ∈ [ n ] ν i \nu = \prod_{i \in [n]} \nu_i ν = ∏ i ∈ [ n ] ν i ( Ω , 2 Ω ) (\Omega, 2^{\Omega}) ( Ω , 2 Ω )
∥ μ − ν ∥ T V ≤ ∑ i ∈ [ n ] ∥ μ i − ν i ∥ T V ,
\Vert \mu - \nu \Vert_{TV} \le \sum_{i \in [n] } \Vert \mu_i - \nu_i \Vert_{TV},
∥ μ − ν ∥ T V ≤ i ∈ [ n ] ∑ ∥ μ i − ν i ∥ T V , where ∥ ⋅ ∥ T V \Vert \cdot \Vert_{TV} ∥ ⋅ ∥ T V
Proof.
Consider an x = ( x 1 , … , x n ) ∈ Ω x = (x_1, \ldots, x_n) \in \Omega x = ( x 1 , … , x n ) ∈ Ω
For each i ∈ 0 , … , n i \in 0, \ldots, n i ∈ 0 , … , n
s ( i ) ≐ μ 1 ( x 1 ) ⋯ μ i ( x i ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) .
s(i) \doteq \mu_1 (x_1) \cdots \mu_i(x_i) \cdot \nu_{i + 1} (x_{i + 1} ) \cdots \nu_n (x_n).
s ( i ) ≐ μ 1 ( x 1 ) ⋯ μ i ( x i ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) . So s ( 0 ) = ν ( x ) s(0) = \nu(x) s ( 0 ) = ν ( x ) s ( n ) = μ ( x ) s(n) = \mu(x) s ( n ) = μ ( x )
ν ( x ) − μ ( x ) = ∑ i ∈ [ n ] ( s ( i − 1 ) − s ( i ) ) = ∑ i ∈ [ n ] ( ( ν i ( x i ) − μ i ( x i ) ) ⋅ μ 1 ( x 1 ) ⋯ μ i − 1 ( x i − 1 ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) ) .
\begin{aligned}
\nu(x) - \mu(x)
&= \sum_{i \in [n]} \left( s(i - 1) - s(i) \right) \\
&= \sum_{i \in [n]} \left( \big( \nu_i(x_i) - \mu_i(x_i) \big) \cdot \mu_1 (x_1) \cdots \mu_{i - 1} (x_{i - 1}) \cdot \nu_{i + 1} (x_{i + 1} ) \cdots \nu_n (x_n)\right).
\end{aligned}
ν ( x ) − μ ( x ) = i ∈ [ n ] ∑ ( s ( i − 1 ) − s ( i ) ) = i ∈ [ n ] ∑ ( ( ν i ( x i ) − μ i ( x i ) ) ⋅ μ 1 ( x 1 ) ⋯ μ i − 1 ( x i − 1 ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) ) . Hence,
2 ⋅ ∥ μ − ν ∥ T V = ∑ x ∈ Ω ∣ ν ( x ) − μ ( x ) ∣ = ∑ x ∈ Ω ∣ ∑ i ∈ [ n ] ( ν i ( x i ) − μ i ( x i ) ) ⋅ μ 1 ( x 1 ) ⋯ μ i − 1 ( x i − 1 ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) ∣ ≤ ∑ x ∈ Ω ∑ i ∈ [ n ] ∣ ν i ( x i ) − μ i ( x i ) ∣ ⋅ μ 1 ( x 1 ) ⋯ μ i − 1 ( x i − 1 ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) = ∑ i ∈ [ n ] ∑ x i ∈ Ω i ∣ ν i ( x i ) − μ i ( x i ) ∣ = ∑ i ∈ [ n ] 2 ⋅ ∥ μ i − ν i ∥ T V .
\begin{aligned}
2 \cdot \Vert \mu - \nu \Vert_{TV}
&= \sum_{x \in \Omega} \vert \nu(x) - \mu(x) \vert \\
&= \sum_{x \in \Omega} \left\vert \sum_{i \in [n]} \big( \nu_i(x_i) - \mu_i(x_i) \big) \cdot \mu_1 (x_1) \cdots \mu_{i - 1} (x_{i - 1}) \cdot \nu_{i + 1} (x_{i + 1} ) \cdots \nu_n (x_n)\right\vert \\
&\le \sum_{x \in \Omega} \sum_{i \in [n]} \left\vert \nu_i(x_i) - \mu_i(x_i) \right\vert \cdot \mu_1 (x_1) \cdots \mu_{i - 1} (x_{i - 1}) \cdot \nu_{i + 1} (x_{i + 1} ) \cdots \nu_n (x_n) \\
&= \sum_{i \in [n]} \sum_{x_i \in \Omega_i} \left\vert \nu_i(x_i) - \mu_i(x_i) \right\vert \\
&= \sum_{i \in [n]} 2 \cdot \Vert \mu_i - \nu_i \Vert_{TV}.
\end{aligned}
2 ⋅ ∥ μ − ν ∥ T V = x ∈ Ω ∑ ∣ ν ( x ) − μ ( x ) ∣ = x ∈ Ω ∑ i ∈ [ n ] ∑ ( ν i ( x i ) − μ i ( x i ) ) ⋅ μ 1 ( x 1 ) ⋯ μ i − 1 ( x i − 1 ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) ≤ x ∈ Ω ∑ i ∈ [ n ] ∑ ∣ ν i ( x i ) − μ i ( x i ) ∣ ⋅ μ 1 ( x 1 ) ⋯ μ i − 1 ( x i − 1 ) ⋅ ν i + 1 ( x i + 1 ) ⋯ ν n ( x n ) = i ∈ [ n ] ∑ x i ∈ Ω i ∑ ∣ ν i ( x i ) − μ i ( x i ) ∣ = i ∈ [ n ] ∑ 2 ⋅ ∥ μ i − ν i ∥ T V . □ \square □
← Back to all notes Back to top ↑