2
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

0
$\begingroup$

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).$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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