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)\leq {\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)\\&\leq {\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}}.$