Let $X$ be a multivariate normal random variable with known mean and covariance, and $Y$ be another random variable. We know for sure $\|X−Y\|_2\le C$ where $C$ is a known constant. A few questions: Is it possible for $Y$ to be normally distributed? Can we say anything about its mean and/or covariance? If we know the mean of $Y$, can we say something about its covariance?

  • 2
    $\begingroup$ Trivial observation to address the first question: when $Y=X$ the condition is satisfied for any non-negative $C$ and obviously $Y$ is normal. Suggestion: draw pictures of the situation when $X$ is univariate. They will make it easy to see that the answers to the questions are "Yes," "A little," and "A little" (in the sense of some bounds). $\endgroup$ – whuber Mar 26 '12 at 20:36
  • $\begingroup$ Thanks, how can I compute these bounds? What should I be looking at? $\endgroup$ – sks Mar 26 '12 at 20:41
  • 2
    $\begingroup$ Write $Y$ as $X+U$ where $U$ is distributed over the ball of radius $C$. This should tell you something about the mean of $Y$. Same thing about the covariance. $\endgroup$ – Xi'an Mar 26 '12 at 20:52
  • 1
    $\begingroup$ Nice idea, X'ian. Note, however, that this approach will not give the full range of possibilities for the covariance: for that to occur, you need $U$ to depend on $X$. $\endgroup$ – whuber Mar 26 '12 at 21:15
  • 1
    $\begingroup$ @whuber: ah! Strictly speaking, : "$U$ distributed over the ball of radius $C$" does not exclude $U$ dependent on $X$! Even though in truth I was not considering this case... $\endgroup$ – Xi'an Mar 28 '12 at 9:23

To get a feeling for the question, consider the univariate case. We can always choose an origin and unit of measurement to make $X$ a standard normal variate (with mean $0$ and unit variance).

The mean of $Y$ (call it $\nu$) can be anywhere between $-C$ and $C$ simply by setting $Y = X + \nu$. Clearly $\|X-Y\| = |X-Y| = |\nu| \le C$. This works in the other direction, though: when the mean of $Y$ exceeds $X+C$, then $E[Y-X] \gt C$ implies $\Pr(|X-Y| \gt C) \gt 0$, violating the assumption. This gives definite, clean bounds on the mean.

We can maximize the variance of $Y$ by setting $Y=X+C$ when $X \gt 0$ and $Y=X-C$ when $X \lt 0$ (and choose whichever you want when $X=0$, because this zero-probability event does not contribute to the variance). In other words, we spread $Y$ as far from the mean as we possibly can. Doing the integral, we find this makes the variance as large as $1+C^2 + 2C\sqrt{\frac{2}{\pi}}$.

To minimize the variance of $Y$, I believe we should set $Y=0$ whenever $-C \lt X \lt C$ and otherwise set $Y=X-C$ for $X \ge C$ and $Y=X+C$ for $X \le -C$. In other words, we push $Y$ towards the mean as much as we can. By symmetry of construction, the mean of $Y$ is zero, whence its variance is the expectation of $Y^2$, equal to

$$\text{Var}(Y) = 2\int_C^\infty (x-C)^2 \phi(x)dx = \frac{-2C \exp(-C^2/2)}{\sqrt{2\pi}}+(1+C^2)\text{erfc}(\frac{C}{\sqrt{2}})$$

($\phi$ is the standard normal PDF). A plot of this variance against $C$ is informative:

Figure 1

This makes intuitive sense: as $C$ grows above $0$, we may place more and more of the probability of $Y$ right on $0$, leaving all the contribution to $Y$'s variance from the tail of a normal distribution, which decreases rapidly.

Putting these results together yields a plot of the allowable interval of variances of $Y$ for small values of $C$:

Figure 2

The lower curve is the same as before; the upper curve is part of a parabola: it grows quadratically.

The analysis in the multivariate case will be the same for the mean--that is computed separately for the marginal distributions--but becomes much more complicated for the covariance, especially its off-diagonal elements. A full, exact answer may be difficult even to write down.

| cite | improve this answer | |
  • $\begingroup$ Wow, this is very detailed, thanks a lot! I think this is exactly what I was looking for. Now I just have to generalize this to the multivariate case :) the good thing is that there are no off-diagonal elements - individual components are all independent. $\endgroup$ – sks Mar 26 '12 at 21:16
  • $\begingroup$ I suspect you can get best bounds on the diagonal elements of the covariance using the same approach. But to bound the off-diagonal elements will be much more difficult. The full bounds will be connected sets of symmetric positive-definite matrices potentially having complicated shapes. $\endgroup$ – whuber Mar 26 '12 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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