10.1 Probability as measure

A probability is a measure of total size 1 on a family of events, like length or area but for chance. Three axioms are enough to prove every rule of probability, to define densities, expectation and variance, and to prove that averages settle down.

In school, the probability of an event was “favourable outcomes over total outcomes”. That works for a die. It fails for a dart thrown at a board (no outcome count), for “toss a coin until it lands heads” (no largest number of tosses), and for “pick a real number between 0 and 1 at random” (uncountably many outcomes, each with chance $0$ ). The fix, found in the first third of the twentieth century, is to stop counting and to treat probability the way we already treat length, area and mass: as a number attached to sets, which adds up over non-overlapping pieces. This chapter builds probability on that idea, proves every familiar rule from three axioms, and finishes with the first great theorem of the subject, the law of large numbers.

Before you start

0.3: sets, unions, intersections and complements, and countable sets. 1.5: the Riemann integral and the fundamental theorem of calculus. 1.6: series and the geometric series. You do not need any earlier probability: the counting rules from JEE and CBSE are used only in examples, and every probability rule is proved from the axioms.

Quick checkWhich of these sets is countable?

Quick checkWhat is

\dfrac12 + \dfrac14 + \dfrac18 + \dfrac1{16} + \cdots

Quick checkWhat is

\displaystyle\int_0^1 3x^2\,dx

The picture

Probability is how much of a total mass of $1$ sits on a set. Roll a die and the mass is $\frac16$ on each face. Measure a continuous quantity, such as the waiting time for a bus, and the mass is smeared along the line. The density says how thickly: the area under the density curve over an interval is the mass on that interval. The picture below draws random samples as a histogram, with bars scaled so that their total area is $1$ , and lays the density curve on top. Set the interval $[a, b)$ with the two sliders. The page reads the probability of that interval two ways: as the fraction of samples that landed in it, and as the area under the curve. Slide the sample size $n$ up from $10$ to $30000$ and watch the two numbers, and the bars and the curve, come together. That coming together is the law of large numbers, proved at the end of this chapter.

Two things to watch. Move $a$ and $b$ together until the interval is very thin: the area, and the fraction, both go to $0$ . A single point has probability $0$ even though it can happen. And try “Uniform on [0, 1]”: its density is the constant $1$ , so the probability of an interval is its length. Length is the first and oldest example of the thing this chapter studies.

The idea, in words

Length, area, volume, mass, and the number of elements in a finite set share three properties. They are never negative. The empty set has size $0$ . And the size of a set made of two non-overlapping pieces is the sum of the sizes of the pieces. A probability is another example with one extra demand: the whole space has size $1$ .

Probability language	Set language
the sample space $\Omega$ : all outcomes that could happen	the whole space
an outcome $\omega$	a point of $\Omega$
an event $A$ : “something happened”	a subset of $\Omega$
” $A$ or $B$ ”	the union $A \cup B$
” $A$ and $B$ ”	the intersection $A \cap B$
“not $A$ ”	the complement $A^c$
$A$ and $B$ cannot both happen	$A \cap B = \varnothing$ (disjoint)
“if $A$ happens then $B$ happens”	$A \subseteq B$

Why· The core intuition: chance is mass that adds over non-overlapping pieces

If two events cannot both happen, the chance that one of them happens is the sum of their chances. Everything else, every rule in a probability course, is this one rule plus the facts that chances are never negative and that something always happens. In the picture: cut the area under the density into two non-overlapping intervals and the two areas add to the area of the union.

Where this came from· From gambling letters to measure theory

In 1654 Blaise Pascal and Pierre de Fermat exchanged letters about the problem of points: how should the stakes of an interrupted game be split? The Chevalier de Méré had brought them the problem. Their correct answer, found by counting how the game could have continued, is usually taken as the start of probability as mathematics. Jacob Bernoulli proved the first law of large numbers (his “golden theorem”), and it appeared in his book Ars Conjectandi in 1713, eight years after he died. Thomas Bayes’s essay, edited by Richard Price, appeared in 1763. All of this counted equally likely cases, which breaks for a point chosen on a line. Around 1900, Émile Borel and Henri Lebesgue built the theory of measuring sets of reals, and in 1933 Andrey Kolmogorov used it to give probability the three axioms below.

The chapter answers six questions in order. (1) What is a size that adds over disjoint pieces, and which sets can it measure? (2) What exactly are the axioms, and what do they prove? (3) How do we update a chance when we learn something, and what does independence mean? (4) How do we attach numbers to outcomes, and describe their spread? (5) What are the average and the typical spread of such numbers? (6) Why do averages of many repeated trials settle down?

Definitions and theorems

Set functions that add (Apostol 13.2 and 13.3)

Definition A

Finitely additive set function

Let $\mathcal A$ be a family of subsets of a set $S$ . A function $f$ that assigns a real number $f(A)$ to every $A$ in $\mathcal A$ is called a set function. It is finitely additive if

f(A \cup B) = f(A) + f(B) \quad\text{whenever } A, B \in \mathcal A,\ A \cap B = \varnothing,\ \text{and } A \cup B \in \mathcal A.

Apostol 13.2 calls this the definition of a finitely additive set function. The family $\mathcal A$ is the domain of $f$ : the sets $f$ is allowed to measure.

In one lineA function $f$ that gives a real number $f(A)$ to each set $A$ in a family of sets, so that $f(A \cup B) = f(A) + f(B)$ whenever $A$ and $B$ are disjoint.

Why it existsLength, area, mass and counting all add over non-overlapping pieces. This is the one property they share, and probability is built on it.

For the rule to be usable we want the union, intersection and complement of sets in the family to stay in the family. That is the next definition.

Definition A

Boolean algebra of sets

A non-empty family $\mathcal A$ of subsets of $S$ is a Boolean algebra if $A \in \mathcal A$ and $B \in \mathcal A$ imply $A \cup B \in \mathcal A$ and $A^c \in \mathcal A$ . It then also contains $A \cap B = (A^c \cup B^c)^c$ (De Morgan’s law, 0.3), the difference $A \setminus B = A \cap B^c$ , the empty set ( $\varnothing = A \cap A^c$ ) and the whole set $S$ ( $S = A \cup A^c$ ). The smallest example is $\{\varnothing, S\}$ and the largest is the family of all subsets of $S$ .

In one lineA non-empty family of subsets of a set $S$ that contains the union $A \cup B$ and the complement $A^c = S \setminus A$ whenever it contains $A$ and $B$ .

Why it existsIt is the smallest family in which you can still say 'or' and 'not' about events, so a set function defined on it can be asked about every combination of its members.

Definition A

Finitely additive measure

A finitely additive set function $f$ on a Boolean algebra is a finitely additive measure (Apostol calls it a “measure”) if $f(A) \ge 0$ for every $A$ in its domain.

In one lineA finitely additive set function on a Boolean algebra that never takes a negative value.

Why it existsLength, area, mass and counting are never negative. Adding that to additivity gives the properties that the next theorem lists, and probability will be a finitely additive measure of total size 1.

Worked example Apostol 13.3, the counting example

Let S = {1, 2, 3} and let the domain be all 8 subsets. Is f(A) = (number of elements of A) a finitely additive measure? Is g(A) = (number of elements of A) squared?

Solution.

Test $f$ on disjoint sets. If $A$ has $k$ elements, $B$ has $m$ elements and they share none, then $A \cup B$ has $k + m$ elements, so $f(A \cup B) = f(A) + f(B)$ . Counting elements in two non-overlapping piles gives the total of the two counts.
Check the sign. A count is never negative. This is the extra condition that turns additive into a measure.
Test $g$ on one pair. Take $A = \{1\}$ and $B = \{2\}$ . They are disjoint, and $g(A \cup B) = 2^2 = 4$ , but $g(A) + g(B) = 1 + 1 = 2$ . One failing pair is enough to show a rule is not additive.

Answer. $f$ is a finitely additive measure, the counting measure. $g$ is non-negative but not additive, so it is not a measure.

Theorem A Apostol Thm 13.1

Additivity for overlapping sets

Let $f$ be finitely additive on a Boolean algebra $\mathcal A$ and let $A, B \in \mathcal A$ . Then

f(A \cup B) = f(A) + f(B \setminus A), \qquad f(A \cup B) = f(A) + f(B) - f(A \cap B).

In one lineIf $f$ is finitely additive on a Boolean algebra, then $f(A \cup B) = f(A) + f(B \setminus A)$ and $f(A \cup B) = f(A) + f(B) - f(A \cap B)$ for all $A, B$ in the algebra.

Why it is trueThe definition only handles disjoint sets. This removes that condition by cutting overlapping sets into disjoint pieces.

ProofApostol 13.2

The idea: Cut A union B into disjoint pieces, apply the definition, and subtract.

A \cup B

is the disjoint union of

A

and

B \setminus A

A

and

B \setminus A

do not overlap, and together they make up everything in

A \cup B

f(A \cup B) = f(A) + f(B \setminus A)

. This is the first formula.

The definition of finite additivity applies to these two disjoint sets, and both are in the algebra (it is closed under difference).

B

is the disjoint union of

B \setminus A

and

A \cap B

, so

f(B) = f(B \setminus A) + f(A \cap B)

B

is cut into the part inside

A

and the part outside it, and these two parts are disjoint.

f(A \cup B) = f(A) + f(B) - f(A \cap B)

Solve the line above for

f(B \setminus A)

and put it into the first formula.

Theorem A Apostol Thm 13.2

Properties of a finitely additive measure

Let $f$ be a finitely additive measure on a Boolean algebra. For all $A, B$ in the algebra:

$f(A \cup B) \le f(A) + f(B)$ .
If $A \subseteq B$ , then $f(B \setminus A) = f(B) - f(A)$ .
If $A \subseteq B$ , then $f(A) \le f(B)$ (monotone).
$f(\varnothing) = 0$ .

In one lineFor a finitely additive measure $f$ : $f(A \cup B) \le f(A) + f(B)$ ; if $A \subseteq B$ then $f(B \setminus A) = f(B) - f(A)$ and $f(A) \le f(B)$ ; and $f(\varnothing) = 0$ .

Why it is trueThese are the rules every size obeys: a union is at most the sum of its parts, a bigger set is at least as large, and nothing has size zero.

ProofApostol 13.3

The idea: Everything follows from the previous theorem and from the fact that f is never negative.

Part 1: subtracting a non-negative number can only make the right side smaller.

By the previous theorem

f(A \cup B) = f(A) + f(B) - f(A \cap B)

, and

f(A \cap B) \ge 0

because

f

is a measure.

Part 2: rearrange this to

f(B \setminus A) = f(B) - f(A)

A \subseteq B

then

A \cup B = B

and

B \setminus A

is what is left. The first formula of the previous theorem reads

f(B) = f(A) + f(B \setminus A)

Part 3:

f(A) \le f(B)

f(B \setminus A) \ge 0

since

f

is a measure, so

f(B) - f(A) \ge 0

Part 4:

f(\varnothing) = f(A) - f(A) = 0

Put

B = A

in part 2. Then

A \subseteq B

and

B \setminus A = \varnothing

Quick checkLet S be the counting numbers and let the family be all finite sets and all sets with a finite complement. Define f(A) = 0 if A is finite and f(A) = 1 if the complement of A is finite. Is f finitely additive?

Why finite additivity is not enough: countable additivity

The set function in the quiz is a perfectly good finitely additive measure. It is also strange. Write the counting numbers as $\mathbb N = \{1\} \cup \{2\} \cup \{3\} \cup \cdots$ , a union of countably many disjoint sets, each of size $f(\{k\}) = 0$ . Yet $f(\mathbb N) = 1$ . Finite additivity says nothing about adding infinitely many pieces, and the size of the union is not the sum of the sizes. For probability we want to say things like “the chance that a coin first lands heads on toss $1$ , or toss $2$ , or toss $3$ , and so on, is the sum of the chances”, an infinite sum. So we demand more.

Definition A

Sigma-algebra

A family $\mathcal F$ of subsets of a set $\Omega$ is a sigma-algebra (also written $\sigma$ -algebra; Apostol writes “Boolean $\sigma$ -algebra”) if

$\Omega \in \mathcal F$ ,
$A \in \mathcal F$ implies $A^c \in \mathcal F$ ,
$A_1, A_2, A_3, \dots \in \mathcal F$ implies $A_1 \cup A_2 \cup A_3 \cup \cdots \in \mathcal F$ .

By De Morgan’s laws it is also closed under countable intersections, and it contains $\varnothing$ , finite unions and differences, so it is a Boolean algebra. Examples: all subsets of $\Omega$ ; the two-set family $\{\varnothing, \Omega\}$ ; and, for $\Omega = \{1, \dots, 6\}$ (a die), the family $\{\varnothing,\ \{1,3,5\},\ \{2,4,6\},\ \Omega\}$ , the events you can decide if you only learn whether the roll was odd or even. The Borel sigma-algebra of the real line is the smallest sigma-algebra that contains every interval. Apostol 14.1 uses it as the family of events for sample spaces inside $\mathbb R$ .

In one lineA family $\mathcal F$ of subsets of $\Omega$ that contains $\Omega$ , the complement of each member, and the union of any countable list of members.

