Markov's Inequality Explained with Worked Examples

For a non-negative random variable and , .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Markov's inequality means

If the average is 10, at most one in five values can be 50 or more: . If mean income is 40 (thousand), at most earn 200 or more. If the mean waiting time is 5 minutes, . For an exponential waiting time the exact probability is , so the bound is far from tight, but it needs only the mean (the exponential distribution).

The proof is one line: , because the part of the expectation from values at least is already at least times their probability (expectation of a discrete variable). Applying it to gives Chebyshev's inequality, and applying it to gives the Chernoff bounds (the moment generating function, Chernoff and Hoeffding bounds).

In combinatorics the case is the first moment method: . The requirement is essential; for variables that can be negative use a shifted or squared version.

What is it used for?

Markov's inequality limits how often a non-negative quantity can be many times larger than its mean.

How to use markov's inequality

  1. Check that .
  2. Find and the threshold .
  3. Compute .
  4. The probability of reaching is at most that.

Graph

Markov bound E(X)/a for E(X) = 10a = 50: 0.210203040506070809010000.20.40.60.81Markov bound E(X)/a for E(X) = 10aboundbound 10/aGraph with x from 10 to 100 and y from 0 to 1.05. Shows the curve bound 10/a; point a = 50: 0.2 at (50, 0.2).

The chance of reaching a threshold falls as 1/a.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: mean 10, threshold 50

Bound when .

Worked example
Answer
0.20.2
  1. Formula

Example 2: mean income

Bound the proportion earning at least 200 when the mean is 40.

Worked example
Answer
0.20.2
  1. Formula

Example 3: waiting time

Bound when the mean is 5 minutes.

Worked example
Answer
0.250.25
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

E(X) = 10, a = 50

P(X ≥ 50) ≤ 0.2

Bound.

E(X) = 3, a = 12

0.25

Bound.

a = 2E(X)

bound 0.5

At most half exceed twice the mean.

Derived Chebyshev

apply to (X − μ)²

k = 2: 0.25.

Word problems

For X ≥ 0 and a > 0, P(X ≥ a) ≤ E(X)/a. It needs only the mean, so it is weak but universal.

Bound

E(X) = 10. Bound P(X ≥ 50).

  1. 10/50
  2. Check: ✓0.2

Another

E(X) = 3. Bound P(X ≥ 12).

  1. 3/12
  2. Check: ✓0.25

Twice the mean Higher

Bound P(X ≥ 2E(X)).

  1. E/2E
  2. Check: ✓0.5

Chebyshev link Higher

Apply to (X − μ)² with a = 4σ². Find 1/4.

  1. σ²/4σ²
  2. Check: ✓0.25

Common mistakes

Negative variable

applying to X < 0 ✗

needs X ≥ 0 ✓

Non-negativity.

Bound above 1

meaningful ✗

trivial if a < E(X) ✓

Check a.

Exact probability

P = E/a ✗

upper bound ✓

Usually loose.

Wrong direction

a/E ✗

E/a ✓

Check.

Exam tips

  1. P(X ≥ a) ≤ E/a.
  2. X ≥ 0.
  3. a > E for usefulness.
  4. Loose but general.
  5. Gives Chebyshev.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Bound E = 4, a = 20 Foundation

0.2

2. Bound E = 5, a = 25 Foundation

0.2

3. Bound E = 2, a = 8 Foundation

0.25

4. Bound E = 1.5, a = 6 Higher

0.25

5. Bound E = 100, a = 400 Higher

0.25

6. Bound E = 7, a = 21 to 4 d.p. Higher

0.3333

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Markov’s inequality
P(X ≥ a) ≤ E(X)/a.
Non-negative variable
X ≥ 0.
Tail bound
Limits large values.
Expectation
Mean.
Chebyshev
Variance version.
Upper bound
Not the exact value.

Frequently asked questions

What is Markov’s inequality?

P(X ≥ a) ≤ E(X)/a.

What are the conditions?

X ≥ 0 and a > 0.

Is it tight?

Rarely.

How does Chebyshev follow?

Apply Markov to (X − μ)².

Which page covers Chebyshev?

Chebyshev’s inequality.

Which page covers the law of large numbers?

weak law of large numbers.

More in Advanced statistics and stochastic processes and the formula sheets.