<p>I don't have a solution to this problem, but the analogous case where the two distributions are discrete has been analyzed in the cryptographic literature.</p>

<p>Suppose we want to distinguish between two distributions $\mathcal{D}_0$, $\mathcal{D}_1$, where these two distributions are "close".  Suppose we have $n$ observations (i.e., a sequence of $n$ numbers that are sampled from either i.i.d. $\mathcal{D}_0$ or i.i.d $\mathcal{D}_1$), and we want to distinguish whether they came from $\mathcal{D}_0$ or from $\mathcal{D}_1$.  Let $d = 0.5 n/D(\mathcal{D}_0 ||\mathcal{D}_1)$, where $D(\mathcal{D}_0 ||\mathcal{D}_1)$ is the Kullback-Leibler divergence between these two distributions.  Then the optimal distinguisher has a probability of error approximately $\Phi(-\sqrt{d}/2)$, where $\Phi(t)$ is the pdf of the standard normal distribution.</p>

<p>See Theorem 6 from <a href="http://infoscience.epfl.ch/record/88161?ln=en" rel="nofollow noreferrer">How Far Can We Go Beyond Linear Cryptanalysis?</a>, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.</p>

<p>I have no proof that this is valid for multivariate Gaussian distributions as well, but it seems reasonable to conjecture that it might.</p>

<hr>

<p>Stepping away from discrete distributions, in your particular case of normal distributions, the one-dimensional case ($p=1$) has also been studied in the cryptographic literature.  If you want to distinguish $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$ given a single observation, the optimal distinguisher has probability of error $\text{erfc}(z)$ where $z = (\mu_1-\mu_0)/(\sigma_0+\sigma_1)$.  I don't recall what happens when you get to see $n$ samples from either $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$, but I imagine this case has been worked out before as well.</p>

<p>See <a href="https://cstheory.stackexchange.com/a/22339/5038">https://cstheory.stackexchange.com/a/22339/5038</a>.</p>

<p>In the multivariate case, the Kullback-Leibler divergence between two multivariate Gaussians is known: see <a href="https://en.wikipedia.org/wiki/Multivariate_normal_distribution#Kullback.E2.80.93Leibler_divergence" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Multivariate_normal_distribution#Kullback.E2.80.93Leibler_divergence</a>.</p>

<p>Also, the Kullback-Leibler divergence is additive when you have $n$ i.i.d. samples, so the Kullback-Leibler divergence of the product distribution will be $n$ times the KL divergence for a single sample: $D(\mathcal{D}_0^n ||\mathcal{D}_1^n) = n \times D(\mathcal{D}_0 ||\mathcal{D}_1)$.  This is a very handy property of the KL divergence, and it will let you calculate the KL divergence between $n$ samples of $\mathcal{N}(\mu_0,\Sigma)$ vs $n$ samples of $\mathcal{N}(\mu_1,\Sigma)$.  (As a conjecture, I would guess that the distinguishing advantage becomes significant only when this KL divergence becomes significant, though I don't know any proof of this.)</p>

<hr>

<p>Finally, you might be interested in <a href="https://en.wikipedia.org/wiki/Pinsker%27s_inequality" rel="nofollow noreferrer">Pinsker's inequality</a>, which connects the total variation distance to the Kullback-Leibler divergence.  The total variation distance measures (twice) the advantage of the optimal distinguisher.</p>

<p>Unfortunately, depending on your goals, Pinsker's inequality might "go the wrong way".</p>

<p>See also <a href="https://stats.stackexchange.com/q/17300/2921">https://stats.stackexchange.com/q/17300/2921</a> and <a href="https://math.stackexchange.com/q/72721/14578">https://math.stackexchange.com/q/72721/14578</a> and <a href="https://stats.stackexchange.com/q/42992/2921">https://stats.stackexchange.com/q/42992/2921</a></p>

<hr>

<p>Update: All of this assumes the two distributions are known.  I just noticed that you want to consider a version of the problem where the distributions are not known to the algorithm.  This can only make the problem harder, but I don't know how much harder, and I don't know of anyone who has studied that variant.</p>

CC BY-SA 3.0
2015-03-27T23:07:24.373Z
2015-03-30T01:53:48.130Z
2017-04-13T12:44:17.130Z
D.W.
<p>Below is a description of the problem:</p>

<hr>

<p>Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$.</p>

<p>And I can get $n$ samples $X_1^{(1)}, X_1^{(2)}, \dots, X_1^{(n)}$ from $\mathcal{N}(\mu_1, \Sigma)$, and another $n$ samples $X_0^{(1)}, X_0^{(2)}, \dots, X_0^{(n)}$ from $\mathcal{N}(\mu_0, \Sigma)$.</p>

<p>Then I flip an unbiased coin $b\in\{1,0\}$, and take a sample $s$ from $\mathcal{N}(\mu_b,\Sigma)$.</p>

<p>I then give the samples $X_1^{(1)}, X_1^{(2)}, \dots, X_1^{(n)}$ and $X_0^{(1)}, X_0^{(2)}, \dots, X_0^{(n)}$ to an algorithm with the sample $s$. The algorithm outputs a bit $b'$ to indicate that the algorithm thinks that $s$ is from $\mathcal{N}(\mu_{b'},\Sigma)$.</p>

