Difficulty: Intermediate | Prerequisites: Basic probability, NP-completeness
This material gives you the probability toolkit used throughout EECS 376: expected value, concentration inequalities (Markov, Chernoff), and the union bound. These tools let you analyse randomised algorithms and prove that they work with high probability. The approximation algorithms section shows what to do when a problem is NP-hard and you need a guaranteed-quality answer in polynomial time.
Expected Value, E[N]
The weighted average of a random variable's possible values: E[N] = sum of v × Pr[N = v] over all v. In simple terms: the long-run average you would see if you repeated the experiment many times.
Linearity of Expectation
For any random variables N₁, ..., Nₖ (not necessarily independent): E[N₁ + ... + Nₖ] = E[N₁] + ... + E[Nₖ]. Think of it as: the expected value of a sum is always the sum of the expected values, no independence required.
Markov's Inequality
If X is a non-negative random variable and a > 0, then Pr[X ≥ a] ≤ E[X] / a. In simple terms: a non-negative random variable is unlikely to be much larger than its mean. Crude but universally applicable.
Chernoff Bound ("Large Deviation")
For independent random variables Y₁, ..., Yₖ taking values in [0, 1] with Y = sum of Yᵢ and mu = E[Y]: Pr[Y - mu ≥ a × mu] ≤ e^(-a² mu / 3). Think of it as: the probability that a sum of independent bounded variables overshoots its mean by a multiplicative factor drops exponentially.
Chernoff Bound ("Small Deviation")
For any lambda in [0, 1]: Pr[Y - mu ≥ lambda × mu] ≤ e^(-lambda² mu / 3) and Pr[mu - Y ≥ lambda × mu] ≤ e^(-lambda² mu / 3). In simple terms: the two-sided version for deviations within a factor of the mean.
Union Bound (Boole's Inequality)
For any events A and B: Pr[A ∪ B] ≤ Pr[A] + Pr[B]. More generally, for events E₁, ..., Eₙ: Pr[∪ Eᵢ] ≤ sum of Pr[Eᵢ]. Think of it as: the probability that at least one bad thing happens is at most the sum of each bad thing's individual probability.
Approximation Ratio (alpha)
For a minimisation problem: OPT ≤ ALG ≤ alpha × OPT, with alpha > 1. For a maximisation problem: OPT ≥ ALG ≥ alpha × OPT, with alpha < 1. In simple terms: how far the algorithm's answer can be from the true optimum, in the worst case.
OPT
The value of an optimal solution to an optimisation problem.
ALG
The value of the solution produced by the approximation algorithm.
The expected value of a random variable N is its weighted average:
E[N] = sum over all v of v × Pr[N = v].
Two useful facts:
For any random variable X, there exists an outcome at least as large as E[X].
For any random variable X, there exists an outcome at most as large as E[X].
Linearity of expectation holds for any collection of random variables, whether or not they are independent:
E[N₁ + N₂ + ... + Nₖ] = E[N₁] + E[N₂] + ... + E[Nₖ].
This is one of the most powerful tools in the course. It lets you compute the expected value of a complicated sum by breaking it into simple indicator variables.
For a non-negative random variable X and any a > 0:
Pr[X ≥ a] ≤ E[X] / a.
Equivalently: Pr[X ≥ a × E[X]] ≤ 1/a.
Markov is the loosest of the concentration inequalities, but it requires the fewest assumptions: the variable just needs to be non-negative. It connects to the Chernoff bound because Chernoff essentially applies Markov to an exponential transformation of the variable.
Let Y₁, ..., Yₖ be independent random variables taking values in [0, 1]. Let Y = sum of Yᵢ and mu = E[Y].
Large deviation bound (for any lambda ≥ 1):
Pr[Y - mu ≥ lambda × mu] ≤ e^(-lambda² mu / 3).
Small deviation bound (for any lambda in [0, 1]):
Pr[Y - mu ≥ lambda × mu] ≤ e^(-lambda² mu / 3).
Pr[mu - Y ≥ lambda × mu] ≤ e^(-lambda² mu / 3).
The key requirement is independence. Chernoff does not apply to dependent variables. When it does apply, it gives exponentially decreasing tail probabilities, which is much tighter than Markov.
How does this compare to Markov? Markov bounds Pr[Y ≥ a] by E[Y]/a, which decreases only as 1/a. Chernoff bounds the same probability by e^(-something × mu), which decreases exponentially. The tradeoff: Chernoff requires independence and bounded variables; Markov requires only non-negativity.
For any events A and B:
Pr[A ∪ B] ≤ Pr[A] + Pr[B].
More generally, for events E₁, ..., Eₙ:
Pr[E₁ ∪ ... ∪ Eₙ] ≤ Pr[E₁] + ... + Pr[Eₙ].
The union bound is used constantly in combination with Chernoff: bound the probability of each bad event using Chernoff, then take a union bound over all of them to show that with high probability none of them occur.
When a problem is NP-hard, we cannot (assuming P ≠ NP) find exact optimal solutions in polynomial time. An approximation algorithm runs in polynomial time and produces a solution within a guaranteed factor of optimal.
For minimisation problems: OPT ≤ ALG ≤ alpha × OPT, where alpha > 1 (closer to 1 is better).
For maximisation problems: OPT ≥ ALG ≥ alpha × OPT, where alpha < 1 (closer to 1 is better).
The following greedy algorithm gives a 2-approximation for Minimum Vertex Cover:
Choose an arbitrary edge (u, v).
Add both endpoints u and v to the cover.
Delete all edges incident to u or v.
Repeat until no edges remain.
Why it is a 2-approximation:
The algorithm picks edges greedily. Each chosen edge contributes 2 vertices to the cover.
OPT must include at least one endpoint of each chosen edge (otherwise that edge would not be covered).
So the number of chosen edges ≤ OPT, and ALG = 2 × (number of chosen edges) ≤ 2 × OPT.
A seemingly tempting but bad idea: for each edge, add just one endpoint. The problem is you might miss edges, because the endpoint you chose might not cover all of that vertex's other edges. Adding both endpoints guarantees every incident edge is covered.
\mathbb{E}[N] = \sum_v v \cdot \Pr[N = v]\mathbb{E}\left[\sum_i N_i\right] = \sum_i \mathbb{E}[N_i] \quad \text{(linearity, no independence needed)}\text{Markov: } \Pr[X \geq a] \leq \frac{\mathbb{E}[X]}{a}, \quad X \geq 0,\; a > 0\text{Chernoff (large deviation): } \Pr[Y - \mu \geq \lambda\mu] \leq e^{-\lambda^2 \mu / 3}, \quad \lambda \geq 1\text{Chernoff (small deviation): } \Pr[|Y - \mu| \geq \lambda\mu] \leq 2\,e^{-\lambda^2 \mu / 3}, \quad \lambda \in [0,1]\text{Union bound: } \Pr\left[\bigcup_i E_i\right] \leq \sum_i \Pr[E_i]\text{Minimisation approx: } \mathrm{OPT} \leq \mathrm{ALG} \leq \alpha \cdot \mathrm{OPT}, \quad \alpha > 1\text{Maximisation approx: } \mathrm{OPT} \geq \mathrm{ALG} \geq \alpha \cdot \mathrm{OPT}, \quad \alpha < 1Students often assume linearity of expectation requires independence. It does not. Linearity holds for any random variables, dependent or not. Independence is needed for Chernoff, not for linearity.
Markov's inequality requires the random variable to be non-negative. Applying it to a variable that can take negative values gives a meaningless bound. If your variable can be negative, shift or transform it first.
A common error with Chernoff bounds is applying them to variables that are not independent. Chernoff bounds require independence of the underlying random variables Y₁, ..., Yₖ.
Students sometimes confuse the approximation ratio direction. For minimisation, alpha > 1 (the algorithm's solution is at most alpha times the optimum). For maximisation, alpha < 1 (the algorithm's solution is at least alpha times the optimum). A "2-approximation" for a minimisation problem means ALG ≤ 2 × OPT, not that the algorithm is off by a factor of 2 from being correct.
⚠️ Linearity of expectation is used constantly in proofs on the exam. Practise breaking a complex random variable into a sum of indicators and applying linearity.
⚠️ Know when to use Markov vs Chernoff. Markov: any non-negative variable, weak bound. Chernoff: independent bounded variables, exponentially strong bound. The exam will test whether you choose the right tool.
⚠️ For the vertex cover 2-approximation, be ready to explain both the algorithm and why the factor of 2 holds. The argument hinges on the fact that OPT must cover at least one endpoint of each edge the algorithm selects.
⚠️ The union bound combined with Chernoff is a standard exam pattern: bound each bad event individually, then take a union bound. Practise this two-step argument.
⚠️ Make sure you can state the Chernoff bound from memory, including the conditions (independence, values in [0, 1]) and the two regimes (large and small deviation).
True or False: Linearity of expectation requires the random variables to be independent. Answer: False.
Fill in the blank: Markov's inequality states Pr[X ≥ a] ≤ ______ for non-negative X. Answer: E[X] / a.
True or False: Chernoff bounds can be applied to dependent random variables. Answer: False. They require independence.
Fill in the blank: The vertex cover greedy algorithm is a ______-approximation. Answer: 2.
True or False: For a minimisation problem, an approximation ratio alpha < 1 means the algorithm is better than optimal. Answer: False. For minimisation, alpha > 1 (the algorithm's cost is at most alpha times OPT). Alpha < 1 would be the maximisation convention.
Q: A fair die is rolled 600 times. Let X be the number of sixes. Using Markov's inequality, bound Pr[X ≥ 200].
A: E[X] = 600 × (1/6) = 100. By Markov, Pr[X ≥ 200] ≤ E[X] / 200 = 100/200 = 0.5. (Note how loose this is; Chernoff would give a much tighter bound.)
Q: Using the same setup, apply the Chernoff bound to bound Pr[X ≥ 200].
A: Here mu = E[X] = 100 and we want Pr[X ≥ 200] = Pr[X - mu ≥ 100] = Pr[X - mu ≥ 1 × mu]. This is the large deviation regime with lambda = 1. Chernoff gives Pr[X - mu ≥ lambda × mu] ≤ e^(-lambda² mu / 3) = e^(-1 × 100/3) = e^(-33.3) ≈ 3.7 × 10^(-15). Vastly tighter than Markov.
Q: Prove that the greedy vertex cover algorithm achieves a 2-approximation.
A: The algorithm repeatedly picks an arbitrary uncovered edge and adds both endpoints to the cover. Let M be the set of edges picked. Each edge in M contributes 2 vertices, so ALG = 2|M|. Now, no two edges in M share an endpoint (once both endpoints of a chosen edge are added, all their incident edges are removed). So the edges in M form a matching. Any vertex cover, including OPT, must include at least one endpoint of each edge in M, so OPT ≥ |M|. Therefore ALG = 2|M| ≤ 2 × OPT.
Q: Let E₁, ..., E₁₀ be events, each with Pr[Eᵢ] = 0.05. Bound the probability that at least one event occurs.
A: By the union bound, Pr[E₁ ∪ ... ∪ E₁₀] ≤ 0.05 × 10 = 0.5. The probability that at least one event occurs is at most 0.5.
Q: Explain why linearity of expectation does not require independence, while Chernoff bounds do.
A: Linearity of expectation follows directly from the definition of expected value and the linearity of summation. It is a property of means, and means are always additive regardless of dependence. Chernoff bounds, by contrast, rely on the moment-generating function of a sum, which factors into a product of individual moment-generating functions only when the variables are independent. Without independence, that factoring step fails.
The probability tools here (Chernoff, union bound) are what makes the "negligible probability" in zero-knowledge proofs and cryptographic security precise. When a crypto protocol claims soundness "except with negligible probability," it is Chernoff doing the heavy lifting.
Approximation algorithms are the practical answer to NP-hardness. The vertex cover 2-approximation is your first example of what you do after proving a problem is NP-complete: you give up on exact solutions and aim for provably good ones.
Linearity of expectation appears in the analysis of randomised algorithms throughout the rest of the course and in algorithms courses more broadly (e.g., EECS 477).
Expected value, linearity of expectation, Markov's inequality, Chernoff bound, large deviation, small deviation, concentration inequality, union bound, Boole's inequality, approximation algorithm, approximation ratio, 2-approximation, vertex cover, minimum vertex cover, greedy algorithm, OPT, ALG, randomised algorithm, EECS 376, foundations of computer science, University of Michigan, probability in CS