# Empirical estimator for total variation distance between two product distributions

Let $X = (X_1, X_2, \ldots , X_n)$ be an $n$-dimensional random variable, where each $X_i$ is a random variable on finite discrete set $S$. In addition, $X_i$ are independent of each other (but not identically distributed). That is, if we denote $X \sim \mathcal{D}$ and $X_i \sim \mathcal{D}_i$, then $\mathcal{D}$ is just the product of $\{ \mathcal{D}_i \}$.

Similarly, let $Y = (Y_1, Y_2, \ldots , Y_n) \sim \mathcal{D}'$ and $Y_i \sim \mathcal{D}'_i$ independently on $S$ (the same $S$ as $X_i$'s). Then $\mathcal{D}'$ is the product of $\{ \mathcal{D}'_i \}$. $X$ and $Y$ are independent.

Now I don't know $\mathcal{D}$ and $\mathcal{D}'$ precisely but I can sample from them (so that I can sample from all the marginal distributions $\mathcal{D}_i$ and $\mathcal{D}'_i$ as well). I would like to estimate the total variation between $\mathcal{D}$ and $\mathcal{D}'$.

Let $d = \|\mathcal{D} - \mathcal{D}'\|_{TV}$ and $\hat{d}$ be our estimator for $d$. Let $N$ be the number of samples we need. I hope to get an error-confidence bound of the form $$\Pr[ |\hat{d} - d| \ge \epsilon] \le \delta$$ where $\delta$ is at least polynomially small w.r.t. $n, |S|, N$ and $\epsilon$.

I just found a similar question. However, the sample space of $X$ and $Y$ here is $S^n$, which is exponentially large, making the bound in that post not applicable to this question. Besides, here we have $\mathcal{D}$ and $\mathcal{D}'$ being product distributions, which could probably make things easier.

Thank you.

I have something that may or may not be useful...

Diaconis notes an interpretation of variation distance of Paul Switzer. Consider $\mu$, $\nu\in M_p(S)$. Given a single observation of $S$, sampled from $\mu$ or $\nu$ with probability $1/2$, guess whether the observation, $o$, was sampled from $\mu$ or $\nu$. The classical strategy presented here gives the probability of being correct as $1/2(1+\|\mu-\nu\|)$:

1. Evaluate $\mu(o)$ and $\nu(o)$.
2. If $\mu(o)\geq\nu(o)$, choose $\mu$.
3. If $\nu(o)>\mu(o)$, choose $\nu$.

To see this is true, let $\{\mu>\nu\}$ be the set $\{t\in S:\mu(t)>\nu(t)\}$. Suppose $o$ is sampled from $\mu$. Then the strategy is correct if $o\in\{\mu=\nu\}$ or $o\in\{\mu>\nu\}$: $$\mathbb{P}[\text{guessing correctly}\,|\,\mu]=\mathbb{P}[o\in\{\mu=\nu\}\,|\,\mu]+\mathbb{P}[o\in\{\mu>\nu\}\,|\,\mu]$$ with a similar expression for $\mathbb{P}[\text{guessing correctly}\,|\,\nu]$.

Note that $\mathbb{P}[o\in\{\mu=\nu\}]=\mu(\{\mu=\nu\})=\nu(\{\mu=\nu\})$ and also $\mathbb{P}[o\in\{\mu>\nu\}\,|\,\mu]=\mu(\{\mu>\nu\})$ (and similar for $o\in\{\mu<\nu\}$). Thus \begin{align*} \mathbb{P}[\text{guessing correctly}] &=\frac12\mathbb{P}[\text{guessing correctly}\,|\,\mu]+\frac12\mathbb{P}[\text{guessing correctly}\,|\,\nu] \\&=\frac12\left(\nu(\{\mu=\nu\})+\mu(\{\mu>\nu\})\right)+\frac12\left(\nu(\{\mu<\nu\})\right) \end{align*} It is easily shown that $$\|\mu-\nu\|=\mu\left(\{\mu>\nu\}\right)-\nu\left(\{\mu>\nu\}\right).$$ Hence $$\mathbb{P}[\text{guessing correctly}]=\frac12\left(\underbrace{\nu(\{\mu=\nu\})+\nu(\{\mu>\nu\})+\nu(\{\mu<\nu\})}_{=1}+\|\mu-\nu\|)\right).$$

Anton, I think your "max" should be a "min".

If I understood your identity correctly, it means that if I define $$\mu_n$$ to be the product of $$(p,1-p)$$ Bernoulli measures on $$\{0,1\}^n$$ and $$\nu_n$$ to be the product of $$(p',1-p')$$ Bernoulli measures on $$\{0,1\}^n$$, then you're saying that $$||\mu_n-\nu_n|| = |p-p'|^n$$ which decays to zero, while of course $$\lim_{n\to\infty} ||\mu_n-\nu_n|| = 1$$ for $$p\neq p'$$.

A correct upper bound on the total variation between product distributions may be found in https://arxiv.org/abs/0711.0987 (Lemma 2.2 for 2 distributions, which generalizes to $$n$$-fold products via the "inclusion-exclusion" formula in Lemma 4.2)

To answer the original question: that "inclusion-exclusion" bound I cited above implies that $$||{\cal D} - {\cal D}'|| \le \sum_{i=1}^n ||{\cal D}_i - {\cal D}'_i||.$$

Further, by the triangle inequality, $$||\hat {\cal D}_i - \hat {\cal D}'_i|| \le ||{\cal D}_i - \hat {\cal D}_i|| + ||{\cal D}'_i - \hat {\cal D}'_i||,$$ where $$\hat{\cdot}$$ indicates the empirical distribution. Finally, it is trivial to show that if we define $$J_i := ||{\cal D}_i - \hat {\cal D}_i||,$$ then $$\mathbb{E}[J_i] \le \sqrt{|S|/N}$$ and $$\mathbb{P}( J_i > \mathbb{E}[J_i] + \epsilon) \le \exp(-N\epsilon^2/2)$$ [see (5) and (17) in https://www.sciencedirect.com/science/article/pii/S0167715213000242 ]. I believe this answers your question.