Why it existsIt is a Boolean algebra that is also closed under countable unions, so that a set function can be asked to add up infinitely many pieces and the answer still makes sense.

The members of $\mathcal F$ are the sets we promise to measure. For a finite or countable $\Omega$ we take all subsets. For the real line we cannot, and the next theorem says why. It is a light-touch note, labelled B: nothing later depends on its proof, but you should know that the restriction is forced.

Theorem B Vitali 1905

Vitali: no uniform probability on every subset

Let $P$ be defined on all subsets of $[0, 1)$ with $P([0,1)) = 1$ , with $P(\bigcup A_n) = \sum P(A_n)$ for disjoint sets $A_1, A_2, \dots$ , and with $P(A \oplus q) = P(A)$ for every set $A$ and every $q$ , where $A \oplus q$ means every point of $A$ moved right by $q$ and wrapped back into $[0,1)$ (add $q$ then subtract $1$ if the result reaches $1$ ). Then these three requirements contradict each other.

In one lineThere is no way to assign a probability to every subset of the interval [0, 1) so that probabilities add over countably many disjoint sets, the whole interval has probability 1, and sliding a set around the circle (mod 1) never changes its probability.

Why it is trueIt shows that a sigma-algebra smaller than 'all subsets' is not a technical convenience. Any uniform random point on a line needs it.

ProofVitali's construction; uses the axiom of choice

The idea: Split [0, 1) into countably many translates of one set V. They all have the same probability, so the total is either 0 or infinity, never 1.

Cut

[0,1)

into equivalence classes.

Define

x \sim y

when

x - y

is a rational number. This is an equivalence relation (0.4): reflexive (

0

is rational), symmetric, and transitive (a sum of two rationals is rational).

Let

V

be a set containing exactly one point from each class.

This step uses the axiom of choice: from each of these classes (there are uncountably many) we pick one point, with no rule that says which.

The sets

V_q

q

rational in

[0,1)

, do not overlap.

For rational

q

[0,1)

the translates

V_q = V \oplus q

are pairwise disjoint. If

v \oplus q = w \oplus r

with

v, w \in V

, then

v - w

is rational, so

v \sim w

, so

v = w

(one point per class), and then

q = r

The sets

V_q

together fill

[0,1)

Take any

x \in [0,1)

. It is equivalent to the chosen point

v

of its class, so

x - v

is rational, and

x = v \oplus q

for a rational

q

[0, 1)

1 = P([0,1)) = \sum_q P(V_q) = c + c + c + \cdots

There are only countably many rationals (0.3), so countable additivity applies. Each

V_q

has the same probability

c = P(V)

by translation invariance.

Contradiction.

c = 0

the sum is

0

. If

c > 0

the partial sums grow past every number, so the sum is infinite. Neither equals

1

So a uniform random point of $[0,1)$ forces us to give up on measuring some sets. Lebesgue measure on the Borel sets (and a bit more) is consistent; the sets that cannot be measured are never needed in applications. The rest of this chapter works inside a sigma-algebra $\mathcal F$ and lets $P$ measure its members only.

Quick checkWhat does the Vitali theorem say about picking a uniform random point of [0, 1)?

Kolmogorov’s axioms

Definition A

Probability measure

A probability space is a triple $(\Omega, \mathcal F, P)$ :

$\Omega$ , the sample space, is a non-empty set whose points $\omega$ are the possible outcomes;
$\mathcal F$ , a sigma-algebra of subsets of $\Omega$ , whose members are called events;
$P$ $P$ , the probability measure, a function from $\mathcal F$ $F$ to the real numbers satisfying Kolmogorov’s three axioms:
1. $P(A) \ge 0$ for every event $A$ ;
2. $P(\Omega) = 1$ ;
3. (countable additivity) if $A_1, A_2, \dots$ are events and no two overlap ( $A_i \cap A_j = \varnothing$ for $i \ne j$ ), then $P(A_1 \cup A_2 \cup \cdots) = \sum_{i=1}^{\infty} P(A_i)$ .

In one lineA function $P$ on a sigma-algebra $\mathcal F$ of subsets of $\Omega$ with $P(A) \ge 0$ , $P(\Omega) = 1$ , and $P(A_1 \cup A_2 \cup \cdots) = P(A_1) + P(A_2) + \cdots$ for disjoint $A_1, A_2, \dots$ .

Why it existsThree short rules that every probability must obey, from which all the others (complement, inclusion-exclusion, continuity) are proved.

Where this came from· Kolmogorov's Grundbegriffe, 1933

Before 1933 several definitions of probability competed: equally likely cases, long-run frequencies, degrees of belief. Andrey Kolmogorov’s monograph Grundbegriffe der Wahrscheinlichkeitsrechnung (“Basic concepts of probability theory”) settled the mathematics by giving the axioms above, built on measure theory as Borel and Lebesgue had developed it around 1900 for length and area. The elements were already around: Borel had used countable additivity in 1909, and others had treated probability as a measure. Kolmogorov put them in one clean frame and showed that the standard theorems of probability, including the laws of large numbers, follow. He also kept the philosophy short: the axioms say nothing about what chance means in the world, only how chances must fit together. Shafer and Vovk’s 2006 article, in the Watch list, traces who contributed which piece.

Dice, coins and darts are all examples of the same definition.

Finite equally likely outcomes. $\Omega = \{1, \dots, 6\}$ , $\mathcal F$ is all subsets, $P(A) = |A|/6$ . This is the counting measure of the Example above, divided by $6$ so that the total is $1$ .
Countably many outcomes. Toss a coin until the first head: $\Omega = \{1, 2, 3, \dots\}$ , and $P(\{k\}) = 2^{-k}$ . The probabilities add to $\sum_{k \ge 1} 2^{-k} = 1$ (geometric series), and $P(A) = \sum_{k \in A} 2^{-k}$ .
A uniform point of an interval. $\Omega = [0, 1]$ , $\mathcal F$ the Borel sets, and $P$ gives each interval its length. An interval $[a, b]$ has $P = b - a$ , and a single point has $P = 0$ .

Now the work: what do the axioms prove? First, they imply finite additivity, so Apostol’s Theorems 13.1 and 13.2 apply to $P$ at once.

Theorem A Apostol 13.5 to 13.7; Kolmogorov 1933

Basic rules of probability

Let $(\Omega, \mathcal F, P)$ be a probability space and $A, B \in \mathcal F$ . Then

$P(\varnothing) = 0$ .
If $A \cap B = \varnothing$ then $P(A \cup B) = P(A) + P(B)$ (finite additivity); the same for any finite list of disjoint events.
$P(A^c) = 1 - P(A)$ .
If $A \subseteq B$ then $P(B \setminus A) = P(B) - P(A)$ and $P(A) \le P(B)$ .
$0 \le P(A) \le 1$ .
$P(A \cup B) = P(A) + P(B) - P(A \cap B)$ .

In one lineFrom the three axioms: $P(\varnothing) = 0$ ; probability is finitely additive; $P(A^c) = 1 - P(A)$ ; $A \subseteq B$ implies $P(A) \le P(B)$ ; every $P(A)$ lies in $[0, 1]$ ; and $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ .

Why it is trueThese are the rules students memorize. Here each is a line or two from the axioms, so none has to be taken on trust.

ProofApostol 13.5

The idea: Pad a finite list with empty sets to use axiom 3. Then the measure theorems of the previous section apply, and the rest are one-line consequences.

Part 1:

P(\varnothing) = 0

Axiom 3 with every

A_i = \varnothing

(disjoint, and their union is

\varnothing

) gives

P(\varnothing) = P(\varnothing) + P(\varnothing) + \cdots

. This is a series of equal non-negative real terms. If the common value

c

were positive, the series would be at least

c + c = 2c > c

, which cannot equal

c

Part 2:

P(A \cup B) = P(A) + P(B)

For disjoint

A, B

use axiom 3 with the list

A, B, \varnothing, \varnothing, \dots

and use part 1: the infinite sum is

P(A) + P(B) + 0 + 0 + \cdots

. A longer finite list works the same way.

Part 3:

P(A^c) = 1 - P(A)

A

and

A^c

are disjoint with union

\Omega

. By part 2 and axiom 2,

P(A) + P(A^c) = P(\Omega) = 1

Parts 4 and 6 are those theorems.

By part 2,

P

is a finitely additive measure on the Boolean algebra

\mathcal F

(axiom 1 gives non-negativity). So Theorems 13.1 and 13.2 above apply to it.

Part 5:

0 \le P(A) \le 1

P(A) \ge 0

is axiom 1.

A \subseteq \Omega

, so by part 4

P(A) \le P(\Omega) = 1

Worked example

Events A, B, C have P(A) = 0.5, P(B) = 0.4, P(C) = 0.3, P(A ∩ B) = 0.2, P(A ∩ C) = 0.1, P(B ∩ C) = 0.15 and P(A ∩ B ∩ C) = 0.05. Find the chance that at least one happens, and the chance that none does.

Solution.

Write the union of two pieces. $A \cup B \cup C = (A \cup B) \cup C$ . The two-set formula only handles two sets, so treat $A \cup B$ as one.
Apply the two-set formula. $P(A \cup B \cup C) = P(A \cup B) + P(C) - P\big((A \cup B) \cap C\big)$ . Rule 6 of the theorem, with $A \cup B$ in the role of $A$ .
Expand both unions. $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ , and $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ , whose two pieces overlap exactly in $A \cap B \cap C$ . So $P\big((A \cup B) \cap C\big) = P(A \cap C) + P(B \cap C) - P(A \cap B \cap C)$ . Rule 6 again, twice.
Combine. $P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(A \cap C) - P(B \cap C) + P(A \cap B \cap C)$ . Collect the terms: add the singles, subtract the pairs, add the triple.
Put in the numbers. $0.5 + 0.4 + 0.3 - 0.2 - 0.1 - 0.15 + 0.05 = 0.8$ . $1.2 - 0.45 + 0.05$ .
None happens. The event “none” is the complement of “at least one”, so its chance is $1 - 0.8 = 0.2$ . Rule 3.

Answer. At least one happens with chance $0.8$ , and none happens with chance $0.2$ . Steps 1 to 4 are the proof of inclusion-exclusion for three events: it holds for any three events.

The formula in step 4 is the inclusion-exclusion formula for three events. For $n$ events the pattern continues: add the singles, subtract the pairs, add the triples, and so on, with alternating signs. It follows by induction in the same way. MATH 431 uses it for $n$ events; we need only the case of two and three.

Theorem A Boole's inequality; Apostol 13.7

Union bound

For events $A_1, A_2, \dots$ (finitely or countably many), not necessarily disjoint, $P\big(\bigcup_n A_n\big) \le \sum_n P(A_n)$ .

In one lineFor any events $A_1, A_2, \dots$ , $P(A_1 \cup A_2 \cup \cdots) \le P(A_1) + P(A_2) + \cdots$ (overlaps are counted twice, so the sum can only be too big).

Why it is trueIt lets you bound the chance that any of many bad things happens by adding up their separate chances, without knowing how they overlap.

Proofstandard

The idea: Make the events disjoint without changing their union: keep only what is new at each step. Each new piece sits inside its original event.

Let

B_n

be what

A_n

adds beyond

A_1, \dots, A_{n-1}

Define

B_1 = A_1

and

B_n = A_n \setminus (A_1 \cup \cdots \cup A_{n-1})

: the part of

A_n

not already covered. Each

B_n

is an event, because a sigma-algebra is closed under finite unions and differences.

The

B_n

are disjoint with the same union.

A point of

\bigcup A_n

lies in a first

A_n

, and then it is in

B_n

and in no earlier

B_k

. So the

B_n

are disjoint and

\bigcup B_n = \bigcup A_n

P\big(\bigcup A_n\big) = \sum P(B_n)

Axiom 3 for the disjoint

B_n

\sum P(B_n) \le \sum P(A_n)

B_n \subseteq A_n

, so

P(B_n) \le P(A_n)

by monotonicity (Basic rules, part 4). Adding inequalities term by term keeps the inequality.

Worked example

A server has 5 failure modes. Each one separately has probability at most 0.01 in a given day. What is the largest the chance of at least one failure can be?

Solution.

Name the events. $A_i$ is “failure mode $i$ happens today”, with $P(A_i) \le 0.01$ for $i = 1, \dots, 5$ . We know nothing about how the modes overlap, so we cannot use inclusion-exclusion.
Apply the union bound. $P(A_1 \cup \cdots \cup A_5) \le P(A_1) + \cdots + P(A_5) \le 5 \times 0.01$ . The bound needs no independence.

Answer. At most $0.05$ . The bound is reached exactly when the failures never happen together; if they always happen together the chance is only $0.01$ .

Theorem A Apostol 13.21; Kolmogorov 1933

Continuity of probability

(Continuity from below.) If $A_1 \subseteq A_2 \subseteq \cdots$ and $A = \bigcup_n A_n$ , then $\lim_{n\to\infty} P(A_n) = P(A)$ .
(Continuity from above.) If $A_1 \supseteq A_2 \supseteq \cdots$ and $A = \bigcap_n A_n$ , then $\lim_{n\to\infty} P(A_n) = P(A)$ .

