Random Structures and Algorithms (5CCM376A & 6CCM376B)

Lecturer: Alexandre Stauffer

Contents

1 Introduction to algorithms and randomization 9

1.1 What is an algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1 Examples of algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 First example of randomized algorithm: primality test . . . . . . . . . . . 10
1.2.2 Why introduce randomization into algorithms? . . . . . . . . . . . . . . . 11
1.3 Types of randomized algorithms: Monte Carlo & Las Vegas . . . . . . . . . . . . 11
1.4 Further examples of randomized algorithms . . . . . . . . . . . . . . . . . . . . . 11
1.4.1 Random primality test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Las Vegas primality test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Matrix multiplication check (Freivalds) . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.1 Some remarks on Freivalds’s algorithm. . . . . . . . . . . . . . . . . . . . 14
1.5.2 Analyzing Freivalds’s algorithm. . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Graphs and randomness 19

2.1 What is a graph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Fundamental definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Handshake lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Paths, cycles, connected components and trees . . . . . . . . . . . . . . . . . . . 20
2.5 Min-cut problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.1 Randomized algorithm for min-cut via edge contraction . . . . . . . . . . 21
2.5.2 Analysis of the randomized algorithms for min-cut . . . . . . . . . . . . . 22
2.6 Random graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3 The probabilistic method 24

3.1 Key basic result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Max-cut problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 The probabilistic method in words . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Independent set problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4 Asymptotics and convergence of random variables 29

4.1 Almost surely and asymptotically almost surely . . . . . . . . . . . . . . . . . . . 29
4.2 Convergence of numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3 Convergence of random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.1 Convergence in probability . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.2 Borel-Cantelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.3 Convergence almost surely . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2
Contents 3

4.3.4 Convergence in L1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3.5 Relation between types of convergence . . . . . . . . . . . . . . . . . . . . 32
4.4 Moment generating and characteristic functions . . . . . . . . . . . . . . . . . . . 33
4.5 Convergence in distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 First and second moment methods 37

