Multidimensional Chebyshev's inequality explained

In probability theory, the multidimensional Chebyshev's inequality^[1] 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 = \operatorname{E}[X] and covariance matrixV = \operatorname{E} [(X - \mu) (X - \mu) ^{T].}

If

V is a positive-definite matrix, for any real number t> 0 :\Pr \left( \sqrt{( X - \mu) ^{T} V ^{-1} (X - \mu) } > t\right) \le (N)/(t ^{2})

Proof

Since

V is positive-definite, so is V ^{-1} . Define the random variabley = (X - \mu) ^{T} V ^{-1} (X - \mu).

Since

y is positive, Markov's inequality holds:\Pr\left( \sqrt{(X - \mu) ^{T} V ^{-1} (X - \mu) } > t\right) = \Pr( \sqrt{y} > t) = \Pr(y > t ^{2) \le} (\operatorname{E)/([y]}{t) ^{2}.}

Finally,

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

Infinite dimensions

l X (equipped with seminorms). This includes most common settings of vector-valued random variables, e.g., when l X is a Banach space (equipped with a single norm), a Hilbert space, or the finite-dimensional setting as described above.

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

\operatorname{E}\left(\| X\| ^{2} _{\alpha} \right) < inf ty

for every seminorm . This is a generalization of the requirement that 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.^[4]

Let

\mu \in l X be the Pettis integral of (i.e., the vector generalization of the mean), and let\sigma _{a} : = \sqrt{\operatorname{E}\|X - \mu\| ^{2 }} _{\alpha}

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

General version of Chebyshev's inequality.

\forall k > 0 : \Pr\left( \|X - \mu\| _{\alpha} \ge k \sigma _{\alpha} \right) \le (1)/(k ^{2}) .

Proof. The proof is straightforward, and essentially the same as the finitary version. If, then is constant (and equal to) almost surely, so the inequality is trivial.

If

\|X - \mu\| _{\alpha} \ge k \sigma ^{2} _{\alpha}

then, so we may safely divide by . The crucial trick in Chebyshev's inequality is to recognize that

1 = \tfrac{\|X - \mu\| ^{2 }{\|X} _{\alpha} - \mu\| ^{2 }} _{\alpha} .

The following calculations complete the proof:

\begin{align} \Pr\left( \|X - \mu\| _{\alpha} \ge k \sigma _{\alpha} \right) & = \int _{\Omega} 1 _{\|X - \mu\| _{\alpha} \ge k \sigma _{\alpha}} d\Pr \\ & = \int _{\Omega} \left ( (\|X - \mu\| ^{2} _{\alpha})/(\|X - \mu\| ^{2} _{\alpha}) \right ) ⋅ 1 _{\|X - \mu\| _{\alpha} \ge k \sigma _{\alpha}} d\Pr \\[ 6 pt] &\le \int _{\Omega} \left ( (\|X - \mu\| ^{2} _{\alpha})/((k\sigma ^{2} _{\alpha)}) \right ) ⋅ 1 _{\|X - \mu\| _{\alpha} \ge k \sigma _{\alpha}} d\Pr \\[ 6 pt] &\le (1)/(k ^{2} \sigma ^{2} _{\alpha}) \int _{\Omega} \|X - \mu\| ^{2} _{\alpha} d\Pr && 1 _{\|X - \mu\| _{\alpha} \ge k \sigma _{\alpha}} \le 1 \\[ 6 pt] & = (1)/(k ^{2} \sigma ^{2} _{\alpha}) \left (\operatorname{E}\|X - \mu\| ^{2} _{\alpha} \right )\\[ 6 pt] & = (1)/(k ^{2} \sigma ^{2} _{\alpha}) \left (\sigma ^{2} _{\alpha} \right )\\[ 6 pt] & = (1)/(k ^{2}) \end{align}

Notes and References

1. Marshall . Albert W. . Olkin . Ingram . December 1960 . Multivariate Chebyshev Inequalities . The Annals of Mathematical Statistics . 31 . 4 . 1001–1014 . 10.1214/aoms/1177705673 . 0003-4851.
2. Navarro . Jorge . A simple proof for the multivariate Chebyshev inequality . 2013-05-24 . math.ST . 1305.5646 .
3. Ait-Haddou . Rachid . Mazure . Marie-Laurence . 2018-02-01 . The Fundamental Blossoming Inequality in Chebyshev Spaces—I: Applications to Schur Functions . Foundations of Computational Mathematics . en . 18 . 1 . 135–158 . 10.1007/s10208-016-9334-8 . 1615-3383.
4. Vakhania, Nikolai Nikolaevich. Probability distributions on linear spaces. New York: North Holland, 1981.