Probability that at least one sample lies within a given st.d.?

I think my question is similar to this one, but different in that I consider a set of realisations, not only one. Sorry if this question is really easy, I'm just not sure how to go rigorously about it.

Say I have $N$ realisations from a multivariate normal distribution $\mathcal{N}(\mu,\Sigma)$. Intuitively, I would expect that the larger $N$, and the more likely I would be to get at least one realisation lying within $\epsilon$ st.d. of the mean $\mu$. I feel that this mixes discrete and continuous probabilities, and I need help to understand how to come up with what I guess is an expectation formula in this case.

Note that while it is clear what "within $\epsilon$ st.d." means in the one-dimensional case, the multidimensional counterpart corresponds to "within the range $[0,\epsilon]$ of the Mahalanobis distance".

If I had to have a go at it, I would find the probability of none being within, as the inverse cumulated density at $\epsilon$ st.d. (the probability of NOT being within), raised to the $N$, or:

$$\left( \frac{1-\mathrm{erf}(\epsilon)}{2} \right)^N$$

So the probability of at least one, would be one minus that, is that right?

• I wonder what you might mean by "$\epsilon$ st.d. of the mean $\mu$", since there isn't any single standard deviation in sight (unless $\Sigma$ is a multiple of the identify matrix). What, then, does "st.d." actually refer to? What is its relationship to $\Sigma$? – whuber Feb 25 '16 at 20:53
• @whuber Standard deviations still have a meaning in dimension n, because the matrix $\Sigma$ defines a "mode of variation" if you will, as an ellipsoid in the general case (defined by the eigenvectors of $\Sigma$). See my other comment below. – Sheljohn Feb 25 '16 at 22:57
• The problem is that there no longer is one single measure of SD. Once again: what could you possibly mean by "$\sigma$" or the "st.d." in such a setting? Mahalanobis distance, perhaps? I still have little idea what you're really trying to ask, although the general thrust can readily be guessed. – whuber Feb 26 '16 at 0:24
• @whuber Yes, "within the range $[0,\epsilon]$ of the Mahalanobis distance" is what I mean by "within $\epsilon$ st.d.". Sorry for the hand-wavy explanation with the ellipsoid, I used the Mahalanobis distance in the former edits of the OP actually and didn't realise that I removed it entirely, and that it made the whole idea of a standard deviation unclear. – Sheljohn Feb 26 '16 at 4:15

One-dimensional case

The probability of observing $x$ within the interval $\mu \pm \epsilon\sigma$ in a single draw is

$$\Pr(X \in [\mu-\epsilon\sigma, \mu+\epsilon\sigma]) = \Pr(|X-\mu| \le \epsilon\sigma)$$

The event "at least one within this interval in $N$ draws" is the complement of "none within this interval in $N$ draws", so we first need to calculate the probability of not being in the interval:

$$1 - \Pr(|X-\mu| \le \epsilon\sigma) = \Pr\left( \left|\frac{X - \mu}{\sigma} \right| > \epsilon \right) = p$$

and then consider this happening $N$ times consecutively (but independently), which simply corresponds to the probability $p^N$ (cf formula in the OP). Finally, the event of interest is the complement of this, so $1-p^N$ is the answer.

As pointed out in comment by Dilip Sarwate, we have in the one-dimensional case

$$\Pr\left( \left|\frac{X - \mu}{\sigma} \right| > \epsilon \right) = \Phi(\epsilon)-\Phi(-\epsilon) = 2\Phi(\epsilon)-1 = \mathrm{erf}(\epsilon/\sqrt{2})$$

where we used the fact that $\Phi(-x) = 1-\Phi(x)$ for symmetric distributions.

Multi-dimensional case

The approach is similar, but now $p$ has a different formulation

$$p=\Pr\left( \left|\frac{X - \mu}{\sigma} \right| > \epsilon \right) \quad\to\quad p=\Pr\left( \mathcal{M}_{\mu,\Sigma}(X)\in [0,\epsilon] \right)$$

using the Mahalanobis distance $\mathcal{M}_{\mu,\Sigma}(x) = \sqrt{ (x-\mu)^t \Sigma^{-1} (x-\mu) }$. Furthermore the "cumulative" density function doesn't make sense anymore (there is no obvious partial order in dimension n), but I think the previous result $p = \mathrm{erf}(\epsilon/\sqrt{2})$ still holds regardless of the number of dimensions, although I don't know how to prove it.

• Good job! Now note that for any normal random variable $X$ with mean $\mu$ and standard deviation $\sigma$, $$\Pr\left( \left|\frac{X - \mu}{\sigma} \right| > \epsilon \right) = \Phi(\epsilon) - \Phi(-\epsilon) = 2\Phi(\epsilon)-1$$ where $\Phi(\cdot)$ is the cumulative probability distribution function of a standard normal random variable. – Dilip Sarwate Feb 25 '16 at 20:48
• What is the connection between the "$\sigma$" in this answer and the "$\Sigma$" referenced in your question? – whuber Feb 25 '16 at 20:54
• @whuber This is actually a question I asked myself, so I went with the 1-dimensional formulation because it is immediately clear. In the n-dimensional counterpart, I would say the equation $|X-\mu|\leq \epsilon\sigma$ translates to the sentence "points within the ellipsoid defined by the eigenvectors of $\epsilon\Sigma$", where $\epsilon$ acts as a scaling factor. The point is that the formula in the OP is valid regardless of the dimension, because the argument of $\mathrm{erf}$ is a number of deviations, no matter their form. Does that make sense? – Sheljohn Feb 25 '16 at 22:54
• The latter part makes no sense to me, but the former part of your comment sounds like you are trying to use Mahalanobis distance. You don't quite get there because in addition to the eigenvectors you need some sense of relative scale along each such direction, which is usually afforded by the eigenvalues. – whuber Feb 26 '16 at 0:26
• No, it does not. At bottom, you are confusing squares with disks: probabilities within squares can be obtained as products of error functions, but probabilities within disks (which is what you are computing when you are using the Mahalanobis distance) are obtained from chi-squared or chi distributions (they have equivalent uses in this setting). – whuber Feb 28 '16 at 22:45