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=\mathbb{E} \left[ X \right]$ and covariance matrix

$V=\mathbb{E} \left[ \left(X - \mu \right) \left( X - \mu \right)^T \right]. \,$

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

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

Proof

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

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

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

$\begin{array}{lll}\mathrm{Pr}\left( \sqrt{\left( X-\mu\right)^T \, V^{-1} \, \left( X-\mu\right) } > t\right) &= \mathrm{Pr}\left( \sqrt{y} > t\right)\\ &=\mathrm{Pr}\left( y > t^2 \right) \\ &\le \frac{\mathbb{E}[y]}{t^2} .\end{array}$

Finally,

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