5
$\begingroup$

Let $X$ and $Y$ be distributions with statistical distance (total variation distance) at most $d$. What is the best upper bound you can give on the statistical distance between $k$ independent copies of $X$ and $k$ independent copies of $Y$?
I can show using a "hybrid argument" that it is at most $k\cdot d$, and I am looking for something better (maybe not always, but at least in some cases).

For example if $d=1/2$ and $k=2$ this bound is $1$ which is meaningless and it cannot be reached by actual distributions because $X_1,X_2$ and $Y_1,Y_2$ have statistical distance $1$ iff their supports are disjoint which would imply that the supports of $X$ and $Y$ are also disjoint in contradiction to $X$ and $Y$ having statistical distance at most $1/2$. The best example I could find was $X\equiv1$ and $Y$ being a uniformly distributed bit so the distance between $X$ and $Y$ is $1/2$ and the distance between $X_1,X_2$ and $Y_1,Y_2$ is $3/4$.

For general $k,d$ I'd like to show that the distance between $k$ samples of $X$ and $k$ samples of $Y$ is at most $1-\left(1-d\right)^k$. (For sanity check: $\left(1-d\right)^k\geq 1-d\cdot k$ for $k\geq 1,d\in\left[0,1\right]$ can be easily shown using basic calculus).
Can you do better (give a counter example), or can you prove that it is the best?

$\endgroup$
6
$\begingroup$

See the "inclusion-exclusion" Lemma 2.2 here https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf . For distributions $p,q,p',q'$, we have $$ ||p\otimes q-p'\otimes q'|| \le ||p-p'|| + ||q-q'|| - ||p-p'|| \cdot ||q-q'||. $$

From here, it immediately follows that if $p=p_1=p_2=\cdots=p_k$ and $q=q_1=p_2=\cdots=q_k$ and furthermore $||p-q||=d$, then the TV between the corresponding products is upper-bounded by $1-(1-d)^k$. This is proved explicitly in Lemma 4.2 in the linked paper.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Another (weaker) bound, along with a lower bound, both easy to obtain: using Hellinger distance as a proxy (and its relation to total variation distance), you get $$ 1-(1-d_{\rm TV}(p, q)^2 )^{k/2} \leq d_{\rm TV}(p^{\otimes k}, q^{\otimes k}) \leq \sqrt{1-(1-d_{\rm TV}(p, q) )^{2k}} $$ See e.g., Fact C.2.3 from my survey on distribution testing.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.