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}{cc}\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}.$

Infinite dimensions

There is a straightforward extension of the vector version of Chebyshev's inequality to infinite dimensional settings^{[more refs. needed]}. Let X be a random variable which takes values in a Fréchet space $𝒳$ (equipped with seminorms || ⋅ ||_α). This includes most common settings of vector-valued random variables, e.g., when $𝒳$ is a Banach space (equipped with a single norm), a Hilbert space, or the finite-dimensional setting as described above.

Suppose that X is of "strong order two", meaning that

$\mathrm{E}(\Vert X{\Vert }_{\alpha }^2)<\mathrm{\infty }$

for every seminorm || ⋅ ||_α. This is a generalization of the requirement that X have finite variance, and is necessary for this strong form of Chebyshev's inequality in infinite dimensions. The terminology "strong order two" is due to Vakhania.

Let $\mu \in 𝒳$ be the Pettis integral of X (i.e., the vector generalization of the mean), and let

${\sigma }_a:=\sqrt{\mathrm{E}\Vert X-\mu {\Vert }_{\alpha }^2}$

be the standard deviation with respect to the seminorm || ⋅ ||_α. In this setting we can state the following:

General version of Chebyshev's inequality. $\mathrm{\forall }k>0:\mathrm{Pr}(\Vert X-\mu {\Vert }_{\alpha }\ge k{\sigma }_{\alpha })\le \frac{1}{k^2}.$

Proof. The proof is straightforward, and essentially the same as the finitary version^{[source needed]}. If σ_α = 0, then X is constant (and equal to μ) almost surely, so the inequality is trivial.

If

$\Vert X-\mu {\Vert }_{\alpha }\ge k{\sigma }_{\alpha }$

then ||X − μ||_α > 0, so we may safely divide by ||X − μ||_α. The crucial trick in Chebyshev's inequality is to recognize that $1=\frac{\Vert X-\mu {\Vert }_{\alpha }^2}{\Vert X-\mu {\Vert }_{\alpha }^2}$.

The following calculations complete the proof:

$\begin{array}{cc}\mathrm{Pr}(\Vert X-\mu {\Vert }_{\alpha }\ge k{\sigma }_{\alpha })& =\underset{\Omega }{\int }{\mathrm{𝟏}}_{\Vert X-\mu {\Vert }_{\alpha }\ge k{\sigma }_{\alpha }}\mathrm{d}\mathrm{Pr}\\ & =\underset{\Omega }{\int }\left(\frac{\Vert X-\mu {\Vert }_{\alpha }^2}{\Vert X-\mu {\Vert }_{\alpha }^2}\right)\cdot {\mathrm{𝟏}}_{\Vert X-\mu {\Vert }_{\alpha }\ge k{\sigma }_{\alpha }}\mathrm{d}\mathrm{Pr}\\ & \le \underset{\Omega }{\int }\left(\frac{\Vert X-\mu {\Vert }_{\alpha }^2}{(k{\sigma }_{\alpha }{)}^2}\right)\cdot {\mathrm{𝟏}}_{\Vert X-\mu {\Vert }_{\alpha }\ge k{\sigma }_{\alpha }}\mathrm{d}\mathrm{Pr}\\ & \le \frac{1}{k^2{\sigma }_{\alpha }^2}\underset{\Omega }{\int }\Vert X-\mu {\Vert }_{\alpha }^2\mathrm{d}\mathrm{Pr}& & {\mathrm{𝟏}}_{\Vert X-\mu {\Vert }_{\alpha }\ge k{\sigma }_{\alpha }}\le 1\\ & =\frac{1}{k^2{\sigma }_{\alpha }^2}(\mathrm{E}\Vert X-\mu {\Vert }_{\alpha }^2)\\ & =\frac{1}{k^2{\sigma }_{\alpha }^2}\left({\sigma }_{\alpha }^2\right)\\ & =\frac{1}{k^2}\end{array}$