Multidimensional Chebyshev's inequality

In probability theory, the multidimensional Chebyshev's inequality is a generalization of Chebyshev's inequality, which puts a bound on the probability of the event that a random variable differs from its expected value by more than a specified amount.

Let X be an N-dimensional random vector with expected value $\mu =\mathrm{E}[X]$ and covariance matrix

$V=\mathrm{E}[(X-\mu )(X-\mu {)}^T].$

If $V$ is a positive-definite matrix, for any real number $t>0$:

$\mathrm{Pr}(\sqrt{(X-\mu {)}^T{V}^{-1}(X-\mu )}>t)\le \frac{N}{t^2}$

Proof

Since $V$ is positive-definite, so is $V^{-1}$. Define the random variable

$y=(X-\mu {)}^T{V}^{-1}(X-\mu ).$

Since $y$ is positive, Markov's inequality holds:

$\mathrm{Pr}(\sqrt{(X-\mu {)}^T{V}^{-1}(X-\mu )}>t)=\mathrm{Pr}(\sqrt{y}>t)=\mathrm{Pr}(y>t^2)\le \frac{\mathrm{E}[y]}{t^2}.$

Finally,

$\begin{array}{rl}\mathrm{E}[y]& =\mathrm{E}[(X-\mu {)}^T{V}^{-1}(X-\mu )]\\ & =\mathrm{E}[\mathrm{trace}(V^{-1}(X-\mu )(X-\mu {)}^T)]\\ & =\mathrm{trace}(V^{-1}V)=N\end{array}.$