<p>Note that the algorithm does not know $\Sigma$, $\mu_1$, $\mu_0$.</p>

<p>The question is: How large should $n$ be so that $\Pr[b=b'] \geq \frac{1}{2}+\epsilon$?</p>

<p>(The bound should be given in terms of $\epsilon$, $\Sigma$, $\mu_1$, $\mu_0$.)</p>

<hr>

<p>Are there any papers that have solutions to this problem?</p>

CC BY-SA 3.0
2015-03-28T13:10:28.533Z
(1) There is some optimal upper-bound on $\epsilon$ even if the algorithm knows $\Sigma, \mu_1,\mu_2$. Wouldn't the optimal strategy if it knows the parameters be to compute the MLE, *i.e* pick the distribution whose mean is closest to $s$? And in this easier case, can you give us the expression for the optimal $\epsilon$ in terms of $\Sigma,\mu_1,\mu_2$? (2) I doubt you can do better than estimating the mean of each sample and picking whichever is closer to $s$. But then you mainly just need to analyze the error of estimating the mean together with the above computation.
usul
CC BY-SA 3.0
2015-03-28T13:10:44.180Z
(3) This is an unusual setup, right? What I expected is that you either give the algorithm $\{X_1^{(i)}\}$ or else $\{X_0^{(i)}\}$, and the algorithm must guess whether these came from the first distribution or the second.
usul
CC BY-SA 3.0
2015-03-28T14:08:17.663Z
@usul Here I assume that $\epsilon \to 0$, and would like to find a sample lower bound for binary classification as in Linear Discriminant Analysis.
Tianyang Li
CC BY-SA 3.0
2015-03-28T21:08:25.497Z
This seems like a question statisticians would have considered. I'd bet that the optimal test is to get estimates $\hat{\mu}_0$ and $\hat{\mu}_1$ of $\mu_0$ and $\mu_1$ from the samples and test which of these two $s$ is closest to. This should be straightforward to analyse.
Thomas Steinke
<reference-request><machine-learning><lg.learning><sample-complexity>
Sample complexity of distinguishing two Gaussian distributions?
Tianyang Li
# Sample complexity of distinguishing two Gaussian distributions?

(Asked by: username_0 on 2015-03-27)

Below is a description of the problem:

---

Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu\_1$, $\mu\_0$.

And I can get $n$ samples $X\_1^{(1)}, X\_1^{(2)}, \dots, X\_1^{(n)}$ from $\mathcal{N}(\mu\_1, \Sigma)$, and another $n$ samples $X\_0^{(1)}, X\_0^{(2)}, \dots, X\_0^{(n)}$ from $\mathcal{N}(\mu\_0, \Sigma)$.

Then I flip an unbiased coin $b\in\{1,0\}$, and take a sample $s$ from $\mathcal{N}(\mu\_b,\Sigma)$.

I then give the samples $X\_1^{(1)}, X\_1^{(2)}, \dots, X\_1^{(n)}$ and $X\_0^{(1)}, X\_0^{(2)}, \dots, X\_0^{(n)}$ to an algorithm with the sample $s$. The algorithm outputs a bit $b'$ to indicate that the algorithm thinks that $s$ is from $\mathcal{N}(\mu\_{b'},\Sigma)$.

Note that the algorithm does not know $\Sigma$, $\mu\_1$, $\mu\_0$.

The question is: How large should $n$ be so that $\Pr[b=b'] \geq \frac{1}{2}+\epsilon$?

(The bound should be given in terms of $\epsilon$, $\Sigma$, $\mu\_1$, $\mu\_0$.)

---

Are there any papers that have solutions to this problem?

**Tags:** reference-request, machine-learning, lg.learning, sample-complexity
> **Comments:**
> **username_1**: (1) There is some optimal upper-bound on $\epsilon$ even if the algorithm knows $\Sigma, \mu_1,\mu_2$. Wouldn't the optimal strategy if it knows the parameters be to compute the MLE, *i.e* pick the distribution whose mean is closest to $s$? And in this easier case, can you give us the expression for the optimal $\epsilon$ in terms of $\Sigma,\mu_1,\mu_2$? (2) I doubt you can do better than estimating the mean of each sample and picking whichever is closer to $s$. But then you mainly just need to analyze the error of estimating the mean together with the above computation.  
> **username_1**: (3) This is an unusual setup, right? What I expected is that you either give the algorithm $\{X_1^{(i)}\}$ or else $\{X_0^{(i)}\}$, and the algorithm must guess whether these came from the first distribution or the second.  
> **username_0**: @usul Here I assume that $\epsilon \to 0$, and would like to find a sample lower bound for binary classification as in Linear Discriminant Analysis.  
> **username_2**: This seems like a question statisticians would have considered. I'd bet that the optimal test is to get estimates $\hat{\mu}_0$ and $\hat{\mu}_1$ of $\mu_0$ and $\mu_1$ from the samples and test which of these two $s$ is closest to. This should be straightforward to analyse.  

---

## 1 answers

### Answer by username_3 on 2015-03-27. Score: 6

I don't have a solution to this problem, but the analogous case where the two distributions are discrete has been analyzed in the cryptographic literature.

Suppose we want to distinguish between two distributions $\mathcal{D}\_0$, $\mathcal{D}\_1$, where these two distributions are "close". Suppose we have $n$ observations (i.e., a sequence of $n$ numbers that are sampled from either i.i.d. $\mathcal{D}\_0$ or i.i.d $\mathcal{D}\_1$), and we want to distinguish whether they came from $\mathcal{D}\_0$ or from $\mathcal{D}\_1$. Let $d = 0.5 n/D(\mathcal{D}\_0 ||\mathcal{D}\_1)$, where $D(\mathcal{D}\_0 ||\mathcal{D}\_1)$ is the Kullback-Leibler divergence between these two distributions. Then the optimal distinguisher has a probability of error approximately $\Phi(-\sqrt{d}/2)$, where $\Phi(t)$ is the pdf of the standard normal distribution.

See Theorem 6 from [How Far Can We Go Beyond Linear Cryptanalysis?](http://infoscience.epfl.ch/record/88161?ln=en), Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

I have no proof that this is valid for multivariate Gaussian distributions as well, but it seems reasonable to conjecture that it might.

---

Stepping away from discrete distributions, in your particular case of normal distributions, the one-dimensional case ($p=1$) has also been studied in the cryptographic literature. If you want to distinguish $\mathcal{N}(\mu\_0,\sigma\_0^2)$ from $\mathcal{N}(\mu\_1,\sigma\_1^2)$ given a single observation, the optimal distinguisher has probability of error $\text{erfc}(z)$ where $z = (\mu\_1-\mu\_0)/(\sigma\_0+\sigma\_1)$. I don't recall what happens when you get to see $n$ samples from either $\mathcal{N}(\mu\_0,\sigma\_0^2)$ from $\mathcal{N}(\mu\_1,\sigma\_1^2)$, but I imagine this case has been worked out before as well.

See <https://cstheory.stackexchange.com/a/22339/5038>.

In the multivariate case, the Kullback-Leibler divergence between two multivariate Gaussians is known: see <https://en.wikipedia.org/wiki/Multivariate_normal_distribution#Kullback.E2.80.93Leibler_divergence>.

Also, the Kullback-Leibler divergence is additive when you have $n$ i.i.d. samples, so the Kullback-Leibler divergence of the product distribution will be $n$ times the KL divergence for a single sample: $D(\mathcal{D}\_0^n ||\mathcal{D}\_1^n) = n \times D(\mathcal{D}\_0 ||\mathcal{D}\_1)$. This is a very handy property of the KL divergence, and it will let you calculate the KL divergence between $n$ samples of $\mathcal{N}(\mu\_0,\Sigma)$ vs $n$ samples of $\mathcal{N}(\mu\_1,\Sigma)$. (As a conjecture, I would guess that the distinguishing advantage becomes significant only when this KL divergence becomes significant, though I don't know any proof of this.)

---

Finally, you might be interested in [Pinsker's inequality](https://en.wikipedia.org/wiki/Pinsker%27s_inequality), which connects the total variation distance to the Kullback-Leibler divergence. The total variation distance measures (twice) the advantage of the optimal distinguisher.

Unfortunately, depending on your goals, Pinsker's inequality might "go the wrong way".

See also <https://stats.stackexchange.com/q/17300/2921> and <https://math.stackexchange.com/q/72721/14578> and <https://stats.stackexchange.com/q/42992/2921>

---

Update: All of this assumes the two distributions are known. I just noticed that you want to consider a version of the problem where the distributions are not known to the algorithm. This can only make the problem harder, but I don't know how much harder, and I don't know of anyone who has studied that variant.


---