In one lineIf events grow, $A_1 \subseteq A_2 \subseteq \cdots$ , then $P(A_n) \to P(\bigcup A_n)$ . If events shrink, $A_1 \supseteq A_2 \supseteq \cdots$ , then $P(A_n) \to P(\bigcap A_n)$ .

Why it is trueIt says that probability of a limit is the limit of probabilities. It is where countable additivity pays off, and it is exactly what fails for the finitely additive measure above.

Proofstandard

The idea: From below, cut the growing sets into disjoint rings and add the series. From above, take complements and use the first part.

Part 1. Cut into rings.

Define

B_1 = A_1

and

B_n = A_n \setminus A_{n-1}

, the ring added at step

n

. The rings are disjoint (each point enters at one first step),

B_1 \cup \cdots \cup B_n = A_n

, and

\bigcup B_n = A

P(A) = \sum_{k=1}^{\infty} P(B_k)

Axiom 3 for the disjoint rings.

P(A) = \lim_n \sum_{k=1}^{n} P(B_k) = \lim_n P(A_n)

A series is the limit of its partial sums (1.6), and finite additivity gives

\sum_{k \le n} P(B_k) = P(A_n)

Part 2. Pass to complements.

If the

A_n

shrink, their complements

A_n^c

grow, and by De Morgan

\bigcup A_n^c = \big(\bigcap A_n\big)^c = A^c

1 - P(A_n) = P(A_n^c) \to P(A^c) = 1 - P(A)

, so

P(A_n) \to P(A)

Part 1 applied to the growing complements, then

P(E^c) = 1 - P(E)

for each event.

Part 2 uses that the whole space has finite size: step 5 subtracts from $P(\Omega) = 1$ . Without finiteness it is false. Count the elements of subsets of the counting numbers (a measure that can be infinite) and take $A_n = \{n, n+1, n+2, \dots\}$ . These shrink to the empty set, which has size $0$ , but every $A_n$ has infinite size, so the sizes do not tend to $0$ . Part 1 has no such restriction.

Worked example

A fair coin is tossed forever. Find the probability that a head eventually appears.

Solution.

Name the events. Let $A_n$ be “a head appears within the first $n$ tosses”. These events grow with $n$ .
Find $P(A_n)$ . The only way to avoid a head in $n$ tosses is $n$ tails, which has chance $2^{-n}$ . So $P(A_n) = 1 - 2^{-n}$ . Rule 3: complement of “all tails”.
Take the union. $\bigcup A_n$ is the event “a head appears at some time”. A head at toss $k$ puts the outcome in $A_k$ and every later $A_n$ .
Use continuity from below. $P\big(\bigcup A_n\big) = \lim_n (1 - 2^{-n}) = 1$ . The theorem above.

Answer. $1$ . Without countable additivity (continuity) we could not pass from the chances $1 - 2^{-n}$ to the chance of the infinite union. The finitely additive example above shows what goes wrong: it has $A_n = \{n, n+1, \dots\}$ shrinking to the empty set, yet $f(A_n) = 1$ for all $n$ .

Proof workshopRebuild the proof of continuity from below

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Updating a chance: conditional probability, independence, Bayes

Definition A

Conditional probability

Let $B$ be an event with $P(B) > 0$ . The conditional probability of an event $A$ given $B$ is

P(A \mid B) = \frac{P(A \cap B)}{P(B)}.

Picture the sample space as a region of total area $1$ . Learning that $B$ happened throws away everything outside $B$ . What is left has area $P(B)$ , so we divide by $P(B)$ to make the remaining region have area $1$ again. The part of $A$ still alive is $A \cap B$ .

In one line $P(A \mid B) = P(A \cap B)/P(B)$ : the chance of $A$ once we know that $B$ happened, defined when $P(B) > 0$ .

Why it existsNew information shrinks the sample space to B, and the chances inside B are rescaled so that they add to 1 again.

Theorem A Apostol 13.12

Conditional probability is a probability measure

Let $P(B) > 0$ and $Q(A) = P(A \mid B)$ . Then $Q$ is a probability measure on $(\Omega, \mathcal F)$ .

In one lineFor fixed $B$ with $P(B) > 0$ , the function $A \mapsto P(A \mid B)$ satisfies the three axioms, so every rule proved for $P$ holds for it.

Why it is trueIt saves work: complement, inclusion-exclusion and continuity are true for conditional probabilities without a new proof.

ProofApostol 13.12

The idea: Check the three axioms; countable additivity transfers because intersecting disjoint sets with B keeps them disjoint.

Axiom 1:

Q(A) \ge 0

A ratio of the non-negative number

P(A \cap B)

by the positive number

P(B)

Axiom 2:

Q(\Omega) = P(B)/P(B) = 1

\Omega \cap B = B

Axiom 3: for disjoint

A_i

Q\big(\bigcup A_i\big) = \dfrac{P\big(\bigcup (A_i \cap B)\big)}{P(B)}

A_1, A_2, \dots

are disjoint then so are

A_1 \cap B, A_2 \cap B, \dots

, and

\big(\bigcup A_i\big) \cap B = \bigcup (A_i \cap B)

= \sum_i \dfrac{P(A_i \cap B)}{P(B)} = \sum_i Q(A_i)

Countable additivity of

P

for the disjoint events

A_i \cap B

, then divide each term by

P(B)

Rearranging the definition gives the multiplication rule $P(A \cap B) = P(A \mid B)\,P(B)$ and, applying it twice, $P(A \cap B \cap C) = P(A)\,P(B \mid A)\,P(C \mid A \cap B)$ (when the events being conditioned on have positive probability).

Theorem A Apostol 13.12

Law of total probability

Let $B_1, B_2, \dots$ be a finite or countable list of disjoint events whose union is $\Omega$ (a partition of the sample space), each with $P(B_i) > 0$ . Then for every event $A$ , $P(A) = \sum_i P(A \mid B_i)\,P(B_i)$ .

In one lineIf $B_1, B_2, \dots$ are disjoint events with union $\Omega$ and each $P(B_i) > 0$ , then $P(A) = \sum_i P(A \mid B_i)\,P(B_i)$ .

Why it is trueIt computes a chance by splitting into cases, the way you do when you say 'first suppose it came from machine 1'.

Proofstandard

The idea: Cut A along the partition and add.

A = \bigcup_i (A \cap B_i)

and the pieces are disjoint.

Every outcome of

A

lies in exactly one

B_i

P(A) = \sum_i P(A \cap B_i)

Axiom 3.

= \sum_i P(A \mid B_i)\,P(B_i)

The multiplication rule applied to each term.

Theorem A Bayes 1763; Apostol 13.12

Bayes' theorem

Let $B_1, B_2, \dots$ be a partition of $\Omega$ with all $P(B_i) > 0$ and let $A$ be an event with $P(A) > 0$ . Then

P(B_j \mid A) = \frac{P(A \mid B_j)\,P(B_j)}{\sum_i P(A \mid B_i)\,P(B_i)}.

In one lineWith a partition $B_1, B_2, \dots$ as above and $P(A) > 0$ : $P(B_j \mid A) = \dfrac{P(A \mid B_j)P(B_j)}{\sum_i P(A \mid B_i)P(B_i)}$ .

Why it is trueIt reverses the direction of conditioning: from 'how likely is the evidence if this cause is true' to 'how likely is this cause given the evidence'.

Proofstandard

The idea: Write P(A and B_j) in two ways, and expand the denominator by total probability.

P(A \cap B_j) = P(B_j \mid A)\,P(A) = P(A \mid B_j)\,P(B_j)

The multiplication rule, used with the roles of

A

and

B_j

in both orders.

P(B_j \mid A) = \dfrac{P(A \mid B_j)\,P(B_j)}{P(A)}

Divide by

P(A) > 0

P(A) = \sum_i P(A \mid B_i)\,P(B_i)

, which gives the formula.

Law of total probability for

P(A)

Worked example

Machines 1, 2 and 3 make 50%, 30% and 20% of a factory's parts. Their defect rates are 1%, 2% and 3%. A part is found defective. What is the chance it came from machine 1?

Solution.

Name the events. $B_i$ is “the part came from machine $i$ ”, with $P(B_1) = 0.5$ , $P(B_2) = 0.3$ , $P(B_3) = 0.2$ . $D$ is “the part is defective”, with $P(D \mid B_1) = 0.01$ , $P(D \mid B_2) = 0.02$ , $P(D \mid B_3) = 0.03$ . The machines are a partition: every part has exactly one maker.
Total probability of a defect. $P(D) = 0.5(0.01) + 0.3(0.02) + 0.2(0.03) = 0.005 + 0.006 + 0.006 = 0.017$ . Split the defective parts by machine.
Apply Bayes. $P(B_1 \mid D) = \dfrac{0.005}{0.017} = \dfrac{5}{17}$ . The numerator is the share of defects that come from machine 1.
Check. The other two posteriors are $\tfrac{6}{17}$ and $\tfrac6{17}$ , and $\tfrac5{17} + \tfrac6{17} + \tfrac6{17} = 1$ . Given a defect, the cause must be one of the three machines.

Answer. $5/17 \approx 0.294$ . Machine 1 makes half the parts but only 29% of the defects, because it is the most careful.

Your answerIn the factory example, what is the chance a defective part came from machine 3?

Quick checkA test is 99% accurate in both directions (it flags 99% of sick people and clears 99% of healthy people). One person in 1000 is sick. A random person tests positive. Roughly how likely are they to be sick?

Definition A

Independent events

Events $A$ and $B$ are independent if $P(A \cap B) = P(A)\,P(B)$ . If $P(B) > 0$ this says $P(A \mid B) = P(A)$ : knowing $B$ does not change the chance of $A$ . Events $A_1, \dots, A_n$ are mutually independent if for every choice of indices $i_1 < \cdots < i_k$ ( $k \ge 2$ ), $P(A_{i_1} \cap \cdots \cap A_{i_k}) = P(A_{i_1}) \cdots P(A_{i_k})$ . They are pairwise independent if this holds only for $k = 2$ .

In one lineEvents $A$ and $B$ are independent when $P(A \cap B) = P(A)\,P(B)$ . Several events are mutually independent when this product rule holds for every sub-collection.

Why it existsIt captures 'learning one tells nothing about the other': when P(B) is positive, independence means P(A | B) = P(A).

Worked example

Toss two fair coins. A = first coin heads, B = second coin heads, C = the two coins agree. Show that A, B, C are pairwise independent but not mutually independent.

Solution.

List the sample space. HH, HT, TH, TT, each with chance $\tfrac14$ . $A = \{HH, HT\}$ , $B = \{HH, TH\}$ , $C = \{HH, TT\}$ . Four equally likely outcomes; each event is two of them.
Single chances. $P(A) = P(B) = P(C) = \tfrac12$ . Each event has two of the four outcomes.
Pairs. $A \cap B = \{HH\}$ , $A \cap C = \{HH\}$ , $B \cap C = \{HH\}$ , each with chance $\tfrac14 = \tfrac12 \cdot \tfrac12$ . The product rule holds for each pair, so the events are pairwise independent.
The triple. $A \cap B \cap C = \{HH\}$ has chance $\tfrac14$ , but $P(A)P(B)P(C) = \tfrac18$ . The product rule fails for the three together.

Answer. Pairwise independent, not mutually independent. Knowing $A$ and $B$ together determines $C$ completely, although any two of the three say nothing about each other.

Theorem A Apostol 13.13

Complements of independent events

If $P(A \cap B) = P(A)P(B)$ , then $P(A \cap B^c) = P(A)P(B^c)$ .

In one lineIf $A$ and $B$ are independent, so are $A$ and $B^c$ , $A^c$ and $B$ , and $A^c$ and $B^c$ .

Why it is trueIt says that independence is about the pair of questions, not about which answer you call success.

ProofApostol 13.13

The idea: Split A along B and subtract.

P(A \cap B^c) = P(A) - P(A \cap B)

A

is the disjoint union of

A \cap B

and

A \cap B^c

= P(A) - P(A)P(B)

The independence hypothesis.

= P(A)\,(1 - P(B)) = P(A)\,P(B^c)

Factor, and use

P(B^c) = 1 - P(B)

The other two statements follow by applying this one again with the roles swapped, then with $B^c$ in place of $B$ .

Quick checkA fair die is rolled once. A is 'the roll is 1' and B is 'the roll is 2'. Are A and B independent?

Quick checkA fair coin has landed heads 10 times in a row. What is the chance of heads on the next toss?

Numbers from outcomes: random variables and distribution functions

Definition A

Random variable

A random variable on $(\Omega, \mathcal F, P)$ is a function $X : \Omega \to \mathbb R$ such that for every real $x$ the set $\{\omega : X(\omega) \le x\}$ is an event (belongs to $\mathcal F$ ). We write this set as $\{X \le x\}$ and its probability as $P(X \le x)$ . Because a sigma-algebra is closed under countable operations, sets like $\{a < X \le b\}$ , $\{X = a\}$ and $\{X \in \text{an interval}\}$ are events too.

In one lineA function $X$ from the sample space to the real numbers such that each event 'X is at most x' is in the sigma-algebra, so that it has a probability.

Why it existsIt lets us ask numerical questions (how many heads, how long to wait) and answer them with the same measure P.

