Multidimensional Chebyshev’s inequality

Let $X$ be an N-dimensional random variable with mean $\mu =𝔼[X]$ and covariance matrix $V=𝔼\left[\left(X-\mu \right){\left(X-\mu \right)}^T\right]$.

If $V$ is invertible (i.e., strictly positive), for any $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: $V$ is positive, so $V^{-1}$ is. Define the random variable

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

$y$ is positive, then Markov’s inequality holds:

$$\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{𝔼[y]}{t^2}$$

Since $V$ is symmetric, a rotation $R$ (i.e., $R{R}^T=R^{T}R=I$) and a diagonal matrix $D$ (i.e., $i\ne j\Rightarrow D_{i,j}=0$) exist such that

$$V=R^{T}DR$$

Since $V$ is positive $D_{ii}>0$. Besides

$$V^{-1}=R^{-1}{D}^{-1}{(R^T)}^{-1}=R^T{D}^{-1}R$$

clearly ${\left[D^{-1}\right]}_{ii}=\frac{1}{D_{ii}}$.

Define $Z=R\left(X-\mu \right)$.

The following identities hold:

$$𝔼\left[Z{Z}^T\right]=R𝔼\left[\left(X-\mu \right){\left(X-\mu \right)}^T\right]R^T=R{R}^{T}DR{R}^T=D\mathit{\hspace{1em}}\Rightarrow \mathit{\hspace{1em}}\forall i\mathit{\hspace{1em}}𝔼\left[Z_i^2\right]=D_{ii}$$

and

$$y=Z^{T}R{V}^{-1}{R}^{T}Z=Z^T{D}^{-1}Z=\sum _{i=1}^N\frac{Z_i^2}{D_{ii}}$$

then

$$𝔼[y]=\sum _{i=1}^N\frac{𝔼\left[Z_i^2\right]}{D_{ii}}=N$$

Title	Multidimensional Chebyshev’s inequality
Canonical name	MultidimensionalChebyshevsInequality
Date of creation	2013-03-22 18:17:55
Last modified on	2013-03-22 18:17:55
Owner	daniWk (21206)
Last modified by	daniWk (21206)
Numerical id	5
Author	daniWk (21206)
Entry type	Theorem
Classification	msc 60A99