An expectation on its own promises nothing about any run. Markov's inequality turns a mean into a tail bound in three lines, and Chebyshev's follows by applying Markov to (X − μ)². Both hold for every distribution with the stated moments — no shape assumed, no independence used — and the price of that generality is slack, which this page measures rather than describes. On a ten-key quicksort, Markov's bound at 24 comparisons is 30791/30240, which is greater than one.
Core ideas
The hard idea is that one inequality gives the other by substitution. The other two are what each assumes and what each costs in accuracy.
If X is never negative, every unit of probability sitting at or above a contributes at least a to the expectation, and nothing contributes less than zero. So E[X] ≥ a·P(X ≥ a), and dividing gives Markov's inequality: P(X ≥ a) ≤ E[X]/a. Non-negativity is the only hypothesis, which is why the bound is often weak — it is consistent with everything the mean allows, including a distribution that is all at 0 and a.
(X − μ)² is never negative, whatever X is, and its expectation is Var(X) by definition. The event |X − μ| ≥ t is the same event as (X − μ)² ≥ t², because squaring is increasing on the non-negatives. So Markov on (X − μ)² at a = t² gives P(|X − μ| ≥ t) ≤ Var(X)/t² immediately. That is the whole derivation, and it is why Discrete Probability can state Chebyshev and leave the proof here.
Neither inequality assumes a shape, a symmetry, or independence, so both hold for the jagged comparison-count distribution as readily as for anything smooth. The price is visible: at a = 24 on ten keys the true tail is 332/675 ≈ 0.4919 and Markov allows 30791/30240 ≈ 1.0182. A bound above one is true and carries no information, and the lab prints it rather than hiding it.
The material
The inequalities the rest of this course quotes, proved here, with their slack measured against an exactly known distribution.
Let X be a random variable taking only non-negative values, with finite expectation, and let a > 0. Then P(X ≥ a) ≤ E[X]/a.
Write the expectation as a sum over the values X can take: E[X] = Σ x·P(X = x), where every term has x ≥ 0 and P(X = x) ≥ 0, so every term is non-negative.
Throw away the terms with x < a. Discarding non-negative terms can only decrease the sum, so E[X] ≥ Σ over x ≥ a of x·P(X = x).
In what is left, every x is at least a, so replacing each x by a can only decrease the sum again: E[X] ≥ a·Σ over x ≥ a of P(X = x) = a·P(X ≥ a). Divide by a > 0.
□
Two features of that argument are worth naming because they are what the rest of the course relies on. It never looks at the shape of the distribution, so it applies to any non-negative X at all; and it is tight, in the sense that a variable taking value a with probability E[X]/a and 0 otherwise meets it with equality. A bound that is attained by some distribution cannot be improved without adding a hypothesis, and the next theorem is what one extra hypothesis buys.
Let X have finite mean μ and finite variance Var(X), and let t > 0. Then P(|X − μ| ≥ t) ≤ Var(X)/t². Writing t = kσ with σ the standard deviation and k > 0 gives the form Discrete Probability states: P(|X − μ| ≥ kσ) ≤ 1/k².
Let Y = (X − μ)². A square is never negative, so Markov's inequality applies to Y, and E[Y] = Var(X) is the definition of the variance.
The events are the same: |X − μ| ≥ t holds exactly when (X − μ)² ≥ t², because both sides of |X − μ| ≥ t are non-negative and squaring preserves order there. So P(|X − μ| ≥ t) = P(Y ≥ t²) ≤ E[Y]/t² = Var(X)/t² by Markov at a = t².
For the second form, put t = kσ. Then Var(X)/t² = σ²/(k²σ²) = 1/k², provided σ > 0; if σ = 0 then X is constant and both sides are 0 for every t > 0.
□
That is the proof the Simulation course of the Operations Research path points at when it states Chebyshev and applies it to a sample mean. It is two lines because Markov did the work, and it is worth noticing which line carries the generality: nothing above assumed the distribution was symmetric, unimodal, or anything else. A confidence interval built on Chebyshev is valid for a simulation whose output distribution nobody has written down, and that is the property being bought.
Randomised quicksort on ten keys is the ideal test, because the lab knows the whole distribution: E[C] = 30791/1260 ≈ 24.4373 and Var(C) = 4913659/317520 ≈ 15.4751, both exact. So every bound can be printed beside the quantity it bounds rather than beside a guess at it. Slide the threshold and the panel recomputes both columns.
At a = 24 the bound exceeds one, and a probability is at most one anyway, so the inequality is true and says nothing whatsoever. That is not a defect in the lab or a badly chosen slider position: it is what Markov does when a is near the mean, and a reader who has never seen it will eventually quote a vacuous bound as though it were evidence. Further out the bound becomes informative in form and steadily worse in accuracy, until at the worst case it overstates the truth by a factor near 3849.
Chebyshev decays as 1/t² where Markov decays as 1/a, so it is the sharper tool once t is a few standard deviations out: at t = 15 it allows 0.069 against a truth of 0.002, a factor of 34, where Markov at the comparable threshold was out by a factor of thousands. It also goes vacuous, at t = 3, for the same reason — σ ≈ 3.93 here, so t = 3 is less than one standard deviation and 1/k² exceeds one.
And it bounds a two-sided event. P(|C − μ| ≥ t) includes runs that were unusually cheap as well as unusually expensive, which is often not the event you care about. Using Chebyshev for a one-sided question is legitimate and wasteful: it throws away half the bound. The lab prints the two-sided exact probability beside it so the comparison is like for like.
Over seeds 1 to 120 the panel counts 60 runs at or above 24 comparisons, which is 1/2, against an exact tail of 332/675 ≈ 0.492. Eleven runs reached 30, against 0.111. One run reached 36, against 0.0138. The measurements are close and they are measurements: they move with the slider, they say nothing about the values no seed reached, and they are about this instance rather than about every instance. The bounds are about every instance and they hold for instances nobody has enumerated, which is the only reason to prove them.
The honest summary is that this page has three ways to answer “how likely is a bad run?” and they are ranked by what they cost and what they cover. The enumeration is exact and available only when the distribution can be computed. The measurement is available always and establishes nothing about unobserved outcomes. The bound is available from two numbers, holds for every distribution with those numbers, and is loose by a factor this page prints.
Interactive
The fixed rule pays n(n − 1)/2 on this input every time; the random rule has an expectation of 2(n + 1)H − 4n and a spread around it
Method
Check the hypothesis, then the event, then the slack — in that order.
Comparison counts, running times, sizes and loads are non-negative and Markov applies directly. A deviation, a profit, or a difference of two counts is not, and applying Markov to it produces a statement that is simply false. Chebyshev has no such restriction because it squares first.
C ≥ a is one-sided; |C − μ| ≥ t is two-sided and includes the cheap runs. Using the second to bound the first is valid and loses a factor of about two. Using the first to bound the second is not valid at all.
At a = 24 on this instance Markov returns 1.0182. A bound above one is true, carries no information, and should not appear in a conclusion. Move the threshold out until the bound drops below one before quoting it.
This lab can, so use it to calibrate: Markov is out by a factor of 2 near the mean and by thousands at the worst case, and Chebyshev by about 34 at fifteen comparisons out. Those factors are what you are accepting when you use a bound on an instance you cannot enumerate.
The lab supplies E[C] = 30791/1260 and Var(C) = 4913659/317520, both exact. The question: bound the probability that a run costs 36 comparisons or more, and compare with the truth.
Chebyshev beats Markov here by a factor of five, and it does so using one extra number about the distribution. That is the trade in general: each further moment you are willing to compute buys a faster decay in the tail, and this library stops at the second because the next step is Chernoff's bound and this course excludes it.
Notice the step that turned a two-sided bound into a one-sided claim, and notice the arithmetic in it. 36 − E = 11.5627, so C ≥ 36 implies |C − E| ≥ 11 but not |C − E| ≥ 12: at C = 36 the deviation is 11.56, and using t = 12 would have been a bound on a smaller event than the one asked about. The containment runs one way only and it is easy to write down backwards.
Here it happens to be an equality rather than a containment. |C − E| ≥ 11 means C ≥ 35.44 or C ≤ 13.44, and the distribution's support starts at 19, so the lower half is empty and P(|C − E| ≥ 11) = P(C ≥ 36) = 13/945 exactly. Chebyshev is bounding precisely the event in question on this instance, and it is still out by a factor of nine.
For a faded rehearsal, do the same at a = 30 and predict which of the two inequalities wins before computing either. The supplied first move is this: 30 is about 1.4 standard deviations above the mean, and Chebyshev at k standard deviations allows 1/k². Work out what 1/k² is there, compare it with E/a = 0.8146, and then check both against the exact 6283/56700.
You should be able to prove Markov's inequality in three steps, obtain Chebyshev's by substituting (X − μ)², state the 1/k² form, recognise a vacuous bound on sight, and say which of a page's numbers is exact, which is measured and which is bounded.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.