Markov's inequality ($\mathbb{P}(Y\ge a)\le \mathbb{E}Y/a$)

For a nonnegative random variable $Y$ and threshold $a>0$, Markov's inequality givesThe useful case has finite expected value; an infinite right side gives no finite information. The bound also holds if $Y$ is nonnegative almost surely. Combining it with the elementary bound one gives $\mathbb{P}(Y\ge a)\le \min \{1,\mathbb{E}Y/a\}$. Nonnegativity is essential: negative values could otherwise cancel the contribution of large positive values to the expected value.

The idea is an average budget. Every outcome where $Y\ge a$ contributes at least $a$ times its probability to $\mathbb{E}Y$, and the other outcomes contribute nonnegative amounts. Formally, the indicator function gives $Y\ge a{1}_{\{Y\ge a\}}$; taking the expected value proves the bound. ^[ref].

For example, let $Y$ take $0$, $1$, $2$, $5$ with respective probabilities $0.5$, $0.2$, $0.2$, $0.1$. Its expected value is $1.1$. At $a=2$, the tail probability is $0.3$, while the bound is $1.1/2=0.55$. At $a=5$, the tail probability is $0.1$, while the bound is $0.22$. A different probability distribution with the same expected value, putting masses $0.78$ and $0.22$ at $0$ and $5$, attains the bound $0.22$ exactly at $a=5$.

Markov's inequality is useful when a moment is easy to compute but a full probability distribution is difficult to determine. A nonnegative count with expected value less than one must have some positive probability of being zero, giving the first moment method. Applying the same bound to a squared centered random variable gives Chebyshev's inequality. Applying it to an exponential function of a random variable gives an exponential Markov bound, which can exploit more than a single moment.

Let $Z$ be a nonnegative integer-valued random variable with $\mathbb{E}Z=A/q$, where $A\ge 0$ and $q\ge 1$ are integers. On $Z>A/q$, the integer $qZ$ is at least $A+1$. Markov's inequality gives $\mathrm{Pr}(Z>A/q)\le A/(A+1)$. Independent restarts therefore need at most $A+1$ attempts in expected value to achieve $Z\le \mathbb{E}Z$. The denominator bound on the expected value matters for this runtime guarantee.

If $X$ is an integrable random variable and $Z$ is a finite, strictly positive $\mathcal{G}$-measurable random variable, thenIndeed, $0\le Z{1}_{\{|X|\ge Z\}}\le |X|$. Monotonicity of conditional expectation and the measurable-factor rule for conditional expectation giveDivision by the strictly positive $Z$ proves the claim. Only the displayed product needs to be an integrable random variable; neither $Z$ nor $|X|/Z$ needs to have finite expected value. The measurable threshold represents information already available before asking how likely the remaining exceedance is.

For a finite-expected value nonnegative random variable and $a>0$, equality in the uncapped Markov's inequality holds exactly when $Y$ takes only $0$ and $a$ almost surely. Indeed the nonnegative difference $Y-a{1}_{\{Y\ge a\}}$ has zero expected value exactly when it vanishes almost surely. Giving $a$ probability $p$ yields $\mathbb{E}Y=pa$ and $\mathbb{P}(Y\ge a)=p$. This shows the bound cannot generally be reduced using only the nonnegative random variable's expected value.

Applying Markov's inequality to the positive random variable $e^{tX}$ givesHere $M_X(t)=\mathbb{E}[e^{tX}]$ is the moment-generating function, and the useful bound requires it to be finite at the chosen $t$. Optimizing over $t>0$ gives the Chernoff bound method: an exponential function weights large values more strongly before applying the same average-budget argument.

For example, let $N$ have the Poisson distribution with parameter one. Its expected value and variance are both one, and its moment-generating function is $M_N(t)=\exp (e^t-1)$. At threshold four, choosing $t=\log 4$ givesThis $t$ minimizes the exponent $e^t-1-4t$ because its derivative is $e^t-4$, with positive second derivative. The direct Markov's inequality bound is $1/4$, and the two-sided Chebyshev's inequality bound, applied to a deviation of at least three from the mean one, is $1/9$. The exact Poisson distribution tail probability is $1-e^{-1}(1+1+1/2+1/6)\approx 0.0189882$. These compare three valid bounds obtained from progressively different information; none is an exact tail probability formula for general random variables.