Markov's Inequality

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.

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.

P[Z ≥ x] ≤ E[Z] / x

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

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.

P[Z ≥ x] ≤ E[Z] / x

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.

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

• Applying Markov's inequality without checking nonnegativity.

  Markov's inequality requires Z to be nonnegative.

  Fix: Verify that all possible values of Z are at least zero before applying the inequality.

• Treating the upper bound as the exact probability.

  The inequality only says that the probability is at most 0.4.

  Fix: Write P[Z ≥ 15] ≤ 0.4 and describe 0.4 as an upper bound.

• Forgetting which quantity is random in the PAC-Bayes probability statement.

  The statement is made over an i.i.d. training set.

  Fix: Interpret the probability as referring to the random dataset sampled independently from the same distribution.

• Ignoring the two roles of Q in the PAC-Bayes bound.

  Q determines the training-loss term and is also compared with P through KL(Q||P).

  Fix: Follow Q in both contributions to the final bound.

Practice Check

1. Markov'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 δ.