<p>See the "inclusion-exclusion" Lemma 2.2 here
<a href="https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf</a> .
For distributions <span class="math-container">$p,q,p',q'$</span>, we have
<span class="math-container">$$ 
||p\otimes q-p'\otimes q'||
\le
||p-p'||
+
||q-q'||
-
||p-p'||
\cdot
||q-q'||.
$$</span></p>

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

CC BY-SA 4.0
2019-03-03T11:39:34.657Z
2019-03-04T08:25:50.723Z
2019-03-04T08:25:50.723Z
Aryeh
<p>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
<span class="math-container">$$
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}}
$$</span>
See e.g., Fact C.2.3 from my <a href="https://eccc.weizmann.ac.il//report/2015/063/" rel="nofollow noreferrer">survey on distribution testing</a>.</p>

CC BY-SA 4.0
2019-03-04T21:17:38.097Z
2019-03-04T21:29:40.110Z
2019-03-04T21:29:40.110Z
Clement C.
<p>Let <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> be distributions with statistical distance (total variation distance) at most <span class="math-container">$d$</span>. What is the best upper bound you can give on the statistical distance between <span class="math-container">$k$</span> independent copies of <span class="math-container">$X$</span> and <span class="math-container">$k$</span> independent copies of <span class="math-container">$Y$</span>?<br>
I can show using a "hybrid argument" that it is at most <span class="math-container">$k\cdot d$</span>, and I am looking for something better (maybe not always, but at least in some cases).  </p>

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

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

<pr.probability>
Statistical Distance Growth Given K Independent Copies
Nathan
# Statistical Distance Growth Given K Independent Copies

(Asked by: username_0 on 2019-03-03)

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?

**Tags:** pr.probability

---

## 2 answers

### Answer by username_1 on 2019-03-03. Score: 6 | Accepted answer

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.


---

### Answer by username_2 on 2019-03-04. Score: 1

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](https://eccc.weizmann.ac.il//report/2015/063/).


---