A random variable is a function, not a number and not random. The randomness is in which outcome $\omega$ occurs. Example: toss a fair coin three times, $\Omega$ the $8$ strings like HTH, and $X(\omega)$ the number of heads. Then $\{X = 2\} = \{HHT, HTH, THH\}$ and $P(X = 2) = \tfrac38$ .

Definition A

Distribution function

The distribution function (also called the cumulative distribution function, cdf) of a random variable $X$ is $F_X(x) = P(X \le x)$ , defined for every real $x$ .

In one line $F_X(x) = P(X \le x)$ : the probability that the random variable is at most $x$ , as a function of $x$ .

Why it existsOne function that records every probability the variable can answer, since all other probabilities about X are built from differences of F.

Theorem A Apostol 14.5 and 14.6

Properties of a distribution function

Let $F = F_X$ . Then:

If $x \le y$ then $F(x) \le F(y)$ .
$\lim_{x \to -\infty} F(x) = 0$ and $\lim_{x \to \infty} F(x) = 1$ .
$\lim_{t \downarrow x} F(t) = F(x)$ for every $x$ (right-continuous).
$P(a < X \le b) = F(b) - F(a)$ for $a < b$ .
$P(X = a) = F(a) - F(a^-)$ , where $F(a^-) = \lim_{t \uparrow a} F(t)$ (this limit exists by part 1).

In one line $F$ is non-decreasing, tends to 0 at minus infinity and to 1 at plus infinity, is continuous from the right, satisfies $P(a < X \le b) = F(b) - F(a)$ , and has $P(X = a) = F(a) - F(a^-)$ , the size of its jump at $a$ .

Why it is trueThese are exactly the facts that let you read probabilities off a graph of F, and they are where continuity of probability from the last section is used.

Proofstandard

The idea: Parts 1 and 4 are monotonicity and finite additivity. Parts 2, 3 and 5 pass to a limit along a monotone sequence of events, using continuity of probability.

Part 1:

F(x) \le F(y)

x \le y

then

\{X \le x\} \subseteq \{X \le y\}

, and probability is monotone.

Part 4:

F(b) = F(a) + P(a < X \le b)

\{X \le b\}

is the disjoint union of

\{X \le a\}

and

\{a < X \le b\}

. Finite additivity.

Part 2.

The events

\{X \le n\}

grow to

\Omega

(every

X(\omega)

is a real number, so it is at most

n

for large

n

). By continuity from below,

F(n) \to P(\Omega) = 1

. Since

F

is non-decreasing and bounded by

1

, the limit along all real

x

exists and has this value. For

-\infty

, the events

\{X \le -n\}

shrink to

\varnothing

, and continuity from above gives

F(-n) \to 0

Part 3.

For

t_n \downarrow x

the events

\{X \le t_n\}

shrink, and their intersection is

\{X \le x\}

. Continuity from above. Monotonicity of

F

then covers every way of approaching from the right.

Part 5:

P(X = a) = F(a) - F(a^-)

\{X = a\}

is the intersection of the shrinking events

\{a - \tfrac1n < X \le a\}

. Continuity from above gives

P(X = a) = \lim_n \big(F(a) - F(a - \tfrac1n)\big)

, using part 4.

Worked example

X is the number of heads in three fair coin tosses. Write F(x), and use it to find P(X = 2) and P(0 < X ≤ 2).

Solution.

The probabilities of single values. $P(X = 0), P(X = 1), P(X = 2), P(X = 3) = \tfrac18, \tfrac38, \tfrac38, \tfrac18$ . Counting: $\binom3k$ strings out of $8$ have $k$ heads.
Build $F$ by adding up. $F(x) = 0$ for $x < 0$ ; $\tfrac18$ for $0 \le x < 1$ ; $\tfrac12$ for $1 \le x < 2$ ; $\tfrac78$ for $2 \le x < 3$ ; $1$ for $x \ge 3$ . $F(x)$ adds the probabilities of all values at most $x$ . It is a staircase that jumps at each value.
Read the jump at 2. $P(X = 2) = F(2) - F(2^-) = \tfrac78 - \tfrac12 = \tfrac38$ . Part 5 of the theorem: the size of the jump.
Use differences. $P(0 < X \le 2) = F(2) - F(0) = \tfrac78 - \tfrac18 = \tfrac34$ . Part 4. Check by hand: $P(X = 1) + P(X = 2) = \tfrac38 + \tfrac38 = \tfrac34$ .

Answer. $P(X = 2) = \tfrac38$ and $P(0 < X \le 2) = \tfrac34$ .

Discrete and continuous distributions

Definition A

Probability mass function

A random variable $X$ is discrete if there is a countable set $S$ of values with $P(X \in S) = 1$ . Its probability mass function is $p(x) = P(X = x)$ . Then $p(x) \ge 0$ , $\sum_{x \in S} p(x) = 1$ , and $P(X \in A) = \sum_{x \in A} p(x)$ for any set $A$ of values, by countable additivity. Its distribution function is a staircase, as in the example above. Three discrete distributions appear everywhere.

Bernoulli( $p$ ): $P(X = 1) = p$ , $P(X = 0) = 1 - p$ . A single yes-or-no trial.
Binomial( $n, p$ ): the number of successes in $n$ independent trials of chance $p$ . Model: $\Omega = \{0,1\}^n$ with $P(\{\omega\}) = p^{k}(1-p)^{n-k}$ if $\omega$ has $k$ ones. These add to $(p + (1-p))^n = 1$ by the binomial theorem. The strings with $k$ ones number $\binom nk$ , so $P(X = k) = \binom nk p^k (1-p)^{n-k}$ .
Geometric( $p$ ): the number of trials up to and including the first success. $P(X = k) = (1-p)^{k-1}p$ for $k = 1, 2, \dots$ These add to $p \sum_{j \ge 0} (1-p)^j = p \cdot \frac1{p} = 1$ (geometric series, 1.6).

In one lineFor a random variable that takes only countably many values, $p(x) = P(X = x)$ . The values $p(x)$ are non-negative and add to 1.

Why it existsWhen the mass sits on separate points, listing the mass at each point says everything.

Definition A

Probability density function

A random variable $X$ has a probability density function $f$ if $f(t) \ge 0$ and, for every $x$ ,

F_X(x) = P(X \le x) = \int_{-\infty}^{x} f(t)\,dt.

Here $\int_{-\infty}^{x} f$ means $\lim_{a \to -\infty} \int_a^x f$ , the limit of ordinary Riemann integrals (1.5). For $f \ge 0$ this limit exists in $[0, \infty]$ , because the integral grows as $a$ decreases (a monotone sequence, 1.2). Write $\int_{-\infty}^{\infty} f$ for the whole mass. Such an integral over an unbounded interval is called an improper integral; the Riemann integral needs a bounded interval, and we take the limit.

In one lineA function $f \ge 0$ with $F_X(x) = \int_{-\infty}^{x} f(t)\,dt$ for all $x$ . Then probabilities of intervals are areas under $f$ .

Why it existsWhen the mass is spread smoothly along the line, no single point carries any, and only the density, the mass per unit length, makes sense.

What follows from this definition, using the theorem on distribution functions and the fundamental theorem of calculus (1.5):

$\int_{-\infty}^{\infty} f = \lim_{x \to \infty} F(x) = 1$ : the total area under a density is $1$ .
$P(a < X \le b) = F(b) - F(a) = \int_a^b f$ : probability is area.
$P(X = a) = F(a) - F(a^-) = 0$ , because $F$ is an integral and so has no jumps. Single points have probability $0$ .
Where $f$ is continuous, $F'(x) = f(x)$ .
$f(x)$ is not a probability. It is a probability per unit length and can exceed $1$ : the density $f(x) = 2$ on $[0, \tfrac12]$ is legitimate, since its area is $1$ .

The word “continuous” needs care. A random variable can have a distribution function $F$ with no jumps and still have no density, because $F$ need not be an integral of anything. The Cantor function, which climbs from $0$ to $1$ while being flat almost everywhere, is the standard example (label B; we do not use it). When we say “a continuous random variable” in this chapter we always mean one with a density.

Worked example

Find c so that f(x) = c·x² for 0 ≤ x ≤ 2 (and 0 elsewhere) is a density. For this X, find F, P(X > 1), E[X] and Var(X).

Solution.

Set the total area to 1. $\int_0^2 c\,x^2\,dx = c \cdot \tfrac83 = 1$ , so $c = \tfrac38$ . Antiderivative $x^3/3$ at $2$ gives $8/3$ . A density must have area $1$ .
Find $F$ . For $0 \le x \le 2$ , $F(x) = \int_0^x \tfrac38 t^2\,dt = \tfrac{x^3}{8}$ ; $F = 0$ for $x < 0$ and $F = 1$ for $x > 2$ . $F$ is the area under $f$ up to $x$ . Check: $F(2) = 1$ .
Tail probability. $P(X > 1) = 1 - F(1) = 1 - \tfrac18 = \tfrac78$ . Complement rule.
Mean. $E[X] = \int_0^2 x \cdot \tfrac38 x^2\,dx = \tfrac38 \cdot \tfrac{2^4}{4} = \tfrac32$ . Expectation of a density is $\int x f(x)\,dx$ (defined in the next section).
Second moment. $E[X^2] = \int_0^2 x^2 \cdot \tfrac38 x^2\,dx = \tfrac38 \cdot \tfrac{2^5}{5} = \tfrac{12}{5}$ . Same, with $x^2$ in place of $x$ .
Variance. $\operatorname{Var}(X) = \tfrac{12}{5} - \left(\tfrac32\right)^2 = \tfrac{48 - 45}{20} = \tfrac{3}{20}$ . Variance is second moment minus mean squared (proved below).

Answer. $c = \tfrac38$ , $P(X > 1) = \tfrac78$ , $E[X] = \tfrac32$ , $\operatorname{Var}(X) = \tfrac3{20}$ .

Your answerX has density f(x) = (3/8)x² on [0, 2]. What is P(X > 1)?

Quick checkIs f(x) = 2 for 0 ≤ x ≤ 1/2 (and 0 elsewhere) a valid probability density?

Three densities are worth knowing in full (Apostol 14.10, 14.13, 14.14).

Uniform on $[a, b]$ : $f(x) = \dfrac1{b-a}$ for $a \le x \le b$ . Area: $(b - a) \cdot \frac1{b-a} = 1$ . The chance of an interval inside $[a,b]$ is its length divided by $b - a$ .

Exponential with rate $\lambda > 0$ : $f(x) = \lambda e^{-\lambda x}$ for $x \ge 0$ (and $0$ for $x < 0$ ). The area is $\lim_{b \to \infty}\int_0^b \lambda e^{-\lambda x}\,dx = \lim_{b\to\infty}\big(1 - e^{-\lambda b}\big) = 1$ . It is the standard model of a waiting time. $P(X > x) = e^{-\lambda x}$ .

Theorem A Apostol 14.13

The exponential distribution forgets

For $X$ exponential with rate $\lambda$ and $s, t \ge 0$ : $P(X > s + t \mid X > s) = e^{-\lambda t} = P(X > t)$ .

In one lineIf $X$ is exponential with rate $\lambda$ , then $P(X > s + t \mid X > s) = P(X > t)$ for all $s, t \ge 0$ .

Why it is trueHaving already waited s minutes does not shorten the remaining wait. This 'memoryless' property is why the exponential is the waiting time of events that strike without wear.

ProofApostol 14.13

The idea: Use the definition of conditional probability and P(X > x) = e^(-lambda x).

P(X > s + t \mid X > s) = \dfrac{P(X > s + t)}{P(X > s)}

\{X > s + t\} \subseteq \{X > s\}

, so the intersection is

\{X > s + t\}

= \dfrac{e^{-\lambda(s+t)}}{e^{-\lambda s}}

P(X > x) = e^{-\lambda x}

from the density.

= e^{-\lambda t} = P(X > t)

The exponents subtract.

Worked example

The time until a server's next crash is exponential with mean 50 hours (so λ = 1/50 per hour). Find the chance it runs more than 80 hours before crashing, and the chance it runs more than 110 hours given that it has already run 30 without crashing.

Solution.

Unconditional. $P(X > 80) = e^{-80/50} = e^{-1.6} \approx 0.2019$ . $P(X > x) = e^{-\lambda x}$ .
Conditional. $P(X > 110 \mid X > 30) = P(X > 80) = e^{-1.6} \approx 0.2019$ . The memoryless property with $s = 30$ and $t = 80$ , since $110 = 30 + 80$ .

Answer. $e^{-1.6} \approx 0.202$ in both cases. A server that has already run 30 hours is, as far as the next crash is concerned, as good as a freshly started one: the remaining time has the same distribution as a new server’s.

Your answerA waiting time is exponential with rate 2 per minute. What is the chance the wait exceeds 1 minute? (Give e raised to a power, or a decimal.)

Normal (Gaussian) with mean $\mu$ and variance $\sigma^2$ : $f(x) = \dfrac{1}{\sigma\sqrt{2\pi}}\,e^{-(x-\mu)^2/(2\sigma^2)}$ . The special case $\mu = 0$ , $\sigma = 1$ is the standard normal density $\varphi(x) = \dfrac{1}{\sqrt{2\pi}}e^{-x^2/2}$ . That this really has area $1$ is a famous computation.