5.1 Markov’s inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Coupon collector problem . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 37
x
5.3 Fundamental inequalities: ex ≥ 1 + x and 1 − x1 → e−1 . . . . . . . . . . . . . 38
5.4 First moment method in words . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.5 Balls into bins problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.6 The union bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.7 Limitations of the first moment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.8 Chebyshev’s inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.9 Paley-Zygmund inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.10 Revisiting the balls into bins problem . . . . . . . . . . . . . . . . . . . . . . . . 42
5.11 Revisiting the coupon collector problem . . . . . . . . . . . . . . . . . . . . . . . 43
5.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6 Chernoff bound 48
6.1 Going beyond first and second moments . . . . . . . . . . . . . . . . . . . . . . . 48
6.2 Chernoff bound: upper tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.3 Chernoff bound: lower tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.4 Example: random walk on Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.5 Largest degree in G(n, p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

7 Martingale 56
7.1 Random walk on Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.2 σ-algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.3 Filtration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.4 Conditional expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.4.1 Properties of conditional expectation . . . . . . . . . . . . . . . . . . . . . 58
7.5 Martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.5.1 Examples of martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.6 Stopping times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.7 Optional stopping theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
7.8 Random walk and martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
7.8.1 Unbiased random walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
7.8.2 Gambler’s ruin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.8.3 Example of wrong application of optional stopping . . . . . . . . . . . . . 62
7.8.4 Biased random walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.8.5 Other examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

8 Galton-Watson branching process 67

8.1 Galton–Watson branching process . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.2 Galton–Watson tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.3 Extinction and survival . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
8.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 Contents

9 Coupling 72
9.1 What is a coupling? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.2 Formal definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
9.3.1 Stochastic domination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
9.3.2 General construction of random variables via Uniform(0, 1) . . . . . . . . 74
9.3.3 Necessary and sufficient condition for stochastic domination . . . . . . . . 74
9.4 Example: Erdős-Rényi random graph . . . . . . . . . . . . . . . . . . . . . . . . . 74
9.5 Example: Galton-Watson process . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

10 Percolation 77
10.1 Definition of bond percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
10.2 A word on motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
10.3 Site percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
10.4 Percolation clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
10.5 Percolation probability and pc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
10.6 Monotonicity and phase transition . . . . . . . . . . . . . . . . . . . . . . . . . . 79
10.7 General lower bound on pc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
10.8 pc for the regular tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
10.9 Finite graphs and Erdős-Rényi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
10.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

11 Review problems 85
11.1 Isolated triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
11.2 Second moment method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
11.3 Percolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
11.4 A gambling game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
List of Theorems

3.1 Theorem (Key result for the probabilistic method) . . . . . . . . . . . . . . . . . 24

4.4 Theorem (Borel-Cantelli) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.6 Theorem (Strong law of large numbers) . . . . . . . . . . . . . . . . . . . . . . . 31
4.8 Theorem (Relation between types of convergence) . . . . . . . . . . . . . . . . . . 32
4.10 Theorem (Moment generating function determines the distribution) . . . . . . . 33
4.12 Corollary (Convergence in distribution via moment generating functions) . . . . 34
4.13 Theorem (Central Limit Theorem (CLT)) . . . . . . . . . . . . . . . . . . . . . . 34

5.1 Theorem (Markov’s Inequality) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.6 Theorem (Union bound) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.7 Theorem (Chebyshev’s inequality) . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.8 Theorem (Paley–Zygmund inequality) . . . . . . . . . . . . . . . . . . . . . . . . 41
5.9 Theorem (Cauchy–Schwarz inequality) . . . . . . . . . . . . . . . . . . . . . . . . 41

6.1 Theorem (Chernoff bound for Bernoulli: upper tail) . . . . . . . . . . . . . . . . 49

6.2 Theorem (Chernoff bound for Bernoulli: lower tail) . . . . . . . . . . . . . . . . . 50
6.3 Corollary (Chernoff bound for Bernoulli: two-sided) . . . . . . . . . . . . . . . . 51

7.6 Theorem (Properties of conditional expectation) . . . . . . . . . . . . . . . . . . 58

7.10 Theorem (Stopped martingales are martingales) . . . . . . . . . . . . . . . . . . . 60
7.11 Theorem (Optional stopping theorem) . . . . . . . . . . . . . . . . . . . . . . . . 60

8.5 Theorem (Galton-Watson phase transition) . . . . . . . . . . . . . . . . . . . . . 69

9.3 Theorem (Expectation under stochastic domination) . . . . . . . . . . . . . . . . 73

9.4 Theorem (Construction of a random variable via Uniform(0, 1)) . . . . . . . . . . 74
9.5 Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

10.5 Theorem (Monotonicity of percolation) . . . . . . . . . . . . . . . . . . . . . . . . 79

10.6 Corollary (Phase transition of percolation) . . . . . . . . . . . . . . . . . . . . . . 79
10.7 Theorem (Lower bound on pc ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
10.8 Theorem (pc on regular trees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
10.9 Theorem (Giant component) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

5
List of Definitions

1.1 Definition (Algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Definition (Randomized algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Definition (Monte Carlo & Las Vegas algorithm) . . . . . . . . . . . . . . . . . . 11

2.1 Definition (Graphs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3 Definition (Trees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Definition (Erdős–Rényi graphs G(n, p)) . . . . . . . . . . . . . . . . . . . . . . . 22

4.1 Definition (Almost surely and asymptotically almost surely) . . . . . . . . . . . . 29

4.3 Definition (Convergence in probability) . . . . . . . . . . . . . . . . . . . . . . . . 30
4.5 Definition (Almost sure convergence) . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.7 Definition (Convergence in L1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.9 Definition (Moment generating function) . . . . . . . . . . . . . . . . . . . . . . . 33
4.11 Definition (Convergence in distribution) . . . . . . . . . . . . . . . . . . . . . . . 33

7.1 Definition (σ-algebra generated by discrete random variables) . . . . . . . . . . . 56

7.2 Definition (Measurability) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.3 Definition (Filtration) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.4 Definition (Adapted sequence) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.5 Definition (Conditioning with respect to random variables) . . . . . . . . . . . . 58
7.7 Definition (Martingale) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.8 Definition (Stopping time) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.9 Definition (Stopped process) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

8.1 Definition (Galton-Watson branching process) . . . . . . . . . . . . . . . . . . . . 67

8.2 Definition (Galton-Watson tree) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.3 Definition (Galton-Watson tree: parent, ancestors and descendants) . . . . . . . 68
8.4 Definition (Extinction time and survival) . . . . . . . . . . . . . . . . . . . . . . 68
8.6 Definition (Critical, supercritical and subcritical regimes) . . . . . . . . . . . . . 69

9.1 Definition (Coupling) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

9.2 Definition (Stochastic domination) . . . . . . . . . . . . . . . . . . . . . . . . . . 73

10.1 Definition (Bond percolation) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

10.2 Definition (Line graph) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
10.3 Definition (Probability measure and percolation) . . . . . . . . . . . . . . . . . . 79
10.4 Definition (Critical probability) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6
List of Recalls

1.7 Î Recall (Probability space and events) . . . . . . . . . . . . . . . . . . . . . . . 12

1.12 Î Recall (Bernoulli distribution and i.i.d.) . . . . . . . . . . . . . . . . . . . . . 13
1.14 Î Recall (Conditional probability and conditional expectation) . . . . . . . . . 15
1.15 Î Recall (Law of total probability and expectation) . . . . . . . . . . . . . . . . 15

2.7 Î Recall (Binomial distribution) . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Î Recall (Indicator random variable) . . . . . . . . . . . . . . . . . . . . . . . . 24

3.4 Î Recall (Linearity of expectation) . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2 Î Recall (Limit of sequences) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.14 Î Recall (Normal distribution) . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.5 Î Recall (Notation ≪ and ≫) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

7
 How to use the lecture notes

These lecture notes are intended to support you in following the lectures and contain the material
covered throughout the module. Each chapter corresponds roughly (but not exactly) to one week
of lecture.

A note on the style used. Theorems, lemmas, algorithms, and similar items are numbered
sequentially within each chapter, without distinction between them. This unified numbering is
intended to make it easier to locate results. The notes will refer to a theorem by its number. You
are not expected to memorize the numbering of theorems, propositions, or lemmas. However, if
a theorem has a standard name (which is clearly written in the statement of the theorem), you
are expected to know it, as you may be asked about it in the exam.

Special icons. The icons below will be used to highlight different types of content:
ž Information specific to the course (e.g., assessment details).
6 It is used either in the title of a section to indicate that the section content is non-examinable,
or inside a boxed region to mark non-examinable material.
Î It recalls a concept introduced in Probability & Statistics I.
 It highlights useful information, intuition, or motivation.
 It is used in the exercise sections to highlight problems that are more challenging and require
deeper thinking. They are intended for students who wish to explore the material of the
module in greater depth.

8
Chapter 1

Introduction to algorithms and

randomization

1.1 What is an algorithm?

An algorithm is a finite, unambiguous sequence of instructions that transforms inputs into
outputs.
Everyday example: a recipe or a procedure to shuffle a deck of cards.
Do not confuse algorithm with computer program: the later is an implementation of an algorithm
in a programming language.

Definition 1.1 (Algorithm). An algorithm A with input set I and output set O is a de-
terministic, well-defined procedure that, for every x ∈ I, halts after finitely many steps and
returns an output A(x) ∈ O. The running time on input x, denoted TA (x), is the number of
steps executed until the output is produced.

1.1.1. Examples of algorithms

√
Recall that if n is not a prime number, then n is divisible by some number x ≤ n.

Algorithm 1.2: Naive primality testing

Input: integer n ≥ 2
Output: true if n is prime, false otherwise

If n = 2, return true.
√
Otherwise, for each integer x from 2 to n, check if n is divisible by x. If it is, return
false.
If no divisor is found in the step above, return true.

9
10 Chapter 1. Introduction to algorithms and randomization

Algorithm 1.3: Deterministic matrix multiplication check

Input: A, B, C ∈ Rn×n
Output: true if AB = C, false otherwise

Compute the product AB.

Check if each term of AB equals the corresponding term of C. If so return true.
Otherwise return false.

ž Instructor’s Note. It is sufficient to describe your algorithms in plain English, as in

the examples above.
The only requirements are that the input is clearly specified and that your description
provides a clear, unambiguous sequence of steps that terminates with a return command.
You won’t be required to write or read pseudocode or any programming language.

1.2 Randomized Algorithms

A randomized algorithm is an algorithm that can make random choices during its execution. An
algorithm that is not randomized is called a deterministic algorithm.
• Deterministic algorithm: if we run it more than once with the same input, the algorithm
always follows the same steps and returns the same output.
• Randomized algorithm: it may follow different execution paths on different runs with the
same input, and may return different outputs in each run. It may even return an incorrect
answer, but we require that for any given input there is a positive probability that the output
is correct.

Definition 1.4 (Randomized algorithm). Let I be an input set and O an output set, and let
Spec : I → 2O map each input to the set of correct outputs. A randomized algorithm A over
(I, O, Spec) is a well-defined procedure that may make random choices during its execution,
and such that the following holds for every input x ∈ I:
(i) the running time TA (x) has finite expectation, E[TA (x)] < ∞;
 
(ii) the probability of the output being correct is positive: Pr A(x) ∈ Spec(x) > 0.

1.2.1. First example of randomized algorithm: primality test

√
Instead of looking for a divisor of n among all numbers up to n, we just check one randomly
chosen number.
Chapter 1. Introduction to algorithms and randomization 11

Algorithm 1.5: Randomized primality test

Input: integer n ≥ 2
Output: true if n is prime, false otherwise

If n = 2, return true.
√
Otherwise, pick I uniformly at random from {2, . . . , n}.
If n is divisible by I, return false.
Otherwise, return true.

1.2.2. Why introduce randomization into algorithms?

• Efficiency: randomization can lead to faster algorithms.
• Simplicity: some randomized algorithms are easier to design and analyze than their determin-
istic counterparts.
• Robustness: randomization can protect against adversarial behavior (i.e., a badly intended
user).

1.3 Types of randomized algorithms: Monte Carlo & Las Vegas

There are two main types: Monte Carlo and Las Vegas algorithm.
• Monte Carlo: it finishes within some fixed time bound but may return an incorrect output
• Las Vegas: it always outputs the correct answer but the running time is random.

Definition 1.6 (Monte Carlo & Las Vegas algorithm). Let A be a randomized algorithm
over (I, O, Spec).
A is Monte Carlo if both the following hold:
• (bounded time) for every x ∈ I there exists a finite t such that P (TA (x) ≤ t) = 1;
• (nonzero error somewhere) there exists x ∈ I for which P (A(x) ∈ Spec(x)) < 1.
A is Las Vegas if, for every x ∈ I:
• (finite expected running time) E [TA (x)] < ∞;
• (always correct) P (A(x) ∈ Spec(x)) = 1.

It is worth noting that some randomized algorithms are neither Monte Carlo nor Las Vegas.

1.4 Further examples of randomized algorithms

1.4.1. Random primality test
Recall the randomized primality test from Algorithm 1.5. It is a Monte Carlo algorithm.
To see that it is a Monte Carlo algorithm, we must show that it has nonzero probability of
making a mistake with at least one choice of the input. This is satisfied. For example, if n = p2
for some prime number p, then

1
P (output is correct) = P (I = p) = √ < 1.
n−1
12 Chapter 1. Introduction to algorithms and randomization

Notice that P (output is correct) can also be written as P (A(n) ∈ Spec(n)).

To finalize the proof that the algorithm is a Monte Carlo algorithm, we must still derive a
positive lower bound on the probability that the output is correct.
• If n is prime, the algorithm is always correct (it never outputs false).
√
• If n is not prime, there exists at least one j ∈ {2, 3, . . . , n} that divides n. In that case,
1
P (the output is correct) ≥ P (I = j) = √ > 0,
n−1
√
where I is the random variable from Algorithm 1.5, and the value n − 1 corresponds to
√
the number of elements in the set {2, 3, . . . , n}. Hence, there is a positive probability of
outputting the correct answer for any input.

 The value √n−11

may seem very small when n is large, but the main point is that it
is strictly positive (that is, the algorithm has a positive probability of giving the correct
answer).

Î Recall 1.7 (Probability space and events). Note that {the output is correct} and {I = j}
are both events.
√
If Ω = {2, . . . , n} is the (sample space) (set of possible outcomes), an event is a subset of Ω.
Given events A ⊆ B ⊆ Ω then P(A) ≤ P(B).
If two events A, B are independent then P(A ∩ B) = P(A)P(B).
If two events A, B are disjoint then P(A ∪ B) = P(A) + P(B).
In our example, {I = j} ⊂ {the output is correct}.

1.4.2. Boosting
One way to improve the probability that Algorithm 1.5 outputs the correct answer is to run it
for many times.

Algorithm 1.8: Boosting Monte Carlo primality test

Input: integers n ≥ 2 and K ≥ 1

Output: true if n is prime, false otherwise

If n = 2, return true.
√
Otherwise, pick I1 , I2 , . . . , IK independently and uniformly at random from {2, . . . , n}.
If n is divisible by at least one of I1 , . . . , IK , return false.
Otherwise, return true.
√
Then, if n is not prime, and letting j ≤ n be a divisor of n, the probability that Algorithm 1.8
outputs the correct answer is
 K
P (the output is correct) ≥ 1 − (P (I1 ̸= j))K ≥ 1 − 1 − √1
n−1
.

1.4.3. Las Vegas primality test

Chapter 1. Introduction to algorithms and randomization 13

Algorithm 1.9: Las Vegas primality test

Input: integer n ≥ 2
Output: true if n is prime, false otherwise

If n = 2, return true.
√
Otherwise, pick I uniformly at random from {2, . . . , n}.
If n is divisible by I, return false.
Otherwise, run the deterministic Algorithm 1.2.

Below is another Las Vegas algorithm for primality test which does not resort to the deterministic
algorithm.

Algorithm 1.10: Las Vegas primality test II

Input: integer n ≥ 2
Output: true if n is prime, false otherwise

If n = 2, return true.
√
Otherwise, pick a uniformly random permutation σ of {2, . . . , n}.
√
For each x from 1 to n − 1 check whether n is divisible by σ(x); if it is, return false.
If no divisor is found in the step above, returns true.

1.5 Matrix multiplication check (Freivalds)

We have seen Algorithm 1.3. We now turn to a randomized algorithm for the same problem,
known as Freivalds’s algorithm. This is one of the earliest examples of applying randomness in
computation.
Recall that we are given three matrices A, B, C and want to check whether AB = C. The key
idea is to pick a random vector r, compute Br and then verify whether A(Br) = Cr.
• If AB = C, then A(Br) = Cr for every vector r. Hence, the algorithm is always correct in
this case.
• However, if AB ̸= C, the algorithm may output the wrong answer: there may exist some
vectors r for which A(Br) = Cr.

Algorithm 1.11: Freivalds’s algorithm

Input: A, B, C ∈ Rn×n
Output: true if AB = C, false otherwise

Sample a random vector r = (r1 , r2 , . . . , rn ) with r1 , . . . , rn i.i.d. Bernoulli(1/2)

Compute x = Br.
If Ax ̸= Cr return false; otherwise return true.

Î Recall 1.12 (Bernoulli distribution and i.i.d.). A random variable X ∼ Bernoulli(p)

has value 0 or 1 with probability P(X = 1) = p and P(X = 0) = 1 − p.
14 Chapter 1. Introduction to algorithms and randomization

The term i.i.d. means independently and identically distributed.

1.5.1. Some remarks on Freivalds’s algorithm.

Checking whether AB = C is a deterministic problem: the input is (A, B, C) and the output
is simply yes or no, with no randomness involved. Freivalds’s algorithm introduces randomness
as a tool to obtain a faster procedure. This randomness is crucial: if the vector r were fixed
deterministically, there would exist inputs A, B, C for which the algorithm always produces the
wrong output.
Freivalds’s algorithm is an example where randomization produces a more efficient algorithm.
• Each matrix–vector product (Br, Ax and Cr) performs n2 arithmetic operations.
• The Algorithm 1.3 requires roughly n3 operations to the calculation of the matrix-matrix
product AB, which for large values of n is much larger than 3n2 .
The trade-off is that Freivalds’s algorithm may output an incorrect answer. The practical
efficiency comes from quantifying how likely Freivalds’s algorithm is to return the correct answer.
The idea is that instead of verifying whether each entry of AB matches the corresponding entry
of C, Freivalds proposes first compressing the information by multiplying both sides by a random
vector r. This way, rather than comparing two matrices with n2 elements each, we only need to
compare the two vectors ABr and Cr, each of length n. This technique is widely used in search
algorithms for large datasets.

1.5.2. Analyzing Freivalds’s algorithm.

We must derive a lower bound on the probability that Freivalds’s algorithm is correct.
Lemma 1.13. Let AB ̸= C where A, B, C are n × n matrices, and let r be a random vector
with i.i.d. Bernoulli(1/2) entries. Then P(ABr = Cr) ≤ 12 .

Proof. Define D = AB − C and assume that D ̸= 0. Since D ̸= 0, some element of D is nonzero;

assume without loss of generality that this element is D1,1 . Hence,
n
X
(Dr)1 = D1,1 r1 + D1,j rj . (1.5.1)
j=2

Now we condition on the possible values of {rj : j ≥ 2} and use that r1 is independent of
r2 , r3 , . . . , rn to obtain
   
X n
\ n
\
P (Dr = 0) = P Dr = 0 {rj = xj } P  {rj = xj }
x2 ,x3 ,...,xn ∈{0,1} j=2 j=2
 Pn   
n n
j=2 D1,j xj
X \ \
= P r1 = − {rj = xj } P  {rj = xj } .
D1,1
x2 ,x3 ,...,xn ∈{0,1} j=2 j=2
Tn
The last line holds because conditioning on j=2 {rj = xj } and using (1.5.1) we have that
(Dr)1 − n (Dr)1 − n
P P
j=2 D1,j rj j=2 D1,j xj
r1 = D1,1 = D1,1 .
This last term is just some number. The probability
that r1 is equal to any given number is at most 1/2, therefore,
 
n
X 1 \ 1
P (Dr = 0) ≤ · P {rj = xj } = .
2 2
x2 ,x3 ,...,xn ∈{0,1} j=2
Chapter 1. Introduction to algorithms and randomization 15

Î Recall 1.14 (Conditional probability and conditional expectation).

• Conditional probability: if A and B are events, then the probability of A conditioned on B
is P(A | B) = P(A∩B)
P(B) .
• Conditional expectation: the
P expectation of a discrete random variable X conditioned on
an event A is E(X | A) = x xP(X = x | A).

Î Recall 1.15 (Law of total probability and expectation).

• Law of total probability. If B1 , B2 , . P events such that P ( ni=1 Bi ) = 1,
S
. . , Bn are disjoint P
and A is another event then P(A) = ni=1 P (A ∩ Bi ) = ni=1 P (A | Bi ) P(Bi ).
Sn
• Law of total expectation. If B1 , B2 , . . . , BP
n are disjoint events such that P ( i=1 Bi ) = 1,
and X is a random variable then E(X) = ni=1 E (X | Bi ) P(Bi ).

 The proof of Lemma 1.13 employs a strategy known as searching for a witness. If
after choosing the random vector r we obtain ABr ̸= Cr, then this choice of r serves as a
certificate (also known as a witness) that demonstrates that AB ̸= C.

1.6 Exercises
Exercise 1.1. There are n balls and n bins. Each ball is placed in a bin chosen independently
and uniformly at random.
(a) Determine the probability that a given bin is empty.
(b) Determine the probability that there is no empty bin.

Exercise 1.2. A machine produces parts labelled 1, 2, . . .. Each part is defective with proba-
bility p ∈ (0, 1), independently of the others. For each i ≥ 1, let Xi be the indicator that part i
is defective.
(a) Determine the distribution of X1 , and compute E(X1 ) and Var(X1 ).
(b) Suppose that at least one of the first two parts is defective. Conditioned on this, determine
the probability that both are defective.
(c) Compute E(X1 + X2 | X1 + X2 ≥ 1).
(d) Let Yn = ni=1 Xi be the number of defective parts among the first n parts. Determine the
P
distribution of Yn , and compute E(Yn ) and Var(Yn ).

Exercise 1.3. In a large population of birds, each bird independently has the disease with
probability 0.1. A diagnostic test detects the disease in an infected bird with probability 0.9,
and it reports positive for a healthy bird with probability 0.1.
(a) We take a given bird from the population and perform the diagnostic test. Determine the
probability that the test is positive for that bird.
(b) Condition on a positive test result. Determine the probability that the bird has the disease.
(c) Now we perform the test again on the same bird. Assume the two test outcomes are
conditionally independent given the bird’s disease status, and that both results are positive.
Determine the probability that the bird has the disease.

Exercise 1.4. An algorithm receives as input a list of n distinct numbers and a target value
16 Chapter 1. Introduction to algorithms and randomization

t. The algorithm must return true if t belongs to the list, and false otherwise. Consider the
following algorithms (all random choices are independent of one another):
• Algorithm 1: pick one element from the list uniformly at random and return true if it
equals t, and false otherwise.
• Algorithm 2: repeatedly pick elements uniformly at random with replacement until either
(i) t is observed, or (ii) every distinct element of the list has been observed at least once;
return true in case (i) and false in case (ii). For this algorithm you can consider its runtime
as the number of elements picked until the algorithm stops. Note that since the elements are
picked with replacement, this number may be larger than n.
• Algorithm 3: repeatedly pick elements uniformly at random with replacement until either
(i) t is observed, or (ii) the same element is picked in two consecutive picks; return true in
case (i) and false in case (ii).
(a) Classify Algorithm 1 as Monte Carlo or Las Vegas, providing justification.
(b) Assuming t is present in the list, determine the probability that Algorithm 1 outputs the
correct answer.
(c) Assuming t is absent from the list, determine the probability that Algorithm 1 outputs the
correct answer.
(d) Determine the probability that Algorithm 2 outputs the correct answer.
(e) Classify Algorithm 2 as Monte Carlo or Las Vegas, providing justification.
(f)  Assuming t is present in the list, determine the probability that Algorithm 3 outputs
the correct answer.
(g) Is Algorithm 3 Monte Carlo? Provide a justification to your answer.

Exercise 1.5. This question is about Freivalds’s algorithm. Recall that the algorithm receives
three n × n matrices A, B, C and decides whether AB = C by drawing a random vector r =
(r1 , . . . , rn ) with i.i.d. entries ri ∼ Bernoulli(1/2) and outputting “AB = C” iff ABr = Cr. In
class we proved the following result: for every A, B, C,
1
P(output is correct) ≥ 2.

We now consider a few variations of Freivalds’s algorithm.

(a) Let r1 , . . . , rn be i.i.d. discrete random variables with some distribution over Z (not nec-
essarily supported on {0, 1}). Show that there exist matrices A, B, C with AB ̸= C such
that
P(ABr = Cr) > 0.
Hint. Take B to be the all-zero matrix, and let C be the matrix whose first row is
(1, −1, 0, . . . , 0) and all other rows are zero.
1
(b) Suppose r1 , . . . , rn are i.i.d. Bernoulli(p) for some p ∈ [0, 1]. Show that p = 2 maximizes

min P(output is correct on input A, B, C).

A,B,C

1
(c) Recall that the proof that Freivalds’s algorithm satisfies P(output is correct) ≥ 2 for any
choice of input relies on the fact that
 Pn 
n
D r
j=2 1,j j
\ 1
max P r1 = − {rj = xj } ≤ .
x2 ,x3 ,...,xn ∈{0,1}n−1 D 1,1 2
j=2
Chapter 1. Introduction to algorithms and randomization 17

Now suppose instead that r1 , . . . , rn are chosen i.i.d. uniformly on {0, 1, 2, . . . , k} for some
integer k > 1. Does this choice yield a smaller upper bound on the probability in the
expression above? Does it change the lower bound on the probability that the output is
correct?

Exercises from the tutorial sheet

Exercise 1.6. We throw a fair coin twice, independently, and let Xi , i ∈ {1, 2}, be the indicator
random variables that the i-th toss is heads. Let Z = X1 .
(a) Compute E(X1 ), E(Z), Var(X2 ), and Var(Z).
(b) Compute E(X1 + X2 ) and E(X1 + Z).
(c) Compute Var(X1 + X2 ) and Var(X1 + Z).

Exercise 1.7. A pomegranate tree bears a random number N of fruits with distribution
Poisson(λ). Conditional on N , the numbers of seeds in different fruits are independent, and
each fruit has a Poisson(µ) number of seeds; assume also that these counts are independent of
N . Let Y be the total number of seeds on the tree.
(a) For any positive integer value n, determine E(Y | N = n).
(b) Determine E(Y ).

Exercise 1.8. We are interested in finding the smallest number in a list of n distinct numbers
(not necessarily sorted). Consider the following randomized algorithm:

Algorithm

Input: a list of n ≥ 2 distinct numbers

Output: the smallest number in the list

Pick one element of the list uniformly at random and return its value.

(a) Classify this algorithm as Monte Carlo or Las Vegas, and justify your answer.
(b) Determine the probability that the algorithm outputs the correct answer.
(c) Now suppose the algorithm instead picks two elements uniformly at random, without re-
placement, and returns the smaller of the two. Determine the probability that the algorithm
outputs the correct answer.

Exercise 1.9. An algorithm receives as input a list of n ≥ 3 distinct, unsorted numbers, where
n is odd, and must output the list’s median; that is, the unique value x in the list such that
exactly n−1 n−1
2 elements are larger than x and exactly 2 elements are smaller than x. Consider
the following algorithms (all random choices are independent of one another):
• Algorithm 1: pick one element from the list uniformly at random and return its value.
• Algorithm 2: pick two elements from the list uniformly at random, without replacement,
and return their average.
• Algorithm 3: given a positive, odd integer M with M < n, pick M elements from the list
uniformly at random, without replacement, and return the median of these M elements.
(a) Classify Algorithm 1 as Monte Carlo or Las Vegas, providing justification.
(b) Explain why Algorithm 2 is neither Monte Carlo nor Las Vegas.
18 Chapter 1. Introduction to algorithms and randomization

(c) Determine the probability that Algorithm 1 outputs the correct answer.
(d) Determine the probability that Algorithm 3 with M = 3 outputs the correct answer.
Chapter 2

Graphs and randomness

2.1 What is a graph?

A graph is a mathematical model for a network: “a set of entities (vertices or nodes) connected
by line segments (edges)” as in Figure 2.1.

2
2 1 4
5
1 4
5 3
3

9
10 8 6
9
10 8 6

7
7
(b) A graph with one loop {4, 4} and a multiple
(a) A simple graph edge {6, 8}.

Figure 2.1: Two examples of graphs.

Definition 2.1 (Graphs). A graph is a pair G = (V, E) where V is a set of vertices (or nodes)
and E ⊆ V 2 is a set of edges. The number of vertices may be either finite or infinite. Edges
are denoted by {u, v} with u, v ∈ V being usually called the endpoints of the edge {u, v}.

Unless stated otherwise, graphs in this module are simple and undirected : no multiple edges
(that is, at most one edge between any two vertices), no loops, and {u, v} = {v, u}.

 Graphs are fundamental mathematical objects with several applications:

• Communication and transportation networks (routing and congestion control),
• Computational biology (protein–protein interaction networks, phylogenetic inference),
• Epidemiology (spread of infection on contact networks),
• Social networks (community detection, influence propagation),
• Operations and scheduling (resource-constrained timetabling),

19
20 Chapter 2. Graphs and randomness

• Power and financial systems (grid contingency analysis, systemic-risk propagation)

• Data science and machine learning (clustering, semi-supervised learning).

2.2 Fundamental definitions

• Two vertices u, v ∈ V are called neighbors or adjacent if {u, v} ∈ E.
• The degree of a vertex v is the number of neighbors of v, and is denoted by dG (v) =
|{u ∈ V : {u, v} ∈ E}|.
• A graph is called regular if all vertices have the same degree.
• A set S ⊆ V determines a partition or a cut of V into the sets S and V \ S.
• The size of the cut S is ∂S = {{u, v} ∈ E : u ∈ S, v ∈ V \ S}.
• ∂S is the set of edges with exactly one endpoint in S; ∂S is usually called the edge boundary
of S.

2.3 Handshake lemma

The following simple result says that the sum of the degrees of the vertices is equal to twice the
number of edges.
P
Lemma 2.2 (Handshake lemma). Given any graph G = (V, E), we have v∈V dG (v) = 2 |E|.

Proof. Note that in the sum each edge is counted twice (once for each of its endpoint). More
formally, we can write
X X X X X X
dG (v) = 1= 1= 2 = 2 |E| ,
v∈V v∈V u : {u,v}∈E {u,v}∈E w∈{u,v} {u,v}∈E

where the second equality is obtained by changing the order of the double sums.

2.4 Paths, cycles, connected components and trees

A path from v0 to vk is a sequence of distinct vertices (v0 , v1 , . . . , vk ) with {vi−1 , vi } ∈ E for
every i. A cycle is a closed path v0 , . . . , vk , v0 with all vi distinct. The length of a path or a
cycle is the number of edges they contain.
The vertices of a graph G = (V, E) partition into connected components: vertices u, v ∈ V lie in
the same component iff there exists a path from u to v. A graph is connected iff it has exactly
one connected component.

Definition 2.3 (Trees). A connected graph without cycles is called a tree. Vertices of degree
1 in a tree are called leaves. See Figure 2.2b for an example.

2.5 Min-cut problem

Given a connected graph G = (V, E), the min-cut problem is to find a nontrivial subset S ⊂ V
that minimizes ∂[Link] size of the min-cut is the smallest number of edges that need to be
removed from the graph in order to disconnect it. In the graph of Figure 2.1a the min-cut is 2
(S = {1, 2} or S = {1, 2, 3, 9, 10} achieve |∂S| = 2).
Chapter 2. Graphs and randomness 21

2 2
1 4 1 4
5 5
3 3

9 9
10 8 6 10 8 6

7 7

(a) A disconnected graph. (b) An example of a tree

 One application of min-cut is to find community structures inside a social network.

ž Instructor’s Note. We will study several problems on graphs such as the min-cut
problem above. You are not expected to memorize their formal definitions. If an assessment
includes a question about any of these problems, the necessary definition will be stated in the
question. However, you are requirement to remember the other definitions in this section,
such as the ones in Sections 2.2 and 2.4.

2.5.1. Randomized algorithm for min-cut via edge contraction

We give a randomized algorithm for the min-cut problem. Start with G0 = G and, for i =
1, 2, . . . , obtain Gi from Gi−1 by contracting a uniformly random edge e = {u, v} (see Figure 2.3):
• Remove every edge with both endpoints in {u, v};
• Merge u and v into a new vertex w = (u, v) and delete u and v;
• For every edge with exactly one endpoint in {u, v}, replace that endpoint by w.

2
1 4 1,2 1,2
5
4 4,6,8
3 5 5
3 3
9
10 6,8
9 9
10 6,8 10

7 7
(a) Graph obtained after con-
tracting {6, 8} in Figure 2.1a (b) After contracting {1, 2} (c) After contracting {4, (6, 8)}.

Figure 2.3: The edge contraction operation.

Algorithm 2.4: Randomized algorithm for min-cut

Input: connected graph G = (V, E)

Output: size of the minimum cut

Repeatedly choose a uniformly random edge from the graph and contract it, until the
graph has only two vertices.
Return the number of edges between the two remaining vertices.
22 Chapter 2. Graphs and randomness

We will check the probability that the algorithm outputs the correct answer in Proposition 2.5.
But before we may ask: Why intuitively is this algorithm any good?
• The algorithm constructs a cut S ⊂ V by contracting edges
• When an edge {u, v} is contracted, the algorithm puts u and v on the same side of the cut
(both in S or both in V \ S).
• The min-cut is a set with a small edge boundary: so by contracting edges uniformly at random,
intuitively the chances of picking an edge at the edge boundary of the min-cut is small.
Below we quantify this intuition precisely.

2.5.2. Analysis of the randomized algorithms for min-cut

Proposition 2.5. Let G = (V, E) be a connected graph with n = |V | vertices. Then, Algo-
2
rithm 2.4 outputs the correct answer with probability at least n(n−1) .

Proof. Let CG be the size of the min-cut, then every vertex of G has degree at least CG (oth-
erwise, that vertex alone would be a cut of size smaller than CG ). We also note that, for any
edge {u, v} ∈ E, the graph H obtained from G by contracting edge {u, v} has minimum degree
at least CG . The reason is that any cut of H is a cut of G.
The probability that Algorithm 2.4 produces the correct answer is equal to the probability that,
at each step of the algorithm, the edge chosen to be contracted is not an edge from the edge
boundary of the min-cut. If H is a graph at some point of the algorithm with k vertices, there
are at least CG k/2 edges in H by the Handshake Lemma and that every degree in H is at least
CG . Therefore the probability that the next edge to be contracted is in a given min-cut is at
most CKCG 2
k/2 = k . Thus the probability that the algorithm avoids contracting any edge of the
min-cut is at least
3  
Y 2 n−2n−3n−4n−5 321 2
1− = ··· = .
k n n−1n−2n−3 543 n(n − 1)
k=n

2.6 Random graphs

It is also natural to consider random graphs.
• Random graphs provide simple models for large, complex networks (e.g., social, communica-
tion, biological, and chemical networks).
• Many models have been proposed to capture specific features of real-world networks (cluster-
ing, heavy-tailed degree distributions, community structure, etc.).
• In this module we focus on the classical Erdős–Rényi model G(n, p), the simplest and most
fundamental random-graph model which already exhibits rich phenomena such as phase tran-
sitions and threshold effects.

Definition 2.6 (Erdős–Rényi graphs G(n, p)). The Erdős–Rényi random graph with param-
eters n ∈
Z+ and p ∈ [0, 1] is defined as follows. Fix a set V = [n] of n vertices. For each
of the n2 possible edges independently, include it in the graph with probability p ∈ [0, 1],
and exclude it otherwise. We denote this model as G(n, p), and a random graph G = (V, E)
obtained in this way is denoted G ∼ G(n, p).

Note that for any given vertex u ∈ V , we have that dG (u) ∼ Binomial(n − 1, p).
Chapter 2. Graphs and randomness 23

Î Recall 2.7 (Binomial distribution). A random variable X ∼ Binomial(n, p) has value in

{0, 1, 2, . . . , n} with probability distribution
 
n k
P(X = k) = p (1 − p)n−k .
k

2.7 Exercises
Exercise 2.1. Consider a simple random walk on Z: a particle that starts at the origin and at
each step independently moves one unit to the right or to the left with probability 1/2 each. If
P random variables uniformly distributed on {−1, 1}, then after t steps the
X1 , X2 , . . . are i.i.d.
position is St = ti=1 Xi , S0 = 0.
(a) Find the probability that the particle reaches 2 before −2.
(b) Find the probability that the particle reaches 3 before −1.
(c) Find the probability that the particle reaches 2 before −1.
(d) Let T be the hitting time of {−2, 2}. Compute E(T ).

Exercise 2.2. Suppose we are given a graph G = (V, E) with n vertices. We know n but not
the number of edges m = |E|. Consider two randomized algorithms to estimate m:
• Algorithm 1: pick a vertex u uniformly at random and then pick another vertex v uniformly
n


at random without replacement. Output 2 if u and v are adjacent in G, and 0 otherwise.
n dG (u)
• Algorithm 2: pick a vertex u uniformly at random from V . Output .
2
(a) Determine the expectation of the output of algorithm 1.
(b) Determine the expectation of the output of algorithm 2.

Exercises from the tutorial sheet

Exercise 2.3. Given a graph G = (V, E), a set S of vertices is called a clique if any two vertices
in S are connected by an edge in G. A clique S of cardinality k is called a k-clique. Now consider
the random graph G ∼ G(n, p).
(a) Determine the expected number of 3-cliques in G.
(b) Determine the expected number of isolated vertices in G, where a vertex is called isolated
if its degree is 0.
(c) Given a set S ⊂ V determine the probability that |∂S| is 0.
Chapter 3

The probabilistic method

3.1 Key basic result

The essence of the probabilistic method lies in the following very simple inequality, which says
that any random variable has a positive probability to be at least as large as its expectation.

Theorem 3.1 (Key result for the probabilistic method). Let X be a random variable with
finite expectation (E(X) < ∞). Then, P (X ≥ E(X)) > 0.

Proof. The proof is via contradiction. Assume that the statement is false; that is, we are
assuming that P (X ≥ E(X)) = 0. Define a new random variable Y = E(X) − X. Then Y is a
positive random variable (that is, P(Y > 0) = 1), which implies that E(Y ) > 0. On the other
hand, using the definition of Y ,

E(Y ) = E (E (X) − X) = E(X) − E(X) = 0,

reaching a contradiction.

3.2 Max-cut problem

We begin by introducing the probabilistic method through the max-cut problem.
Given a graph G = (V, E), the goal is to find a subset S ⊂ V maximizing |∂S|.

 The max-cut models situations where objects (vertices) must be divided into two groups
while maximizing interactions (edges) across them.

|E|
Computing the maximum cut is difficult! We will prove that its size is always at least 2 .
The problem is deterministic, but the proof employs probability in an elegant way.

Î Recall 3.2 (Indicator random variable). Given an event A, an indicator random variable
(or indicator function) 1(A) is the random variable that has value 1 if the event A holds, and
has value 0 if the event A does not hold. Therefore, 1(A) is a Bernoulli(p) random variable
with parameter p = P(A). Hence, E(1(A)) = p = P(A).

Proposition 3.3. Given any graph G = (V, E), there exists S ⊂ V such that |∂S| ≥ |E|/2.

24
Chapter 3. The probabilistic method 25

Proof. First, let W be a random subset of V obtained by adding each vertex of V to W inde-
pendently with probability 1/2. Since W is a random set, then ∂W is a random set of edges.
We want to compute its expectation. Using linearity of expectation (see a recall at the end of
the proof):
!
X X X
E (|∂W |) = E 1 (e ∈ ∂W ) = E (1 (e ∈ ∂W )) = P (e ∈ ∂W ) .
e∈E e∈E e∈E

Now we estimate P (e ∈ ∂W ). For a given edge e to be in ∂W , we need that exactly one of e’s
endpoint be in W . The probability that this happens is 2 × 21 × 12 . Therefore,
X1 |E|
E (|∂W |) = = .
2 2
e∈E
 
Using Theorem 3.1 we obtain that P |∂W | ≥ |E| 2 > 0. Therefore, there exists a subset S ⊂ V
|E|
such that |∂S| ≥ 2 .

Î Recall 3.4 (Linearity of expectation). Given any two random variables X and Y (not
necessarily independent of each other) we have E(X + Y ) = E(X) + E(Y ).

 The probabilistic method guarantees the existence of a large cut, but provides no
information about which cut achieves this value.

3.3 The probabilistic method in words

The probabilistic method is not a theorem to be “quoted,” but rather a technique for proving
the existence of certain objects. In general, we start with a set Ω of possible objects. Each
S ∈ Ω is assigned a value f (S), and the goal is to show that some S achieves a large value of
f (S).
The method proceeds by introducing a probability distribution on Ω and defining a random
variable X as a random element of Ω. We then compute E(f (X)), and by Theorem 3.1, conclude
that there exists S ∈ Ω such that f (S) ≥ E(f (X)).
In the max-cut problem, Ω is the collection of subsets S ⊂ V and the value of each S is
f (S) = |∂S|. The probability distribution on Ω is that of picking each vertex independently
with probability 1/2; that is, for each S ⊂ V the probability of getting that particular S is equal
to 2−|V | .

3.4 Independent set problem

We derive a bound on the size of the largest independent set in a graph. Given a graph G =
(V, E), a subset S ⊂ V is an independent set if every edge e ∈ E has at most one endpoint in
S. Let I(G) denote the size of the largest independent set of G.

 Independent set has many applications. Below are a few examples:

• Wireless networks: it models transmitters that can operate simultaneously without inter-
ference;
• Scheduling: it captures sets of jobs that do not use the same resources and therefore can
be scheduled to run simultaneously;
26 Chapter 3. The probabilistic method

• Biology or social networks: it can represent genes that do not interact directly or groups
of individuals with no conflicting relationships.

Proposition 3.5. Let G = (V, E) be a graph with n = |V | vertices and m = |E| edges. Then
n2
I(G) ≥ 4m .

Proof. We start constructing a random set of vertices Z by putting each vertex of v indepen-
dently in Z with probability p. We will
P choose the value of p later. Note that Z is not necessarily
an independent set. Define MZ = {u,v}∈V 1(u ∈ Z and v ∈ Z). That is, MZ is the number
of edges with both endpoints in Z. We will construct W by taking Z and removing from it one
endpoint for each edge that has both endpoints in Z. In this way, W is an independent set.
Note that |W | ≥ |Z| − MZ , therefore

E(|W |) ≥ E(|Z| − MZ ) = E(|Z|) − E(MZ ).

Since Z is a binomial random variable with parameters n and p, we get E(|Z|) = np. As for
E(MZ ), we have
X X
E(MZ ) = P(u ∈ Z and v ∈ Z) = p2 = mp2 .
{u,v}∈E {u,v}∈V

Putting the two estimates together, we obtain

E(|W |) ≥ np − mp2 .

So using Theorem 3.1 we have that I(G) ≥ np−mp2 . But this is true for all p ∈ [0, 1]. So we can
now choose the p that maximizes the expression np − mp2 so that we get the best bound. This
can easily be done by first derivating in p and seeing the value of p that makes the derivative
n
equal to 0, which is p = 2m . Substituting this value into np − mp2 gives that
 n   n 2 n2
I(G) ≥ n −m = .
2m 2m 4m

ž Instructor’s Note. As with the min-cut problem, I do not expect you to memorize
the definition of the max-cut and the independent set problems.

3.5 Exercises
Exercise 3.1. Let X be any random variable. Show that P (X ≤ E(X)) > 0.

Exercise 3.2. A town is represented by a graph G = (V, E), where each vertex is a street
corner and each edge is a road between two corners. The mayor wants to install streetlights at
some corners so that every corner is lit: we say that a corner is lit if either a streetlight is placed
there or it has a neighboring corner with a streetlight. The goal of this exercise is to show that
it is possible to achieve this using at most n 1+log(δ+1)
δ+1 streetlights, where n = |V | is the number
of vertices in G and δ = minv∈V dG (v) is the smallest degree in G.
For this, let U ⊂ V be a random subset of vertices obtained by picking each vertex of V
independently with probability p ∈ (0, 1). Let W be the set of vertices of V \ U that have no
neighbors in U .
Hint: You may use the inequality e−x ≥ 1 − x which is valid for all x ∈ R.
Chapter 3. The probabilistic method 27

(a) If we place a streetlight at each vertex of U , show that the probability that there is an unlit
corner is at most ne−p(δ+1) .
(b) Determine E(|U ∪ W |).
(c) Deduce that it is possible to lit all corners with at most n 1+log(δ+1)
δ+1 streetlights.

Exercise 3.3. You own a large collection Ω of artworks. Each artwork x ∈ Ω is associated with
an n-bit binary string fx ∈ {0, 1}n describing its features (for example, abstract or realistic,
modern or classical style, large or small, etc.). No two artworks in your collection share the
same feature string; that is, for any distinct x, y ∈ Ω, fx ̸= fy . Consequently, |Ω| ≤ 2n .
We wish to select a subset S ⊆ Ω to include in an exhibition. The exhibition should not include
any pair of similar artworks, where two artworks are considered similar if they differ in fewer
than three features. That is, x, y ∈ Ω are similar if
n
X
|fx (i) − fy (i)| < 3,
i=1

where fx (i) and fy (i) are the i-th bits in the strings fx and fy , respectively.
(a) Show that there exists a selection S of pairwise dissimilar artworks such that |S| ≥
2 |Ω|
n(n+1)+2 .
Hint: Consider a random process that adds artworks one at a time to S.
(b) Suppose that, for each artwork x ∈ Ω, the number of other artworks in Ω that are similar
¯ 1 P
to x is ∆x . Let ∆ = |Ω| x∈Ω ∆x be the average number of artworks similar to a given
one.
Show that there exists a selection S of pairwise dissimilar artworks such that |S| ≥ 2|Ω|
∆¯.
Hint: Randomly select each artwork with a suitable probability, and then remove one
artwork from every similar pair.

Exercises from the tutorial sheet

Exercise 3.4. A university wants to seat students in an exam hall so that no two friends sit
side by side. Let G = (V, E) be a graph in which each vertex v ∈ V is a student and an edge
{u, v} ∈ E indicates that u and v are friends. The hall has n = |V | seats arranged in a single
row.
Consider the following randomized procedure: sample a uniform random permutation π of V
and seat the students in the order π (1) , π (2) , . . . , π (n).
(a) For each edge {u, v} ∈ E, determine the probability that u and v are seated side by side.
(b) Let d̄G denote the average degree of G. Conclude that there exists a seating arrangement
with at most d̄G pairs of friends seated side by side.

Exercise 3.5. Two companies, A and B, each provide long-distance connections between 1000
cities. Every pair of cities must be connected by a direct link operated by exactly one of the
two providers.
We want to decide, for each pair of cities, which company provides the link between them so that
no group of 20 cities is completely dependent on a single provider; that is, within any subset of
20 cities, there must be at least one pair connected by an A-link and at least one pair connected
by a B-link.
Show that such an assignment of providers to pairs
of cities is possible.
Hint: You can use that for any n ≥ k we have nk ≤ nk /k!.
28 Chapter 3. The probabilistic method

Exercise 3.6. A non-trivial 3-arithmetic progression (3-AP) is a set of three natural numbers
(a, a + d, a + 2d) where a, d ∈ N. Let [n] denote the set {1,
√
2, . . . , n}. Show that, for any n, there
3 n
exists a set S ⊆ [n] with no 3-AP and such that |S| ≥ 4 .
2
Hint: You can use that the number of 3-AP inside [n] is at most n4 . If you want to know
where this bound comes from, the number of 3-AP inside [n] is
n−1
n−1 n−1
2
X 1X 1X 1 n(n − 1) n2
(n − 2d) ≤ (n − d) = d= ≤ .
2 2 2 2 4
d=1 d=1 d=1
Chapter 4

Asymptotics and convergence of

random variables

4.1 Almost surely and asymptotically almost surely

Many examples in this module will be studied asymptotically as the size of the problem goes to
infinity. This is indeed what happens in many applications. We start with a definition of what
it means for an event (actually, a sequence of events) to happen asymptotically.

Definition 4.1 (Almost surely and asymptotically almost surely).

• An event F is said to the happen almost surely (a.s.) if P(F ) = 1.
• A sequence of events F1 , F2 , . . . occurs asymptotically almost surely (a.a.s.) if we have
lim inf n→∞ P (Fn ) = 1.
In some places, you will see the term with high probability (w.h.p.) instead of asymptotically
almost surely. They are equivalent and you are free to use either of the two.

Examples: if U ∼ Uniform(0, 1), then F = {U ̸= 1/3} happens almost surely and Fn =

{U ≥ 1/n} happens asymptotically almost surely.

 Why do we say that an event occurs almost surely rather than surely when P(F ) = 1?
Because even when an event has probability one, there may still exist legitimate outcomes
in the probability space where it fails to occur.
For example, for F = {U ̸= 1/3} as above, we have P(F ) = 1 since P(U = 1/3) = 0; yet the
outcome U = 1/3 is perfectly valid. The term almost surely emphasizes this distinction: the
event holds except on a set of probability zero.

4.2 Convergence of numbers

Recall the definition of convergence of numbers. Figure 4.1 shows four examples.

Î Recall 4.2 (Limit of sequences). Given a sequence of real numbers a1 , a2 , . . ., we say that
limn→∞ an = C for some C ∈ [−∞, ∞] if for every ε > 0 there exists n0 = n0 (ε) such that

|an − C| < ε, for all n ≥ n0 .

29
30 Chapter 4. Asymptotics and convergence of random variables

Moreover, if limn→∞ an = C and f is a continuous function, then limn→∞ f (an ) = f (C).

(a) f (n) = e1/n converges to 1 (b) f (n) = (−1)n does not converge

√
(c) f (n) = n converges to ∞ (d) f (n) = sin(n) does not converge

Figure 4.1: Examples of convergence of numbers.

4.3 Convergence of random variables

What if instead of a sequence of numbers we have a sequence of random variables X1 , X2 . . .?
How can we argue that they converge to some quantity? For this, several notions of convergence
are useful.

4.3.1. Convergence in probability

Definition 4.3 (Convergence in probability). A sequence of random variables (Xn )n con-

p
verges in probability to a number C, written Xn →
− C, if for every ε > 0,

P(|Xn − C| > ε) → 0.
p
Examples: If Xn ∼ Bernoulli(1/n) then Xn → − 0. Another example is the weak
P law of large
numbers. If Xn are i.i.d. with finite expectation µ ∈ (−∞, ∞), and Sn = n1 ni=1 Xi , then
p
Sn →
− E(X1 ).

4.3.2. Borel-Cantelli
In order to prove results about convergence of random variables, the following simple theorem
will be fundamental.
Chapter 4. Asymptotics and convergence of random variables 31

Theorem 4.4 (Borel-Cantelli). Let (Fn )n≥1 be a sequence of events.

(i) If ∞
P
n=1 P(Fn ) < ∞, then P (Fn occurs infinitely often) = 0.
(ii) If Fn are independent events and ∞
P
n=1 P(Fn ) = ∞, then P (Fn occurs infinitely often) =
1.

P∞
Proof. (i) Let τ = n=1 1(Fn ) be the number of Fn that occur. Therefore,
∞
X
E(τ ) = P(Fn ).
n=1
P∞
If n=1 P(Fn ) < ∞ we have that τ has finite expectation, which implies that P(τ < ∞) =
1.
(ii) It suffices to show that P ( ∞ c
T
n=m Fn ) = 0 for any m, since this means that for any m there
exists at least one Fn with n ≥ m that occurs. We write
∞ ∞ ∞ ∞
! !
\ Y Y X
c c
P Fn = P (Fn ) = (1 − P (Fn )) ≤ exp − P (Fn ) ,
n=m n=m n=m n=m

x
P∞ we used the inequality 1 − x ≤ e valid for all x ∈ R. The result then follows since
where
n=m P (Fn ) = ∞.

4.3.3. Convergence almost surely

Definition 4.5 (Almost sure convergence). Xn converges almost surely to a constant C,

a.s.
written Xn −−→ C, if  
P lim Xn = C = 1.
n→∞

a.s.
Examples.
P∞ If Xn ∼ Bernoulli(1/n2 ) then Xn −−→ 0. This holds by Borel-Cantelli since
n=1 P(Xn = 1) < ∞. Now consider the example Xn ∼ Bernoulli(1/n), where Xn are in-
dependent of one another. does not converge a.s. (by the second part of Borel-Cantelli) but
converges in probability.

ž Instructor’s Note. The concept of almost sure convergence will be explained more
deeply in Fundamentals of Probability. For this module, it is important to understand the
difference with convergence in probability and convergence in L1 , and how to use Borel-
Cantelli to show almost sure convergence.

An important example is the strong law of large numbers.

Theorem 4.6 (Strong law of large numbers). Let Sn = X1 + X2 + · · · + Xn where the Xi

are i.i.d. random variables with expectation E(Xi ) = µ ∈ (−∞, ∞). Then,

Sn a.s.
−−→ µ.
n

4.3.4. Convergence in L1
32 Chapter 4. Asymptotics and convergence of random variables

Figure 4.2: Illustration of the law Pof large numbers. The horizontal axis gives the value n and
the vertical axis gives f (n) = n1 ni=1 Xi the average of the first n elements, where X1 , X2 , . . .
are i.i.d. Exponential(1) random variables. The plot shows convergence to 1 for that particular
sampling of X1 , X2 , . . .. This is intuitively what almost sure convergence means: it says that with
probability 1 our sampling of X1 , X2 , . . . will be such that the sequence f (1), f (2), . . . converges
to 1.

Definition 4.7 (Convergence in L1 ). Xn converges in L1 to a constant C, written Xn → C

in L1 , if
E (|Xn − C|) → 0.

Un
Examples. Let U1 , U2 , . . . be i.i.d. Uniform(0, 1) random variables, and set Xn = n . Then
Xn → 0 in L1 since
1
E(|Xn |) = → 0.
n
Now let Xn = n with probability 1/n, otherwise Xn = 0: it does not converge in L1 but
converges in probability. To see this, if this sequence were to converge in L1 we would have for
some value C that

0 = lim E(|Xn − C|)

n→∞
  
1 1
= lim |n − C| + |C| 1 −
n→∞ n n
= 1 + |C|.

Since 0 cannot be equal to 1 + |C| for any choice of C the sequence cannot converge in L1 .

4.3.5. Relation between types of convergence

Theorem 4.8 (Relation between types of convergence). Almost sure convergence implies
convergence in probability. Convergence in L1 implies convergence in probability. Almost
sure convergence and convergence in L1 are incomparable in general: neither implies the
other.

Proof. The first statement we leave as an exercise, and the second statement will be an ex-
ercise for the next week. For the third statement, we provide two examples. First, let U ∼
Uniform(0, 1) and Xn = n2 · 1(U ≤ 1/n). Then, Xn converges almost surely to 0 but does
not converge in L1 since E(Xn ) = n2 · n1 = n. To show that convergence in L1 does not imply
Chapter 4. Asymptotics and convergence of random variables 33

convergence almost surely, consider Xn ∼ Bernoulli(1/n), independently of one another. Note

that Xn converges to 0 in L1 but it does not converge almost surely by the second part of
Borel-Cantelli.

4.4 Moment generating and characteristic functions

Before introducing another mode of convergence, we need to introduce another fundamental
quantity.

Definition 4.9 (Moment generating function). The moment generating function (m.g.f.) of
a random variable X is
MX (t) = E etX , t ∈ R,

whenever the expectation exists in a neighborhood of 0.

The next theorem gives two important properties of moment generating function.

Theorem 4.10 (Moment generating function determines the distribution). Let X be a ran-
dom variable such that its moment generating function exists in a neighborhood of 0. Then,
• MX (t) uniquely determines the distribution of X,
(n) (n)
• MX (0) = E(X n ) where MX is the n-th derivative of MX (t).

Examples. If X ∼ Bernoulli(p) then

MX (t) = (1 − p)e0 + pet = (1 − p) + pet .

If X ∼ Uniform(0, 1) then
1
et − 1
Z
MX (t) = ext dx = .
0 t
If X ∼ Exponential(λ) then
Z ∞
λ
MX (t) = λe−λx ext dx = , for t ∈ (0, λ).
0 λ−t

The moment generating function is useful to show that two random variables have the same
distribution. For this, we only need to show that their moment generating functions are the
same in some region around 0. However, not all random variables have a moment generating
1 tX ) = ∞
function. For example, X defined on R with density function fX (x) = π(1+x 2 ) has E(e

for all t ̸= 0.

4.5 Convergence in distribution

Definition 4.11 (Convergence in distribution). Xn converges in distribution to a random

d
variable X, written Xn −
→ X, if

P(Xn ≤ t) → P(X ≤ t) for all continuity points t of the distribution function of X.

d
If we know the distribution of X (for example, X ∼ Uniform(0, 1), we also write Xn −
→
Uniform(0, 1)).
34 Chapter 4. Asymptotics and convergence of random variables

Corollary 4.12 (Convergence in distribution via moment generating functions). Theorem 4.10
implies that if there exists ε > 0 so that for all t ∈ (−ε, ε) we have MXn (t) and MX (t) are finite
d
and MXn (t) → MX (t), then Xn −
→ X.

Example. Consider a random variable Xn which with probability 1/n is distributed according
to a Bernoulli(1/2) and with probability 1 − 1/n is distributed according to a Uniform(0, 1).
d
Then, Xn −
→ Uniform(0, 1) since, for any t ∈ (−1, 1) we have

 t
et − 1
   
1 1 1 t 1 e −1
MXn (t) = + e + 1− → , as n → ∞,
n 2 2 n t t

where the right-hand side is the moment generating function of Uniform(0, 1).
A very important example of convergence in distribution is the Central Limit Theorem.

Theorem 4.13 (Central Limit Theorem (CLT)). Let Sn = X1 + X2 + · · · + Xn where the Xi

are i.i.d. random variables with expectation E(Xi ) = µ ∈ (−∞, ∞) and variance Var(Xi ) =
σ 2 ∈ (0, ∞). Then,
Sn − nµ d
√ −
→ N (0, 1),
nσ 2
where N (0, 1) stands for the standard Normal distribution.

Î Recall 4.14 (Normal distribution). A random variable X ∼ N (µ, σ) has value in R with
density function
(y − µ)2
 
1
fX (y) = √ exp − .
2πσ 2 2σ 2

Figure 4.3: Illustration of the law of large numbers

 The law of large numbers and the central limit theorem are simple examples of a
universal behavior. If we have a sequence of i.i.d. random variables (Xn )n with finite mean
µ and finite variance σ 2 , then regardless of the actual distribution of the Xn we have
• The average mean Sn = n1 ni=1 Xi converges a.s. to µ, and
P
Pn
(Xi −µ)
• The “standardized sum” i=1 √
σ n
converges to N (0, 1) random variable.
Chapter 4. Asymptotics and convergence of random variables 35

4.6 Exercises
Exercise 4.1. Let U ∼ Exponential(1). For each of the following events, determine whether
the event occurs almost surely, and justify your answer:
(a) {U ̸= 2}.
(b) {U = 2}.
(c) {U ≤ 2}.
(d) {U ∈ N}, where N = {1, 2, . . .} denotes the set of natural numbers.

Exercise 4.2. Consider the sequence of graphs (Gn )n , where Gn ∼ G(n, p) with fixed p ∈ (0, 1)
and Gn = (Vn , En ). Recall that we identify Vn with [n] = {1, 2, . . . , n}. Let u denote vertex
number 1.
|En | a.s.
(a) Determine whether n
−−→ p, and justify your answer.
2
dG (u) − (n − 1)p d
(b) Determine whether p n −
→ N (0, 1), and justify your answer.
(n − 1)p(1 − p)
(c) Let v denote vertex number 2. Consider the event Fn = {u and v have a common neighbor}.
Determine whether Fn occurs asymptotically almost surely.
Now assume that Gn ∼ G(n, pn ), where pn = c/n for some constant c > 0. Recall that dGn (u)
denotes the degree of vertex u in Gn .
d
(d) Show that dGn (u) −
→ Poisson(c).

Exercise 4.3 ( ). Let (Xn )n≥1 be random variables and let C ∈ R. Show that if
∞
X
P (|Xn − C| > ε) < ∞ for all ε > 0,
n=1

then Xn → C almost surely.

Exercise 4.4 ( ). This exercise will help you prove the Central Limit Theorem. Let (X Pn )n be
i.i.d. random variables with mean E(X1 ) = µ and variance Var(X1 ) = σ 2 , and let Sn = ni=1 Xi
be the sum of the first n values. The Central Limit Theorem states that
Sn − nµ d
√ −
→ N (0, 1).
σ n
Assume that there exists ε > 0 such that the moment generating function MX1 (t) exists for all
t ∈ (−ε, ε).
(a) Compute the moment generating function of a Normal random variable with parameters µ
and σ.
Xn −µ
(b) Let Yn = σ . Compute the moment generating function of Yn as a function of MX1 (·).
Note that Yn is a random variable with mean 0 and variance 1, and its
moment generating
function exists in (−ε, ε). This implies that, letting φ(t) = log MY1 (t) , we can obtain a
constant C so that
t2 t2
− C|t3 | ≤ φ(t) ≤ + C|t3 |, for all t ∈ (−ε, ε).
2 2
Sn − nµ
(c) Compute the moment generating function of √ as a function of φ.
σ n
36 Chapter 4. Asymptotics and convergence of random variables

Sn − nµ d
(d) Justify why combining the inequalities for φ and the previous step implies that √ −
→
σ n
N (0, 1).

Exercises from the tutorial sheet

1


Exercise 4.5. Consider the sequence of independent random variables Xn ∼ Geometric 1 − n ,
n ≥ 1.
(a) Determine whether Xn converges in probability.
(b) Determine whether Xn converges almost surely.
(c) Determine whether Xn converges in L1 .
1


(d) What changes in your answers to parts (a–c) if Xn ∼ Geometric 1 − n2
?

Exercise 4.6. Let X ∼ Exponential(1) and, for a > 0, define the random variable Y = aX.
(a) Compute the moment generating function of Y .
(b) Use this result to show that Y follows an Exponential(1/a) distribution.

Exercise 4.7. Imagine that we have a new digital currency called NewCoin, whose value starts
at 1 on day 0. Each day i = 1, 2, . . ., the value is obtained by taking the value from day i − 1 and
increasing it by one unit with probability p ∈ (0, 1), or decreasing it by one unit with probability
1 − p. Let Sn denote the value of NewCoin on day n.
Assume first that p = 32 .
(a) Compute E(Sn ) and Var(Sn ) as functions of n.
Sn
(b) Determine whether converges to some quantity. If so, find the limit and specify the
n
mode of convergence.
Now assume that p = 12 .
(a) ( ) Suppose that NewCoin is declared bankrupt the first time it reaches the value 0.
Does this event occur almost surely?
Chapter 5

First and second moment methods

5.1 Markov’s inequality

The first moment method relies on an application of Markov’s inequality.

Theorem 5.1 (Markov’s Inequality). Let X be a nonnegative random variable. Then, for
every m ∈ R+ , P (X ≥ m) ≤ E(X)
m .

Proof. It is equivalent to show that E(X) ≥ mP (X ≥ m). But this is already true since
E(X) = E (X1 (X < m) + X1 (X ≥ m))
= E (X1 (X < m)) + E (X1 (X ≥ m)) Linearity of expectation
≥ E (X1 (X < m)) + mE (1 (X ≥ m)) Using X ≥ m in the second term
≥ mP (X ≥ m) . Using X ≥ 0 in the first term.

What does Markov’s inequality tell us? In words, it says that

a non-negative random variable X with small expectation is unlikely to be large.

 Note that it is important that the random variable X is non-negative. Otherwise, the
following is a simple counterexample. Let X be the random variable that has value −2
with probability 14 and value 1 with probability 34 . Then, E(X) = (−2) 41 + 1 34 = 14 and
P (X ≥ 1) = P (X = 1) = 34 . However Markov’s inequality would give the incorrect bound
P(X ≥ 1) ≤ E(X) = 14 .

5.2 Coupon collector problem

Suppose we have n coupons. At each round we draw a coupon with replacement, uniformly at
random from the set of n coupons. Repeat this for t rounds.
How large should t be so that a.a.s. all coupons are picked?

Clearly, we need at least t ≥ n. But is t or order n enough? Do we need t = n2 or another

power or n?
We will show that if t = cn log n for some constant c > 1, then all coupons are picked a.a.s. An
application of the first moment method usually consists of the steps below.

37
38 Chapter 5. First and second moment methods

Step 1: setting up a counting variable as a sum of indicators. We introduce some

indicator random variables. In our case, let

1, if coupon i was never drawn
Xi =
0, otherwise.

Then, introduce a counting random variable

n
X
X= Xi .
i=1

Note that we have drawn all coupons after t samples if and only if X = 0.

Step 2: calculate expectations. Now we compute E(X) in order to apply Markov’s inequal-
ity. Everything we need is an upper bound on E(X). We start using linearity of expectations:
n
X
E(X) = E (Xi ) .
i=1

Since Xi is a Bernoulli random variable, E(Xi ) is the probability that Xi is equal to 1. This is
the probability that coupon i was never drawn, therefore
n n 
1 t 1 t
X X   
E(X) = P (Xi = 1) = 1− =n 1− .
n n
i=1 i=1

It is usually useful to write such types of “(1 − · · · )t ” bounds as an exponential using Lemma 5.2
that we state below. Since we need an upper bound on E(X), this goes in the correct direction,
giving
E(X) ≤ ne−t/n ≤ ne−c log n = n1−c ,
where we used the value of t in the last equality. Note that when c > 1 this bound goes to 0 as
n → ∞.

Step 3: applying Markov’s inequality. Since E(X) → 0, Markov’s inequality can be

applied to give
P (X ≥ 1) ≤ E(X) ≤ n1−c → 0.
Thus, in fact, we draw each coupon at least once a.a.s.

1 x
→ e−1


5.3 Fundamental inequalities: ex ≥ 1 + x and 1 − x
Despite its simplicity, the following inequalities are very useful and it is good to know them well.

Lemma 5.2. For any x ∈ R, ex ≥ 1 + x.

6 Non-examinable material.

Proof. Let f (x) = ex − (1 + x). Differentiating, we have

f ′ (x) = ex − 1.

This implies that f is increasing in (0, ∞) and is decreasing in (−∞, 0). So it has a point of
minimum at x = 0. Since f (0) = e0 − 1 − 0 = 0, we have that f (x) ≥ 0 for all x ∈ R, which
Chapter 5. First and second moment methods 39

establishes the lemma.

1 x
= e−1 .


Lemma 5.3. As x → ∞, we have limx→∞ 1 − x

6 Non-examinable material. The proof of Lemma 5.3 uses Lemma 5.4 below, which
in turn follows by analyzing the Taylor expansion of log(1 + x).
Lemma 5.4. For any x ∈ (−1/2, ∞),
2
1 + x ≥ ex−x .

Proof of Lemma 5.3. For x > 2 we get

1 x
   
1
exp −1 − ≤ 1− ≤ exp (−1) .
x x

The proof is completed by noting that as x → ∞ both sides converge to e−1 .

5.4 First moment method in words

The first moment method is used to prove that a certain event does not occur. It consists of
the following steps:
• Define a random variable X that counts the number of occurrences of the event in question.
• Show that E(X) is small (e.g., by computing a upper bound on E(X)).
• Use Markov’s inequality to infer that P(X ≥ 1) ≤ E(X) is small.
So if E(X) is small, then the probability that the event occurs is also small.
This technique is called the first moment method because it relies solely on estimating the
expectation (that is, the first moment) of X.

5.5 Balls into bins problem

We have m bins and n balls. Each ball is placed into a bin chosen independently and uniformly
at random. How large should m be so that, as n → ∞, a.a.s. no bin contains more than one
ball?
We will show that m ≫ n2 is enough. Define the counting random variable X as the number of
pairs of balls that fall into the same bin, and express it as a sum of indicators:
X
X= Ij,k ,
j̸=k∈[n]

where Ij,k is the indicator random variable that balls j and k land in the same bin. Note that
there exists a bin with at least two balls if and only if X ≥ 1.
Now compute
n


X X 1 2
E(X) = E(Ij,k ) = = .
m m
j̸=k∈[n] j̸=k∈[n]

Thus,
n(n − 1)
E(X) = → 0 as n → ∞ (since m ≫ n2 ).
2m
Therefore, a.a.s. every bin contains at most one ball.
40 Chapter 5. First and second moment methods

Î Recall 5.5 (Notation ≪ and ≫). Given two functions f (n) and g(n) the notation f (n) ≪
g(n) means that limn→∞ fg(n)
(n)
= 0. The notation f (n) ≫ g(n) means that limn→∞ fg(n)
(n)
= ∞.
f (n)
We say that f and g have the same order of magnitude if limn→∞ g(n) ∈ (0, ∞).

 This is also known as the birthday paradox. If m = 365 is the number of days of the year,
and we have n students, assuming the birthday of each student is distributed independently
and uniformly at random over the year, the probability that two
√ students share a birthday
is small only when n is relatively small (not much larger than 365).

5.6 The union bound

This is a simple bound that is often useful. It can be proved using elementary probability
(as could have been done in Lecture 1), but here it is presented as an application of Markov’s
inequality.
Sn Pn
Theorem 5.6 (Union bound). Let A1 , A2 , . . . , An be events. Then, P ( i=1 Ai ) ≤ i=1 P (Ai ).

Proof. Note that

n n n n
! ! !
[ X X X
P Ai =P 1 (Ai ) ≥ 1 ≤E 1 (Ai ) = P (Ai ) ,
i=1 i=1 i=1 i=1

where the inequality is an application of Markov’s inequality since the sum of indicators is a
non-negative random variable.

5.7 Limitations of the first moment

The first moment method is used to show that a certain event does not occur. We introduce
a counting random variable X, show that E(X) is small, and apply Markov’s to infer that
P(X ≥ 1) is also small.

 What if E(X) is large? Does this imply that P(X ≥ 1) is large and the event occurs?
Not necessarily. Consider the following simple example. Let X be a random variable that
9 1 n
equals 0 with probability 10 and equals a parameter n with probability 10 . Then E(X) = 10 ,
1
which grows with n. However, P(X ≥ 1) = 10 , which does not depend on n. Not really:
9 1
Let X be 0 with probability 10 and equals a parameter n with probability 10 .

5.8 Chebyshev’s inequality

Theorem 5.7 (Chebyshev’s inequality). Let X be a random variable with finite variance.
Then, for any z > 0,
Var (X)
P (|X − E(X)| ≥ z) ≤ .
z2

Proof. First write  

P (|X − E(X)| ≥ z) = P (X − E(X))2 ≥ z 2 .
Chapter 5. First and second moment methods 41

Now (X − E(X))2 is a non-negative random variable, and the result follows by applying Markov’s
inequality to that random variable noting that E (X − E(X))2 = Var(X).

 Intuitively, a random variable X typically lies

p within a few standard deviations of its
expectation. Thus, if E(X) is large compared to Var(X), then X is very likely to be close
to E(X).In particular, P(X ≥ 1) is large, giving the opposite direction of the first moment
method.

5.9 Paley-Zygmund inequality

The following well-known inequality is sometimes easier to apply than Chebyshev’s. For clarity,
we use the notation E2 (X) to denote (E(X))2 .

Theorem 5.8 (Paley–Zygmund inequality). Let X ≥ 0 be a random variable with finite

variance Var(X) < ∞. Then, for any θ > 0,

(1 − θ)2 E2 (X)
P(X ≥ θE (X)) ≥ .
E (X 2 )
E2 (X)
Taking the limit as θ → 0, we obtain P (X > 0) ≥ E(X 2 )
.

Two simple corollaries are worth noting. First, setting X = Y makes the two terms equal.
Second, if Y = 1 (the constant random variable), we obtain the inequality E2 (X) ≤ E(X 2 ),
which in turn implies that Var(X) ≥ 0 for any random variable.

6 Non-examinable material.
Before proving the Paley–Zygmund inequality, we recall a fundamental tool known as the
Cauchy–Schwarz inequality, stated here in the form for random variables.

Theorem p5.9 (Cauchy–Schwarz inequality). Let X and Y be random variables. Then,

E (XY ) ≤ E(X 2 ) E(Y 2 ).

We are now ready to prove the Paley–Zygmund inequality.

Proof of Theorem 5.8. Write

E (X) = E (X1 (X < θE (X))) + E (X1 (X ≥ θE (X))) .

The first term is at most

E (X1 (X < θE (X))) ≤ θE(X)P (X < θE (X)) ≤ θE(X).

For the second term, we apply Cauchy-Schwarz:

p
E (X1 (X ≥ θE (X))) ≤ E (X 2 ) P (X ≥ θE (X)).

Thus, p p
E (X) ≤ θE (X) + E (X 2 ) P(X ≥ θE (X)).
42 Chapter 5. First and second moment methods

Rearranging gives p p
(1 − θ)E (X) ≤ E (X 2 ) P(X ≥ θE (X)).
Squaring both sides and reorganizing we obtain

(1 − θ)2 E2 (X)
P(X ≥ θE (X)) ≥ .
E (X 2 )

Since the above works for all θ > 0, we can take the limit in both sides as θ → ∞.

What does Theorem 5.8 tell us? In essence, it says that if E(X) is large and Var(X) is relatively
small (for instance, at most CE2 (X) for some constant C) then
E2 (X) 1
P (X > 0) ≥ 2
≥ .
(C + 1)E (X) C +1
In particular, this gives a positive lower bound on the probability that X is at least a constant
fraction of its expectation.

5.10 Revisiting the balls into bins problem

We have m bins and n balls, and each ball is placed independently into a uniformly chosen bin.
If m ≫ n2 as n → ∞, the first moment method shows that a.a.s. no bin contains more than one
ball. But is the threshold n2 sharp? If m ≪ n2 , is there a bin with more than one ball a.a.s.?
Let X be the number of pairs of balls that end up in the same bin. We can write it as a sum of
indicators: X
X= Ij,k ,
j̸=k∈[n]

where Ij,k is the indicator random variable that balls j and k fall into the same bin. Then,
n


X X 1
2
E(X) = E(Ij,k ) = = .
m m
j̸=k∈[n] j̸=k∈[n]

Thus, if m ≪ n2 , we have E(X) → ∞, as desired.

We now compute the second moment. To help us not to get confused with the fact that Ij,k
has two indices, let P denote the set of pairs P = {(j, k) : j < k, j ∈ [n], k ∈ [n]}. Then, for a
pair p = (j, k) ∈ P , write Ip for Ij,k . We also order the pairs according to the some arbitrary
ordering, so that given two pairs p, p′ either p′ < p or p′ > p. With this,
 2
X X X X X
X2 =  Ip  = Ip2 + 2 Ip Ip′ . = Ip + 2 Ip Ip′ ,
p∈P p∈P p<p′ p∈P p<p′

where Ip2 = Ip because Ip ∈ {0, 1}. The second sum is over pairs of pairs p, p′ such that p < p′ .
So each pair of pairs is counted exactly once, justifying the number 2 appearing before the sum.
Then X X X
E(X 2 ) = E(Ip ) + E(Ip Ip′ ) = E(X) + E(Ip Ip′ ).
p∈P p<p′ p<p′

For the cross term E(Ip Ip′ ), there are two cases:
• Disjoint tuples. If the pairs p and p′ have no element in common, then events are independent,
so
1
E(Ip Ip′ ) = E(Ip )E(Ip′ ) = 2 .
m
Chapter 5. First and second moment methods 43

• Non-disjoint tuples. If p and p′ have one ball in common, then p ∪ p′ is a set of three balls
and all need to fall inside the same bin. There are m possible bin, so the probability that all
three go into the same bin is
m 1
E(Ij,k Ij,k′ ) = 3 = 2 .
m m
Putting everything together, we obtain
 
2
X 1 |P | 1
E(X ) = E(X) + 2 2
= E(X) + 2 .
′
m 2 m2
p<p

n


Since |P | = 2 we get
   n
       
|P | 2 1 n n n (n + 1)(n − 2)
= = −1 = .
2 2 2 2 2 2 4

At this point, let us combine everything using the Paley–Zygmund inequality:

n 2 1


2 m2
P(X > 0) ≥ n 1

n (n+1)(n−2) 1

.
2 m + 2 2 m2

Our goal is to show that P(X > 0) goes to 1 as n → ∞ 2

2 n

when m ≪ n . To simplify the
expression, multiply numerator and denominator by m / 2 :
n


2
P(X > 0) ≥ (n+1)(n−2)
→1
m + 2

as long as m ≪ n2 . Consequently,
P(X > 0) → 1.

5.11 Revisiting the coupon collector problem

Suppose we have n coupons. We draw t coupons with replacement, uniformly at random from
the set of n coupons. Using the first moment method, we showed that a.a.s. as n → ∞ all
coupons are drawn when t = cn log n for some constant c > 1. Is n log n sharp? Can we show
that a.a.s. not all coupons are picked when c < 1? We will use the second-moment method.
Recall that 
1, if coupon i was never drawn
Xi =
0, otherwise.
and
n
X
X= Xi .
i=1

For the second moment, we get

n
X X
2
X = Xi2 + Xi Xj .
i=1 i<j

We want to get a lower bound on P(X ≥ 1). Recall that

 t
1
E(X) = n 1 − .
n
44 Chapter 5. First and second moment methods

t
Here we cannot use the upper bound 1 − n1 ≤ e−t/n since the second-moment method requires
a lower bound on E(X). There are other inequalities that we can use to obtain a lower bound
on the expression above. But, in general, for the second moment method, it is better to remain
with an equality at this point since E(Xi ) naturally appears in the calculation of the second
moment. The main thing we need to assess is that E(X) does not go to zero with n.

n
From Lemma 5.3, we know that 1 − n1 → e−1 . Therefore, for any ε > 0, there exists
n0 = n0 (ε) such that
1 n
 
1− ≥ e−1−ε .
n
Thus, for all large enough n we have
 n·t/n
1
E(X) = n 1 − ≥ ne−(1+ε)t/n = n1−(1+ε)c .
n

Since ε > 0 is arbitrary and c < 1, we chose ε so that c(1 + ε) < 1, so the above is valid for this
choice of ε for all large enough n. Consequently,

E(X) → ∞.

Now we compute the second moment of X:

X
E(X 2 ) = E(X) + 2 E (Xi Xj ) .
i<j

For the “cross terms” note that

2 t
 
E (Xi Xj ) = 1 − ,
n

since we need that each of the t draws avoids the i-th and j-th coupons. Putting things together
we have
1 t 2 t 1 t 2 t
        
2 n
E(X ) = n 1 − +2 1− ≤n 1− + n(n − 1) 1 − .
n 2 n n n

Using this and Paley-Zygmund we obtain

2t
n2 1 − n1 1
P(X > 0) ≥
t
t ≥ 2t .
n 1 − n1 + n(n − 1) 1 − n2 1
+ n(n−1) (1− n )
1 t n2 1 2t
n(1− n ) (1− n )

At this moment we
t need to see that this expression does not go to zero as n → ∞. We already
saw that n 1 − n1 → ∞ and note that n(n−1) n2
→ 1. As for the remaining term, note that

2 t 2 t 2 t




1− n 1− n 1− n
= ≤ = 1.
1 2t 2 1 t 2 t




1− n
1− n + n2 1− n

Therefore,
1
lim P(X > 0) ≥ t ≥ 1.
n→∞ (1− n2 )
limn→∞ 2t
(1− n1 )

Therefore, P(X > 0) → 1 when c < 1.

Chapter 5. First and second moment methods 45

5.12 Exercises
Exercise 5.1. Let X be a random variable such that E(X 4 ) = 10. Determine whether P(X ≥
1
10) ≤ 1000 , justifying your answer.

Exercise 5.2. Let X1 , X2 , . . . be a sequence of random variables such that Xn → C in L1 .

p
Use Markov’s inequality to show that Xn → − C.

Exercise 5.3. Let X1 , X2 , . . . be a sequence of random variables such that the following two
properties hold:
E(Xn2 )
• E2 (Xn )
→ 1 as n → ∞, and
• limn→∞ E(Xn ) > 0.
Show that P(Xn > 0) → 1 as n → ∞.

Exercise 5.4. Let X be a bounded random variable. That is, there is a value M ∈ (−∞, ∞)
−E(X)
such that P(X ≤ M ) = 1. Show that for any a < E(X) we have P(X ≤ a) ≤ MM −a .
Hint: consider the random variable Y = M − X.

Exercise 5.5. Let Gn ∼ G(n, p). We say that Gn has an isolated vertex if Gn has a vertex of
degree 0. This exercise will show that the property of having an isolated vertex for G(n, p) has
a phase transition at log(n)
n .
c log(n)
(a) Show that if p ≥ n for some constant c > 1 then Gn has no isolated vertex a.a.s.
c log(n)
(b) Show that if p ≤ n for some constant c < 1 then Gn has an isolated vertex a.a.s.

Exercise 5.6. Toss a fair coin n times, independently of one another. Let Ln be the length of
the longest consecutive sequence of heads among the n tosses.
(a) Show that for any c > 1, Ln is smaller than c log2 (n) a.a.s. as n → ∞.
(b) Show that for any c < 1, Ln is larger than c log2 (n) a.a.s. as n → ∞.

Exercise 5.7. A virus begins with a single particle at time 0 (called generation 0). At each
unit of time every particle splits into two offspring, and each offspring independently either
• does not mutate (it has exactly the same genome as its parent) with probability p, or
• mutates with probability 1 − p.
The particles present at time i ∈ {0, 1, 2, . . .} are called the particles of generation i, and the
single particle at generation 0 is referred to as the root particle. Once a mutation occurs in some
offspring particle v, all the descendants of v are considered “mutated” and no longer count as
having the same genome as the root particle.
Let Zn be the number of particles in generation n whose genome is still identical to the genome
of the root particle.
(a) Show that E(Zn ) = (2p)n .
1
(b) Use Markov’s inequality to show that if p < 2 then the genome of the root particle will
p
eventually cease to exist, that is Zn →
− 0.
1 (1−(2p)−n )
(c) Assume p > 2 and show that E(Zn2 ) = (2p)n + (2p)2n 1
2(1− 2p )
.

(d) Apply the Paley–Zygmund inequality to deduce that for p > 12 the genome of the root
particle does not cease to exist with positive probability. That is, show that limn→∞ P(Zn >
46 Chapter 5. First and second moment methods

0) > 0.

Exercise 5.8. At a conference, n identical chairs are arranged evenly around a large circular
table. In the morning session, m researchers from Team A sit down uniformly at random
on distinct chairs. Later, in the afternoon, m researchers from Team B arrive and sit down
uniformly at random on distinct chairs that are not occupied by a researcher from Team A.
Two researchers sitting in neighbouring chairs can easily start a conversation. Let X be the
number of adjacent pairs of chairs where one chair is occupied by a member of Team A and the
other by a member of Team B.
We want to determine for which team size m = m(n) we have that a conversation can start
among researchers from different teams. To do this, determine a function f (n) such that if
m ≫ f (n) we have X ≥ 1 a.a.s., and if m ≪ f (n) we have X = 0 a.a.s.

Exercise 5.9. An ant is located at a vertex a of a graph G and a food source is located at a
vertex f . The graph G is such that the vertices a and f are connected by n disjoint paths, each
of length n. Recall that the length of a path is the number of edges in the path. Below is an
illustration for n = 4:

a f

In the graph G, each edge is free with probability e−φ and blocked with probability 1 − e−φ ,
independently of all other edges, where φ = φn > 0 is a parameter that may depend on n. The
ant can reach the food source only by traversing edges that are free.
Determine a function fn of n such that, as n → ∞,
• if φ ≪ fn , the ant can reach the food source a.a.s.;
• if φ ≫ fn , the ant cannot reach the food source a.a.s.

Exercise 5.10. Suppose we have a sequence of graphs G1 , G2 , . . . where Gn = (Vn , En ) with

n = |Vn |. For each n, independently sample a uniform random permutation π of Vn and order the
vertices according to this permutation. Let Fn be the event that there exists an edge {u, v} ∈ En
such that u and v are adjacent in the permutation. Let wn = v∈Vn dGn2 (v) be the number of
P

wedges in Gn (i.e., the number of triples {u, v, x} such that {u, v} , {v, x} ∈ En ). Assume that
limn→∞ |E n| wn
|Vn | = ∞ and limn→∞ |En |2 = 0.

Use the second-moment method to show that as n → ∞ we have P (Fn ) → 1.

Exercises from the tutorial sheet

Exercise 5.11. This exercise is meant to show that Markov’s inequality cannot be improved
in general.
Chapter 5. First and second moment methods 47

Let X be a non-negative random variable. Show that there is a probability distribution for X
so that
1
P (X ≥ 2E(X)) = .
2
Exercise
Pn 5.12. Let X1 , X2 , . . . , Xn be i.i.d. Bernoulli(1/2) random variables. Let Sn =
X
i=1 i .
(a) Use Markov’s inequality to obtain a upper bound on P Sn ≥ 3n


4 .
(b) Use Chebyshev’s inequality to obtain a upper bound on P Sn ≥ 3n ∪ Sn ≤ 14 .
 

4

Exercise 5.13. Let Gn ∼ G(n, p) and denote Gn = (Vn , En ). Let Tn be the number of triangles
in Gn ; that is, Tn is the number of triplets u, v, w ∈ Vn such that {u, v}, {u, w} and {v, w} all
belong to En . A triangle is also called a 3-clique.
(a) Show that if p ≪ n−1 then Gn has no triangle a.a.s.
(b) Show that if p ≫ n−1 then Gn has at least one triangle a.a.s.

Exercise 5.14. This exercises revisits the random procedure we did to obtain a lower bound
on the maximum cut of a graph via the probabilistic method.
Let G = (V, E) be any graph with m = |E| edges. Consider the following randomized procedure
to construct random sets of vertices S1 , S2 , . . .: place each vertex of V independently into S1
with probability 1/2, and let X1 = |∂S1 | be the number of edges crossing the cut S1 . Repeat this
procedure k times independently, obtaining X1 , X2 , . . . , Xk , and let Mk = max{X1 , . . . , Xk } be
the largest cut found.
(a) Show that E (X) = m/2 and Var (X) = m/4.
(b) Use Chebyshev’s inequality to prove that for every t > 0,
m
P (X1 ≥ m/2 + t) ≤ .
4t2

(c) Deduce that

km
P (M ≥ m/2 + t) ≤ .
4t2
(d) Conclude that for any fixed α > 0 (independent of m), if k ≪ m then

P M ≥ 12 + α m → 0,

so repeating the algorithm a “sublinear” number of times cannot improve much beyond the
expected value m/2 by any constant fraction.
Chapter 6

Chernoff bound

6.1 Going beyond first and second moments

Chebyshev’s inequality and Paley–Zygmund show that a random variable is concentrated around
its expectation. These inequalities are very general: there is no need to know the distribution of
X, and when X can be written as a sum of indicators, there is no need to assume the indicators
are independent. The only thing needed is to obtain an upper bound for Var (X).
Summarizing, if X is a random variable, then Chebyshev’s inequality says that

Var (X)
P (|X − E (X)| ≥ ε E (X)) ≤ ,
ε2 (E (X))2

which goes to zero whenever Var (X) ≪ (E (X))2 .

Now we show that one can do better when we know a bit more about X; in particular, when X
has an exponential moment. This method is called the Chernoff bound.

6.2 Chernoff bound: upper tail

The idea is very simple. Let X be a random variable and suppose we want to show that X is
concentrated around its mean. For example, we may want to show that the probability that X
deviates much from E (X) is small (because E (X) is large). The crucial idea is to write
 
P (X ≥ (1 + ε)E (X)) = P eθX ≥ eθ(1+ε)E(X) ,

which holds for every θ ∈ R+ . Note that eθX is a nonnegative random variable, so we are set
up to apply Markov’s inequality:
   
P (X ≥ (1 + ε)E (X)) = P eθX ≥ eθ(1+ε)E(X) ≤ e−θ(1+ε)E(X) E eθX .

Since this bound holds for every θ > 0, we may optimize over θ to get as good a bound as
possible:  
P (X ≥ (1 + ε)E (X)) ≤ inf E eθX e−θ(1+ε)E(X) .
θ>0

θX increases with θ, whereas e−θ(1+ε)E(X) decreases; the optimal value of θ

Heuristically, E e
will balance the two terms.

48
Chapter 6. Chernoff bound 49

Theorem 6.1 (Chernoff bound for Bernoulli: upper tail). Let X1 , X2 , . . . , Xn beP
independent
Bernoulli random variables (not necessarily identically distributed). Let Sn = ni=1 Xi and
1 Pn
p = n i=1 E (Xi ). Then, for any λ > np,
     
λ
P (Sn ≥ λ) ≤ exp −λ log − 1 − np .
np

Setting λ = (1 + ε)np gives

np
eε

P (Sn ≥ (1 + ε)np) ≤ .
(1 + ε)1+ε

A simplified and commonly more useful bound is

 2 
ε np
P (Sn ≥ (1 + ε)np) ≤ exp − .
2+ε

Proof. For any θ > 0 we have

 
P (X ≥ λ) = P eθX ≥ eθλ
 
≤ e−θλ E eθX
n
Y  
= e−θλ E eθXi ,
i=1

where the last step follows by independence of Xi ’s. If we know the moment generating function
of each Xi we can compute the product; otherwise we may bound it and then choose the value
of θ that optimizes

(i.e., minimizes) the bound. Since the Xi are Bernoulli, if pi = E(Xi ) we
have that E eθXi = pi eθ + (1 − pi ). Then,
n 
Y 
−θλ
P (X ≥ λ) ≤ e pi eθ + (1 − pi )
i=1
n  
Y  
−θλ
=e pi eθ − 1 + 1
i=1
n
!
X  
≤ exp −θλ + pi eθ − 1
i=1
  
= exp −θλ + np eθ − 1 . (6.2.1)

λ
Note that we used Lemma 5.2 in the second inequality. The bound is optimized when eθ = np .
First it is important to check that this bound is feasible, and in fact it is since λ > np. This is
natural, since we should not get a good decay on the probability P(X ≥ λ) when λ < E(X) = np.
λ
How do you show that the bound is optmized when eθ = np ? Well, you need to differentiate
θ


−θλ + np e − 1 and see where the minimum of this expression is as a function of θ. That is,
we first computer
d   
−θλ + np eθ − 1 = −λ + npeθ
dθ
and then noticed that the above is zero when

npeθ = λ.
50 Chapter 6. Chernoff bound

You must also notice that this is indeed a minimum of the function; a quick second derivative
check completes this part of the argument:

d2  
θ

−θλ + np e − 1 = npeθ > 0.
dθ2
λ
So, indeed, eθ = np is a minimum.
Now replacing this value of θ into (6.2.1) we obtain
     
λ
P (X ≥ λ) ≤ exp −λ log − 1 − np .
np

For λ = (1 + ε)np this becomes

P (X ≥ (1 + ε)np) ≤ exp (−(1 + ε)np log(1 + ε) + npε)

np
eε

= .
(1 + ε)1+ε

You are expected to understand the proof until this point. In applications, the bound above is
a bit cumbersome to use. So, in practice, the bound below is more easily applicable:
 2 
ε np
P (X ≥ (1 + ε)np) ≤ exp − .
2+ε

The derivation of this final step is beyond the scope of this module; it goes by analyzing carefully
the function log(1 + ε).

ž Instructor’s Note. In the assessment, you will not be required to remember a

Chernoff bound (so you don’t need to remember the expressions in Theorem 6.1 and 6.2).
However, you may be asked to derive a Chernoff bound or to apply a Chernoff bound that
is already given to you in the assessment.

6.3 Chernoff bound: lower tail

For the lower tail, we apply the same trick to the random variable e−θX , which is decreasing in
X, thereby enabling Markov’s inequality. For any θ > 0,
   
P (X ≤ (1 − ε)E (X)) = P e−θX ≥ e−θ(1−ε)E(X) ≤ E e−θX eθ(1−ε)E(X) .

Theorem 6.2 (Chernoff bound for Bernoulli:

Pn lower tail). Let1XP
1 , X2 , . . . , Xn be independent
n
Bernoulli random variables. Let Sn = i=1 Xi and p = n i=1 E (Xi ). Then, for any
ε ∈ (0, 1),  2 
ε np
P (Sn ≤ (1 − ε)np) ≤ exp − .
2

Proof. Repeat the argument leading to (6.2.1), replacing θ by −θ and optimizing at e−θ = λ
np
(now λ < np, where λ = (1 − ε)np):
     
λ
P (X ≤ λ) ≤ exp −λ log − 1 − np .
np
Chapter 6. Chernoff bound 51

Now you set λ = (1 − ε)np. As with the upper tail, you should be able to get up to this point,
but the bound you will obtain is difficult to work with in applications. To turn it into a more
useful bound, you apply inequalities such as (1 − ε) log(1 − ε) ≥ −ε + ε2 /2, which you do not
need to remember for this module. At the end, you obtain the following more useful bound:
 2 
ε np
P (X ≤ (1 − ε)np) ≤ exp − .
2

Theorems 6.1 and 6.2 together give the following corollary.

Corollary 6.3 (Chernoff bound for Bernoulli:
Pn two-sided). Let X1 , X2 , . . . , Xn be independent
1 Pn
Bernoulli random variables. Let Sn = i=1 Xi and p = n i=1 E (Xi ). Then, for any ε ∈ (0, 1),
 2 
ε np
P (|Sn − np| ≥ εnp) ≤ 2 exp − .
3

6.4 Example: random walk on Z

Consider a random walk on Z: a particle that starts at S0 = 0 and, at each step, with probability
p ≥ 1/2 moves one unit to the right, and with probability 1 − p moves one unit to the left. Let
Xi ∈ {−1, 1} be the random variable encoding the ith step: Xi = −1 if the ith step is to the
left and Xi = 1 if it is to the right. Define
t
X
St = St−1 + Xt = Xi ,
i=1

so St is the position of the particle at time t (i.e., after t steps).

Let
ρ = E (Xi ) = p − (1 − p) = 2p − 1 ∈ [0, 1].
Then E (St ) = tρ for every t because
E (St ) = E (X1 + X2 + · · · + Xt ) = tρ.

We could derive a Chernoff bound directly for St , since its distribution is known, but for simplic-
ity (and to practice the method) we reduce to Bernoulli variables to use Theorems 6.1 and 6.2.
1+Xi
Note that if we set Yi = 2 , then Yi ∼ Bernoulli(p). Thus
t
X 1 + Xi t + St t + E (St ) t + tρ t(1 + ρ)
Y = = , µ = E (Y ) = = = .
2 2 2 2 2
i=1

Using the Bernoulli Chernoff bounds (Corollary 6.3), for any δ ∈ (0, 1),
 2 
ε µ
P (|Y − µ| ≥ εµ) ≤ 2 exp − .
3
From this we obtain concentration of St around tρ by writing, for any δ ∈ (0, 1),
 
|St − tρ| δtρ
P (|St − tρ| ≥ δtρ) = P ≥
2 2
 
δtρ
= P |Y − µ| ≥ µ
2µ
   
δρ
= P |Y − µ| ≥ µ .
1+ρ
52 Chapter 6. Chernoff bound

δρ δρ
Note that 1+ρ ∈ (0, 1). Plugging this into the Chernoff bound above (with ε = 1+ρ ) yields

δ 2 ρ2 µ δ 2 ρ2 t
   
P (|St − tρ| ≥ δtρ) ≤ 2 exp − = 2 exp − .
3(1 + ρ)2 6(1 + ρ)

 This inequality shows that after t steps, St is concentrated around tρ. For any fixed
δ > 0, the probability that the random walk lies outside ((1 − δ)E(St ), (1 + δ)E(St )) decays
exponentially fast in t. If δ decreases with t, for example δ = √1t , the exponential term
δ 2 ρ2 t ρ2 √
becomes 6(1+ρ) = 6(1+ρ) , independent of t. This is expected since δtρ scales as tρ, match-
ing the growth of the standard deviation of St , so the probability of leaving the interval
((1 − δ)E(St ), (1 + δ)E(St )) remains bounded away from zero. The Chernoff bound thus
reveals that whenever δ ≫ √1t , the probability already decays exponentially fast with δ 2 t.

6.5 Largest degree in G(n, p)

Let Gn = (Vn , En ) ∼ G(n, p) and let ∆n = maxu∈Vn dGn (u) be the largest degree of a vertex of
Gn . We want to show that ∆n is of order smaller than log n.
Proposition 6.4. Let p = λ/n for some constant λ > 0. Then, a.a.s. we have ∆n ≪ log n.

Proof. Let K be any value. If ∆n ≥ K then there exists u ∈ Vn such that dGn (u) ≥ K. So we
can write X
P (∆n ≥ K) ≤ P (dGn (u) ≥ K) .
u∈Vn

Note that dGn (u) ∼ Binomial(n − 1, p). Using the Chernoff Bound (first inequality in Theo-
rem 6.1) gives     
K
P (degGn (u) ≥ K) ≤ exp −K log −1 .
(n − 1)p
Note that the right-hand side above does not depend on u. So we obtain
    
K
P (∆n ≥ K) ≤ n exp −K log −1 .
(n − 1)p

So we need to take K large enough so that the bound above goes to 0as n →∞.  For this, it
suffices to set K so that K ≫ log log n since for such a K we obtain K log (n−1)p − 1 ≥ K log
log n K
2
K

for all large enough n. Moreover, we need K ≪ log n so that P (∆n ≥ K) → 0 gives that
∆n ≪ log n. Therefore, we need to set K to be much larger than logloglogn n and much smaller than
log n; for example, set K = √ log n and we obtain for all large enough n that
log log n

  
  log n log √ log n
log n log log n
P ∆n ≥ √ ≤ n exp − √ 
log log n 2 log log n
  
log n
log √log log n
= exp log n − log n √ 
2 log log n

→0 as n → ∞.
Chapter 6. Chernoff bound 53

Suppose we have a sequence of graphs G1 , G2 , . . . where Gn = (Vn , En ) with n = |Vn |. For each
n, independently sample a uniform random permutation π of Vn and order the vertices according
to this permutation. Let Fn be the event that there exists an edge {u, v} ∈ En such that u and v
are adjacent in the permutation. Let wn = v∈Vn dGn2 (v) be the number of wedges in Gn (i.e.,
P

|En |
the number of triples {u, v, x} such that {u, v} , {v, x} ∈ En ). Assume that limn→∞ |Vn | =∞
and limn→∞ |Ewnn|2 = 0.
Use the second-moment method to show that as n → ∞ we have P (Fn ) → 1.

6.6 Exercises
2
Exercise 6.1. Let X ∼ N (0, 1). Using E eθX = eθ /2 , show that for t > 0,

2 /2
P(X ≥ t) ≤ e−t .

ExerciseP6.2. Let X1 , . . . , Xn be independent exponential random variables with rate 1, and

let Sn = i Xi .
1
(a) Show that E eθXi = 1−θ


for θ < 1.
(b) For any ε > 0, derive the Chernoff bound

P(Sn ≥ (1 + ε)n) ≤ exp(−n(ε − log(1 + ε))) .

Exercise 6.3. Let n, m be integers, and consider the random graph G = (V, E) where V =
{1, 2, . . . , n} is the vertex set, and E is a
random set of m edges chosen independently and
uniformly with replacement among the n2 possible unordered pairs of vertices. Thus, multiple
edges between two vertices are allowed. Assume that m = Cn for some fixed constant C > 0,
and let I be the number of isolated vertices in G (that is, the number of vertices of degree 0).
(a) Compute E (I).
(b) Show that a.a.s. the maximum degree of G is at most log n.

Exercise 6.4. Let G ∼ G(n, p), and let A, B ⊆ V (G) be two disjoint subsets of size k ≥ 1. Let
X(A, B) denote the number of edges with one endpoint in A and one in B.
(a) Use the Chernoff bound to prove that, for any fixed A, B,
 2 2
2 2

ε pk
P |X(A, B) − pk | ≥ εpk ≤ 2 exp − .
3

(b) Apply a union bound over all possible pairs of disjoint k-sets to show that a.a.s. all pairs
A, B satisfy |X(A, B) − pk 2 | ≤ εpk 2 , provided pk ≫ log n as n → ∞.

k
Hint: you can apply the inequality nk ≤ ne


k which holds for all n ≥ k > 0.

Exercise 6.5. A winery has 20,000 vines. On each vine, the number of grape clusters is an
independent Poisson (100) random variable, and conditioned on the number of clusters, each
cluster independently contains a Poisson (50) number of grapes. During the production, to
reduce the density of grapes and increase the quality of the final product, each grape cluster
is cut and discarded with probability 1/2, independently of everything else. We call this the
pruning step. When a grape cluster is discarded during pruning, all the grapes in that cluster
are discarded. For each grape cluster that was not discarded during pruning, each individual
grape fails to mature and is also discarded with probability 1/5, independently. This is called
the maturity check step.
54 Chapter 6. Chernoff bound

(a) Let X be Poisson(λ). Compute the moment generating function of X.

(b) Given X as above and for any ε ∈ (0, 1), derive the Chernoff bounds
λ
eε

P(X ≥ (1 + ε)λ) ≤ .
(1 + ε)1+ε

and λ
e−ε

P(X ≤ (1 − ε)λ) ≤ .
(1 − ε)1−ε

(c) Show that after the pruning step, the number of remaining grape cluster in a given vine is
Poisson(50).
(d) Show that, given a grape cluster that remained after the pruning step, the number of grapes
in that cluster that were not discarded during the maturity check is Poisson(25).
(e) Let C be the total number of grape clusters in the winery after pruning. Show that
C ∼ Poisson(1,000,000).
(f) Consider the random variable C from the previous item. Show that P(C < 800,000) ≤
e−10,000 .
e−ε −ε2 /2 .
Hint: You can use that for any ε ∈ (0, 1) we have (1−ε)1−ε ≤ e

(g) ( ) Consider the random variable C from the previous two items and let G be the
total number of usable grapes after the pruning and maturity check steps. Show that
P(G ≤ 16,000,000 | C ≥ 800,000) ≤ e−400,000 .
(h) Suppose that the winery needs at least 16,000,000 fully matured grapes to produce its usual
amount of wine. Use the result from the previous two parts to show that the probability
that the winery does not have enough grapes to produce its usual amount of wine is at
most e−10,000 − e−400,000 .

Exercises from the tutorial sheet

Exercise 6.6. Given a parameter λP> 0, let X1 , X2 , . . . be i.i.d. Exponential(λ) random vari-
ables. For any n ∈ Z+ , define Sn = ni=1 Xi .
(a) Determine E(Sn ).
(b) Show that for any δ > 0 we have
 
(1 + δ)n
P Sn ≥ ≤ exp (−n (δ − log(1 + δ))) .
λ

(c) Show that for any δ > 0 we have

 
(1 − δ)n
P Sn ≤ ≤ exp (−n (−δ − log(1 − δ))) .
λ

Exercise 6.7. Let G ∼ G 100, 91 , and let X be the total number of edges in G.

Use the Chernoff bound to show that

1
P(500 ≤ X ≤ 600) ≥ .
2
Exercise 6.8. Throw m = n log n balls independently and uniformly at random into n bins.
For a fixed bin i, let Xi be the number of balls in bin i, and let Mn = maxi∈[n] Xi be the
maximum load of a bin.
Chapter 6. Chernoff bound 55

(a) Show that

2 /(2+ε)
P(Xi ≥ (1 + ε) log n) ≤ n−ε .

(b) Deduce that, for any c > 3, a.a.s. as n → ∞ we have Mn ≤ c log n.

Chapter 7

Martingale

7.1 Random walk on Z

We consider a random walk particle that starts from the origin and at each step jumps one unit
to the right or to the [Link] S0 = 0, and let X1 , X2 , . . . be i.i.d. random variables in {−1, 1}
such that
P(X1 = 1) = p and P(X1 = −1) = 1 − p.

The position of the walker at step t ∈ Z+ is

t
X
St = St−1 + Xt = S0 + Xi .
i=1

We showed via Chernoff bound that for large time t the random walk is concentrated around
tρ, where ρ = E(X1 ) = 2p − 1. We also showed that the probability that |St − tρ| > εtρ decays
exponentially fast with tρ.
A walker that jumps one unit to the right or to the left is called a simple random walk. If
p = 1/2 the random walk is called unbiased, while it is biased if p ̸= 1/2.

7.2 σ-algebra

Definition 7.1 (σ-algebra generated by discrete random variables). Given a sequence of

discrete random variables X1 , . . . , Xt , the σ-algebra generated by X1 , . . . , Xt , which is denoted
by σ(X1 , X2 , . . . , Xt ), is the collection of all events that depend only on X1 , . . . , Xt .
More formally, if Ωt denotes the sample space of X1 , . . . , Xt , the σ-algebra σ(X1 , X2 , . . . , Xt )
is the set of all subsets of Ωt .

The definition of σ-algebra is more general, and in the case of continuous random variables it is
more involved. However, the definition above will suffice in this module.
The concept of σ-algebra is a way to model the information revealed by a set of random vari-
ables.

56
Chapter 7. Martingale 57

Definition 7.2 (Measurability). Given random variables X1 , X2 , . . . , Xt and the correspond-

ing σ-algebra F = σ(X1 , X2 , . . . , Xt ), we say that a random variable Y is F-measurable (or
is measurable with respect to F) if Y is a deterministic function of X1 , X2 , . . . , Xt . In other
words, Y depends only on X1 , X2 , . . . , Xt .
We say that an event E is F-measurable if the indicator random variable 1(E) is F-measurable.

Example: for the example of random walk on Z, the three random variables below are measurable
with respect to σ(X1 , X2 , . . . , Xt ):
• St ,
• max {Si : i ∈ {0, 1, 2, . . . , t}},
• ti=1 {Si = 0}.
S

7.3 Filtration

Definition 7.3 (Filtration). A filtration is an increasing sequence of σ-algebras F0 ⊆ F1 ⊆

F2 ⊆ · · · . For example, given a sequence of random variables X1 , X2 , . . ., we have the filtration
Ft = σ(X1 , . . . , Xt ), for t ∈ {1, 2, . . .}.

In our simple random walk example, Ft contains everything we know after the first t steps, such
as St and any function of X1 , . . . , Xt . So having a filtration is a way of revealing more and more
about the random walk.

Definition 7.4 (Adapted sequence). Given a filtration {Ft }t≥0 , a sequence of random vari-
ables Y1 , Y2 , . . . , is said to be adapted to (Ft ) if each Yt is measurable with respect to Ft .

Example: four sequences adapted to the filtration Ft = σ(X1 , X2 , . . . , Xt ):

• {St }t
• {max {Si : i ∈ {01, 2, . . . , t}}}t ,
 St
• i=1 {Si = 0} t
• Given a ∈ Z, the sequence {1 (τa ≤ t)}t , where τa = inf {k ≥ 0 : Sk = a} is the hitting time of
a.

7.4 Conditional expectation

Recall that given a random variable Y and an event F , the conditional expectation is E(Y |
1{F })
F ) = E(YP(F ) . For example: E(St ) = tρ and E(St | S1 = 1) = 1 + (t − 1)ρ.

What if we want to know the expectation of St conditioning on S1 (as a random variable)?

58 Chapter 7. Martingale

Definition 7.5 (Conditioning with respect to random variables). Let X1 , X2 , . . . , Xt be

discrete random variables on Ωt , and let Y be another random variable. Define E(Y |
X1 , . . . , Xt ) as a new random variable which for each realization (x1 , . . . , xt ) ∈ Ωt takes the
value E(Y | X1 = x1 , . . . , Xt = xt ) with probability P (X1 = x1 , X2 = x2 , . . . , Xt = xt ).Note
that E(Y | X1 , X2 , . . . , Xt ) depends only on X1 , X2 , . . . , Xt .

In words: it is the expected value of Y after observing X1 , X2 , . . . , Xt . If Ft = σ(X1 , X2 , . . . , Xt )

we also write E(Y | Ft ) instead of E(Y | X1 , X2 , . . . , Xt ).

7.4.1. Properties of conditional expectation

The conditional expectation E(Y | X1 , . . . , Xt ) behaves like an ordinary expectation, except that
it depends on the information given by X1 , . . . , Xt .

Theorem 7.6 (Properties of conditional expectation). Let Y, Z, X1 , X2 , . . . , Xt be random

variables. The conditional expectation satisfies the following properties (the equalities below
are equalities of probability distributions):
(i) Linearity: for any constants a, b ∈ R,
d
E(aY + bZ | X1 , . . . , Xt ) = a E(Y | X1 , . . . , Xt ) + b E(Z | X1 , . . . , Xt )

(ii) If Z is measurable with respect to X1 , . . . , Xt , then

d
E(ZY | X1 , . . . , Xt ) = ZE(Y | X1 , . . . , Xt )

(iii) If Y is independent of (X1 , . . . , Xt ), then E(Y | X1 , . . . , Xt ) = E(Y ).

(iv) Tower property: for s < t,

d
E E(Y | X1 , . . . , Xt ) | X1 , . . . , Xs = E(Y | X1 , . . . , Xs ).

Proof. For the first three items, it is enough to note that the equalities holds for each possible
values x1 , . . . , xt of the random variables X1 , X2 , . . . , Xt . Therefore, the equality should hold for
the random variable E(· | X1 , . . . , Xt ).
We now prove the last item. Assume that X1 , . . . , Xt are discrete random variables (otherwise
replace sums by integrals). Then, for any x1 , . . . , xs we have

E (E(Y | X1 , . . . , Xt ) | X1 = x1 , . . . , Xs = xs )
X
= E(Y | X1 = x1 , . . . , Xt = xt )P (Xs+1 = xs+1 , . . . , Xt = xt | X1 = x1 , . . . , Xs = xs )
xs+1 ,...,xt

= E(Y | X1 = x1 , . . . , Xs = xs ).

Since the above holds for all x1 , . . . , xs , then

E (E(Y | X1 , . . . , Xt ) | X1 , . . . , Xs ) = E (Y | X1 , . . . , Xs ) .

What are the values of E (E (Y | X1 , X2 , . . . , Xt )) and E(St | X1 )?

Chapter 7. Martingale 59

7.5 Martingales

Definition 7.7 (Martingale). Let (Ft )t≥0 be a filtration. A sequence of random variables
(Mt )t≥0 is a martingale with respect to (Ft ) if all the following hold:
(i) E(|Mt |) < ∞ for all t;
(ii) (Mt ) is adapted to (Ft ), that is Mt is measurable with respect to Ft ;
(iii) E(Mt+1 | Ft ) = Mt for all t.
If (i) and (ii) above hold and E(Mt+1 | Ft ) ≤ Mt , we say that (Mt ) is a supermartingale. If
(i) and (ii) above hold and E(Mt+1 | Ft ) ≥ Mt , we say that (Mt ) is a submartingale.

Let Mt be a martingale adapted to a filtration Ft , where M0 is some deterministic value a.

What is E(Mt )? By the tower property and then the martingale property, E(Mt ) = E(E(Mt |
Ft−1 )) = E(Mt−1 ). Therefore, by induction E(Mt ) = E(M0 ) = a. If {Mt }t is a submartingale
(or a supermartingale) then E(Mt ) ≥ E(M0 ) = a (or E(Mt ) ≤ E(M0 ) = a).

7.5.1. Examples of martingales

We use our simple random walk example to produce examples of martingales. Let Ft =
σ(X1 , . . . , Xt ) be the filtration. The following are martingales:
• Mt = St − tρ.
• Mt = (St − ρt)2 − (1 − ρ2 )t.
 St
• Mt = 1−pp .

7.6 Stopping times

Definition 7.8 (Stopping time). Let (Ft )t≥0 be a filtration. A random time τ ∈ Z+ ∪ {∞}
is a stopping time if for every t ≥ 0, the event {τ ≤ t} belongs to Ft .

In words: at time t, we can tell whether the stopping time has already occurred, using only the
information revealed by Ft .
The following are examples of stopping times.
• The hitting time τa = inf {t ≥ 0 : St = a}.
• The first return time τ0+ = inf {t ≥ 1 : St = 0}.
• The first exit time, inf {t ≥ 0 : St ̸∈ [−10, 10]}.
The last visit to the origin sup {t ≥ 0 : St = 0} is not a stopping time.

Definition 7.9 (Stopped process). If M1 , M2 , . . . is a sequence of random variables and τ is

a stopping time with respect to a filtration {Ft }t such that M1 , . . . , Mt are Ft -measurable,
then
Zt = Mt∧τ is called a stopped process,
where t ∧ τ is a shorthand for min {t, τ }.

Note that Zt is equal to Mt for all t ∈ {0, 1, 2, . . . , τ } and then, from time τ onwards Zt remains
stopped at Mτ ; that is, Zt = Mτ for all t > τ .
60 Chapter 7. Martingale

Theorem 7.10 (Stopped martingales are martingales). Let {Mt }t be a martingale and τ be
a stopping time with respect to a filtration {Ft }t . Define Zt = Mt∧τ for all t. Then Zt is a
martingale with respect to {Ft }t .

Proof. Note that Zt = Mt 1 (τ ≥ t) + Mτ 1 (τ ≤ t − 1). We first check property (i). Notice that
Mt is measurable with respect to Ft . Since τ is a stopping time, both indicator functions are
measurable with respect to Ft .
For property (ii), note that

E(|Zt |) ≤ sup {E(|Mi |) : i ∈ {0, 1, 2, . . . , t}} < ∞,

since E(|Mi |) < ∞ for all i and the supremum is taken over a finite number of elements.
Finally, for property (iii) we write

E (Zt+1 | Ft ) = E (Mt+1 1 (τ ≥ t + 1) | Ft ) + E (Mτ 1 (τ ≤ t) | Ft ) .

Note that {τ ≥ t + 1} ∈ Ft . For the second term, note that Mτ 1 (τ ≤ t) is equal to 0 if τ > t
and it is equal to some M1 , M2 , . . . , Mt if τ ≤ t. In particular, Mτ 1 (τ ≤ t) is measurable with
respect to Ft . Therefore

E (Zt+1 | Ft ) = 1 (τ ≥ t + 1) · E (Mt+1 | Ft ) + Mτ 1 (τ ≤ t)
= Mt 1 (τ ≥ t + 1) + Mτ 1 (τ ≤ t) = Zt ,

where in the second equality we used that {Mt }t is a martingale.

7.7 Optional stopping theorem

Theorem 7.11 (Optional stopping theorem). Let {Mt }t be a martingale and τ be a stopping
time with respect to a filtration Ft . Then, E(Mτ ) = E(M0 ) if at least one of the conditions
below is satisfied:
(i) There exists a fixed K < ∞ such that |Mt | ≤ K a.s. for all t.
(ii) There exists a fixed T < ∞ such that τ ≤ T a.s.
(iii) E(τ ) < ∞ and there exists K < ∞ such that E (|Mt+1 − Mt | | Ft ) ≤ K a.s. for all t.
Moreover, if one of the three conditions above is satisfied and {Mt }t is a submartingale (or
supermartingale), then E(Mτ ) ≥ E(M0 ) (or E(Mτ ) ≤ E(M0 )).

Proof of Theorem 7.11 for bounded stopping times. Let τ take values in {0, 1, . . . , T } for some
fixed T . Define the stopped process Mt′ = Mt∧τ . By Theorem 7.10, we know that Mt′ is a
martingale. Therefore, E(Mt′ ) = E(M0′ ) = M0 for all t. If we then set t = T , we note that
τ ∧ T = τ , which gives
M0 = E(MT′ ) = E(MT ∧τ ) = E(Mτ ).

7.8 Random walk and martingales

7.8.1. Unbiased random walk
In this part we will assume that p = 1/2.
Chapter 7. Martingale 61

Proposition 7.12. Let p = 1/2 and {St }t be an unbiased simple random walk. For any a ∈ Z
recall that τa = inf {t ≥ 0 : St = a}. Then,

b
P (τa < τ−b ) = .
a+b
Proof. Let τ−b,a = τa ∧ τ−b . {St }t is a martingale for the filtration Ft = σ(X1 , X2 , . . . , Xt ), and
τ−b,a is a stopping time. We need to show that we can apply optional stopping. First τ−b,a
is not bounded (so regularity condition (i) does not hold), but we can see that the regularity
condition (ii) is satisfied because St − St−1 ∈ {−1, 1}, so it is bounded, and E(τ−b,a ) < ∞. The
reason for this second fact is that if St ∈ (−b, a) and the walker takes b + a consecutive steps to
the right, then St+a+b ̸∈ (−b, a). The probability that such event happens is 2−a−b . If Y is a
geometric random variable with parameter 2−a−b then E(τ−b,a ) ≤ E ((a + b)Y ) = (a + b)E(Y ) =
(a + b)2a+b < ∞.
We now apply the Optional Stopping Theorem:

E(Sτ−b,a ) = E(S0 ) = 0.

Since Sτ−b,a takes only the two values +a and −b,

E(Sτ−b,a ) = a P(Sτ−b,a = a) − b P(Sτ−b,a = −b) = 0.

With P(Sτ−b,a = a) = ρ and P(Sτ−b,a = −b) = 1 − ρ, we get aρ − b(1 − ρ) = 0 which implies

b
ρ = a+b .
Proposition 7.13. Let p = 1/2 and, for any a, b ∈ Z+ , define τ−b,a = τa ∧ τ−b the first hitting
time of the set {−b, a}. Then,
E (τ−b,a ) = ab.

Proof. Consider the martingale

Mt = St2 − t.
Note that Mt − Mt−1 = St2 − t − St−1 2 2
+ t − 1 = St2 − St−1 − 1 which is not bounded. So the
regularity conditions (i) and (ii) do not hold. So, let’s check condition (iii). Write τ = τ−b,a .
We have
2


sup E (|Mt∧τ |) ≤ sup E St∧τ + E (t ∧ τ )
t t
≤ sup max a2 , b2 + E (τ ) < ∞,

t

where the last step follows since St ∈ [−b, a] for t ≤ τ and E (τ ) was proved in the previous
example.
We can then apply the Optional Stopping Theorem, which gives

E(Mτ ) = E(M0 ) = 0.

Hence
E(Sτ2 ) − E(τ ) = 0 ⇒ E(τ ) = E(Sτ2 ).

Since Sτ takes the values +a and −b,

b a
E(Sτ2 ) = a2 P(Sτ = a) + b2 P(Sτ = −b) = a2 + b2 = ab.
a+b a+b
Therefore E(τ ) = ab.
62 Chapter 7. Martingale

7.8.2. Gambler’s ruin

A gambler starts with £K and plays a fair game against the [Link] each round:
• with probability 1/2 the gambler wins £1,
• with probability 1/2 the gambler loses £1.
The game ends as soon as the gambler’s capital hits 0 or £N .Let St be the gambler’s capital
after t rounds, with S0 = K.
• Question: can the gambler expect to profit from the game? Mathematically, is there a stopping
time τ such that E(Sτ ) > K?
• Define τ0 = inf {t ≥ 0 : St = 0} and τN = inf {t ≥ 0 : St = N }. Question: What is the proba-
bility that the gambler reaches £N before going bankrupt?

7.8.3. Example of wrong application of optional stopping

Consider simple random walk {St }t with p = P(X1 = 1) = 21 and Ft = σ(X1 , . . . , Xt ). Given
a ∈ Z+ , what does the optional stopping theorem give if applied to τa ?
What is wrong?

7.8.4. Biased random walk

1−p
Proposition 7.14. For p > 1/2, let β = p ∈ (0, 1). Then,
1 − βb
P (τa < τ−b ) =
1 − β a+b
and
1 − βb
 b
β − β a+b
   
1
E (τ−b,a ) = a −b ,
ρ 1 − β a+b 1 − β a+b
where ρ = 2p − 1.

 Let p = 1/2. Note that

b
P (τ−b = ∞) ≤ lim P (τa < τ−b ) = lim = 0.
a→∞ a→∞ a+b
This shows that simple random walk on Z is recurrent, meaning that it reaches any given
vertex after finitely many steps a.s. Curiously, for any b ∈ Z+ , we have

E (τ−b ) ≥ lim E (τ−b,a ) = lim ab = ∞.

a→∞ a→∞

When p > 1/2, note that

1 − βb
P (τ−b = ∞) = lim P (τa < τ−b ) = lim = 1 − β b ∈ (0, 1).
a→∞ a→∞ 1 − β a+b

Thus biased simple random walk on Z is transient: it has a positive probability of never
visiting a given vertex.

7.8.5. Other examples

Consider a (non-simple) random walk St = ti=1 Xi starting from S0 = 0 and such that Xi are
P
i.i.d. with P(Xi = −1) = 2/3 and P(Xi = 2) = 1/3. Note that E(Xi ) = 0 as in the unbiased
b
simple random walk case. We showed in class that P(τa < τ−b ) < a+b .
Chapter 7. Martingale 63

 Think of a gambling game, where at step i we get Xi pounds. Then St is the total
amount we gained or losed after t steps, and q = P(τa < τ−b ) is the probability that we
manage to get a target profit of a before losing all of our initial capital b. The example
above shows that, if the goal is to maximize q, then the unbiased simple random walk is a
better game to play.

7.9 Exercises
Exercise 7.1. Suppose we invest S0 = £2 in a risky fund. At each month t ∈ {1, 2, . . .}, one
of the following happens independently of Ft−1 :
• with probability p ∈ (0, 1) the fund goes bankrupt and our capital becomes St = 0 (and stays
0 thereafter),
• with probability 1 − p the fund grows deterministically from St−1 to St = 2St−1 .
We would like to accumulate £210 . So let

τ = inf t ≥ 0 : St ≥ £210 or St = 0 .


(a) Compute the probability that Sτ = 210 .

(b) Determine the interval of values of p such that E (Sτ ) > S0 .
Hint: the items above can be solved without martingales.
Now assume that, at each month, if the fund does not go bankrupt then instead of growing
deterministically, it doubles with probability 3/4 or halves with probability 1/4. More precisely,
for each t ≥ 1,
• with probability p we have St = 0 (and it stays 0 thereafter),
• with probability 1 − p we have
(
2St−1 , with probability 3/4,
St =
St−1 /2, with probability 1/4.

For any t, let Ft = σ (S0 , S1 , . . . , St ).

(c) Show that τ is a stopping time with respect to {Ft }t .
(d) Compute the value p⋆ such that, with respect to the filtration {Ft }t , we have that {St }t is
a martingale when p = p⋆ .
(e) For which values of p is {St }t a submartingale with respect to {Ft }t ?
(f) Determine the interval of values of p such that E (Sτ ) > S0 .

Exercise 7.2. Let {Mt }t be a submartingale and τ be a stopping time with respect to the
filtration {Ft }t . Show that if Mt′ = Mt∧τ then {Mt′ }t is a submartingale with respect to {Ft }t .

Exercise 7.3. Let X1 , X2 , . . . be i.i.d. Geometric(p) random variables, where P(Xi = k) =

(1 − p)k−1 p for k ∈ N, and define the random walk
t
X
St = (Xi − 2), S0 = 0.
i=1

1
Note that each step takes integer values in {−1, 0, 1, 2, . . .}, with mean E(Xi − 2) = p − 2.
64 Chapter 7. Martingale

(a) Show that the moment generating function of Yi := Xi − 2 exists for θ < − log(1 − p) and
is given by
  p e−θ
E eθYi = .
1 − (1 − p)eθ

(b) Determine β ̸= 1 such that E(β Yi ) = 1 when p ̸= 21 . Express β explicitly in terms of p.

(c) Using the value of β from the previous part, show that β St t is a martingale with respect


to the filtration Ft = σ(X1 , X2 , . . . , Xt ) when p ̸= 1/2.

(d) Fix integers a, b ≥ 1, and define

τa = min{t ≥ 1 : St ≥ a}, τ−b = min{t ≥ 1 : St ≤ −b}, τ−b,a = τa ∧ τ−b .

Using the martingale β St prove that for p > 1/2

1 − β −b
P(τa < τ−b ) ≤ .
β a − β −b
Exercise 7.4 ( ). During a winter business dinner, n people leave their coats at the restaurant
entrance (with no identification). At the end of the dinner, all n people come to pick up their
coats at the same time. The owner, not knowing whose coat is whose, chooses a uniformly
random permutation of the n coats and hands them out accordingly. Everyone who gets their
own coat is happy and leaves. Let L1 be the number of such people. The remaining n − L1
people return to the owner and complain. The owner then takes the remaining n − L1 coats
and, independently of everything else, chooses a uniformly random permutation of these coats
and hands them out to the n − L1 people. Let L2 be the number of people who now get their
own coat and leave; the other n − L1 − L2 again complain. The owner repeats this procedure
until everyone receives their own coat. Let ξ be the total number of rounds needed (i.e., the
smallest integer with L1 + L2 + · · · + Lξ = n).
Determine E (ξ).
Hint: compute E(L1 ) and try to come up with a martingale that allows you to use optional
stopping and obtain E(ξ).

Exercise 7.5 ( ). Let {St }t≥0 be a random walk on Z, defined by

St = X1 + X2 + · · · + Xt , S0 = 0,

where {Xi }i≥1 are i.i.d. random variables with E(Xi ) = 0 and |Xi | ≤ c for some constant c ≥ 1.
Assume further that P(X1 ̸= 0) > 0 to avoid trivial cases.
(a) Show that {St } is a martingale with respect to its natural filtration Ft = σ(X1 , . . . , Xt ).
(b) Let Mt = St2 − t E(X12 ). Show that {Mt } is a martingale.
(c) Fix a ≥ 1 and define τa = min {t : |St | ≥ a}. For each fixed integer n ≥ 1, define the
stopping time sn = τa ∧ n. Show that limn→∞ E(sn ) < ∞.
(d) Use the above to show that τa < ∞ almost surely.
Hint: note that sn ≥ n · 1 (τa = ∞) for all n ≥ 1.

Exercises from the tutorial sheet

Exercise 7.6. Throw a fair six-sided die once and let X be the number appearing on the top
face. Define the random variables
• I = 1 (X is an even number),
• J = 1 (X is a prime number),
Chapter 7. Martingale 65

• Y = X · 1 (X ∈ {2, 4}),
• Z = X · 1 (X ∈ {2, 4, 6}).
Describe the distribution or determine the value of the following quantities:
(a) E (X | I).
(b) E (I | X).
(c) E (I · J | Y ).
Now consider the sequence of σ-algebras
F1 = σ(I), F2 = σ(Z), F3 = σ(X).
(d) Is the sequence F1 , F2 , F3 a filtration?

Exercise 7.7. We invest an initial amount S0 = £1,000 in a fund whose value changes monthly
as follows. At the end of each month t ∈ {1, 2, . . .}, independently of the past,
(
(1 + ε) St−1 , with probability 1/2,
St =
(1 − ε) St−1 , with probability 1/2,
where ε ∈ (0, 1) is fixed. For each t ∈ Z+ , define the filtration Ft = σ(S0 , S1 , . . . , St ).
(a) Determine whether {St }t is a martingale with respect to {Ft }t .
(b) Compute the expected value of the investment after five years.
(c) Suppose that after one year (twelve months) the investment is worth £1,500. Conditioned
on this information, compute the expected value of the investment after five years.

Exercise 7.8. Consider two simple random walks {St }t and {St′ }t on Z defined as follows. Fix
p ∈ (1/2, 1) and let X1 , X1′ , X2 , X2′ , . . . be i.i.d. random variables taking values in {−1, 0, 1} with
1 p 1−p
P(X1 = 0) = , P(X1 = 1) = , and P(X1 = −1) = .
2 2 2
Pt Pt
Let S0 = S0′ = 0 and, for every t ∈ N, define St = i=1 Xi and St′ = ′
i=1 Xi . Define also the
relative position of the two walkers at time t by
Dt = St − St′ .
Finally, for every t ∈ Z+ , define
Ft = σ(St , St′ ), Gt = σ(S1 , S1′ , . . . , St , St′ ), Ht = σ(D1 , . . . , Dt ).
(a) Is {Ft }t a filtration?
(b) Is {Gt }t a filtration?
(c) Is {Ht }t a filtration?
(d) Is Xt measurable with respect to Ft , Gt , or Ht ?
(e) Is {Dt }t a martingale with respect to Gt ? Is it a martingale with respect to Ht ?
(f) Find k ∈ R such that Mt = St − kt is a martingale with respect to Gt , or show that no such
a kexists.
Now, define the first meeting time of the walkers as
τ = min {t ≥ 1 : Dt = 0} ,
and define the start of the first “triple meeting” of the walkers by
τ ′ = min {t ≥ 1 : Dt = Dt+1 = Dt+2 = 0} .
66 Chapter 7. Martingale

(g) Is τ a stopping time with respect to {Gt }t ? Is it a stopping time with respect to {Ht }t ?
(h) Is τ ′ a stopping time with respect to {Gt }t or {Ht }t ?

Exercise 7.9. Consider two simple random walks on Z, denoted {St }t≥0 and {St′ }t≥0 , with
initial positions S0 = 1 and S0′ = −1. At each time step, we choose one of the two walkers
uniformly at random and update only that walker’s position: the chosen walker moves one
unit to the right with probability p, or moves or unit to the left with probability 1 − p. Let
Dt = |St − St′ | denote the distance between the two walkers at time t, and define the meeting
time
τ = inf{t ≥ 0 : Dt = 0}.
Note that the number of times the first walker has moved by time t is Binomial(t, 1/2).
(a) Assume p = 21 . Is it true that τ is finite almost surely? Justify your answer.
(b) Does your conclusion in part (a) change if p > 12 ? Explain why or why not.
(c) For n ∈ Z+ let τn = inf {t ≥ 0 : Dt ≥ n}. Compute P(τ < τn ) the probability that the
walkers meet before their distance increase to n.

Exercise 7.10. Consider the simple random walk {St }t on Z starting from S0 = 0 and such
that P(St = St−1 + 1) = p > 1/2. For any a, b ∈ Z+ define τa = inf {t : St = a} and τ−b,a =
τa ∧ τ−b = min {τa , τ−b }.
(a) Show that for any a, b ∈ Z+ we have
1 − βb
P (τa < τ−b ) = ,
1 − β a+b
1−p
where β = p ∈ (0, 1).
(b) For any given finite a, b ∈ Z+ show that E(τ−b,a ) < ∞.
(c) With a, b, β as above, show that
1 − βb
 b
β − β a+b
   
1
E (τ−b,a ) = a −b ,
ρ 1 − β a+b 1 − β a+b
where ρ = 2p − 1.

Exercise 7.11. Suppose we have a randomized algorithm with binary output (that is, the
algorithm outputs either “yes” or “no”). Suppose that, regardless of whether the correct answer
is “yes” or “no”, the algorithm gives the correct answer with probability 2/3.
To improve the performance of the algorithm, we build a program that repeatedly runs the
algorithm until the difference between the number of occurrences of the two answers is at least
n. In other words, if we define Xi ∈ {−1, 1} by Xi = 1 if and only if the i-th execution of the
algorithm outputs “yes”, the program stops at the first step τ such that
τ
X
Xi = n,
i=1

and outputs “yes” if τi=1 Xi > 0, otherwise it outputs “no”. Suppose further that each execu-
P
tion of the algorithm takes an independent random time distributed as Uniform(0, 100).
(a) Compute the probability that the program outputs the correct answer.
(b) Compute the expected number of repetitions E(τ ).
(c) Compute the expected total time for the program to terminate.
Chapter 8

Galton-Watson branching process

8.1 Galton–Watson branching process

This is a simple probabilistic model for the spread of an infection (or the growth of a popula-
tion).

Definition 8.1 (Galton-Watson branching process). Start at time 0 with one infected indi-
vidual, and define S0 = 1. For k ≥ 0 and i ≥ 1, let Zk,i be i.i.d. random variables on Z+ . For
k ≥ 1, set (PS
k−1
i=1 Zk−1,i , if Sk−1 ≥ 1
Sk =
0, if Sk−1 = 0.

In words, Sk is the number of people from generation k. Each person i ∈ {1, 2, . . . , Sk−1 } from
generation k − 1 gives rise to Zk−1,i new individuals (called its offspring) at generation k.

8.2 Galton–Watson tree

A Galton-Watson branching process can be represented as a (possibly infinite) random tree (that
is, a random, connected, acyclic graph); refer to Figure 8.1.

Definition 8.2 (Galton-Watson tree). Given a Galton-Watson braching process {St }t , the
Galton-Watson tree is the following random graph:
• Vertices are labelled (k, i) for k ∈ Z+ with Sk > 0 and i ∈ {1, 2, . . . , Sk },
• Vertex (k, i) represents the ith individual at generation k,
• There is an edge between (k, i) and (k + 1, j) iff (k, i) is an offspring of (k + 1, j).
• The degree of vertex (k, i) is Zk,i .

67
68 Chapter 8. Galton-Watson branching process

(2, 1)
(1, 1)

S0 S1 S2 S3 S4 S5
Figure 8.1: An example of a Galton-Watson tree with S6 = 0. The leftmost endpoint of an edge
is the parent and the rightmost endpoint of an edge is the child, so the generations are ordered
from left to right. Vertex (1, 1) and one of its child (2, 1) are labelled in the figure. Note that
Z1,1 = 2 and Z2,1 = 3. Regarding vertex (2, 1), its descendants are colored in orange, and its
ancestors are colored in blue.

Definition 8.3 (Galton-Watson tree: parent, ancestors and descendants). Given a Gal-
ton–Watson tree G = (V, E):
• If there is an edge between some (k, i) ∈ V and some (k + 1, j) ∈ V , we say that the former
is the parent of the latter, and the latter is the offspring or child of the former.
• The ancestors of (k, i) are the vertices on the unique path from the root (0, 1) to (k, i),
excluding (k, i) itself.
• The descendants of (k, i) are all vertices (ℓ, j) with ℓ > k such that (k, i) is an ancestor of
(ℓ, j).

8.3 Extinction and survival

A main question is whether the infection eventually dies out or survives forever.

Definition 8.4 (Extinction time and survival). The extinction time is τ = inf {t ≥ 1 : St = 0}
with the convention that inf ∅ = ∞. We say the population dies out or becomes extinct if
τ < ∞, otherwise we say that the population survives.

Note that τ is a stopping time with respect to the filtration Ft = σ(S0 , S1 , . . . , St ).

 To avoid trivial cases, we assume

P(Z = 1) < 1, and P(Z = 0) ∈ (0, 1),

Chapter 8. Galton-Watson branching process 69

where Z stands for a random variable with the distribution of the Zk,i . In fact, if P(Z = 1) =
1 then Sk = 1 for all k, while if P(Z = 0) ∈ {0, 1} the population either dies immediately or
always survives.

Interestingly, to decide whether extinction occurs almost surely, it is enough to look at µ =

E(Z).

Theorem 8.5 (Galton-Watson phase transition). Let µ = E(Z) < ∞. Then:

P(τ < ∞) = 1 if µ ≤ 1, P(τ = ∞) > 0 if µ > 1.

 The infection cannot survive with probability 1 because P(S1 = 0) = P(Z = 0) > 0.

Definition 8.6 (Critical, supercritical and subcritical regimes). The Galton-Watson branch-
ing process is called
• Subcritical if µ < 1,
• Critical if µ = 1,
• Supercritical if µ > 1.

Proof of Theorem 8.5 for µ ≤ 1. Define

Mt = St µ−t .
Show that (Mt ) is a martingale with respect to Ft = σ(S0 , . . . , St ). Hence, for any t, we have
E(Mt ) = M0 = 1.
In the case µ < 1, we simply apply Markov’s inequality and the Martingale:
P(τ = ∞) = lim P(St ≥ 1) ≤ lim E(St ) = lim E(Mt ) µt = lim µt = 0.
t→∞ t→∞ t→∞ t→∞

Case µ = 1, which implies that Mt = St . For any a ∈ Z+ , let τa = inf {t : St ≥ a}. Show that
you can apply optional stopping to Mt and τa . We obtain
1 = E (Sτ ∧τa ) = E (Sτ 1 (τ < τa ) + Sτa 1 (τa < τ )) = E (Sτa 1 (τa < τ )) ≥ a P(τa < τ ),
so P(τa < τ ) ≤ 1/a. Taking a → ∞ gives P(τ = ∞) = 0.

6 Non-examinable material.

Proof of Theorem 8.5 for µ > 1. Case µ > 1. This case is difficult to handle via martingales,
so we take a different strategy and use the recursive definition of the branching process. Let
qt = P(St = 0) (the probability that extinction has occurred by time t). Then qt is increasing
in t, and since qt ∈ (0, 1), the limit q∞ = limt→∞ qt exists. Moreover,
X X
n n
qt = P(S1 = n)qt−1 = P(Z = n)qt−1 = φ(qt−1 ),
n n

where φ(q) = E(q Z ) is the generating function of Z. Thus qt = φ(φ(· · · φ(0))) = φt (0), the
t-fold composition of φ with itself with argument q0 = 0.
As t → ∞, qt → q∞ where q∞ = φ(q∞ ), i.e. q∞ is a fixed point of φ. Since φ is increasing,
70 Chapter 8. Galton-Watson branching process

φ(0) = P(Z = 0) > 0, and φ(1) = 1, the smallest fixed point is q∞ . Because φ′ (1) = E(Z) =
µ > 1, there exists a fixed point in (0, 1), so q∞ < 1 and therefore P(τ = ∞) = 1−q∞ > 0.

 The case µ > 1 cannot be solved via Martingales. In order to see this, consider
the following process starting from S0 = 1: for every t, St = 0 with probability 1/2 or
St = 2µSt−1 with probability 1/2, for some µ > 1. Note that if St = 0 then Ss = 0 for all
s ≥ t. Let τ inf {t : St = 0}. Note that

P(τ > t) = 2−t .

In particular, τ < ∞ almost surely and the process goes extinct. However, Mt = St µ−t is a
martingale because E(Mt+1 | Ft ) = µ−t−1 21 2µSt = Mt .
So in order to show that the Galton-Watson process survives for µ > 1 it is not enough to
use the fact that Mt is a martingale.

6 Non-examinable material. The martingale {Mt }t also gives quantitative informa-

tion:
1
P(τ > t) ≤ µt when µ < 1, and P(τ > τa ) ≤ when µ = 1.
a
In general
E(St ) µt
E(St | τ > t) = = ≥ µt .
P(τ > t) P(τ > t)
Hence, in the supercritical case (µ > 1), if the infection has not died out by time t, then St
is typically exponential in t.
In contrast, in the subcritical case (µ < 1),
τ ∞ ∞
!
X X X 1
E St = E(St 1 (t < τ )) = µt = < ∞.
1−µ
t=0 t=0 t=0

Therefore the expected size of the total population is finite.

8.4 Exercises

Exercise 8.1. Let µ > 1. Show that there exists a process {St }t with S0 = 1 and St ≥ 0 for
all t ∈ Z+ , such that {Mt }t defined by Mt = St µ−t is a martingale with respect to the filtraton
Ft = σ(S0 , S1 , . . . , St ), but P(τ = ∞) = 0, where τ = inf {t : St = 0}.
Hint: construct a process that, regardless of St−1 ≥ 1, sets St = 0 with probability 1/2.

Exercise 8.2. Given a parameter λ > 0, consider a Galton–Watson branching process {St }t≥0
with S0 = 1 and the following offspring distribution. Each individual has 0 children with prob-
ability 1/2; otherwise (with probability 1/2), its number of children is given by a Geometric(λ)
random variable.
(a) Determine the interval of values of λ for which this branching process survives with positive
probability.
Chapter 8. Galton-Watson branching process 71

Exercises from the tutorial sheet

Exercise 8.3. Given a parameter λ ∈ (0, 1/2), consider a Galton–Watson branching process
{St }t≥0 with S0 = 1 and offspring distribution given by a random variable Z such that
(
λi , if i ≥ 1
P(Z = i) = 1−2λ
1−λ , if i = 0.

(a) Determine the interval of values of λ for which this branching process survives with positive
probability.

Exercise 8.4. A virus begins with a single particle at time 0 (generation 0). At each unit of
time, every particle splits into an independent Poisson(λ) number of offspring. Each offspring
independently
• does not mutate (it has exactly the same genome as its parent) with probability p, or
• mutates with probability 1 − p.
The particles present at time i ∈ {0, 1, 2, . . .} are called particles of generation i, and the single
particle at generation 0 is referred to as the root particle. Once a mutation occurs in some
offspring particle v, all descendants of v are considered mutated and no longer count as having
the same genome as the root particle.
(a) Determine for which values of λ, p the genome of the root particle will eventually cease to
exist almost surely.

Exercise 8.5. Given a parameter λ > 0, consider a Galton–Watson branching process (Sn )n≥0
with S0 = 1 and the following offspring distribution. Each individual has 0 children with prob-
ability 1/2; otherwise (with probability 1/2), its number of children is given by a Geometric(λ)
random variable.
(a) Determine the interval of values of λ for which this branching process survives with positive
probability.

Exercise 8.6. Given a parameter λ > 0, consider the following branching process. At time 0,
we have S0 = 1 individual. Then, for each t ≥ 1, we define St as follows:
• If t is even, each individual at generation t − 1 has an independent number of offsprings
distributed as Poisson(λ).
• If t is odd, each individual at generation t − 1 has an independent number of offsprings
distributed as Bernoulli(1/2).
(a) Determine E(S2 ).
(b) Determine the value of α > 0 so that Mt = S2t αt is a martingale with respect to the
filtration Ft = σ(S0 , S1 , . . . , St ).
(c) Determine the largest value of λ so that St becomes extinct almost surely.
Chapter 9

Coupling

9.1 What is a coupling?

Let X ∼ Bernoulli(1/2) and Y ∼ Bernoulli(1/4). We would like to say that X ≥ Y . However,
if X and Y are independent, we have that
1
P (X < Y ) = P (X = 0, Y = 1) = P (X = 0) P (Y = 1) = > 0.
8

How to say that X ≥ Y ? The idea is to construct X and Y together ; for example:
• Throw two fair coins independently.
• Set X = 1 ( first coin is heads) and Y = 1 (both coins are heads).
• Notice that X ∼ Bernoulli(1/2) and Y ∼ Bernoulli(1/4).
• Moreover, P (X < Y ) = 0; thus X ≥ Y almost surely.
This illustrates a fundamental concept known as coupling.

9.2 Formal definition

Definition 9.1 (Coupling). Given two discrete random variables X and Y with sample
spaces ΩX , ΩY and probability distributions PX , PY , respectively, a coupling of X and Y is a
probability measure Q on ΩX × ΩY such that for all x ∈ ΩX and y ∈ ΩY ,
X X
Q(X = x, Y = y) = PX (X = x) and Q(X = x, Y = y) = PY (Y = y).
y∈ΩY x∈ΩX

An analogous definition holds for continuous random variables by replacing probability dis-
tribution with density functions and by replacing sums with integrals.

A simple coupling is to sample X and Y independently of one another. Despite always being a
coupling, this is usually not very useful.

9.3 Examples
Let p > q ∈ (0, 1) and set X ∼ Bernoulli(p) and Y ∼ Bernoulli(q). Can we couple them
so that X ≥ Y almost surely? Yes! Let U ∼ Uniform(0, 1) and set X = 1 (U ≤ p) and
Y = 1 (U ≤ q). Check that this is a coupling!

72
Chapter 9. Coupling 73

Let p > q ∈ (0, 1) and set X ∼ Geometric(p) and Y ∼ Geometric(q). Can we couple them
so that X ≤ Y almost surely? Yes! Let A1 , A2 , . . . be i.i.d. Bernoulli(p) and let B1 , B2 , . . .
be i.i.d. Bernoulli(q) such that for every i we have Ai coupled with Bi as before, which gives
Ai ≥ Bi for all i almost surely. Then, X = min {i : Ai = 1} and Y = min {i : Bi = 1}. It follows
that X and Y have the desired distribution and X ≤ Y almost surely under this coupling.

9.3.1. Stochastic domination

Let’s get back to our question: given two random variables X and Y , when can we say that
X ≤Y?

Definition 9.2 (Stochastic domination). Given two random variables X and Y , we say that
X is stochastically dominated by Y , written X ⪯ Y , if there exists a coupling Q of X and Y
such that
Q (X ≤ Y ) = 1.
In this case, we also say that Y stochastically dominates X, denoted Y ⪰ X.

This is precisely the situation for the variables X ∼ Bernoulli(p) and Y ∼ Bernoulli(q) with
p > q, which gives X ⪰ Y .
Example: X ∼ Binomial(n, p) and Y ∼ Binomial(n + m, p). Show that X ⪯ Y . We use the
fact that the sum of two independent binomial random variables with the same parameter p is
nothing else than a Binomial random variable with the parameter p and the sum of the other two
binomials. That is, if perform the coupling by first sampling X ∼ Binomial(n, p) and sampling
an independent random variable W ∼ Binomial(m, p), then setting Y = X + W implies that
Y ∼ Binomial(n + m, p). Since W ≥ 0 almost surely, we have that, under this coupling, X ≤ Y
almost surely.

Theorem 9.3 (Expectation under stochastic domination). Let X and Y be random variables
on a common sample space Ω, and let f : Ω → R be a non-decreasing function. If X is
stochastically dominated by Y , then

E (f (X)) ≤ E (f (Y )) .

Moreover, given any X, Y , if the above inequality holds for all increasing functions f , then
X ⪯Y.

Proof. We prove only one direction (the direction that if X ⪯ Y then E (f (X)) ≤ E (f (Y )).
Given any coupling Q we have
X
E (f (Y )) − E (f (X)) = QR(X = x, Y = y)(f (y) − f (x)).
x,y∈Ω

By stochastic domination we can choose Q such that Q(X ≤ Y ) = 1. That is, the sum above
can be restricted to values x ≤ y. Therefore,
X
E (f (Y )) − E (f (X)) = QR(X = x, Y = y)(f (y) − f (x)).
x≤y∈Ω

Since f is non-decreasing f (y) − f (x) ≥ 0 for all y ≥ x, thus

X
E (f (Y )) − E (f (X)) = QR(X = x, Y = y)(f (y) − f (x)) ≥ 0.
x≤y∈Ω
74 Chapter 9. Coupling

9.3.2. General construction of random variables via Uniform(0, 1)

How to prove that X ⪯ Y ? The following is a crucial fact: Any random variable can be
constructed from a Uniform(0, 1) random variable.
Let U ∼ Uniform(0, 1) and FX (x) = P(X ≤ x) be the distribution function of a random variable
X. Define the inverse FX−1 (u) = inf {x ∈ R : FX (x) ≥ u}.

Theorem 9.4 (Construction of a random variable via Uniform(0, 1)). Let X be any real-
valued random variable with distribution function FX (x) = P (X ≤ x). If U ∼ Uniform(0, 1)
and is independent of everything else, then

FX−1 (U ) has the same distribution as X.

Proof. Fix x ∈ R. By definition of the generalised inverse,

 −1
FX (u) ≤ x ⇐⇒ u ≤ FX (x) for all u ∈ (0, 1).
Therefore,
P FX−1 (U ) ≤ x = P (U ≤ FX (x)) = FX (x),

d
since U ∼ Uniform(0, 1). Hence the cdf of FX−1 (U ) equals FX , so FX−1 (U ) = X.

Examples: X ∼ Geometric(p) and Y ∼ Uniform(a, b). If U ∼ Uniform(0, 1), we get FX (x) =

1 − (1 − p)x−1 and X = 1 + log(1−U )
log(1−p) (note that both logs are negative); as for Y , we get
y−a
FY (y) = b−a and Y = a + (b − a)U .

9.3.3. Necessary and sufficient condition for stochastic domination

Theorem 9.5. Let X, Y be two random variables with common sample space Ω and distri-
bution functions FX , FY . Then X ⪯ Y if and only if

FX (z) ≥ FY (z), for all z ∈ Ω.

Proof. First we show that if FX ≥ FY pointwise, we have X ⪯ Y . For this, define a coupling
Q of X, Y as follows: let U ∼ Uniform(0, 1) and set X = FX−1 (U ) and Y = FY−1 (U ). Note
that X, Y have the correct marginal distributions and Q(X ≤ Y ) because FX ≥ FY pointwise.
Therefore, X ⪯ Y .
Now assume that there exists z ∈ Ω such that FX (z) < FY (z). To reach a contradiction, assume
that X ⪯ Y . Consider the function f : Ω → R defined as f (w) = 1 (w ≥ z) and note that f (w)
is non-decreasing in w. Therefore, X ⪯ Y implies that
E(f (X)) ≤ E(f (Y )).
However,
E(f (X)) = P(X ≥ z) = 1 − fX (z) > 1 − fX (Y ) = E(f (Y )),
which gives a contradiction.

9.4 Example: Erdős-Rényi random graph

Proposition 9.6. Let p > q ∈ (0, 1) and let n ∈ Z+ . Set V = [n] and define Gp = (V, Ep ) ∼
G(n, p) and Gq = (V, Eq ) ∼ G(n, q). It is possible to couple Gp and Gq such that Ep ⊇ Eq
almost surely.
Chapter 9. Coupling 75

Proof. For each unordered pair of vertices u, v ∈ V we have 1 ({u, v} ∈ Ep ) is Bernoulli(p) and
1 ({u, v} ∈ Eq ) is Bernoulli(q). So we can couple these indicators so that

1 ({u, v} ∈ Ep ) ≥ 1 ({u, v} ∈ Eq ) almost surely.

9.5 Example: Galton-Watson process

Proposition 9.7. Let Z, Z ′ be two discrete random variables in Z+ . Let {St }t and {St′ }t be two
Galton-Watson branching processes with offspring distributions given by Z and Z ′ , respectively.
If Z ⪯ Z ′ , then {St }t ⪯ {St′ }t meaning that we can devise a coupling between the two processes
such that
St ≤ St′ , for all t ≥ 0, almost surely.

Proof. We can do a coupling each generation at a time, first coupling S0 , S0′ , then S1 , S1′ and
so on and so forth. We can couple the number of offsprings of each individual so that the
offsprings with distribution Z is always less than or equal the number of offsprings obtained
with distribution Z ′ . Refer to the lecture for a more pictorial description of this proof.

9.6 Exercises
Exercise 9.1. Let {St }t and {St′ }t be two Galton-Watson branching processes such that {St }t ⪯
{St′ }t with S0 = S0′ = 1. Show that if {St }t is supercritical, then so is {St′ }t .

Exercise 9.2. Given p, q ∈ (0, 1) with p < q, for each positive integer n let Gp ∼ G(n, p) and
Gq ∼ G(n, q). Let Mp be the size of the largest component of Gp , and let Mq be the size of the
largest component of Gq . Show that Mp ⪯ Mq .

Exercise 9.3. You are given two fair dices:

• Die A: a standard 6-sided die with faces numbered {1, 2, 3, 4, 5, 6}.
• Die B: an 8-sided die with faces numbered {1, 2, 3, 4, 5, 6, 7, 8}.
You throw each die independently, and each die has an equal probability of landing in each of
the faces. Let X be the outcome of Die A and Y be the outcome of Die B.
Determine whether Y stochastically dominates X.

Exercises from the tutorial sheet

Exercise 9.4. Given λ′ > λ > 0, let X ∼ Exponential(λ) and Y ∼ Exponential(λ′ ). Show
that X ⪯ Y and specify a coupling Q of X, Y such that Q(X ≤ Y ) = 1.

Exercise 9.5. Let X ∼ Uniform(0, 1), let Y ∼ Uniform(0, 10) and let Z ∼ Uniform(1, 9).
(a) Is X ⪯ Y or Y ⪯ X?
(b) Is X ⪯ Z or Z ⪯ X?
(c) Is Y ⪯ Z or Z ⪯ Y ?

Exercise 9.6. Let Z be a random variable which assumes value 0, 1 or 2 with probabilities .8, .1
and .1, respectively. Let Z1 be a random variable which assumes value 0, 1 or 2 with probabilities
.5, .3 and .2, respectively. In a branching process, given an individual v, the siblings of v are the
other individuals in the branching process with the same parent as v.
76 Chapter 9. Coupling

Now consider a branching process {St }t starting from S0 = 1 which evolves as follows. If an
individual has exactly one sibling, then its number of children is given by an independent random
variable with the same distribution as Z1 . On the other hand, if an individual has any other
number of siblings (0 or at least 2), then its number of children is given by an independent
random variable with the same distribution of Z.
Determine whether this branching process gets extinct almost surely.

Exercise 9.7. Let X1 , X2 , . . . be i.i.d. random variables with distribution Geometric(1/4), and
let X1′ , X2′ , . . . be i.i.d. random variables with distribution Geometric(1/5). Let {St }t and {St′ }t
be two random walks on Z starting from S0 = S0′ = 0 and such that
t
X t
X
St = (Xi − 2) and St′ = (Xi′ − 2).
i=1 i=1

Given a > 0, define τa = inf {t : St ≥ a} and τa′ = inf {t : St′ ≥ a}, with the convention that
inf ∅ = ∞.
Show that τa ⪰ τa′ .
Chapter 10

Percolation

10.1 Definition of bond percolation

Let G = (V, E) be an infinite (or finite) graph of finite degrees. We can keep in mind the
following two examples:
(a) The Zd graph where V = Zd and E = E(Z d ) is the set of edges {u, v} such that ∥u−v∥1 = 1,
(b) The infinite d-regular tree (every vertex has exactly d neighbours).
Regardless of the graph, we will distinguish a vertex o which we refer to as the origin.

Definition 10.1 (Bond percolation). Bond percolation with parameter p ∈ [0, 1] on G =

(V, E) is defined as follows. To each edge e ∈ E, associate an independent random variable
ωe ∼ Bernoulli(p). If ωe = 1 we say that e is open, and if ωe = 0 we say that e is closed.
Define Gp = (V, Ep ) to be the graph induced by the open edges:

Ep = {e ∈ E : ωe = 1} .

The graph Gp is called percolation on G of density (or parameter) p.

 Observe that G1 coincides with G, while G0 is the graph on V without any edges.
Percolation also makes sense on finite graphs. In fact,

if G is the complete graph on n
n
vertices (that is, the graph with n vertices and all 2 edges), then Gp is the Erdős-Rényi
random graph distributed as G(n, p).

10.2 A word on motivation

Percolation was first introduced as a mathematical model for the flow of fluids through porous
materials, such as rocks. Open edges represent pores or fissures that can connect to form
microscopic channels through the medium. The main question of interest is whether water can
flow from the outside to the inside of the rock, by “percolating” through the fissures.
Percolation can also be viewed as a model of:
• Materials with impurity,
• Random medium or environment,
• Random graphs or random networks,

77
78 Chapter 10. Percolation

• Networks subject to failing links.

Percolation is a modern and highly active area of research in mathematics. It has not only
been widely studied as a simple model for porous materials, but has even been applied as a
mathematical technique to solve other problems.

10.3 Site percolation

There is a closely related variant called site percolation, where instead of declaring edges open
or closed, we declare the vertices open or closed.

6 Non-examinable material. For any graph G, bond percolation on G corresponds

to site percolation on another graph G′ , called the line graph of G.

Definition 10.2 (Line graph). The line graph of a graph G = (V, E) is the graph
G′ = (V ′ , E ′ ) where

V ′ = E, E ′ = (x, y) ∈ V ′ × V ′ : x, y ∈ E share a common vertex in G .



Therefore, site percolation is in some sense more general than bond percolation.

10.4 Percolation clusters

Consider now the random graph Gp . For each x ∈ V , let Cx denote the cluster of x; that is,
the connected component of x in Gp . In percolation it is common to use the terminology cluster
instead of connected component.

Figure 10.1: Examples of bond percolation on a piece of Z2 with parameter p = 0.45 (left) and
p = 0.55 (right). Only the open edges of Gp are shown. The largest cluster is highlighted in red.

The main problem in percolation is about determining whether an infinite cluster exists. When-
ever such an infinite cluster appears, we say that percolation occurs.

 In the physical interpretation (for instance, flow through a porous rock), the existence of
an infinite cluster means that the micro–channels inside the rock form a connected network,
so that water can flow from one side of the material to the other.
Chapter 10. Percolation 79

10.5 Percolation probability and pc

Given the origin o ∈ V , let Bn be the ball of radius n centered at o in G. Thus, Bn is the
set of vertices within distance n (i.e., reachable by a path of length at most n) from o. Let
Bnc = V \ Bn .

Definition 10.3 (Probability measure and percolation). Let Pp denote the probability mea-
sure induced by the graph Gp . Define the event

{o ⇝ Bnc } = {there exist an open path from o to Bnc } ,

and the probability

θn (p) = Pp (o ⇝ Bnc ) .

Note that θn (p) is a non-increasing function of n, so we can define its limit as

θ(p) = lim θn (p) = Pp (|Co | = ∞) ,

n→∞

which is the probability that the origin is in an infinite cluster.

Definition 10.4 (Critical probability). Given a graph G = (V, E) the critical probability is
defined as
pc = pc (G) = inf {p ∈ [0, 1] : θ(p) > 0} .

Then, for all p < pc , the probability of the existence of an infinite cluster is zero. Indeed, by the
union bound over x ∈ V ,
!
[ X
Pp {|Cx | = ∞} ≤ Pp (|Cx | = ∞) = 0,
x∈V x∈V

because Pp (|Cx | = ∞) = 0 since θ(p) = 0.

 The above result requires us to prove that if θ(p) = 0 then Pp (v ⇝ ∞) = 0 for any
v ∈ V . In the two examples of graphs (Zd and the regular tree) this follows by symmetry of
the graph. In fact, it follows in greater generality but we will not prove this as it requires
an additional result.

10.6 Monotonicity and phase transition

We aim to prove the following result.

Theorem 10.5 (Monotonicity of percolation). θ(p) is a non-decreasing function of p.

At first, this may look obvious: if we increase p, then Gp should contain more edges, hence it
should be more likely to contain an infinite cluster. The intuition is clear, but we need a rigorous
argument: coupling.
An immediate consequence of Theorem 10.5 is the phase transition.
Corollary 10.6 (Phase transition of percolation). For p < pc , θ(p) = 0, while for p > pc ,
θ(p) > 0.
80 Chapter 10. Percolation

 We employ the term phase transition in analogy to the transition of water from liquid
to solid at 0◦ C. Note that water suffers a visible (or macroscopic) change from liquid to
solid as the temperature decreases past 0◦ C. Similarly, the percolating cluster undergoes a
macroscopic change with the appearance of an infinite cluster as the parameter p is increased
past pc .

Proof of Theorem 10.5. The event {|C| = ∞} is an increasing event, meaning that if it occurs
for a configuration ω ′ , it also occurs for any ω ≥ ω ′ .
Let p > p′ and define ω, ω ′ as bond percolation with parameter p and p′ , respectively. We
construct ω, ω ′ in a coupled way as follows. For each edge e ∈ E, let Ue be an independent
Uniform(0, 1) random variable. Then, set ωe = 1 (Ue ≤ p) and ωe′ = 1 (Ue ≤ p′ ). Note that
ωe ≥ ωe′ and ωe ∼ Bernoulli(p) and ωe′ ∼ Bernoulli(p′ ). Let Q denote the probability
measure induced by this coupling.
Now let C(ω) and C(ω ′ ) be the clusters of the origin under each configuration. Then

θ(p) = Pp (|C(ω)| = ∞) = Q (|C(ω)| = ∞) ≥ Q |C(ω ′ )| = ∞ = Pp′ |C(ω ′ )| = ∞ = θ(p′ ).

The inequality follows from ω ⪰ ω ′ . The second and third equalities use the definition of
coupling.

10.7 General lower bound on pc

We will use the first-moment method to obtain a lower bound for the critical probability pc .
This lower bound holds for any infinite regular graph (all vertices have the same degree).

Theorem 10.7 (Lower bound on pc ). Let G be an infinite d-regular graph. Then, for every
1
p < d−1 ,
θ(p) = 0.
1
Consequently, pc (G) ≥ d−1 .

Proof. Recall that

θ(p) = lim Pp (0 ⇝ B c (n)) .
n→∞

Moreover,

{0 ⇝ B c (n)} ⊂ {∃ a path of open edges from the origin with length at least n} .

Thus, it suffices to count open paths. For each n, set

ρn (p) = Pp {∃ a path of open edges from the origin with length at least n} .

Let Pn be the set of paths from the origin with exactly n edges (this set is deterministic). Let
Xn be the number of paths in Pn whose edges are all open. By Markov’s inequality,

ρn (p) = Pp (Xn ≥ 1) ≤ Ep (Xn ) .

P
Since Xn = P ∈Pn 1 (all edges of P are open),
X X
Ep (Xn ) = Pp (all edges of P are open) = pn ≤ d(d − 1)n−1 pn ,
P ∈Pn P ∈Pn
Chapter 10. Percolation 81

because there are at most d choices for the first edge of the path and then at most d − 1 choices
at each subsequent edge of the path.
Hence
θ(p) ≤ lim ρn (p) ≤ lim d(d − 1)n−1 pn = lim pd ((d − 1)p)n−1 .
n→∞ n→∞ n→∞
If (d − 1)p < 1, the limit is 0, hence θ(p) = 0.

10.8 pc for the regular tree

Theorem 10.8 (pc on regular trees). Let Td = (V, E) be the infinite d-regular tree. Then
1
pc (Td ) = .
d−1

1
We already showed that pc ≥ d−1 . So it remains to show an upper bound.
There are two ways to prove this: one via branching process and another with the second
moment method.
1
Proof of Theorem 10.8 via the second-moment method. We only need to show that for p > d−1
there exists an infinite cluster. Let Xn be the number of paths from the origin to distance n
whose edges are all open. Then
X
Xn = 1all edges of P are open,
P ∈Pn

where Pn is the set of paths from the origin to distance n. Note that, in a regular tree we have
|Pn | = d(d − 1)n−1 , therefore
E(Xn ) = d(d − 1)n−1 pn .
1
When p > d−1 we have that E(Xn ) → ∞ as n → ∞.
1
We will show that for p > d−1 ,
lim Pp (Xn > 0) → 1,
n→∞
which implies the existence (with positive probability) of an infinite open path from the origin.
We use the second moment. We compute
X
E(Xn2 ) = E(Xn )2 Pp all edges of P and P ′ are open .

P ̸=P ′

For P ̸= P ′ , let ρ(P, P ′ ) be their most distant common ancestor from the origin (the last shared
vertex). Let |ρ(P, P ′ )| = i ∈ {0, 1, . . . , n − 1} be its level (distance from the origin). Given i,
the two paths together use i + 2(n − i) = 2n − i edges, so
Pp all edges of P and P ′ are open = p2n−i .

Counting the pairs with |ρ(P, P ′ )| = i yields

  n−1  
d i−1 d − 1
X
E(Xn2 ) = E(Xn ) + (d − 1)2(n−1) 2n
p + d(d − 1) (d − 1)2(n−1−i) p2n−i .
2 2
i=1

Using d ≤ 2(d − 1) for d ≥ 1, we can bound

n−1 n−1
((d − 1)p)−i ≤ E(Xn ) + ((d
X X
E(Xn2 ) ≤ E(Xn ) + ((d − 1)p)2n + ((d − 1)p)2n−i = E(Xn ) + ((d − 1)p)2n
i=1 i=0
82 Chapter 10. Percolation

By Paley–Zygmund,

(E(Xn ))2 (dp)2 ((d − 1)p)2n−2 (dp)2 ((d − 1)p)2n−2

Pp (Xn > 0) ≥ ≥  ≥ .
E(Xn2 )
 
2n 1 2n 1
E(Ln ) + ((d − 1)p) 1− 1
((d − 1)p) 1− 1
(d−1)p (d−1)p

Thus  2
d 1
Pp (Xn > 0) ≥ 1 > 0,
d−1 1
1− (d−1)p

uniformly in large n, which implies the desired positive probability of an infinite open path.
1
Hence pc (Td ) ≤ d−1 , completing the proof.

Proof of Theorem 10.8 via branching process. Given vertex o, for each k ∈ Z+ let Wk be the
vertices at distance exactly k from o. Note that |Wk | = d(d − 1)k−1 . We will see Wk a branching
process that starts at W1 = d. Then, note that for each k ≥ 2, each vertex v ∈ Wk−1 has exactly
d − 1 neighbors in Wk because one of its neighbors is in Wk−2 . Now we define the branching
process. Let S0 = {o}. Then, for each k ≥ 1 we let Sk be a subset of Wk defined as the set of
vertices u ∈ Wk which are connected via an open edge to a vertex in Sk−1 . Then, any vertex in
Sk is a vertex of distance k from o for which the unique path that connects it to o is composed
only of open edges. In other words, Sk contains all vertices from Wk that belong to the cluster
of the origin. So, the origin is in an infinite cluster if and only if the branching process {Sk }k
survives.
Note that |S1 | ∼ Binomial(d, p) and for k ≥ 2 we have |Sk | is equal to the sum of |Sk−1 |
independent Binomial(d − 1, p) random variables. Because d becomes d − 1 from generations
2 and higher, we can see that conditioned on S1 we obtain a Galton-Watson branching process
with offspring distribution Binomial(d − 1, p), whose expectation is (d − 1)p. Therefore, if
(d − 1)p < 1 the branching process becomes extinct almost surely, implying that the cluster
of the origin is finite almost surely. On the other hand, if (d − 1)p > 1, the branching process
survives with positive probability, which gives that the origin is in an infinite cluster with positive
probability.

10.9 Finite graphs and Erdős-Rényi

We now consider G(n, p) or percolation in the complete graph with n vertices. Clearly, no
infinite cluster can exist in finite graphs. Instead, we will look for the appearance of a giant
component.
For any ε > 0, define the event En,p,ε that G ∼ G(n, p) has a connected component of size
at least εn. Moreover, let Ci denote the connected component of vertex number i, and let
C = C1 .

Theorem 10.9 (Giant component). Let limn→∞ pn = λ ∈ [0, ∞]. Then, if λ > 1, we have
that En,p,ε occurs a.a.s. for some ε > 0.
On the other hand, if λ < 1, we have that En,p,ε does not occurs a.a.s. for any ε > 0. Moreover,
there exists c = c(p) such that P (|C| ≥ x) ≤ e−cx .

Proof. The proof of the first part is beyond the scope of this course. We will see the proof of
the second part. So, assume that p ≪ n1 . The proof strategy is to show that

|C|is stochastically dominated by a subcritical Galton-Watson branching process with offspring distribution Bi
(10.9.1)
Chapter 10. Percolation 83

Assuming the above for the moment, let Z ∼ Binomial(n, p) and note that E(Z) = np < 1.
Therefore, letting X be the total number of individuals in this Galton-Watson branching process
we obtain
P (|C| ≥ x) ≤ P(X ≥ x) ≤ e−cx .
Taking the union bound over all vertices, we have
 
P max |Ci | ≥ x ≤ ne−cx .
i∈V

Choosen x = C log n for some large enough C gives that the above bound goes to zero as n → ∞,
establishing that a.a.s. there are no connected component of size larger than C log n.
It remains to show (10.9.1). Take vertex 1. We know that dG (1) ∼ Binomial(n − 1, p) ⪯
Binomial(n, p).

 Note that the condition on λ does not change with ε > 0.

Moreover, letting Cmax = maxi∈[n] |Ci | be the size of the largest component, we have that
there exists ε = ε(λ) > 0 and c = c(λ) ∈ (0, ∞) such that Cmax ≤ c log n if λ < 1 whereas
Cmax ≥ εn if λ > 1. This shows an abrupt phase transition in the size of the largest
component when p is of order n1 .
There is another phase transition, that of when G(n, p) becomes a connected graph (that is,
Cmax = n). This happens when p is of order logn n .

10.10 Exercises
Exercise 10.1. Let d ≥ 3 and G = (V, E) be a graph. Site percolation on G is the process
obtained by declaring each vertex to be open independently with probability p, and vertices that
are not open are declared to be closed. An open path for site percolation is a path in G where all
vertices in the path are open. The critical probability for site percolation is the smallest value
of p so that there exists a positive probability that the origin is in an infinite open path for site
percolation.
Determine the critical probability for site percolation on the infinite d-regular tree.

Exercise 10.2. Let G be the graph obtained from the infinite 3-regular tree by replacing each
vertex by a cycle of length 4 as illustrated below: Determine pc (G).

···

···
···
···

···

Exercise 10.3 ( ). Consider the graph G = (V, E), where V is an infinite set of vertices, G
is a tree, the degrees of the vertices are either 3 or 5, and each edge of G has an endpoint with
degree 3 and an endpoint with degree 5. Assume that the origin has degree 3.
Determine pc (G).
84 Chapter 10. Percolation

Exercise 10.4 ( ). The graph induced by Z 2 and the 4-regular tree are two infinite regular
graphs where the degrees are equal to 4. Let Gp be the graph obtained by doing percolation on
Z 2 with probability p, and let Tp be the graph obtained by doing percolation on the 4-regular
tree with probability p. Let M be the size of the open cluster of the origin in Gp , and let M ′ be
the size of the open cluster of the root in Tp .
Show that M ⪯ M ′ .

Exercises from the tutorial sheet

Exercise 10.5. Consider two graphs G1 = (V, E1 ) and G2 = (V, E2 ) with the same vertex set.
(a) Show that if E1 ⊂ E2 then pc (G1 ) ≥ pc (G2 ).
(b) Use the above to conclude that pc (Z3 ) ≤ pc (Z2 ).

Exercise 10.6. Recall that the critical probability for percolation on Z2 is 1/2. Let G be the
graph obtained from Z2 by replacing each edge with a path of length k (see the figure below for
an example with k = 3). Determine pc (G).
.. .. .. .. .. ..
. . . . . .
··· ···

··· ···

··· ···

··· ···

··· ···

··· ···
.. .. .. .. .. ..
. . . . . .

Exercise 10.7. Consider a Galton Watson tree G = (V, E) where the offspring distribution
is given by a random variable Z. Fix p ∈ [0, 1] and let Gp be the random graph obtained by
performing bond percolation with parameter p on the random graph G. Assume that E(Z) > 1
such that the event |V | = ∞ has positive probability. Let Pp be the probability induced by
the random graph Gp . Let o be the origin of the Galton Watson tree. Establish the following
results:
1
(a) Pp (o ⇝ ∞) = 0 for all p < E(Z) .
1
(b) Pp (o ⇝ ∞) > 0 for all p > E(Z) .
1
(c) Pp (o ⇝ ∞ | |V | = ∞) > 0 for all p > E(Z) .
Chapter 11

Review problems

11.1 Isolated triangle

Given a graph G = (V, E), a triple of vertices (u, v, w) is called an isolated triangle if u, v, w are
neighbors of one another but are not neighbors of any other vertex in V .
Let A = (Au,v )u,v∈V be the adjacency matrix of G:

(
1, if {u, v} ∈ E
Au,v =
0, otherwise.

Algorithm 11.1: Algorithm for detecting isolated triangles

Input: An adjacency matrix A ∈ Rn×n of an undirected graph G

Output: true if A has an isolated triangle, false otherwise

Pick a vertex u uniformly at random from V .

If u has degree 2, let v, w be the neighbors of u; otherwise, return false.
If v, w are neighbors between themselves and have degree 2, return true; otherwise return
false.

Exercise 11.1. What is the probability that the output is correct when G has an isolated
triangle?

Exercise 11.2. What is the probability that the output is correct when G does not have an
isolated triangle?

Exercise 11.3. Is the algorithm above a randomized algorithm?

Exercise 11.4. Is the algorithm above Monte Carlo, Las Vegas or neither?

Exercise 11.5. Run the algorithm for k times, independently, and output true if at least one
of the iterations return true, otherwise output false. What is the probability that the output
produced in this procedure is correct?

Now consider the random graph G ∼ G(n, p) where p = p(n) can depend on n. For each triple

85
86 Chapter 11. Review problems

u, v, w ∈ V , define Iu,v,w = 1 (u, v, w are an isolated triangle in G). Define also,

X
X= Iu,v,w .
u<v<w

Exercise 11.6. Show that if p ≪ n1 or p ≫ n1 then G does not have an isolated triangle almost
surely.
Hint: you may use that, for any constant c > 0, we have limx→∞ x3 e−cx = 0.

n
p3 (1 − p)3(n−3) .


Hint: prove that E(X) = 3

Exercise 11.7. Compute E(X 2 ).

Hint: Note that it is not possible for two non-disjoint
and
distinct triples to be isolated triangles
simultaneously. You should get E(X 2 ) = E(X) + n3 n−3 6
3 p (1 − p)
6(n−6)+9 .

Exercise 11.8. Show that if p = nλ for some constant λ then G has an isolated triangle with
positive probability.  
x
Hint: you may use that, for any constant x ∈ (0, 1), we have 1 − x ≥ exp − 1−x .

Hint:

11.2 Second moment method

Pn
Let I1 , I2 , . . . be a sequence of indicator random variables, and define Xn = i=1 Ii .

Exercise 11.9. As n → ∞, show that if

E(Xn2 )
E(Xn ) → ∞ and →1
E2 (Xn )

then P(Xn ≥ 1) → 1.

11.3 Percolation
Consider the variation of the binary tree below:

···
···
···
o ···
···
···
···
···

Exercise 11.10. Determine pc .

Chapter 11. Review problems 87

Consider the graph obtained from the previous graph by replacing each edge with a path of
length 2.

···
···
···
o ···
···
···
···
···

Exercise 11.11. Determine pc for this new graph.

11.4 A gambling game

A person starts with k pounds and repeatedly plays a gambling game. At each round:
• With probability 9
10 , the person loses 1 pound.
• With probability 1
10 , the person wins 1 pound.
Let St denote the person’s wealth after t rounds, with S0 = k. For any N , define τN =
inf {t : St ≥ N }, with the convention that inf ∅ = ∞. Let Ft = σ(S0 , S1 , . . . , St ) be the natural
filtration. The player must stop if their wealth reaches 0. That is, the game ends at time τ0 .

Exercise 11.12. Let N be fixed. Is τN a stopping time with respect to {Ft }t ?

Exercise 11.13. Determine the value α ∈ R+ so that Mt = αSt is a martingale with respect
to the filtration {Ft }t .

Exercise 11.14. Determine whether P(τN < ∞) goes to 1 as N → ∞.