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 ${\displaystyle \mu =\operatorname {E} [X]}$ and covariance matrix

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

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

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

Proof

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

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

Since ${\displaystyle y}$ is positive, Markov's inequality holds:

${\displaystyle \Pr \left({\sqrt {(X-\mu )^{T}V^{-1}(X-\mu )}}>t\right)=\Pr({\sqrt {y}}>t)=\Pr(y>t^{2})\leq {\frac {\operatorname {E} [y]}{t^{2}}}.}$

Finally,

${\displaystyle {\begin{aligned}\operatorname {E} [y]&=\operatorname {E} [(X-\mu )^{T}V^{-1}(X-\mu )]\\[6pt]&=\operatorname {E} [\operatorname {trace} (V^{-1}(X-\mu )(X-\mu )^{T})]\\[6pt]&=\operatorname {trace} (V^{-1}V)=N\end{aligned}}.}$