Theorem B Gauss; Apostol 14.14

The Gaussian integral

$\displaystyle I = \int_{-\infty}^{\infty} e^{-x^2/2}\,dx$ is finite and equals $\sqrt{2\pi}$ . Hence $\int \varphi = 1$ , and for any $\mu$ and $\sigma > 0$ the normal density with mean $\mu$ and variance $\sigma^2$ also has area $1$ .

In one line $\displaystyle\int_{-\infty}^{\infty} e^{-x^2/2}\,dx = \sqrt{2\pi}$ , so the standard normal density has total area 1.

Why it is trueThe antiderivative of e^(-x^2/2) is not an elementary function, so the area cannot be found by the fundamental theorem directly. Squaring the integral turns it into a two-dimensional one that polar coordinates can do.

Proofstandard; uses Fubini and polar coordinates from multivariable calculus (Apostol ch. 11)

The idea: Show the integral is finite by comparison. Square it, view the product as an integral over the plane, and switch to polar coordinates, where the radial integral has an elementary antiderivative.

The integral is finite:

e^{-x^2/2} \le e^{1/2}e^{-|x|}

, and the area under

e^{-|x|}

2

(|x| - 1)^2 \ge 0

gives

x^2/2 \ge |x| - \tfrac12

, so

e^{-x^2/2} \le e^{1/2}e^{-|x|}

. And

\int_0^b e^{-x}\,dx \le 1

for all

b

I^2 = \displaystyle\iint_{\mathbb R^2} e^{-(x^2+y^2)/2}\,dx\,dy

Because

e^{-(x^2+y^2)/2} = e^{-x^2/2}e^{-y^2/2}

