Multidimensional Chebyshev's inequality

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 ${\displaystyle X}$ be an ${\displaystyle 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}}.}$ ^{[1] [2]}

Infinite dimensions

There is a straightforward extension of the vector version of Chebyshev's inequality to infinite dimensional settings^{[more refs. needed]}. ^[3] Let X be a random variable which takes values in a Fréchet space ${\displaystyle {\mathcal {X}}}$ (equipped with seminorms || ⋅ ||_α). This includes most common settings of vector-valued random variables, e.g., when ${\displaystyle {\mathcal {X}}}$ 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

${\displaystyle \operatorname {E} \left(\|X\|_{\alpha }^{2}\right)<\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. ^[4]

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

${\displaystyle \sigma _{a}:={\sqrt {\operatorname {E} \|X-\mu \|_{\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.${\displaystyle \forall k>0:\quad \Pr \left(\|X-\mu \|_{\alpha }\geq k\sigma _{\alpha }\right)\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

${\displaystyle \|X-\mu \|_{\alpha }\geq k\sigma _{\alpha }}$

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

The following calculations complete the proof:

${\displaystyle {\begin{aligned}\Pr \left(\|X-\mu \|_{\alpha }\geq k\sigma _{\alpha }\right)&=\int _{\Omega }\mathbf {1} _{\|X-\mu \|_{\alpha }\geq k\sigma _{\alpha }}\,\mathrm {d} \Pr \\&=\int _{\Omega }\left({\frac {\|X-\mu \|_{\alpha }^{2}}{\|X-\mu \|_{\alpha }^{2}}}\right)\cdot \mathbf {1} _{\|X-\mu \|_{\alpha }\geq k\sigma _{\alpha }}\,\mathrm {d} \Pr \\[6pt]&\leq \int _{\Omega }\left({\frac {\|X-\mu \|_{\alpha }^{2}}{(k\sigma _{\alpha })^{2}}}\right)\cdot \mathbf {1} _{\|X-\mu \|_{\alpha }\geq k\sigma _{\alpha }}\,\mathrm {d} \Pr \\[6pt]&\leq {\frac {1}{k^{2}\sigma _{\alpha }^{2}}}\int _{\Omega }\|X-\mu \|_{\alpha }^{2}\,\mathrm {d} \Pr &&\mathbf {1} _{\|X-\mu \|_{\alpha }\geq k\sigma _{\alpha }}\leq 1\\[6pt]&={\frac {1}{k^{2}\sigma _{\alpha }^{2}}}\left(\operatorname {E} \|X-\mu \|_{\alpha }^{2}\right)\\[6pt]&={\frac {1}{k^{2}\sigma _{\alpha }^{2}}}\left(\sigma _{\alpha }^{2}\right)\\[6pt]&={\frac {1}{k^{2}}}\end{aligned}}}$

References

1. 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.
4. Vakhania, Nikolai Nikolaevich. Probability distributions on linear spaces. New York: North Holland, 1981.