Sample complexity of distinguishing two Gaussian distributions? 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?
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?, 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, 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.