, the product of the two one-variable integrals is a double integral over the whole plane (Fubini's theorem, a tool from multivariable calculus that we use without proof).

= \displaystyle\int_0^{2\pi}\int_0^{\infty} e^{-r^2/2}\,r\,dr\,d\theta

Substitute

x = r\cos\theta

y = r\sin\theta

. The plane is covered by

r \ge 0

0 \le \theta < 2\pi

, and the area element becomes

r\,dr\,d\theta

(change of variables in a double integral, also taken from multivariable calculus).

The inner integral is

1

, so

I^2 = 2\pi \cdot 1 = 2\pi

An antiderivative of

r\,e^{-r^2/2}

-e^{-r^2/2}

, so

\int_0^b r e^{-r^2/2}\,dr = 1 - e^{-b^2/2} \to 1

b \to \infty

. This is the fundamental theorem of calculus (1.5).

I = \sqrt{2\pi}

I > 0

because the integrand is positive, so we take the positive square root.

So the normal density with parameters

\mu

\sigma^2

has area

1

For the general case substitute

u = (x - \mu)/\sigma

dx = \sigma\,du

: the factor

\frac1{\sigma\sqrt{2\pi}}

times

\sigma\sqrt{2\pi}

1

The plane-integral step uses outside tools, which is why this theorem is labelled B. Everything else in the chapter is proved from the axioms and the one-variable integral. A numerical check is easy: the area under $\varphi$ between $-1.96$ and $1.96$ is about $0.95$ , and between $-1$ and $1$ about $0.683$ .

Your answerFor the standard normal density, the area between −1 and 1 is about 0.6827. Using symmetry, what is the area to the right of 1 (to 3 decimal places)?

The centre and the spread: expectation and variance

Definition A

Expectation

Let $X$ be a random variable. If $X$ is discrete with mass function $p$ and $\sum_x |x|\,p(x) < \infty$ , its expectation (mean, expected value) is $E[X] = \sum_x x\,p(x)$ . If $X$ has a density $f$ and $\int_{-\infty}^{\infty} |x|\,f(x)\,dx < \infty$ , then $E[X] = \int_{-\infty}^{\infty} x\,f(x)\,dx$ . The requirement of absolute convergence is not a pedantic extra: a series that converges only conditionally can be rearranged to any sum (1.6), so the average would depend on the order of the outcomes. If the condition fails, we say $E[X]$ does not exist. The same two formulas with $g(x)$ in place of $x$ give $E[g(X)]$ (Apostol 14.26).

In one lineThe probability-weighted average of the values of $X$ : $E[X] = \sum x\,p(x)$ for a discrete variable and $E[X] = \int x f(x)\,dx$ for one with a density, when these converge absolutely.

Why it existsIt is the single number that the average of many repeated trials settles to, and the balance point of the mass.

Balance-point picture: put the mass on a ruler. $E[X]$ is where the ruler balances.

Worked example

Roll a fair die and let X be the number shown. Find E[X], E[X²] and the variance.

Solution.

Mean. $E[X] = \tfrac16(1 + 2 + 3 + 4 + 5 + 6) = \tfrac{21}{6} = \tfrac72$ . Each value has $p(x) = \tfrac16$ .
Second moment. $E[X^2] = \tfrac16(1 + 4 + 9 + 16 + 25 + 36) = \tfrac{91}{6}$ . The formula for $E[g(X)]$ with $g(x) = x^2$ .
Variance. $\operatorname{Var}(X) = E[X^2] - E[X]^2 = \tfrac{91}{6} - \tfrac{49}{4} = \tfrac{182 - 147}{12} = \tfrac{35}{12} \approx 2.917$ . The variance shortcut, proved below.

Answer. $E[X] = 3.5$ (a value the die can never show: the mean is a balance point, not a typical outcome), $E[X^2] = 91/6$ , $\operatorname{Var}(X) = 35/12$ .

Theorem A Apostol 14.25 and 14.26

Linearity of expectation

Let $\Omega$ be countable, with $\mathcal F$ all subsets so that every single outcome is an event, and let $X, Y$ be random variables with $E|X| < \infty$ and $E|Y| < \infty$ . Then $E[X + Y] = E[X] + E[Y]$ , and $E[aX + b] = aE[X] + b$ for constants $a, b$ . (The same is true in general. The proof for densities uses the joint density of two variables, Apostol 14.21, which we do not develop.)

In one lineFor random variables on a countable sample space with finite expectation, $E[X + Y] = E[X] + E[Y]$ and $E[aX + b] = aE[X] + b$ .

Why it is trueNo independence is needed. It is the most useful rule in probability, because it lets you find an average by adding the averages of simple pieces.

Proofstandard

The idea: On a countable sample space the expectation is a sum over outcomes. Sums add, and constants pull out.

E[X] = \sum_x x\,P(X = x) = \sum_{\omega} X(\omega)\,P(\{\omega\})

Group the outcomes by the value of

X

: the outcomes with

X(\omega) = x

contribute

x \cdot P(X = x)

in total. The series converges absolutely, so the grouping and the order do not matter (rearrangement of absolutely convergent series).

E[X + Y] = \sum_\omega \big(X(\omega) + Y(\omega)\big)P(\{\omega\})

The same formula for the random variable

X + Y

= \sum_\omega X(\omega)P(\{\omega\}) + \sum_\omega Y(\omega)P(\{\omega\}) = E[X] + E[Y]

Two absolutely convergent series can be added term by term.

E[aX + b] = a\sum_\omega X(\omega)P(\{\omega\}) + b\sum_\omega P(\{\omega\}) = aE[X] + b

Constants come out of an absolutely convergent sum, and

\sum_\omega P(\{\omega\}) = 1

Definition A

Variance

If $E[X] = \mu$ exists and $E[(X - \mu)^2] < \infty$ , the variance of $X$ is $\operatorname{Var}(X) = E[(X - \mu)^2]$ . The standard deviation is $\sigma = \sqrt{\operatorname{Var}(X)}$ , in the same units as $X$ .

In one line $\operatorname{Var}(X) = E\big[(X - \mu)^2\big]$ with $\mu = E[X]$ : the average squared distance from the mean, a measure of spread.

Why it existsAveraging the distance itself would cancel (the signed distances average to 0). Squaring makes every deviation count, and it gives the algebra that makes Chebyshev's inequality work.

Theorem A Apostol 14.25

Variance shortcut and scaling

If $\operatorname{Var}(X)$ exists, then $\operatorname{Var}(X) = E[X^2] - \mu^2$ with $\mu = E[X]$ , and $\operatorname{Var}(aX + b) = a^2\operatorname{Var}(X)$ .

In one line $\operatorname{Var}(X) = E[X^2] - (E[X])^2$ and $\operatorname{Var}(aX + b) = a^2\operatorname{Var}(X)$ .

Why it is trueThe shortcut is the form used for every computation. The scaling rule says shifting does not change spread and stretching by a stretches the spread by a.

Proofstandard

The idea: Expand the square and use linearity of expectation.

\operatorname{Var}(X) = E[X^2 - 2\mu X + \mu^2]

Expand

(X - \mu)^2 = X^2 - 2\mu X + \mu^2

= E[X^2] - 2\mu E[X] + \mu^2 = E[X^2] - 2\mu^2 + \mu^2

Linearity:

\mu

is a constant.

= E[X^2] - \mu^2

Combine.

Scaling:

\operatorname{Var}(aX + b) = E[a^2(X - \mu)^2] = a^2\operatorname{Var}(X)

E[aX + b] = a\mu + b

by linearity, so

(aX + b) - (a\mu + b) = a(X - \mu)

Worked example Apostol 14.10 and 14.13

Find the mean and variance of the uniform distribution on [a, b], and of the exponential distribution with rate λ.

Solution.

Uniform mean. $E[X] = \int_a^b \dfrac{x}{b-a}\,dx = \dfrac{b^2 - a^2}{2(b-a)} = \dfrac{a+b}{2}$ . The midpoint: the ruler balances at the middle.
Uniform second moment. $E[X^2] = \dfrac{b^3 - a^3}{3(b-a)} = \dfrac{a^2 + ab + b^2}{3}$ . $b^3 - a^3 = (b-a)(a^2 + ab + b^2)$ .
Uniform variance. $\dfrac{a^2+ab+b^2}{3} - \dfrac{(a+b)^2}{4} = \dfrac{4a^2 + 4ab + 4b^2 - 3a^2 - 6ab - 3b^2}{12} = \dfrac{(b-a)^2}{12}$ . Common denominator $12$ and the shortcut formula.
Exponential mean. $\int_0^b x\lambda e^{-\lambda x}\,dx = \Big[-\big(x + \tfrac1\lambda\big)e^{-\lambda x}\Big]_0^b \to \tfrac1\lambda$ as $b \to \infty$ . Differentiate the bracket to check it is an antiderivative. The term $b\,e^{-\lambda b}$ tends to $0$ because an exponential beats any power.
Exponential second moment. An antiderivative of $x^2\lambda e^{-\lambda x}$ is $-\big(x^2 + \tfrac{2x}\lambda + \tfrac2{\lambda^2}\big)e^{-\lambda x}$ , so $E[X^2] = \tfrac{2}{\lambda^2}$ . Same method: integrating by parts reduces the power of $x$ by one each time.
Exponential variance. $\tfrac2{\lambda^2} - \tfrac1{\lambda^2} = \tfrac1{\lambda^2}$ . The shortcut formula.

Answer. Uniform: mean $\tfrac{a+b}2$ , variance $\tfrac{(b-a)^2}{12}$ . Exponential: mean $\tfrac1\lambda$ , variance $\tfrac1{\lambda^2}$ (so the standard deviation equals the mean). For the normal distribution with parameters $\mu$ and $\sigma^2$ : the mean is $\mu$ (the density is symmetric about $\mu$ ) and the variance is $\sigma^2$ (integrate $x^2\varphi$ by parts: $\int x \cdot x\varphi = [-x\varphi] + \int\varphi = 1$ for the standard case, then scale by the scaling rule).

Your answerX is uniform on [0, 6]. What is Var(X)?

Quick checkX has density 1/(π(1 + x²)) on the whole real line (the Cauchy distribution). Does X have an expectation?

To combine variances we need independent random variables.

Definition A

Independent random variables

Random variables $X$ and $Y$ on the same probability space are independent if for all intervals $A, B$ of the real line the events $\{X \in A\}$ and $\{Y \in B\}$ are independent. For discrete variables this includes $P(X = x, Y = y) = P(X = x)P(Y = y)$ for all values $x, y$ . A list $X_1, \dots, X_n$ is independent if the events $\{X_i \in A_i\}$ are mutually independent for all intervals $A_i$ .

In one line $X$ and $Y$ are independent when every event about $X$ is independent of every event about $Y$ : $P(X \in A, Y \in B) = P(X \in A)P(Y \in B)$ for all intervals $A$ , $B$ .

Why it existsIt is independence of events transferred to numbers, and it is what lets variances of sums add.

Theorem A Apostol 14.25

Variance of a sum of independent variables

Let $X, Y$ be independent discrete random variables with finite variance. Then $\operatorname{Var}(X + Y) = \operatorname{Var}(X) + \operatorname{Var}(Y)$ . The same is true for random variables with densities (Apostol 14.21 and 14.25), and by induction for any finite list of independent variables.

In one lineIf $X$ and $Y$ are independent discrete random variables with finite variance, then $E[XY] = E[X]E[Y]$ and $\operatorname{Var}(X + Y) = \operatorname{Var}(X) + \operatorname{Var}(Y)$ .

Why it is trueIt is why the spread of an average of n independent measurements shrinks like one over the square root of n: variances add, and the standard deviation grows only like the square root.

Proofstandard

The idea: Expand the square of X+Y minus its mean. The cross term has mean zero because, for independent variables, the mean of the product is the product of the means.

E[XY] = \sum_{x,y} xy\,p_X(x)p_Y(y) = \Big(\sum_x x\,p_X(x)\Big)\Big(\sum_y y\,p_Y(y)\Big) = E[X]E[Y]

Independence gives

P(X = x, Y = y) = p_X(x)\,p_Y(y)

. The double series for

E|XY|

converges because it factors as

E|X|\cdot E|Y|

. A series of non-negative terms can be summed in either order, and for absolutely convergent series the same holds.

Then

E[X'Y'] = E[X']E[Y'] = 0

Let

X' = X - \mu_X

and

Y' = Y - \mu_Y

. They are again independent (shifting does not change which events about them are independent), and

E[X'] = E[Y'] = 0

\operatorname{Var}(X + Y) = E[X'^2] + 2E[X'Y'] + E[Y'^2]

Expand

(X' + Y')^2 = X'^2 + 2X'Y' + Y'^2

and use linearity. The mean of

X + Y

\mu_X + \mu_Y

= \operatorname{Var}(X) + \operatorname{Var}(Y)

The middle term is

0

Worked example

X is binomial with n = 10 and p = 0.3: the number of successes in 10 independent trials. Find E[X] and Var(X).

Solution.

Write $X$ as a sum. $X = I_1 + \cdots + I_{10}$ , where $I_k = 1$ if trial $k$ succeeds and $0$ otherwise. Each $I_k$ is a Bernoulli( $0.3$ ) variable, and the trials are independent.
Mean of one trial. $E[I_k] = 0.3$ . $1 \cdot 0.3 + 0 \cdot 0.7$ .
Variance of one trial. $E[I_k^2] = 0.3$ (since $I_k^2 = I_k$ ), so $\operatorname{Var}(I_k) = 0.3 - 0.09 = 0.21$ . Shortcut formula.
Add up. $E[X] = 10 \times 0.3 = 3$ by linearity, and $\operatorname{Var}(X) = 10 \times 0.21 = 2.1$ since variances of independent variables add. The last two theorems.

Answer. $E[X] = 3$ , $\operatorname{Var}(X) = 2.1$ . In general, a binomial has mean $np$ and variance $np(1-p)$ .

Chebyshev’s inequality and the law of large numbers

Variance measures spread. The next theorem makes that precise: a small variance forces the variable to stay close to its mean.

Where this came from· Chebyshev and the road to the law of large numbers

Jacob Bernoulli’s proof that relative frequencies settle near the true probability appeared in 1713 and was elaborate. The inequality below gives a short proof. Irénée-Jules Bienaymé stated it in 1853, and Pafnuty Chebyshev published a general form in 1867, using it to prove a law of large numbers; the inequality now carries Chebyshev’s name, though some authors write Bienaymé–Chebyshev. The name “law of large numbers” is Siméon-Denis Poisson’s, from the 1830s. Chebyshev’s student Andrey Markov later studied sequences whose steps depend on each other (see 2.11).

Theorem A Markov; standard

Markov's inequality

Let $Y$ be a random variable with $Y \ge 0$ and finite expectation, and let $a > 0$ . Then $P(Y \ge a) \le \dfrac{E[Y]}{a}$ .

In one lineIf $Y \ge 0$ and $a > 0$ , then $P(Y \ge a) \le E[Y]/a$ .

Why it is trueA non-negative quantity with a small average cannot often be large. It is the first step to Chebyshev.

Proofstandard

The idea: Compare Y with a times the indicator of the event 'Y at least a'. Pointwise, the second is smaller, so its expectation is smaller.

For every outcome,

a\,\mathbf 1_{\{Y \ge a\}}(\omega) \le Y(\omega)

, where

\mathbf 1_{\{Y \ge a\}}

1

when

Y \ge a

and

0

otherwise.

Y(\omega) \ge a

, the left side is

a

and the right side is

Y(\omega) \ge a

. If

Y(\omega) < a

, the left side is

0

and the right side is

Y(\omega) \ge 0

Take expectations:

a\,E\big[\mathbf 1_{\{Y \ge a\}}\big] \le E[Y]

Expectation preserves inequalities: if

U \le V

pointwise then

E[U] \le E[V]

. For a discrete variable the sums compare term by term, and for a density the integrals compare by monotonicity of the integral (1.5).

a\,P(Y \ge a) \le E[Y]

The indicator takes the value

1

with probability

P(Y \ge a)

and

0

otherwise, so its mean is

P(Y \ge a)

. Divide by

a > 0

Theorem A Apostol Thm 14.11

Chebyshev's inequality

Let $X$ have mean $\mu$ and variance $\sigma^2 < \infty$ . Then for every $c > 0$ ,

P\big(|X - \mu| \ge c\big) \le \frac{\sigma^2}{c^2}.

Equivalently, with $c = k\sigma$ : the chance of being at least $k$ standard deviations away from the mean is at most $1/k^2$ .

In one lineIf $X$ has mean $\mu$ and finite variance, then for every $c > 0$ , $P(|X - \mu| \ge c) \le \operatorname{Var}(X)/c^2$ .

Why it is trueIt bounds the chance of a large deviation using only the variance, without knowing the distribution. It is crude but universal, which is exactly what the law of large numbers needs.

Proofstandard

The idea: Apply Markov's inequality to the squared deviation. The event 'distance at least c' is the same as 'squared distance at least c squared'.

Let

Y = (X - \mu)^2 \ge 0

Put

Y = (X - \mu)^2

. It is non-negative, and

E[Y] = \operatorname{Var}(X) = \sigma^2

by the definition of variance.

The events

\{|X - \mu| \ge c\}

and

\{Y \ge c^2\}

are the same.

Squaring is an increasing function on non-negative numbers, so

|X - \mu| \ge c

exactly when

(X - \mu)^2 \ge c^2

P(|X - \mu| \ge c) = P(Y \ge c^2) \le \dfrac{E[Y]}{c^2}

Markov's inequality with

a = c^2 > 0

= \dfrac{\sigma^2}{c^2}

Substitute

E[Y] = \sigma^2

Why· The picture behind the proof

In the histogram at the top of the page, the variance is the average of the squared distance from the centre. If a lot of mass sat far out, at distance $c$ or more, each unit of that mass would contribute at least $c^2$ to this average, so the average would be at least $c^2$ times the far-out mass. The variance is a fixed number $\sigma^2$ , which caps the far-out mass at $\sigma^2/c^2$ . The proof says exactly this with symbols: the shaded tails count at least $c^2$ each.

Proof workshopRebuild the proof of Chebyshev's inequality

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Worked example the method of Apostol 14.29

A fair die is rolled n times and the average of the rolls is taken. How many rolls guarantee, with probability at least 90%, that the average is within 0.1 of 3.5? Use Chebyshev. Then compare with the normal approximation.

Solution.

Set up. Let $\bar X$ be the average of the $n$ rolls. $E[\bar X] = 3.5$ and one roll has variance $\tfrac{35}{12}$ . Both were found in the die example above.
Variance of the average. $\operatorname{Var}(\bar X) = \dfrac{1}{n^2}\cdot n \cdot \dfrac{35}{12} = \dfrac{35}{12n}$ . Variances of independent rolls add, and dividing by $n$ divides the variance by $n^2$ (scaling rule).
Apply Chebyshev. $P\big(|\bar X - 3.5| \ge 0.1\big) \le \dfrac{35/(12n)}{0.1^2} = \dfrac{291.67}{n}$ . $c = 0.1$ , so $c^2 = 0.01$ , and $\tfrac{35}{12} \div 0.01 = 291.67$ .
Make the bound at most $0.1$ . $\dfrac{291.67}{n} \le 0.1$ gives $n \ge 2916.7$ , so $n = 2917$ . “At least 90% within” means at most 10% outside. Divide $291.67$ by $0.1$ and round up.
Compare with the truth. The normal approximation (the central limit theorem, Apostol 14.30) says that $P(|Z| \le 1.645) = 0.90$ for a standard normal $Z$ , so we need $1.645 \times \sqrt{35/(12n)} \le 0.1$ , which gives $n \ge 790$ . The standard deviation of $\bar X$ is $\sqrt{35/(12n)}$ , and a 90% band is about $1.645$ standard deviations wide on each side.

Answer. Chebyshev guarantees that $n = 2917$ rolls suffice. About $790$ are really needed. Chebyshev is safe for every distribution and therefore loose for this one.

Your answerBy Chebyshev's inequality, how many rolls of a fair die make P(|average − 3.5| ≥ 0.1) at most 0.1?

Theorem A Bernoulli 1713; Chebyshev 1867; Apostol 14.29

Weak law of large numbers

Let $X_1, X_2, \dots$ be independent random variables with $E[X_i] = \mu$ and $\operatorname{Var}(X_i) = \sigma^2 < \infty$ , and let $\bar X_n = (X_1 + \cdots + X_n)/n$ . Then for every $\varepsilon > 0$ and every $n$ ,

P\big(|\bar X_n - \mu| \ge \varepsilon\big) \le \frac{\sigma^2}{n\varepsilon^2}, \qquad\text{so}\qquad \lim_{n\to\infty} P\big(|\bar X_n - \mu| \ge \varepsilon\big) = 0.

In one lineIf $X_1, X_2, \dots$ are independent with the same mean $\mu$ and the same finite variance $\sigma^2$ , then for every $\varepsilon > 0$ , $P(|\bar X_n - \mu| \ge \varepsilon) \le \dfrac{\sigma^2}{n\varepsilon^2} \to 0$ .

Why it is trueIt turns 'averages settle to the mean' into a statement with a number: the chance of an error of size epsilon after n trials is at most sigma squared over n epsilon squared.

ProofApostol 14.29

The idea: Find the mean and variance of the average, then apply Chebyshev's inequality to it.

E[\bar X_n] = \dfrac{1}{n}(\mu + \cdots + \mu) = \mu

Linearity of expectation.

\operatorname{Var}(\bar X_n) = \dfrac{1}{n^2}\,(\sigma^2 + \cdots + \sigma^2) = \dfrac{\sigma^2}{n}

Variances of independent variables add, and the scaling rule divides by

n^2

P\big(|\bar X_n - \mu| \ge \varepsilon\big) \le \dfrac{\operatorname{Var}(\bar X_n)}{\varepsilon^2} = \dfrac{\sigma^2}{n\varepsilon^2}

Chebyshev's inequality for the random variable

\bar X_n

, with

c = \varepsilon

The bound tends to

0

\sigma^2

and

\varepsilon

are fixed, so

\sigma^2/(n\varepsilon^2) \to 0

n \to \infty

Our proof of the variance rule covered discrete variables; for variables with densities the same argument works with joint densities. The finite variance is a hypothesis of this proof, because Chebyshev’s inequality needs it. A finer argument, by Khinchin in 1929, shows that for independent variables with the same distribution a finite mean alone is enough. The theorem is about the chance of a deviation, not about every single run. It does not say the running average of one particular sequence stays within $\varepsilon$ forever (that is the strong law, proved by Borel in 1909; it needs more). Nor does it say that heads must catch up after a long run of tails: independence means the past carries no information. And it needs a mean to exist. For the Cauchy distribution the average of $n$ samples is again Cauchy, however large $n$ is, and never settles. The lab below shows both behaviours.

Python labThe law of large numbers, and how loose Chebyshev's bound is

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(7)
var = 35 / 12                                    # variance of one fair die
eps, runs = 0.5, 20000
print("n     Chebyshev bound   observed frequency of |mean - 3.5| >= 0.5")
for n in (10, 100, 1000):
    means = rng.integers(1, 7, size=(runs, n)).mean(axis=1)
    print(f"{n:<5d} {var / (n * eps**2):<17.4f} {np.mean(np.abs(means - 3.5) >= eps):.4f}")

n = 3000
paths = rng.integers(1, 7, size=(4, n)).cumsum(axis=1) / np.arange(1, n + 1)
for p in paths:
    plt.plot(p)
plt.axhline(3.5, color="black", lw=1)
plt.xlabel("number of rolls n"); plt.ylabel("average of the first n rolls")
plt.title("Four runs of the running average of a fair die")

Try this. At n = 100 the Chebyshev bound is 0.1167 but the observed frequency of a deviation of at least 0.5 is about 0.004: about 30 times smaller. At n = 10 the bound exceeds 1, which says nothing. Now change rng.integers(1, 7, size=(4, n)) in the plot to rng.standard_cauchy(size=(4, n)) and run again. The running averages of Cauchy samples keep making large jumps even at n = 3000, because the Cauchy distribution has no mean.

Quick checkBy the weak law of large numbers, what happens to the chance that the average of n fair-die rolls differs from 3.5 by at least 0.2?

Beyond the course: for understanding· What Chebyshev cannot say: the central limit theorem

Chebyshev’s bound $1/k^2$ is the same for every distribution. For the average of many independent variables the truth is much smaller and has a universal shape: the average, standardized to have mean $0$ and standard deviation $1$ , has a distribution that approaches the standard normal (Apostol 14.30). For the standardized coin average this gives about $0.0455$ for a deviation of two standard deviations, where Chebyshev gives $0.25$ . The theorem is the reason the normal curve is everywhere, and it is the tool behind confidence intervals and the A/B test below. Its proof needs more machinery than this chapter develops.

Examples and non-examples

The worked examples sit beside the ideas they practise, above. Four short contrasts to keep straight.

Probability, not a probability. $\mu(A) = |A|$ on a finite set is a measure but not a probability (the total is $|S|$ , not $1$ ). Dividing by $|S|$ makes it one. Length on $[0, 5]$ is a measure of total $5$ ; dividing by $5$ gives the uniform probability.

Additive, not countably additive. The finite/cofinite set function of the quiz is finitely additive and fails continuity. It is not a probability measure, since $\mathbb N$ is a countable union of sets of size $0$ and has size $1$ .

A density, not a probability. $f(x) = 2$ on $[0, \frac12]$ is a density, and $f(0.1) = 2$ is not a probability. $P(X = 0.1) = 0$ .

A mean that does not exist. The Cauchy density is symmetric, area $1$ , and has no mean. Variance and the law of large numbers need the mean to exist first.

Where it is used

Used inside maths· Inside maths: Bernstein polynomials prove Weierstrass's approximation theorem with Chebyshev's inequality

Weierstrass (1885) proved that every continuous function on $[0, 1]$ is a uniform limit of polynomials. Sergei Bernstein (1912) gave an explicit proof that is a law of large numbers in disguise. For $f$ continuous on $[0,1]$ let

B_n f(x) = \sum_{k=0}^{n} f\!\left(\tfrac kn\right)\binom nk x^k (1-x)^{n-k} = E\big[f(S_n/n)\big],

where $S_n$ is binomial with $n$ trials and success chance $x$ . So $B_nf(x)$ is the average of $f$ at the random point $S_n/n$ , and by the law of large numbers $S_n/n$ is near $x$ with high probability.

Claim: $B_nf \to f$ uniformly on $[0, 1]$ .

|B_nf(x) - f(x)| \le \varepsilon + 2M\,P(|Y - x| \ge \delta) \le \varepsilon + 2M\,\frac{x(1-x)}{n\delta^2} \le \varepsilon + \frac{M}{2n\delta^2}.

The middle step is Chebyshev with $\operatorname{Var}(Y) = x(1-x)/n$ ; the last uses $x(1-x) \le \frac14$ . The bound does not depend on $x$ , so for $n > M/(2\varepsilon\delta^2)$ the error is below $2\varepsilon$ everywhere. $\blacksquare$

For $f(x) = |x - \frac12|$ the largest error is about $0.123$ at $n = 10$ , $0.040$ at $n = 100$ and $0.0126$ at $n = 1000$ : slow, but guaranteed. Compare 15.1: interpolating at equally spaced points does not converge for every continuous function, which is a reason to value this proof.

Used inside maths· Inside maths: the probabilistic method (a cut that cuts at least half the edges)

To show something exists, show it has positive probability. A graph with $m$ edges: split its vertices into two groups by tossing a fair coin for each vertex. An edge is cut when its endpoints land in different groups, which has chance $\frac12$ . Let $C$ be the number of cut edges; it is the sum of $m$ indicators, each with mean $\frac12$ , so $E[C] = m/2$ by linearity (no independence needed). A random variable cannot be always below its mean, so some split has $C \ge m/2$ . Check on $K_4$ (four vertices, all six edges): the average cut over the $16$ splits is $3 = 6/2$ , and the best split puts two vertices on each side and cuts $4$ edges. The proof gives a guarantee without constructing the split.

Used in the real world· Monte Carlo: estimating π, an integral, or a price by random sampling

Throw $n$ random points into the unit square. A point $(x, y)$ is a hit if $x^2 + y^2 < 1$ , and the chance of a hit is the area of the quarter disc, $\pi/4$ . So $\hat\pi = 4 \times (\text{hits})/n$ . Each throw is Bernoulli( $\pi/4$ ), so $\operatorname{Var}(\hat\pi) = 16 \cdot \frac\pi4\left(1 - \frac\pi4\right)/n \approx 2.697/n$ and the standard deviation is about $1.642/\sqrt n$ . At $n = 10^6$ the typical error is $0.0016$ : three correct digits. The error shrinks like $1/\sqrt n$ whatever the problem, so each extra digit costs a hundred times more samples. Chebyshev gives a guarantee: $P(|\hat\pi - \pi| \ge 0.01) \le 2.697/(n \cdot 10^{-4})$ , below $0.05$ once $n \ge 540000$ .

The same idea estimates any integral, as an expectation: $\int_0^1 g(x)\,dx = E[g(U)]$ for $U$ uniform. With $g(x) = 4/(1+x^2)$ the integral is $\pi$ , and $g(U)$ has variance $2\pi + 4 - \pi^2 \approx 0.414$ , about $6.5$ times smaller than the hit-or-miss variance. Same answer, a sixth of the samples. Physicists at Los Alamos built the method in the 1940s: Stanisław Ulam, thinking in 1946 about the chance of winning a game of solitaire, saw that one could estimate it by playing many random games, and John von Neumann and others turned the idea to neutron diffusion. Today it prices financial options, renders film frames (path tracing averages random light paths per pixel, which is why images look grainy until enough samples accumulate), and, as Markov chain Monte Carlo (2.11), samples from Bayesian posteriors.

Python labMonte Carlo estimate of π: the error really falls like 1/√n

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(3)
print("n        typical error (sd over 200 runs)   1.642/sqrt(n)")
for n in (100, 1_000, 10_000):
    est = 4 * (rng.random((200, n))**2 + rng.random((200, n))**2 < 1).mean(axis=1)
    print(f"{n:<8d} {est.std():<34.5f} {1.642 / np.sqrt(n):.5f}")

x, y = rng.random(2000), rng.random(2000)
inside = x**2 + y**2 < 1
plt.figure(figsize=(4, 4))
plt.scatter(x[inside], y[inside], s=3, color="tab:green")
plt.scatter(x[~inside], y[~inside], s=3, color="tab:red")
plt.title(f"2000 points: pi is about {4 * inside.mean():.3f}"); plt.gca().set_aspect("equal")

Try this. Check the last column: the typical error (standard deviation over 200 runs) matches 1.642/√n at each n, and going from n = 100 to n = 10000 (100 times more points) makes the error about 10 times smaller, from about 0.166 to 0.0166. Then replace the hit-or-miss line by est = (4 / (1 + rng.random((200, n))**2)).mean(axis=1) and see the error drop by a factor of roughly 2.5 (the square root of 6.5; with only 200 runs the measured ratio wobbles between about 2.5 and 3).

Used in the real world· A Bayesian spam filter: Bayes' theorem on words

In 1998 a Microsoft Research team (Sahami, Dumais, Heckerman and Horvitz) published a Bayesian approach to filtering junk email, and in August 2002 Paul Graham’s essay A Plan for Spam popularised the simple version that most filters copy. Graham reported that his filter, on his own mail, missed fewer than $5$ spams in $1000$ with no false positives. The idea is Bayes’ theorem with an independence assumption. Let $S$ be “the message is spam”. For each word $w$ in the message, estimate $P(w \mid S)$ and $P(w \mid \text{ham})$ from counts. The words are treated as conditionally independent given the class: among spam messages, whether ‘free’ appears tells you nothing about whether ‘winner’ appears, and the same among ham. In symbols, $P(w_1 \cap w_2 \mid S) = P(w_1 \mid S)\,P(w_2 \mid S)$ , which is the product rule of independence applied to the conditional measure $P(\cdot \mid S)$ (a probability measure by the theorem above). This is a weaker claim than plain independence, and it is not the same: ‘free’ and ‘winner’ both occur more often in spam, so over all messages they are dependent. The assumption is called “naive”, is usually false in detail and usually good enough. With it the odds multiply:

\frac{P(S \mid \text{words})}{P(\text{ham} \mid \text{words})} = \frac{P(S)}{P(\text{ham})} \prod_{w} \frac{P(w \mid S)}{P(w \mid \text{ham})}.

Worked example the corpus counts are invented for illustration

A toy corpus of 100 messages: 40 spam, 60 ham. The word 'free' appears in 24 spam and 3 ham messages, 'winner' in 12 spam and 0 ham, 'meeting' in 2 spam and 27 ham. A new message contains 'free' and 'winner'. Find the chance it is spam.

Solution.

Smooth the counts. Estimate $P(w \mid S) = \dfrac{\text{spam count} + 1}{40 + 2}$ and $P(w \mid \text{ham}) = \dfrac{\text{ham count} + 1}{60 + 2}$ . Adding $1$ stops a word seen in no ham message (like ‘winner’) from getting probability $0$ , which would make the odds infinite on a single word.
Likelihood ratios. ‘free’: $\dfrac{25/42}{4/62} \approx 9.23$ . ‘winner’: $\dfrac{13/42}{1/62} \approx 19.19$ . How many times more likely the word is in spam than in ham.
Prior odds. $P(S)/P(\text{ham}) = 40/60 = \tfrac23$ . The base rate of spam in the corpus.
Multiply. Posterior odds $= \tfrac23 \times 9.23 \times 19.19 \approx 118.0$ . Bayes’ theorem in odds form with the independence assumption.
Convert to a probability. $118.0/(1 + 118.0) \approx 0.992$ . odds $= p/(1-p)$ , so $p = \text{odds}/(1 + \text{odds})$ .
Add a harmless word. With ‘meeting’ too, its ratio is $\dfrac{3/42}{28/62} \approx 0.158$ , so odds $\approx 18.7$ and $P(S) \approx 0.949$ . A word common in ham pulls the odds down, but two spam words still win.

Answer. About $99.2\%$ spam, and $94.9\%$ if the message also mentions a meeting. Real filters do the same sum over thousands of words, usually with logarithms, so that products become sums and thousands of small factors cannot underflow to zero.

Used in the real world· A/B testing: is version B really better?

A website shows page A to $4000$ visitors and page B to another $4000$ . A gets $200$ sign-ups ( $5.0\%$ ) and B gets $240$ ( $6.0\%$ ). Is B better, or is this luck? Treat each visitor as a Bernoulli trial. If A and B were equally good, with a common rate near the pooled $\hat p = 440/8000 = 0.055$ , the difference of the two observed rates has mean $0$ and variance $\hat p(1 - \hat p)\left(\tfrac1{4000} + \tfrac1{4000}\right) \approx 2.6 \times 10^{-5}$ , a standard deviation of $0.0051$ . The observed difference $0.010$ is $0.010/0.0051 \approx 1.96$ standard deviations. By the normal approximation (the central limit theorem, label B), a gap this large happens by luck about $5\%$ of the time: borderline.

Chebyshev alone gives $P(|\text{diff}| \ge 0.01) \le 2.6 \times 10^{-5}/10^{-4} = 0.26$ , too weak to conclude anything. That is the practical meaning of “Chebyshev is loose”. To design a test that could detect a gap of $\delta = 0.01$ around a rate of $5\%$ with the usual $80\%$ power and $5\%$ false-alarm rate, a standard rule of thumb is $n \approx 16\,p(1-p)/\delta^2$ , which gives $16(0.0475)/10^{-4} = 7600$ visitors per page with $p = 5\%$ and about $8300$ with $p = 5.5\%$ ; the exact normal calculation for $5\%$ against $6\%$ gives about $8150$ . Choose $n$ before looking at the data: checking repeatedly and stopping the moment the result looks significant inflates the false-alarm rate far above $5\%$ .

Traps

Watch out· P(A given B) is not P(B given A)

A test that catches 99% of sick people does not mean 99% of positives are sick (the quiz above gave about 9%). The two conditional probabilities differ by the ratio of the base rates, which is exactly what Bayes’ theorem multiplies in.

Watch out· Disjoint is not independent

Disjoint events with positive probability are dependent: if one happens the other cannot. Independence needs $P(A \cap B) = P(A)P(B)$ , not $P(A \cap B) = 0$ .

Watch out· Pairwise independent is not mutually independent

Three events can be independent two at a time and still fail the product rule for all three (two coins and ‘they agree’). Mutual independence needs the product rule for every sub-collection.

Watch out· A density is not a probability

$f(x)$ can be larger than $1$ , and $P(X = x) = 0$ for every single $x$ . The probability is the area $\int_a^b f$ . A probability of $0$ does not mean impossible: a uniform point on $[0,1]$ lands somewhere, yet each particular value had chance $0$ .

Watch out· The law of large numbers does not say the coin is 'due'

After a run of tails, the next toss still has chance $\frac12$ of heads. The average settles because the early excess is diluted by a growing number of new tosses, not because the future compensates. The deviation of the count of heads from $n/2$ typically grows like $\sqrt n$ ; only its ratio to $n$ shrinks.

Watch out· Chebyshev is a guarantee, not an estimate

The bound $\sigma^2/c^2$ holds for every distribution and is therefore far from the truth for any particular one (0.25 against 0.0455 at two standard deviations for a coin average). Use it to prove convergence. To compute a probability, use the distribution or the central limit theorem.

Watch out· Expectation can fail to exist, and the average of the outcomes need not be an outcome

$E[X]$ requires $\int |x| f < \infty$ (or the discrete analogue). The Cauchy distribution has none. And $E[\text{die}] = 3.5$ is a value the die never shows.

Problems

check

Events $A$ and $B$ have $P(A) = 0.3$ , $P(B) = 0.2$ and $P(A \cap B) = 0.1$ . Find the probability that at least one of them happens, the probability that neither does, and the probability that exactly one does.

Solution

At least one: $P(A \cup B) = 0.3 + 0.2 - 0.1 = 0.4$ (inclusion-exclusion). Neither: the complement, $1 - 0.4 = 0.6$ . Exactly one: the event ” $A$ or $B$ but not both” is $(A \cup B) \setminus (A \cap B)$ , and $A \cap B \subseteq A \cup B$ , so its probability is $0.4 - 0.1 = 0.3$ (rule 4 of the basic rules).

check

A fair die is rolled twice. Given that the second roll is larger than the first, what is the probability that the first roll was $1$ ?

Solution

The pairs (first, second) with second larger: there are $5 + 4 + 3 + 2 + 1 = 15$ of them, all equally likely out of $36$ . Those with first roll $1$ : $(1,2), \dots, (1,6)$ , five of them. So the probability is $\tfrac5{15} = \tfrac13$ . Equivalently $\dfrac{P(\text{first is } 1 \text{ and second larger})}{P(\text{second larger})} = \dfrac{5/36}{15/36} = \tfrac13$ .

check

Show that $f(x) = 4x^3$ on $[0, 1]$ (and $0$ elsewhere) is a density. For $X$ with this density find $F$ and $P(X < \tfrac12)$ .

Solution

$f \ge 0$ and $\int_0^1 4x^3\,dx = [x^4]_0^1 = 1$ . For $0 \le x \le 1$ , $F(x) = \int_0^x 4t^3\,dt = x^4$ (with $F = 0$ below $0$ and $F = 1$ above $1$ ). So $P(X < \tfrac12) = F(\tfrac12) = \tfrac1{16}$ (a single point has probability $0$ , so $<$ and $\le$ agree).

check

A variable has mean $50$ and standard deviation $5$ . What does Chebyshev’s inequality say about $P(|X - 50| \ge 15)$ ?

Solution

$P(|X - 50| \ge 15) \le \dfrac{25}{15^2} = \dfrac{25}{225} = \dfrac19$ . Here $15 = 3\sigma$ , so this is the case $k = 3$ , $1/k^2 = 1/9$ .

use

In a class of $60$ students, $35$ know Python, $28$ know Java and $12$ know both. How many know neither? If a student is chosen at random, what is the probability of knowing neither?

Solution

Inclusion-exclusion: the number who know at least one is $35 + 28 - 12 = 51$ . So $60 - 51 = 9$ know neither, and the probability is $9/60 = \tfrac3{20}$ . (Equal probabilities for all students make $P(A) = |A|/60$ a probability measure, and inclusion-exclusion for probabilities is the counting formula divided by $60$ .)

use

Urn 1 holds $3$ red and $1$ blue ball; urn 2 holds $1$ red and $3$ blue. A fair coin picks an urn, and a ball is drawn (and put back). It is red. What is the probability the urn is urn 1? The ball is drawn again and is red again: now what is the probability?

Solution

Let $U_1$ be “urn 1”. $P(\text{red}) = \tfrac12 \cdot \tfrac34 + \tfrac12 \cdot \tfrac14 = \tfrac12$ . By Bayes, $P(U_1 \mid R) = \dfrac{\frac12 \cdot \frac34}{\frac12} = \tfrac34$ . For two reds in a row (draws with replacement are independent given the urn): $P(RR \mid U_1) = \tfrac9{16}$ , $P(RR \mid U_2) = \tfrac1{16}$ , so $P(U_1 \mid RR) = \dfrac{\frac12 \cdot \frac9{16}}{\frac12 \cdot \frac9{16} + \frac12 \cdot \frac1{16}} = \tfrac{9}{10}$ .

use

Calls reach a help line with an exponential waiting time between calls, mean $4$ minutes. What is the chance the next call comes within $2$ minutes? What is the median wait: the time $m$ with $P(X \le m) = \tfrac12$ ?

Solution

The rate is $\lambda = \tfrac14$ per minute, so $F(x) = 1 - e^{-x/4}$ for $x \ge 0$ . Within $2$ minutes: $F(2) = 1 - e^{-0.5} \approx 0.3935$ . For the median we solve $1 - e^{-m/4} = \tfrac12$ , so $e^{-m/4} = \tfrac12$ and $m = 4\ln 2 \approx 2.77$ minutes. The median is below the mean ( $4$ ): a few long waits pull the mean up.

use

$X$ is the number shown by a fair die. Find $\operatorname{Var}(2X + 5)$ and $E[(X - 3.5)^2]$ .

Solution

$\operatorname{Var}(X) = \tfrac{35}{12}$ (worked example). By scaling, $\operatorname{Var}(2X + 5) = 4 \cdot \tfrac{35}{12} = \tfrac{35}{3} \approx 11.67$ : the shift by $5$ changes nothing. And $E[(X - 3.5)^2]$ is by definition $\operatorname{Var}(X) = \tfrac{35}{12} \approx 2.917$ .

prove

Prove Bonferroni’s inequality: $P(A \cap B) \ge P(A) + P(B) - 1$ , and more generally $P(A_1 \cap \cdots \cap A_n) \ge 1 - \sum_{i=1}^{n} P(A_i^c)$ .

Solution

By De Morgan, $(A_1 \cap \cdots \cap A_n)^c = A_1^c \cup \cdots \cup A_n^c$ . By the union bound, $P(A_1^c \cup \cdots \cup A_n^c) \le \sum P(A_i^c)$ . By the complement rule, $P(A_1 \cap \cdots \cap A_n) = 1 - P(A_1^c \cup \cdots \cup A_n^c) \ge 1 - \sum P(A_i^c)$ . For $n = 2$ the right side is $1 - (1 - P(A)) - (1 - P(B)) = P(A) + P(B) - 1$ . $\blacksquare$

prove

Prove that an event $A$ with $P(A) = 0$ or $P(A) = 1$ is independent of every event $B$ .

Solution

If $P(A) = 0$ : $A \cap B \subseteq A$ , so $0 \le P(A \cap B) \le P(A) = 0$ , and $P(A \cap B) = 0 = P(A)P(B)$ . If $P(A) = 1$ : $P(A^c) = 0$ , so by the first case $A^c$ is independent of $B$ , and by the theorem on complements, so is $A = (A^c)^c$ . Directly: $P(A \cap B) = P(B) - P(A^c \cap B) = P(B) - 0 = P(B) = P(A)P(B)$ . $\blacksquare$

prove

Prove that if $\operatorname{Var}(X) = 0$ then $P(X = \mu) = 1$ , where $\mu = E[X]$ .

Solution

For each $n$ , Chebyshev with $c = 1/n$ gives $P(|X - \mu| \ge \tfrac1n) \le 0 \cdot n^2 = 0$ . The events $E_n = \{|X - \mu| \ge \tfrac1n\}$ grow with $n$ and their union is $\{X \ne \mu\}$ (if $X(\omega) \ne \mu$ then $|X(\omega) - \mu| \ge \frac1n$ for large $n$ ). By continuity from below, $P(X \ne \mu) = \lim P(E_n) = 0$ , so $P(X = \mu) = 1$ . $\blacksquare$

prove

Let $A_1, A_2, \dots$ be events. Prove that if $P(A_n) = 0$ for all $n$ then $P(\bigcup A_n) = 0$ , and if $P(A_n) = 1$ for all $n$ then $P(\bigcap A_n) = 1$ . Why does this fail for uncountable unions?

Solution

By the union bound, $0 \le P(\bigcup A_n) \le \sum P(A_n) = 0$ . For the second part, the complements have probability $0$ , so $P\big(\bigcup A_n^c\big) = 0$ , and $\bigcap A_n = (\bigcup A_n^c)^c$ has probability $1$ . For uncountable unions: $[0,1] = \bigcup_{x \in [0,1]}\{x\}$ is a union of sets of probability $0$ under the uniform distribution, but has probability $1$ . Countable additivity only covers countable lists, which is why 0.3 matters here. $\blacksquare$

stretch

Show that Chebyshev’s inequality cannot be improved without more information: for every $c > 0$ and $0 < p \le 1$ , find a random variable $X$ with mean $0$ and $P(|X| \ge c) = \sigma^2/c^2$ exactly.

Solution

Let $X = c$ with probability $p/2$ , $X = -c$ with probability $p/2$ , and $X = 0$ with probability $1 - p$ . Then $E[X] = 0$ , $E[X^2] = c^2 p$ , so $\sigma^2 = c^2p$ . And $P(|X| \ge c) = p = \sigma^2/c^2$ . So equality holds; no smaller bound that depends only on $\sigma^2$ and $c$ could be true for all distributions.

stretchthe first Borel–Cantelli lemma

Let $A_1, A_2, \dots$ be events with $\sum_n P(A_n) < \infty$ . Let $E$ be the event that infinitely many of the $A_n$ happen. Prove that $P(E) = 0$ .

Solution

$E = \bigcap_{N \ge 1}\bigcup_{n \ge N} A_n$ : an outcome is in infinitely many $A_n$ exactly when for every $N$ it lies in some $A_n$ with $n \ge N$ . For each $N$ , $E \subseteq \bigcup_{n \ge N} A_n$ , so by monotonicity and the union bound $P(E) \le \sum_{n \ge N} P(A_n)$ . This is the tail of a convergent series, so it tends to $0$ as $N \to \infty$ . Hence $P(E) \le 0$ , and $P(E) = 0$ . $\blacksquare$ Example: if $P(A_n) = 1/n^2$ then with probability $1$ only finitely many of the $A_n$ occur.

Summary

A probability is a measure of total size $1$ : never negative, and additive over non-overlapping pieces. The sets it measures (events) form a sigma-algebra, because finite additivity alone does not give limits (the finite/cofinite example) and because not every subset can be measured (Vitali, label B).
Kolmogorov’s axioms are $P(A) \ge 0$ , $P(\Omega) = 1$ and countable additivity. From them we proved $P(\varnothing) = 0$ , the complement rule, monotonicity, inclusion-exclusion for $2$ and $3$ events, the union bound, and continuity from below and above.
Conditional probability $P(A \mid B) = P(A \cap B)/P(B)$ is itself a probability measure. It gives the multiplication rule, the law of total probability and Bayes’ theorem. Independence means $P(A \cap B) = P(A)P(B)$ ; disjoint is not independent, and pairwise is not mutual.
A random variable is a function on the sample space. Its distribution function $F(x) = P(X \le x)$ is non-decreasing, right-continuous, has limits $0$ and $1$ , and jumps by $P(X = a)$ at $a$ .
A discrete variable has a mass function $p$ with sum $1$ . A continuous variable has a density $f \ge 0$ with area $1$ , and probability is area. The uniform, exponential (memoryless, mean $1/\lambda$ ) and normal (area $1$ by the Gaussian integral) densities are the standard examples.
Expectation is the weighted average (absolute convergence required) and is linear. Variance is $E[X^2] - (E[X])^2$ , scales as $a^2$ , and adds for independent variables.
Chebyshev’s inequality $P(|X - \mu| \ge c) \le \sigma^2/c^2$ follows from Markov’s inequality applied to $(X - \mu)^2$ . It gives the weak law of large numbers: $P(|\bar X_n - \mu| \ge \varepsilon) \le \sigma^2/(n\varepsilon^2) \to 0$ .
Used: Monte Carlo (error $\propto 1/\sqrt n$ ), Bayesian spam filters (odds multiply), A/B tests (the normal approximation is needed because Chebyshev is too loose), and, inside maths, Bernstein’s proof of Weierstrass’s theorem.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture

The idea, in words

Definitions and theorems

Set functions that add (Apostol 13.2 and 13.3)

Finitely additive set function

Boolean algebra of sets

Finitely additive measure

Additivity for overlapping sets

Properties of a finitely additive measure

Why finite additivity is not enough: countable additivity

Sigma-algebra

Vitali: no uniform probability on every subset

Kolmogorov’s axioms

Probability measure

Basic rules of probability

Union bound

Continuity of probability

Updating a chance: conditional probability, independence, Bayes

Conditional probability

Conditional probability is a probability measure

Law of total probability

Bayes' theorem

Independent events

Complements of independent events

Numbers from outcomes: random variables and distribution functions

Random variable

Distribution function

Properties of a distribution function

Discrete and continuous distributions

Probability mass function

Probability density function

The exponential distribution forgets

The Gaussian integral

The centre and the spread: expectation and variance

Expectation

Linearity of expectation

Variance

Variance shortcut and scaling

Independent random variables

Variance of a sum of independent variables

Chebyshev’s inequality and the law of large numbers

Markov's inequality

Chebyshev's inequality

Weak law of large numbers

Examples and non-examples

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere