Markov
P(X ≥ 1) ≤ E[X]
For non-negative integer X.
For a non-negative integer random variable , . If , then with positive probability : an object with none of the unwanted structures exists.
This page is easier if you are comfortable with:
This is Markov's inequality with threshold 1. In a random graph with , , the expected number of triangles is , so the probability of having any triangle is at most 0.12. For in : . The expectation is computed by adding indicator variables (expectation).
The method proves existence. Colour the edges of red or blue at random. The expected number of monochromatic is , so some colouring has none: therefore (Ramsey numbers). For with the expectation is , and the method gives nothing, consistent with the pentagon construction needing more care.
The bound is weak when the events are strongly dependent, but it is simple and powerful: it underlies the lower bounds in Ramsey theory, the study of random graphs (binomial counts) and results in extremal graph theory. A permutation example is the expected number of fixed points of a random permutation, 1, as in derangements.
If the expected number of bad structures is below one, a structure-free object must exist.
Only expectations below 1 prove that a structure-free object exists.
These examples are worked by hand, step by step, so you can compare your own working.
Find the expected number of triangles in .
Find the expected number of monochromatic in a random 2-colouring of .
Find the expected number of copies.
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
P(X ≥ 1) ≤ E[X]
For non-negative integer X.
E = C(6, 4)·2^(1−6) = 15/32
Random 2-colouring.
E < 1 so a good colouring exists: R(4,4) > 6
Lower bound.
E = 252/512 = 0.4922
So R(5,5) > 10.
If X counts bad objects and E[X] < 1, then P(X = 0) > 0, so a good object exists. For R(k, k): colour K_n at random; the expected number of monochromatic K_k is C(n, k)·2^(1 − C(k, 2)). If it is below 1, then R(k, k) > n.
Each K₄ has 6 edges. Find 2·(1/2)⁶.
Find E for K₆ with k = 4.
Since E < 1, what follows?
Find E for n = 10, k = 5.
E = 2.5, so bad objects exist ✗
inconclusive ✓
The method needs E < 1.
2^(−C(k,2)) ✗
2^(1 − C(k,2)) ✓
Two colours.
independent events ✗
linearity of expectation needs none ✓
Sum the indicators.
C(k, n) ✗
C(n, k) ✓
Choose k from n.
Try each one on paper, then open the answer. Use the solver above to see the full working.
0.03125
15
0.4688
2.5
252
0.4922
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Showing E[X] < 1 so X = 0 has positive probability.
Lower bounds such as R(4,4) > 6.
No; linearity of expectation is enough.
No conclusion.
Ramsey numbers.
Turán’s theorem.
More in Discrete maths and number theory and the formula sheets.