Markov's Inequality
Markov's inequality provides this connection: it turns the average size of Z into an upper bound on the probability of the event Z ≥ x.
From an Average to a Probability Bound
Suppose Z is a random variable that never takes a negative value. You know its expectation, written E[Z], but you want to control the probability that Z reaches or exceeds a threshold x. Markov's inequality provides this connection: it turns the average size of Z into an upper bound on the probability of the event Z ≥ x.
A nonnegative random variable is a random variable whose possible values are all at least zero. Markov's inequality applies specifically to this kind of variable.
The expectation E[Z] represents the average value of Z. Markov's inequality does not require knowing the complete distribution of Z. It uses only the nonnegative condition, the expectation, and a chosen threshold.
Tracing the Threshold Event
The event being bounded is Z ≥ x. This means that Z reaches or exceeds the threshold x. Markov's inequality says that the probability of this event cannot be larger than the expectation divided by the threshold.
The visual separates two roles. E[Z] describes the average amount of Z, while x describes how large Z must be before the event counts. Dividing the first by the second produces an upper bound for the event probability.
A Worked Threshold Calculation
Bounding a Large Value of Z
Suppose Z is nonnegative, E[Z] = 6, and the threshold is x = 15. Bound the probability that Z reaches or exceeds 15.
- 1Identify the event
The event of interest is Z ≥ 15.
- 2Apply Markov's inequality
Use P[Z ≥ x] ≤ E[Z] / x with E[Z] = 6 and x = 15.
- 3Calculate the ratio
The ratio is 6/15 = 0.4.
P[Z ≥ 15] ≤ 0.4. The probability is at most 0.4.
Why the Threshold Matters
For a fixed nonnegative random variable and a fixed expectation, Markov's bound has the form E[Z] / x. Increasing x makes this ratio smaller because the same expectation is divided by a larger threshold. The probability P[Z ≥ x] is also monotonically nonincreasing: reaching a higher threshold does not become more likely.
- 1Keep E[Z] fixed.
- 2Increase the threshold x.
- 3The denominator becomes larger.
- 4The ratio E[Z] / x becomes smaller, so the upper bound decreases.
PAC-Bayes as the Larger Application
The PAC-Bayes theorem gives a mathematical bound on the generalization error of a hypothesis class. Its central comparison is between the expected loss associated with a distribution Q over hypotheses and the loss measured on an i.i.d. training set. The comparison also includes the Kullback-Leibler divergence between Q and a prior distribution P.
At a high level, the PAC-Bayes theorem says that, with probability at least 1 - δ over an i.i.d. training set, an expected-loss quantity is bounded using the training-set loss and a square-root term. That square-root term contains KL(Q||P), the training-set size m, and the confidence parameter δ. The inequality holds for every distribution Q over the hypothesis class H, including a Q that depends on the data.
The key tracing move is to follow Q through two roles. First, Q determines the training-loss term L_S(Q). Second, Q is compared with P through KL(Q||P). Both contributions appear in the final bound, together with the training-set size and confidence parameter inside the square-root term.
Where Markov's Inequality Enters
At a high level, the PAC-Bayes proof constructs a nonnegative random quantity from the quantities being controlled. Markov's inequality is then used to convert information about the expectation of that quantity into a probability statement about the event that the quantity exceeds a threshold. After this conversion, the resulting statement is interpreted over the random i.i.d. training set.
Reading the Dataset Probability
The statement with probability at least 1 - δ is a statement about the random i.i.d. training set. The training set is sampled independently from the same distribution, and the theorem says that the PAC-Bayes inequality holds for such a dataset with probability at least 1 - δ.
The phrase for every distribution Q over H is important. The bound is not restricted to a distribution Q chosen before seeing the data; it also includes data-dependent Q. The prior P remains the reference distribution used in the KL(Q||P) term.
Common Misreadings
Common mistake Applying Markov's inequality without checking nonnegativity.
What it looks likeUsing P[Z ≥ x] ≤ E[Z] / x for a variable that can take negative values.
Why it failsMarkov's inequality requires Z to be nonnegative.
Do this insteadVerify that all possible values of Z are at least zero before applying the inequality.
Common mistake Treating the upper bound as the exact probability.
What it looks likeConcluding that P[Z ≥ 15] = 0.4 from the calculation 6/15 = 0.4.
Why it failsThe inequality only says that the probability is at most 0.4.
Do this insteadWrite P[Z ≥ 15] ≤ 0.4 and describe 0.4 as an upper bound.
Common mistake Forgetting which quantity is random in the PAC-Bayes probability statement.
What it looks likeReading probability at least 1 - δ as a claim about one fixed training set without qualification.
Why it failsThe statement is made over an i.i.d. training set.
Do this insteadInterpret the probability as referring to the random dataset sampled independently from the same distribution.
Common mistake Ignoring the two roles of Q in the PAC-Bayes bound.
What it looks likeTracking Q only in the training-loss term and overlooking KL(Q||P).
Why it failsQ determines the training-loss term and is also compared with P through KL(Q||P).
Do this insteadFollow Q in both contributions to the final bound.
Practice Check
Suppose Z is nonnegative and E[Z] = 8. Use Markov's inequality to write an upper bound for P[Z ≥ 20]. Then explain what would happen to the bound if the threshold were increased while E[Z] stayed fixed.
Hints
- Substitute E[Z] = 8 and x = 20 into P[Z ≥ x] ≤ E[Z] / x.
- Keep the result as an upper bound, not an equality.
- For the second part, compare E[Z] divided by the original threshold with E[Z] divided by a larger threshold.
- 1Markov's inequality applies to a nonnegative random variable Z. It connects the expectation E[Z] with the threshold probability P[Z ≥ x] through P[Z ≥ x] ≤ E[Z] / x. The result is an upper bound, not necessarily the exact probability. For a fixed expectation, increasing the threshold makes the bound smaller. In the PAC-Bayes proof, Markov's inequality provides the high-level step that converts an expectation of a nonnegative quantity into a probability statement over an i.i.d. training set. The PAC-Bayes bound combines training-set loss with a square-root term containing KL(Q||P), m, and δ.
Key Takeaways
- A nonnegative random variable takes values at least zero, and its expectation describes its average value.
- Markov's inequality states that P[Z ≥ x] ≤ E[Z] / x.
- The inequality gives an upper bound rather than necessarily the exact threshold probability.
- Increasing the threshold decreases the bound when the expectation is fixed.
- In PAC-Bayes, Markov's inequality helps turn an expectation into a high-probability statement over an i.i.d. training set, while Q appears through training loss and KL(Q||P).