Difficulty: Intermediate | Prerequisites: expected value, basic summation, non-negative random variables, familiarity with randomized algorithm types from the first half of Section 10.
Markov's inequality is the first of several "tail bound" tools you will meet in this course. A tail bound answers the question: how likely is a random variable to be far from its expected value? This matters because many algorithmic guarantees depend on bounding the probability that something bad happens (too many collisions, too long a runtime, too large an error). Markov's inequality is the simplest such bound, requiring only that the variable is non-negative. It is often loose, but it applies very broadly, and tighter bounds (Chebyshev, Chernoff) build on the same intuition.
Markov's inequality says that for any non-negative random variable, the probability of it being at least a is at most E[Z]/a. The bound is simple and widely applicable but often loose. The Reverse Markov's inequality gives a lower bound when the variable is also bounded above. Linearity of expectation (E[X+Y] = E[X] + E[Y], always, regardless of dependence) is the workhorse property that makes expected-value calculations tractable.
Markov's inequality
For any non-negative random variable Z and any a > 0: Pr[Z >= a] <= E[Z] / a.
In simple terms, a random variable that averages small is unlikely to be very large.
Tail bound / tail probability
The probability that a random variable falls far from its expected value, specifically in the "tail" of its distribution. Markov's inequality is the most basic tail bound.
Non-negative random variable
A random variable that never takes a value below zero. Markov's inequality requires this; without it, the bound does not hold.
Reverse Markov's inequality
For a random variable Z that is never larger than B and any a > 0: Pr[Z > a] >= (E[Z] - a) / (B - a). This provides a lower bound on the tail probability.
Think of it as: if the expected value is well above a, the variable must exceed a at least some of the time.
Linearity of expectation
For any random variables X and Y (regardless of dependence): E[X + Y] = E[X] + E[Y]. For any constant c: E[cX] = c * E[X].
In simple terms, the expected value of a sum is always the sum of the expected values, even when the variables are dependent. This is one of the most useful facts in all of probability.
Requirement: Z must be a non-negative random variable, and a > 0.
Statement: Pr[Z >= a] <= E[Z] / a.
Proof sketch (for discrete non-negative Z):
Start from the definition of expected value: E[Z] = sum over all i >= 0 of i * Pr[Z = i].
Split the sum at a: the first part (i = 0 to a-1) is non-negative, so dropping it only decreases the total.
In the remaining sum (i = a to infinity), each i >= a, so replace i with a to get a lower bound.
This gives E[Z] >= a * Pr[Z >= a], which rearranges to the result.
The proof for continuous variables is identical but uses integrals instead of sums.
Pr[Z >= a * E[Z]] <= 1/a.
This says the probability of being a times larger than the mean is at most 1/a.
Often more intuitive for quick calculations.
Coin with Pr[heads] = 30%, flipped 100 times.
Let Z = number of heads. Then E[Z] = 30.
Pr[Z >= 60] = Pr[Z >= 2 * E[Z]] <= 1/2 by the corollary.
So the probability of getting 60 or more heads is at most 50%. (The true probability is much lower; Markov's bound is loose here.)
Hash table of size n^2, uniform random hash function, inserting n elements.
Z = number of collisions. For each pair (i, j), Pr[h(s_i) = h(s_j)] = 1/n^2.
E[Z] = C(n, 2) * (1/n^2) = (n-1)/(2n) < 1/2.
By Markov: Pr[Z >= 1] <= Pr[Z >= 2 * E[Z]] <= 1/2.
So the probability of any collision is at most 1/2. (Again, the true probability is considerably lower.)
Requires an upper bound B on Z (Z is never larger than B), plus a > 0.
Statement: Pr[Z > a] >= (E[Z] - a) / (B - a).
Proof idea: define Z' = B - Z. Since Z <= B, Z' is non-negative. Apply standard Markov's to Z' to bound Pr[Z <= a] = Pr[Z' >= B - a], then take the complement.
This gives a lower bound on the tail, useful when you want to show something is likely rather than unlikely.
Scaling: E[cX] = c * E[X]. Proved by pulling the constant out of the summation in the definition of expectation.
Additivity: E[X + Y] = E[X] + E[Y]. Proved by expanding the double sum over the joint distribution, marginalising out the other variable, and recognising marginal probabilities.
The key insight: linearity holds for all random variables, whether or not they are independent. This is what makes it so powerful. You do not need to know anything about the dependence structure.
Markov's inequality
\Pr[Z \geq a] \leq \frac{\mathbb{E}[Z]}{a}Markov's inequality (multiplicative form)
\Pr[Z \geq a \cdot \mathbb{E}[Z]] \leq \frac{1}{a}Reverse Markov's inequality (Z never exceeds B)
\Pr[Z > a] \geq \frac{\mathbb{E}[Z] - a}{B - a}Linearity of expectation
\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\mathbb{E}[cX] = c \cdot \mathbb{E}[X]Expected collisions in a hash table (n elements, table size n^2, uniform hashing)
\mathbb{E}[Z] = \binom{n}{2} \cdot \frac{1}{n^2} = \frac{n-1}{2n} < \frac{1}{2}Markov's inequality underpins quick back-of-envelope calculations wherever you need to bound rare events. In networking, it bounds the probability that a queue exceeds a certain length. In hash-table design, it bounds collision rates and informs decisions about table sizing. Linearity of expectation is the tool behind nearly every expected-value calculation in algorithm analysis, from counting expected comparisons in sorting to expected runtimes in randomized graph algorithms.
Students often forget the non-negativity requirement. Markov's inequality does not hold for random variables that can be negative. If you try to apply it to a variable with negative values, you can get nonsensical bounds.
The bound is frequently loose, and students sometimes treat it as a tight estimate. It is an upper bound on probability, not an approximation. The true probability can be much smaller.
Linearity of expectation does not require independence. This is the single most common error. E[X + Y] = E[X] + E[Y] holds always, even when X and Y are dependent. Independence is needed for E[XY] = E[X] * E[Y], which is a different property.
Students sometimes confuse Markov's inequality with Chebyshev's. Markov's uses only the mean; Chebyshev's additionally uses the variance and gives a tighter bound. They are related but distinct tools.
Know how to apply Markov's inequality to a described scenario: identify Z, confirm it is non-negative, compute E[Z], and plug in.
Be comfortable with the proof. Exams may ask you to reproduce it or adapt it to a slightly different setting.
The corollary (multiplicative form) is a common shortcut on exams. Recognise when Z >= a can be rewritten as Z >= k * E[Z].
Reverse Markov's: know when and how to use it. The key condition is an upper bound B on Z.
Linearity of expectation: expect to use it for computing E[Z] in problems involving indicator random variables (one indicator per pair, per element, and so on). The hash-table collision example is a prototype.
True or false: Markov's inequality can be applied to any random variable. (False. The variable must be non-negative.)
Fill in the blank: By Markov's inequality, if E[Z] = 10, then Pr[Z >= 50] <= ____. (10/50 = 1/5)
True or false: Linearity of expectation requires the random variables to be independent. (False. It holds regardless of dependence.)
True or false: The Reverse Markov's inequality gives an upper bound on Pr[Z > a]. (False. It gives a lower bound.)
Fill in the blank: For the hash table example with n elements and table size n^2, the expected number of collisions is less than ____. (1/2)
Q: A non-negative random variable Z has E[Z] = 8. What is an upper bound on Pr[Z >= 24] using Markov's inequality?
A: Pr[Z >= 24] <= E[Z] / 24 = 8/24 = 1/3.
Q: You roll a fair die 600 times. Let Z be the number of sixes. Use Markov's inequality to bound Pr[Z >= 200].
A: E[Z] = 600 * (1/6) = 100. By Markov: Pr[Z >= 200] <= 100/200 = 1/2.
Q: A random variable Z satisfies 0 <= Z <= 10 and E[Z] = 7. Use the Reverse Markov's inequality to give a lower bound on Pr[Z > 4].
A: Pr[Z > 4] >= (E[Z] - 4) / (B - 4) = (7 - 4) / (10 - 4) = 3/6 = 1/2.
Q: Let X_1, X_2, ..., X_n be random variables (not necessarily independent) with E[X_i] = 5 for all i. What is E[X_1 + X_2 + ... + X_n]?
A: By linearity of expectation, E[X_1 + ... + X_n] = n * 5 = 5n. Independence is not needed.
Q: Why does Markov's inequality often give a loose bound?
A: Because it uses only the expected value and the non-negativity assumption. It knows nothing about the shape of the distribution, the variance or any higher moments. This generality is what makes it so broadly applicable, but it comes at the cost of precision.
Markov's inequality is the foundation for Chebyshev's inequality, which adds variance information to get a tighter bound, and for Chernoff bounds, which are exponentially tight. These are covered in subsequent sections of EECS 376. Linearity of expectation is used throughout the course whenever an expected value needs computing, particularly in the analysis of randomized algorithms from the first half of this section. The hash-table collision example connects to the birthday paradox and to the design of universal hash families.
Markov's inequality, Markov inequality, tail bound, tail probability, probability bound, non-negative random variable, expected value, Reverse Markov's inequality, linearity of expectation, hash table collisions, birthday paradox, indicator random variable, Chebyshev's inequality, Chernoff bound, EECS 376, foundations of computer science, University of Michigan, probability in CS