Statistical Distance Growth Given K Independent Copies

Question

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?

Answer 1

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 2

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.