First Moment Method Explained with Worked Examples

For a non-negative integer random variable , . If , then with positive probability : an object with none of the unwanted structures exists.

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 First moment method means

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.

What is it used for?

If the expected number of bad structures is below one, a structure-free object must exist.

How to use first moment method

  1. Define as the count of the unwanted structures.
  2. Write as a sum of indicator variables and compute .
  3. Conclude .
  4. If , an object with exists.

Graph

Expected counts: triangles in G(10, 0.1), K4 in K6 colouring, K3 in K50.120.469 < 12.5 > 1: no conclusion00.511.522.533.5400.511.522.53Expected counts: triangles in G(10, 0.1), K4 in K6 colouring, K3 in K5caseyGraph with x from 0 to 4 and y from 0 to 3. Shows bars (3); point 0.12 at (1, 0.12); point 0.469 < 1 at (2, 0.469); point 2.5 > 1: no conclusion at (3, 2.5).

Only expectations below 1 prove that a structure-free object exists.

Worked examples

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

Example 1: triangles in a random graph

Find the expected number of triangles in .

Worked example
Answer
0.120.12
  1. Formula

Example 2: a colouring of K₆

Find the expected number of monochromatic in a random 2-colouring of .

Worked example
Answer
0.469<10.469<1
  1. Formula

Example 3: K₄ in G(20, 0.05)

Find the expected number of copies.

Worked example
Answer
7.6×10−57.6\times10^{-5}
  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.

Markov

P(X ≥ 1) ≤ E[X]

For non-negative integer X.

K₄ in K₆

E = C(6, 4)·2^(1−6) = 15/32

Random 2-colouring.

Conclusion

E < 1 so a good colouring exists: R(4,4) > 6

Lower bound.

K₅ in K₁₀

E = 252/512 = 0.4922

So R(5,5) > 10.

Word problems

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.

Probability one K₄ is monochromatic

Each K₄ has 6 edges. Find 2·(1/2)⁶.

  1. 2^(1 − 6)
  2. Check: 1/32 ✓0.03125.

Expectation

Find E for K₆ with k = 4.

  1. C(6, 4) = 15
  2. 15/32
  3. Check: 0.46875 ✓0.4688.

Conclusion Higher

Since E < 1, what follows?

  1. P(no monochromatic K₄) > 0
  2. Check: R(4,4) > 6 ✓R(4,4) > 6.

A larger case Higher

Find E for n = 10, k = 5.

  1. C(10, 5) = 252
  2. 252 × 2⁻⁹
  3. Check: 0.4922 ✓0.4922.

Common mistakes

Concluding from E > 1

E = 2.5, so bad objects exist ✗

inconclusive ✓

The method needs E < 1.

Wrong exponent

2^(−C(k,2)) ✗

2^(1 − C(k,2)) ✓

Two colours.

Assuming independence needed

independent events ✗

linearity of expectation needs none ✓

Sum the indicators.

Mixing up n and k

C(k, n) ✗

C(n, k) ✓

Choose k from n.

Exam tips

  1. E[X] < 1 ⇒ good object exists.
  2. Linearity of expectation.
  3. C(n, k)·2^(1 − C(k,2)).
  4. Lower bound on R.
  5. E ≥ 1 proves nothing.

Practice questions

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

1. 2^(1−6) Foundation

0.03125

2. C(6, 4) Foundation

15

3. E for n = 6, k = 4 to 4 d.p. Foundation

0.4688

4. C(5, 3)·2^(1−3) Higher

2.5

5. C(10, 5) Higher

252

6. E for n = 10, k = 5 to 4 d.p. Higher

0.4922

Practice generator

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

Solve: …

Key terms

First moment method
Use E[X] < 1 to show X = 0 is possible.
Linearity of expectation
E[ΣXᵢ] = ΣE[Xᵢ].
Indicator variable
1 if an event occurs.
Markov’s inequality
P(X ≥ a) ≤ E[X]/a.
Probabilistic method
Existence by randomness.
Monochromatic
All one colour.

Frequently asked questions

What is the first moment method?

Showing E[X] < 1 so X = 0 has positive probability.

What does it prove for Ramsey numbers?

Lower bounds such as R(4,4) > 6.

Do events need to be independent?

No; linearity of expectation is enough.

What if E ≥ 1?

No conclusion.

Which page covers Ramsey numbers?

Ramsey numbers.

Which page covers Turán’s theorem?

Turán’s theorem.

More in Discrete maths and number theory and the formula sheets.