Suppose there are two sets of random variables $X_1,...,X_n$ and $Y_1,...,Y_n$ with all the variables being defined over the same sample space, but not necessarily being identically distributed. Is there a general relationship between the total variation distance of the joint distribution under independent coupling, $d_{TV}(X,Y)$, $X=(X_1, ...,X_n)$, $Y=(Y_1 , ... , Y_n)$ and the collection of distances between the marginals, $d_{TV}(X_i,Y_i)$?
3
-
1$\begingroup$ What do you mean by "under independent coupling"? $\endgroup$– Iosif PinelisCommented Nov 13 at 22:52
-
$\begingroup$ @IosifPinelis A coupling such that $P(x_1,...x_n)=\prod_{i=1}^n P(x_i)$ $\endgroup$– David PascallCommented Nov 14 at 12:04
-
$\begingroup$ What is $P$ here? Also, a coupling couples two objects. Why not just say that (say) the $X_i$'s are independent (if this is what you meant)? $\endgroup$– Iosif PinelisCommented Nov 14 at 13:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There is, but it is not tight, e.g. the upper and lower bounds qualitatively differ. What you're asking about is typically referred to as "tensorization" of the total variation distance. It is well-known that TV does not tensorize. Instead, what one can do is apply a generic inequality, such as
$$\tag{1} \frac{1}{2}H^2(P,Q) \leq \mathsf{TV}(P,Q) \leq H(P,Q), $$ where $H(P,Q)$ is the Hellinger distance, which satisfies the tensorization identity
$$\tag{2} \frac{1}{2}H^2(X,Y) = 1 - \prod_{i = 1}^n (1 - \frac{1}{2}H^2(X_i,Y_i)). $$
One can chain these inequalities together to get the result you are asking about. This yields roughly a quadratic gap between the lower and upper bound though (coming from the quadratic gap in Eq. 1).
It is worth mentioning one can sometimes do better than the above quadratic gap. Provided $\mathsf{TV}(X_i,Y_i)\geq \epsilon$ (some constant) for all $i$, it is straightforward to show that $\mathsf{TV}(X,Y)\to 1$ as $n\to\infty$. A natural quantity to study is $1 - \mathsf{TV}(X,Y)$, which is related to the optimal failure probability in testing the hypothesis $X$ vs $Y$. One can sometimes write
$$ 1-\mathsf{TV}(X,Y) = \exp(-D_B(X,Y)+o(1)) $$ for an appropriate distance measure $D_B$ that does tensorize (where the $o(1)$ is as $n\to\infty$). See Remark 16.2. More typically, one can only write $1-\mathsf{TV}(X,Y) = \exp(-C(X,Y)+o(1))$ for a distance measure $C(X,Y)$ which is somewhat hard to compute (the Chernoff information, see for example these notes). One can obtain bounds on $C(X,Y)$ in terms of a distance measure that does tensorize, but this is essentially equivalent to what was described in the first half of this answer.
