5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ (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. $\endgroup$
    – usul
    Commented Mar 28, 2015 at 13:10
  • 1
    $\begingroup$ (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. $\endgroup$
    – usul
    Commented Mar 28, 2015 at 13:10
  • $\begingroup$ @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. $\endgroup$
    – Tianyang Li
    Commented Mar 28, 2015 at 14:08
  • $\begingroup$ 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. $\endgroup$
    – Thomas Steinke
    Commented Mar 28, 2015 at 21:08

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\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.