In probability theory, Markov's inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant. It is named after the Russian mathematician Andrey Markov.

Markov's inequality (and other similar inequalities) relate probabilities to expectations, and provide (frequently) loose but still useful bounds for the cumulative distribution function of a random variable.

Statement

In the language of measure theory, Markov's inequality states that if (X,Σ,μ) is a measure space, f is a measurable extended real-valued function, and t > 0, then

$\backslash mu(\backslash \{x\backslash in\; X|\backslash ,|f(x)|\backslash geq\; t\backslash \})\; \backslash leq\; \{1\backslash over\; t\}\backslash int\_X\; f\backslash ,d\backslash mu.$

For the special case where the space has measure 1 (i.e., it is a probability space), it can be restated as follows: if X is any random variable and a > 0, then

$\backslash textrm\{Pr\}(|X|\; \backslash geq\; a)\; \backslash leq\; \backslash frac\{\backslash textrm\{E\}(|X|)\}\{a\}.$

Proof

For any measurable set A, let 1_A be its indicator function, that is, 1_A(x) = 1 if x ∈ A, and 0 otherwise. If A_t is defined as A_t={x ∈ X| |f(x)| ≥ t}, then

$0\backslash leq\; t\backslash ,1\_\{A\_t\}\backslash leq\; |f|1\_\{A\_t\}\backslash leq\; |f|.$

Therefore

$\backslash int\_X\; t\backslash ,1\_\{A\_t\}\backslash ,d\backslash mu\backslash leq\backslash int\_\{A\_t\}|f|\backslash ,d\backslash mu\backslash leq\backslash int\_X\; |f|\backslash ,d\backslash mu.$

Now, note that the left side of this inequality is the same as

$t\backslash int\_X\; 1\_\{A\_t\}\backslash ,d\backslash mu=t\backslash mu(A\_t).$

Thus we have

$t\backslash mu(\backslash \{x\backslash in\; X|\backslash ,|f(x)|\backslash geq\; t\backslash \})\; \backslash leq\; \backslash int\_X|f|\backslash ,d\backslash mu,$

and since t > 0, both sides can be divided by t, obtaining

$\backslash mu(\backslash \{x\backslash in\; X|\backslash ,|f(x)|\backslash geq\; t\backslash \})\; \backslash leq\; \{1\backslash over\; t\}\backslash int\_X|f|\backslash ,d\backslash mu.$

Q.E.D.

Examples

• Markov's inequality is used to prove Chebyshev's inequality.
• If X is a non-negative integer valued random variable, as is often the case in combinatorics, then taking a = 1 in Markov's inequality gives that $\backslash textrm\{Pr\}(X\; \backslash neq\; 0)\; \backslash leq\; \backslash textrm\{E\}(X).$ If X is the cardinality of some set, then this proves that that set is not empty. Thus one gets existence proofs.

Inequalities | Probability theory

Markow-Ungleichung | Desigualdad de Markov | Inégalité de Markov | Markov-ongelijkheid | Markovs ulikhet | Nierówność Markowa | Неравенство Маркова | อสมการของมาร์คอฟ