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 $μ = E [X]$ and covariance matrix

V = E [(X - μ) (X - μ)^{T}] .

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

Pr (\sqrt{(X - μ)^{T} V^{- 1} (X - μ)} > t) \leq \frac{N}{t^{2}}

Proof

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

y = (X - μ)^{T} V^{- 1} (X - μ) .

Since $y$ is positive, Markov's inequality holds:

Pr (\sqrt{(X - μ)^{T} V^{- 1} (X - μ)} > t) = Pr (\sqrt{y} > t) = Pr (y > t^{2}) \leq \frac{E [y]}{t^{2}} .

Finally,

\begin{matrix} E [y] & = E [(X - μ)^{T} V^{- 1} (X - μ)] \\ = E [trace (V^{- 1} (X - μ) (X - μ)^{T})] \\ = trace (V^{- 1} V) = N \end{matrix} .

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 $|| \cdot || α$ ). 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

E (‖ X ‖_{α}^{2}) < \infty

for every seminorm $|| \cdot || α$ . 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 $μ \in 𝒳$ be the Pettis integral of $X$ (i.e., the vector generalization of the mean), and let

σ_{a} := \sqrt{E ‖ X - μ ‖_{α}^{2}}

be the standard deviation with respect to the seminorm $|| \cdot || α$ . In this setting we can state the following:

General version of Chebyshev's inequality.

\forall k > 0 : Pr (‖ X - μ ‖_{α} \geq k σ_{α}) \leq \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

‖ X - μ ‖_{α} \geq k σ_{α}

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

The following calculations complete the proof:

\begin{matrix} Pr (‖ X - μ ‖_{α} \geq k σ_{α}) & = \int_{Ω} 𝟏_{‖ X - μ ‖_{α} \geq k σ_{α}} d Pr \\ = \int_{Ω} (\frac{‖ X - μ ‖_{α}^{2}}{‖ X - μ ‖_{α}^{2}}) \cdot 𝟏_{‖ X - μ ‖_{α} \geq k σ_{α}} d Pr \\ \leq \int_{Ω} (\frac{‖ X - μ ‖_{α}^{2}}{(k σ_{α})^{2}}) \cdot 𝟏_{‖ X - μ ‖_{α} \geq k σ_{α}} d Pr \\ \leq \frac{1}{k^{2} σ_{α}^{2}} \int_{Ω} ‖ X - μ ‖_{α}^{2} d Pr & 𝟏_{‖ X - μ ‖_{α} \geq k σ_{α}} \leq 1 \\ = \frac{1}{k^{2} σ_{α}^{2}} (E ‖ X - μ ‖_{α}^{2}) \\ = \frac{1}{k^{2} σ_{α}^{2}} (σ_{α}^{2}) \\ = \frac{1}{k^{2}} \end{matrix}

References

1 2 Marshall, Albert W.; Olkin, Ingram (December 1960). "Multivariate Chebyshev Inequalities". The Annals of Mathematical Statistics. 31 (4): 1001–1014. doi:10.1214/aoms/1177705673. ISSN 0003-4851.
↑ Navarro, Jorge (2013-05-24). "A simple proof for the multivariate Chebyshev inequality". arXiv:1305.5646 [math.ST].
↑ Altomare, Francesco; Campiti, Michele (1994). De Gruyter (ed.). Korovkin-type Approximation Theory and Its Applications. p. 313. doi:10.1515/9783110884586. ISBN 978-3-11-014178-8.
↑ Vakhania, Nikolai Nikolaevich. Probability distributions on linear spaces. New York: North Holland, 1981.

[awm-1] 1 2 Marshall, Albert W.; Olkin, Ingram (December 1960). "Multivariate Chebyshev Inequalities". The Annals of Mathematical Statistics. 31 (4): 1001–1014. doi:10.1214/aoms/1177705673. ISSN 0003-4851.

[2] Navarro, Jorge (2013-05-24). "A simple proof for the multivariate Chebyshev inequality". arXiv:1305.5646 [math.ST].

[3] Altomare, Francesco; Campiti, Michele (1994). De Gruyter (ed.). Korovkin-type Approximation Theory and Its Applications. p. 313. doi:10.1515/9783110884586. ISBN 978-3-11-014178-8.

[4] Vakhania, Nikolai Nikolaevich. Probability distributions on linear spaces. New York: North Holland, 1981.