Notes for probability

John Kerl

July 28, 2011

Abstract

This is a crib sheet for probability. Content is taken from Dr. Tom Kennedy’s splendid lectures for Math 564 (probability) at the University of Arizona in spring of 2007. That is, these are (except for my appendices) simply my hand-written class notes (with some examples omitted for brevity), made legible and searchable.

When I take a course, my two fundamental questions for myself are (1) What do I expect myself to know? and (2) How do I know I know it? A crib sheet such as this one addresses the first question; homework assignments address the second.

Contents

Contents  2

1 Events  4
1.1 Fundamental definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Conditioning and independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Discrete random variables  6
2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Catalog of discrete random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Multiple discrete random variables  10
3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4 Sample mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.5 Moment-generating functions and characteristic functions . . . . . . . . . . . . . . . . . . . . 12
3.6 Sums of discrete random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Continuous random variables  14
4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Catalog of continuous random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 The normal distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.4 The gamma distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.5 Functions of a single random variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.6 Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5 Multiple continuous random variables  19
5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.4 The IID paradigm: S_{n} and \overline{X}_{n} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.5 Functions of multiple random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.6 Moment-generating functions and characteristic functions . . . . . . . . . . . . . . . . . . . . 22
5.7 Change of variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.8 Conditional density and expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.9 The bivariate normal distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.10 Covariance and correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6 Laws of averages  26
6.1 The weak law of large numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 The strong law of large numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.3 The central limit theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.4 Confidence intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

A The coin-flipping experiments  30
A.1 Single coin flips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
A.2 Batches of coin flips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

B Bayes’ theorem  34
B.1 Algebraic approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
B.2 Graphical/numerical approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
B.3 Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
B.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

C Probability and measure theory  38

D A proof of the inclusion-exclusion formula  41

References  45

Index  46

1 Events

1.1 Fundamental definitions

Definitions 1.1. When we do an experiment, we obtain an outcome. The set of all outcomes, conventionally written Ω, is called the sample space. (Mathematically, we only require Ω to be a set.)

Definition 1.2. An event is, intuitively, any subset of the sample space. Technically, it is any measurable subset of the sample space.

Example 1.3. The experiment is rolling a 6-sided die once. The outcome is the number of pips on the top face after the roll. The sample space Ω is {1, 2, 3, 4, 5, 6}. Example events are “the result of the roll is a 3” and “the result of the roll is odd”.

Definition 1.4. Events A and B are disjoint if A ∩ B = ∅.

Definition 1.5. A collection F of subsets of Ω is called a σ-field or event space if ∅ ∈ F, F is closed under countable unions, and F is closed under complements. (Note in particular that this means Ω ∈ F and F is closed under countable intersections.)

Remark 1.6. There is a superficial resemblance with topological spaces: A topological space X has a topology T which is a collection of “open” subsets that is closed under complements, finite (rather than countable) intersection and arbitrary (rather than countable) union.

Examples 1.7. The smallest (or coarsest) σ-field for any Ω is {∅, Ω}; the largest (or finest) is 2^{Ω}, the set of all subsets of Ω. There may be many σ-fields in between. For example, if A is any subset of Ω which isn’t ∅ or Ω, then one can check that the 4-element collection {∅, A, A^{c}, Ω} is a σ-field.

Definition 1.8. A probability measure P is a function from a σ-field F to [0, 1] such that:

• For all A ∈ F, P (A) ≥ 0;

• P (Ω) = 1 and P (∅) = 0;

• If A_{1}, A_{2}, …, is a finite or countable subset of F, with the A_{i}’s all (pairwise) disjoint, then

P (∪_{i}A_{i}) = ∑_{i} P (A_{i}).

This is the countable additivity property of the probability measure P.

Remark 1.9. For uncountable Ω, 2^{Ω} is a σ-field, but it is impossible to define a probability measure on it; it is “too big”. Consult your favorite textbook on Lebesgue measure for the reason why. For finite or countable Ω, on the other hand, 2^{Ω} is in fact what we think of for F.

Definition 1.10. A probability space is a triple (Ω, F, P) of a sample space Ω, a σ-field F on Ω, and a probability measure P on F.

Remark 1.11. Technically, a probability space is nothing more than a measure space Ω with the additional requirement that P (Ω) = 1.

1.2 Conditioning and independence

Definition 1.12. Let A, B be two events with P (B) > 0. Then we define the conditional probability of A given B to be

P (A|B) = \frac{P (A ∩ B)}{P (B)}.

Mnemonic: intersection over given.

Notation 1.13. We will often write P (A, B) in place of P (A ∩ B). Definition 1.14. Two events A and B are independent (or pairwise independent) if

P (A ∩ B) = P (A)P (B).

Mnemonic: write down P (A) = P (A|B) = P (A ∩ B)/P (B) and clear the denominators. Remark 1.15. This is not the same as disjoint. If A and B are disjoint, then by countable additivity of P, we have

P (A ∪ B) = P (A) + P (B).

Definition 1.16. Events A_{1}, …, A_{n} are independent if for all I ⊆ {1, 2, …, n},

P (∩_{i∈I}A_{i}) = ∏_{i∈I} P (A_{i}).

Mnemonic: We just look at all possible factorizations. Example 1.17. Three events A, B, and C are independent if P (A∩B) = P (A)P (B), P (A∩C) = P (A)P (C), P (B∩C) = P (B)P (C), and P (A∩B∩C) = P (A)P (B)P (C). Theorem 1.18 (Partition theorem). Let {B_{i}} be a countable partition of Ω and let A be an event. Then

P (A) = ∑_{i} P (A|B_{i})P (B_{i}).

Proof. Note that

P (A) = ∑_{i} P (A ∩ B_{i})

since the B_{i}’s partition Ω.

2 Discrete random variables

2.1 Definitions

Definition 2.1. A random variable X is a function X : Ω → ℝ. We say X is a discrete random variable if its range, X(Ω), is finite or countable. Example 2.2. Roll two 6-sided dice and let X be their sum. Definition 2.3. Given a random variable X, the probability mass function or PMF of X, written f(x) or f_{X}(x), is

f_{X}(x) = P (X = x) = P (X^{−1}(x)).

This is the probability that X’s value is some specific real number x. Note that X^{−1}(x), the preimage of x, is an event and so we can compute its probability using the probability measure P. Definition 2.4. Let X_{1} and X_{2} be two random variables on two probability spaces (Ω_{1}, F_{1}, P_{1}) and (Ω_{2}, F_{2}, P_{2}), respectively. Then X_{1} and X_{2} are identically distributed if X_{1}(x) = X_{2}(x) for all x ∈ ℝ. Remark 2.5. Identically distributed discrete random variables X and Y have the same PMF. Remark 2.6. Just as with events, which have a general measure-theoretic definition (definition 1.2), there is also a general measure-theoretic definition for random variables: they are simply measurable functions from a probability space to a measurable space.

2.2 Catalog of discrete random variables

Note: mean and variance are defined in section 2.3. They are included here for ready reference. Bernoulli DRV:

• Parameter p ∈ [0, 1].

• Range X = {0, 1}.

• PMF P (X = 0) = p, P (X = 1) = 1 − p.

• Example: Flip a p-weighted coin once.

• Mean: 1 − p.

• Variance: p(1 − p).

Binomial DRV:

• Two parameters: p ∈ [0, 1] and n ∈ ℤ^{+}.

• Range X = {0, 1, 2, …, n}.

• PMF P (X = k) = \binom{n}{k}p^{k}(1 − p)^{n−k}.

• Example: Flip a p-weighted coin n times; X is the number of heads.

• Mean: np.

• Variance: np(1 − p). Remark 2.7. There is a trick to see that the sum of probabilities is 1 — recognize the sum of probabilities as the expansion of (p + (1 − p))^{n} using the binomial theorem:

1 = 1^{n} = (p + (1 − p))^{n} = ∑_{k=0}^{n} \binom{n}{k}p^{k}(1 − p)^{n−k}.

Poisson DRV:

• Parameter λ > 0.

• Range X = {0, 1, 2, …}.

• PMF P (X = k) = \frac{λ^{k}}{k!} e^{−λ}.

• Example: Limiting case of binomial random variable with large n, small p, and λ = np ≈ 1.

• Mean: λ.

• Variance: λ.

Geometric DRV:

• Parameter p ∈ [0, 1].

• Range X = {1, 2, 3, …}.

• PMF P (X = k) = p(1 − p)^{k−1}.

• Example: Flip a p-weighted coin until you get heads; X is the number of flips it takes. (Note: some authors count the number of tails before the head.)

• Mean: 1/p.

• Variance: (1 − p)/p^{2}.

Negative binomial DRV:

• Two parameters p ∈ [0, 1] and n = 1, 2, 3, . . ..

• Range X = {n, n + 1, n + 2, …}.

• PMF P (X = k) = \binom{k−1}{n−1}p^{n}(1 − p)^{k−n}.

• Example: Flip a p-weighted coin until you get n heads; X is the number of flips it takes.

• Note: Deriving the \binom{k−1}{n−1} factor is a non-trivial counting problem; it is deferred until later in the course.

• Mean: n/p.

• Variance: n(1 − p)/p^{2}.

2.3 Expectations

Definition 2.8. Functions of a discrete random variable: If X : Ω → ℝ and g : ℝ → ℝ then g(X) : Ω → ℝ is another random variable. Let Y = g(X).

To find the PMF of g(X) given PMF of (X): write the latter as f_{X}(x) = P (X = x). Then

P (g(X) = y) = ∑_{x∈g^{−1}(y)} P (X = x) = ∑_{x∈g^{−1}(y)} f_{X}(x).

Definition 2.9. Let X be a discrete random variable with PMF f_{X}(x). If

∑_{x} |x|f_{X}(x) < ∞

(i.e. if we have absolute convergence) then we define the expected value (also call expectation or mean) of X to be

E[X] = ∑_{x} xf_{X}(x) = ∑_{x} xP (X = x).

Mnemonic: This is just the weighted sum of possible X values, weighted by their probabilities.

Theorem 2.10 (Law of the Unconscious Statistician). Let X be a discrete random variable and g : ℝ → ℝ. Let Y = g(X). If

∑_{x} |g(x)| f_{X}(x) < ∞

then

E[Y] = ∑_{x} g(x)f_{X}(x).

Definition 2.11. The variance of X, written σ^{2}(X) or Var(X), is

σ^{2}(X) = E[(X − E[X])^{2}].

Definition 2.12. The square root of the variance is the standard deviation, written σ(X) or σ_{X}.

Proposition 2.13. Let μ = E[X]. Then

σ^{2}(X) = E[X^{2}] − E[X]^{2}.

Proof. FOIL, and use linearity of expectation.

Proposition 2.14. Var(cX) = c^{2}Var(X).

Proof.

Var(cX) = E[c^{2}X^{2}] − E[cX]^{2} = c^{2}E[X^{2}] − c^{2}E[X]^{2} = c^{2} (E[X^{2}] − E[X]^{2}) = c^{2}Var(X).

Theorem 2.15. Let X be a discrete random variable; let a, b ∈ ℝ. Then

(i) E[aX + b] = aE[X] + b.

(ii) If P (X = b) = 1 then E[X] = b.

(iii) If a ≤ X ≤ b then a ≤ E[X] ≤ b. (iv) If g, h : ℝ → ℝ and g(X), h(X) have finite means, then E[g(X) + h(X)] = E[g(X)] + E[h(X)]. Definition 2.16. Let X be a discrete random variable and let B be an event. The conditional PMF of X given B is

f(x|B) = P (X = x|B).

The conditional expectation of X given B is

E[X|B] = ∑_{x} xf(x|B)

provided (as usual) that the sum converges absolutely. Theorem 2.17 (Partition theorem). Let {B_{i}} be a countable partition of Ω and let X be a random variable. Then

E[X] = ∑_{i} E[X|B_{i}]P (B_{i}).

3 Multiple discrete random variables

3.1 Definitions

Definition 3.1. We define the joint PMF or joint density of X and Y to be

f_{X,Y} (x, y) = P (X = x, Y = y).

Proposition 3.2. For A ⊆ ℝ^{2} we have

P ((x, y) ∈ A) = ∑_{(x,y)∈A} f_{X,Y} (x, y).

Corollary 3.3. Let g(x, y) : ℝ^{2} → ℝ. Let X and Y be discrete random variables and let Z = g(X, Y). Then

f_{Z}(z) = P (Z = z) = ∑_{z∈g^{−1}(x,y)} f_{X,Y} (x, y).

We can use joint densities to recover marginal densities: Corollary 3.4. Let X and Y be discrete random variables with joint density f_{X,Y}. Then

f_{X}(x) = ∑_{y} f_{X,Y} (x, y)  and  f_{Y} (y) = ∑_{x} f_{X,Y} (x, y).

3.2 Expectations

Theorem 3.5 (Law of the Unconscious Statistician). Let X and Y be discrete random variables and let g(x, y) : ℝ^{2} → ℝ. Let Z = g(X, Y). Then

E[Z] = ∑_{x,y} g(x, y)f_{X,Y} (x, y).

Proof. As in the single-variable case (theorem 3.5). Corollary 3.6. Let X and Y be discrete random variables, and let a, b ∈ ℝ. Then

E[aX + bY] = aE[X] + bE[Y].

Proof. Use g(x, y) = ax + by, and use the theorem twice.

3.3 Independence

Recall definition 1.14 of independent events: A and B are independent if P (A ∩ B) = P (A)P (B). We use this to define independence of discrete random variables. Definition 3.7. Two discrete random variables X and Y are independent if, for all x and y,

P (X = x, Y = y) = P (X = x)P (Y = y).

Using PMF notation, we say X and Y are independent if

f_{X,Y} (x, y) = f_{X}(x)f_{Y} (y)

for all x and y, i.e. if the joint PMF factors.

Notation 3.8. We often abbreviate independent and identically distributed (definitions 3.7 and 2.4) as IID.

Question: given only the joint density of X and Y, can we tell if X and Y are independent? From corollary 3.4, we can recover the PMFs of X and Y:

f_{X}(x) = ∑_{y} f_{X,Y} (x, y)  and  f_{Y} (y) = ∑_{x} f_{X,Y} (x, y).

Then we can multiply them back together and see if we get the joint density back. Point:

• If X and Y are independent, then we can go from marginals to joint PMFs by multiplying.

• We can always go from joint PMFs to marginals by summing as above. Theorem 3.9. If X and Y are independent discrete random variables, then

E[XY] = E[X]E[Y].

Remark. See definition 5.25 for the general case. Theorem 3.10. If X and Y are independent discrete random variables and g, h : ℝ → ℝ then g(X) and h(Y) are independent discrete random variables. Corollary 3.11. In particular,

E[g(X)h(Y)] = E[g(X)]E[h(Y)]

provided g(X) and h(Y) have finite mean. Theorem 3.12. If X and Y are independent discrete random variables then

Var(X + Y) = Var(X) + Var(Y).

Proof. Use definition 2.11 and theorem 3.9. Definition 3.13. We say that X and Y are uncorrelated if

E[XY] = E[X]E[Y].

Remark 3.14. Independent implies uncorrelated but not vice versa. Remark 3.15. Theorem 3.12 holds for uncorrelated discrete random variables.

3.4 Sample mean

Definition 3.16. Let X_{1}, …, X_{n} be independent and identically distributed. (Think of multiple trials of the same experiment.) Since each X_{i} has the same expectation, we call their common mean the population mean and denote it by μ. Likewise, we call their common variance the population variance and denote it by σ^{2}. Let

\overline{X} = \frac{∑_{i=1}^{n} X_{i}}{n} .

This is a new random variable, called the sample mean of X_{1}, …, X_{n}.

By linearity of expectation,

E[\overline{X}] = \frac{1}{n} ∑_{i=1}^{n} E[X_{j}] = μ.

Recall from proposition that the variance scales as Var(cX) = c^{2}Var(X). Also, since the X_{i}’s are independent, their variances add. Thus

Var(\overline{X}) = Var (\frac{∑_{i=1}^{n} X_{i}}{n} ) = \frac{1}{n^{2}} Var (∑_{i=1}^{n} X_{i}) = \frac{n}{n^{2}} σ^{2} = \frac{σ^{2}}{n} .

3.5 Moment-generating functions and characteristic functions

Definitions 3.17. Let X be a discrete random variable. Then the moment-generating function or MGF of X is

M_{X}(t) = E[e^{tX}].

By the Law of the Unconscious Statistician (theorem 2.10), this is

M_{X}(t) = ∑_{x} e^{tx}f_{X}(x).

Likewise, the characteristic function of X is

β_{X}(t) = E[e^{itX}]

which is

β_{X}(t) = ∑_{x} e^{itx}f_{X}(x).

Remark 3.18. These functions are just computational tricks. There is no intrinsic meaning in these functions.

Proposition 3.19. Let M_{X}(t) be the moment-generating function for a discrete random variable X. Then

E[X^{k}] = M_{X}^{(k)}(0) = \frac{d^{k}}{dt^{k}} M_{X}(t)|_{t=0}.

Proposition 3.20. If X and Y are identically distributed, they have the same PMF (remark 2.5) and thus they also have the same MGF.

Proposition 3.21. Let X and Y be independent discrete random variables and let Z = X + Y. Then

M_{Z}(t) = M_{X}(t)M_{Y} (t).

3.6 Sums of discrete random variables

Moment-generating functions are perhaps a better approach than the following.

Let X and Y be discrete random variables and let Z = X + Y. We can find the PMF of Z by

f_{Z}(z) = P (Z = z) = P (X + Y = z) = ∑_{x+y=z} f_{X,Y} (x, y) = ∑_{x} ∑_{y=z−x} f_{X,Y} (x, y) = ∑_{x} f_{X,Y} (x, z − x).

Now further suppose that X and Y are independent. Then

f_{X,Y} (x, z − x) = f_{X}(x)f_{Y} (z − x)

so

f_{Z}(z) = ∑_{x} f_{X}(x)f_{Y} (z − x).

This is the convolution of f_{X} and f_{Y}. Note that, as always in convolutions, we are summing over all the ways in which x and y can add up to z.

4 Continuous random variables

4.1 Definitions

A continuous random variable, mimicking definition 2.1, is a function from Ω to ℝ with the property that for all x ∈ ℝ, P (X = x) = 0. Thus, the PMF which we used for discrete random variables is not useful. Instead we first define another function, namely, P (X ≤ x).

Definition 4.1. The cumulative distribution function or CDF for a random variable (whether discrete or continuous) is

F_{X}(x) = P (X ≤ x).

Theorem 4.2. The CDF F_{X}(x) for a random variable satisfies the following properties:

• 0 ≤ F_{X}(x) ≤ 1, and F_{X} is non-decreasing.

• lim_{x→−∞} F_{X}(x) = 0 and lim_{x→+∞} F_{X}(x) = 1.

• F_{X}(x) is right-continuous (in the sense from introductory calculus).

Definition 4.3. A random variable X is a continuous random variable if there exists a function f_{X}(x), called the probability density function of PDF, such that the CDF F_{X}(x) is given by ∫_{−∞}^{+∞} f_{X}(x) dx.

Remark 4.4. Note that the integral is done using Lebesgue measure (or, for the purposes of this course, Riemann integration). If we allow counting measure and require countable range, then we can subsume discrete random variables into this definition. However, that is outside the scope of this course.

Remark 4.5. Some random variables are neither discrete nor continuous; these appear for example in dynamical systems.

Remark 4.6. The PDF and CDF are related as follows (making use of the second fundamental theorem of calculus):

F_{X}(x) = ∫_{−∞}^{x} f_{X}(t) dt
f_{X}(x) = \frac{d}{dx}F_{X}(x).

Remark 4.7. The PDF of X is the probability that X lies in some interval. E.g.

P (a ≤ X ≤ b) = ∫_{a}^{b} f_{X}(x) dx.

Thus PDFs are non-negative and have integral 1.

Remark 4.8. We can now neatly define some terminology from statistics. Namely:

• Let X be a random variable from ℝ to ℝ with CDF F_{X}(x) and f_{X}(x).

• The mean of X is the expectation value E[X] as defined below.

• The median of X is F_{X}^{−1}(0.5).

• A mode of X is a local maximum of f_{X}(x). If the PDF has two local maxima, we say that X is bimodal. If the PDF has a single maximum, we call it the mode of X.

4.2 Catalog of continuous random variables

Note: mean and variance are defined in section 4.6. They are included here for ready reference. I thought about including graphs of the PDFs and CDFs, but instead I will refer you to the excellent Wikipedia article on Probability distribution, and the pages linking from there. Uniform CRV:

• Parameters a < b.

• Range [a, b].

• PDF

f_{X}(x) = \begin{cases}\frac{1}{b−a}, & a ≤ x ≤ b \\ 0, elsewhere. \end{cases}

• CDF

F_{X}(x) = \begin{cases}0, & x < a \\ \frac{x−a}{b−a}, & a ≤ x < b \\ 0, & b ≤ x \end{cases}

• Mean: (a + b)/2.

• Variance: (b − a)^{2}/12.

Exponential CRV:

• Parameter λ > 0.

• Range X = {0, ∞}.

• PDF

f_{X}(x) = \begin{cases}λe^{−λx}, & x ≥ 0 \\ 0, & x < 0. \end{cases}

• CDF

F_{X}(x) = \begin{cases}1 − e^{−λx}, & x ≥ 0 \\ 0, & x < 0. \end{cases}

• Mean: 1/λ.

• Variance: 1/λ^{2}.

Cauchy CRV:

• No parameters.

• Range X = {−∞, ∞}.

• PDF

f_{X}(x) = \frac{1}{π(1 + x^{2})}.

• CDF

F_{X}(x) = \frac{tan^{−1}(x)}{π} + \frac{1}{2}.

• Mean: infinite.

• Variance: infinite.

Normal CRV (see section 4.3):

• Parameters μ ∈ ℝ, σ > 0.

• Note: with μ = 0 and σ = 1 we have the standard normal distribution. One says it has zero mean and unit variance.

• Range X = {−∞, ∞}.

• PDF

f_{X}(x) = \frac{1}{σ\sqrt{2π}} exp [ \frac{−1}{2} (\frac{x − μ}{σ})^{2}] .

• CDF: No closed-form expression. Related to erf(x) but not quite the same: The standard normal CDF is \frac{1}{2}(1 + erf(x/\sqrt{2})). Note that some computing systems may have erf(x) but not normalcdf, or vice versa. Thus this conversion formula comes in handy.

• Mean: μ.

• Variance: σ^{2}.

Gamma CRV (see section 4.4):

• Parameters λ > 0, w > 0.

• Range x ≥ 0.

• PDF

f_{X}(x) = \frac{λ^{w}}{Γ(w)} x^{w−1}e^{−λx}, x ≥ 0.

• CDF TBD.

• Mean: w/λ.

• Variance: w/λ^{2}.

4.3 The normal distribution

Definition 4.9. The normal distribution has two parameters: real μ and positive σ. A random variable with the normal distribution has PDF

f(x) = \frac{1}{σ\sqrt{2π}} exp [ \frac{−1}{2} (\frac{x − μ}{σ})^{2}] .

Remark 4.10. The normal distribution has mean μ and variance σ^{2}. Definition 4.11. With μ = 0 and σ = 1 we have the standard normal distribution.

4.4 The gamma distribution

Definition 4.12. The gamma function is defined by

Γ(ω) = ∫_{0}^{∞} x^{w−1}e^{−x}dx.

Remark 4.13. Integration by parts shows that Γ(n) = (n − 1)!. Thus, the gamma function is a generalized factorial function.

Definition 4.14. The gamma distribution has two parameters λ, w > 0. A random variable with the gamma distribution has PDF

f(x) = \begin{cases}\frac{λ^{w}}{Γ(w)}x^{w−1}e^{−λx}, & x ≥ 0 \\ 0, & x < 0. \end{cases}

Remark 4.15. With w = 1 we have an exponential distribution. Thus, the gamma distribution generalizes the exponential distribution.

Proposition 4.16. The gamma distribution has mean w/λ.

4.5 Functions of a single random variable

Given a continuous random variable X and g(x) : ℝ → ℝ, we have a new continuous random variable Y = g(X). Often one wants to find the PDF of Y given the PDF of X. The method is to first find the CDF of Y, then differentiate to find the PDF.

Example 4.17. Let X be uniform on [0, 1] and let Y = X^{2}. The CDF of Y is

P (Y ≤ y) = P (X^{2} ≤ y) = P (X ≤ \sqrt{y}) = ∫_{0}^{√\overline{y}} 1 dx = \sqrt{y}

i.e.

F_{Y} (y) = \begin{cases}0, & y < 0 \\ \sqrt{y}, & 0 ≤ y < 1 \\ 1, & 1 ≤ y. \end{cases}

Then the PDF is

f_{Y} (y) = \begin{cases}0, & y < 0 \\ \frac{1}{2\sqrt{y}} , & 0 ≤ y < 1 \\ 0, & 1 ≤ y. \end{cases}

The critical step in the method is going from P (X^{2} ≤ y) to P (X ≤ \sqrt{y}).

4.6 Expectations

Definition 4.18. Let X be a continuous random variable with PDF f_{X}(x). If

∫_{−∞}^{+∞} |x|f_{X}(x) dx < ∞

(i.e. if we have absolute convergence) then we define the expected value (also call expectation or mean) of X to be

E[X] = ∫_{−∞}^{+∞} x f_{X}(x) dx.

Mnemonic: As in the discrete case, this is just the weighted sum of possible X values, weighted by their probabilities.

Definition 4.19. Let X be a continuous random variable. The variance of X is

E[(X − μ)^{2}]

where μ = E[X]. By the corollary to the Law of the Unconscious Statistician (below),

Var(X) = E[X^{2}] − E[X]^{2}.

Theorem 4.20 (Law of the Unconscious Statistician). Let X be a continuous random variable and g : ℝ → ℝ. Let Y = g(X). If

∫_{−∞}^{+∞} |g(x)| f_{X}(x) dx < ∞

then

E[Y] = ∫_{−∞}^{+∞} g(x) f_{X}(x) dx < ∞

Corollary 4.21. If g, h : ℝ → ℝ and a, b ∈ ℝ then

E[ag(X) + bh(X)] = aE[g(X)] + bE[h(X)].

5 Multiple continuous random variables

5.1 Definitions

Definition 5.1. Given two continuous random variables X and Y, we define their joint CDF to be

F_{X,Y} (x, y) = P (X ≤ x, Y ≤ y).

Definition 5.2. Two random variables X and Y are jointly continuous if there exists a function f_{X,Y} (x, y) (their joint PDF) such that

F_{X,Y} (x, y) = ∫_{−∞}^{x} ∫_{−∞}^{y} f_{X,Y} (u, v) dv du.

The joint PDF is thought of as

P (a ≤ X ≤ b, c ≤ Y ≤ d) = ∫_{x=a}^{x=b} ∫_{y=c}^{y=d} f_{X,Y} (x, y) dy dx

and more generally for A ⊆ ℝ^{2}

P ((x, y) ∈ A) = ∫ ∫_{A} f_{X,Y} (x, y) dy dx.

The joint CDF and joint PDF are related by

f_{X,Y} (x, y) = \frac{∂^{2}}{∂x∂y} F_{X,Y} (x, y)
F_{X,Y} (x, y) = ∫_{−∞}^{x} ∫_{−∞}^{y} f(u, v) dv du.

Given a joint CDF F_{X,Y} (x, y) we may recover the marginal CDFs F_{X}(x) and F_{Y} (y) by

F_{X}(x) = lim_{y→+∞} F_{X,Y} (x, y)

and similarly for F_{Y} (y). How do we recover the marginal PDFs given the joint PDFs? To derive the formula, differentiate the CDF:

f_{X}(x) = \frac{d}{dx}F_{X}(x) = \frac{d}{dx}F_{X,Y} (x, +∞)
= \frac{d}{dx} ∫_{−∞}^{+∞} [∫_{−∞}^{x} f_{X,Y} (u, v) du] dv
= \frac{d}{dx} ∫_{−∞}^{x} [∫_{−∞}^{+∞} f_{X,Y} (u, v) dv] du
= ∫_{−∞}^{+∞} f_{X,Y} (x, v) dv

i.e. the formula is

f_{X}(x) = ∫_{−∞}^{+∞} f_{X,Y} (x, y) dy.

That is, we integrate away one variable.

5.2 Independence

Definition 5.3. Two continuous random variables X and Y are independent iff their CDFs factor:

F_{X,Y} (x, y) = F_{X}(x)F_{Y} (y).

Remark 5.4. For discrete random variables, we defined independence (definition 3.7) in terms of the factoring of the PMFs; for continuous random variables, we define independence in terms of the factoring of the CDFs. Factorization of PDFs does hold (as shown in the following theorem), but it is a consequence rather than a definition.

Theorem 5.5. Two continuous random variables X and Y are independent iff their PDFs factor:

f_{X,Y} (x, y) = f_{X}(x)f_{Y} (y).

Proof.

f_{X,Y} (x, y) = \frac{∂^{2}}{∂x∂y} F_{X,Y} (x, y)
= \frac{∂^{2}}{∂x∂y} [F_{X}(x)F_{Y} (y)]
= \frac{∂}{∂x} [F_{X}(x)] \frac{∂}{∂y} [F_{Y} (y)]
= f_{X}(x)f_{Y} (y).

5.3 Expectations

Theorem 5.6 (Law of the Unconscious Statistician). Let X and Y be continuous random variables and g(x, y) : ℝ^{2} → ℝ. Let Z = g(X, Y). If

∫_{−∞}^{+∞} ∫_{−∞}^{+∞} |g(x, y)| f_{X,Y} (x, y) dx dy < ∞

then

E[Z] = ∫_{−∞}^{+∞} ∫_{−∞}^{+∞} g(x, y) f_{X,Y} (x, y) dx dy.

Corollary 5.7. Let X and Y be continuous random variables and let a, b ∈ ℝ. Then

E[aX + bY] = aE[X] + bE[Y].

Theorem 5.8. Let X and Y be independent continuous random variables and let g, h : ℝ → ℝ. Then

E[g(X)h(Y)] = E[g(X)]E[h(Y)].

Corollary 5.9. Let X and Y be independent continuous random variables. Then

E[XY] = E[X]E[Y].

Corollary 5.10. Let X and Y be independent continuous random variables. Then

Var(X + Y) = Var(X) + Var(Y).

Proof. Computation.

Remark 5.11. Expectations always add. They multiply only when X and Y are independent. Variances add only when X and Y are independent.

Theorem 5.12. Let X and Y be independent random variables and let g, h : ℝ → ℝ. Then g(X) and h(Y) are independent.

5.4 The IID paradigm: S_{n} and \overline{X}_{n}

Notation: Let X_{n} be a sequence of IID random variables, with common mean μ and common variance σ^{2}. We write

S_{n} = ∑_{i=1}^{n} X_{n}

and

\overline{X}_{n} = \frac{1}{n} ∑_{i=1}^{n} X_{n}.

The latter is called the sample mean of the X_{n}’s.

Mean and variance of S_{n}: We already know

E[S_{n}] = E [∑_{i=1}^{n} X_{i}] = ∑_{i=1}^{n} E[X_{i}] = nμ

and (using independence of the trials to split up the variance)

Var(S_{n}) = Var (∑_{i=1}^{n} X_{i}) = ∑_{i=1}^{n} Var(X_{i}) = nσ^{2}.

Mean and variance of \overline{X}_{n}: Likewise,

E[\overline{X}_{n}] = E [\frac{1}{n} ∑_{i=1}^{n} X_{i}] = \frac{1}{n} ∑_{i=1}^{n} E[X_{i}] = \frac{1}{n}nμ = μ

and (using independence of the trials to split up the variance)

Var(\overline{X}_{n}) = Var (\frac{1}{n} ∑_{i=1}^{n} X_{i}) = \frac{1}{n^{2}} Var (∑_{i=1}^{n} X_{i}) = \frac{1}{n^{2}} ∑_{i=1}^{n} Var(X_{i}) = \frac{nσ^{2}}{n^{2}} = \frac{σ^{2}}{n} .

5.5 Functions of multiple random variables

Let X, Y be continuous random variables and let g(x, y) : ℝ^{2} → ℝ. Let Z = g(X, Y). How do we find the PDF of Z? As in the univariate case (section 4.5), the method is to first find the CDF of Z, then differentiate.

[Need to type up the example from 3-21.]

[Need to type up convolution notes for independent X, Y from 3-23.]

f_{Z}(z) = ∫ f_{X}(x)f_{Y} (z − x)dx.

5.6 Moment-generating functions and characteristic functions

Definition 5.13. Much as in the discrete case (definitions 3.17),

M_{X}(t) = E[e^{tX}] = ∫_{−∞}^{+∞} e^{tx}f_{X}(x)dx

and

β_{X}(t) = E[e^{itX}] = ∫_{−∞}^{+∞} e^{itx}f_{X}(x)dx.

Proposition 5.14. We have:

(i) M_{X}^{(k)}(0) = E[X^{k}]. (ii) If Y = aX + b, then M_{Y} (t) = e^{bt}M_{X}(at). (iii) If X and Y are independent, then M_{X+Y} (t) = M_{X}(t)M_{Y} (t). Example 5.15. The standard normal random variable Z has (tedious computations omitted here) momentgenerating function

M_{Z}(t) = exp(t^{2}/2).

The general normal random variable X = μ + σZ has moment-generating function

M_{X}(t) = exp(μt + σ^{2}t^{2}/2).

Proposition 5.16. Let X_{1}, …, X_{n} be independent normal random variables with means μ_{i} and variances σ_{i}^{2}. Then Y = ∑ X_{i} has normal distribution with mean ∑ μ_{i} and variance ∑ σ_{i}^{2}.

5.7 Change of variables

Let X and Y be continuous random variables. If T : ℝ^{2} → ℝ^{2} is invertible, sending (U, V) = T (X, Y), then

∫_{D} f(x, y) dx dy = ∫_{T (D)} f(x(u, v), y(u, v)) |J(u, v)| du dv

where J(u, v) is the Jacobian matrix

J(u, v) = (\begin{matrix}∂x/∂u & ∂x/∂v \\ ∂y/∂u & ∂y/∂v \end{matrix}) .

Theorem 5.17. Let X and Y be jointly continuous random variables with PDF f_{X,Y} (x, y). Let

D = {(x, y) : f_{X,Y} (x, y) > 0}

i.e. the range of X, Y. Suppose T : D → S ⊆ ℝ^{2} is 1-1 and onto. Define new random variables U and V by (U, V) = T (X, Y). Then

f_{U,V} (u, v) = \begin{cases}f_{X,Y} (x(u, v), y(u, v)) |J(u, v)| & if(u, v) ∈ S \\ 0 & otherwise \end{cases}

where J(u, v) is as above.

5.8 Conditional density and expectation

Given two continuous random variables X and Y, we want to define P (X|Y = y). Since Y = y is a null event, the usual intersection-over-given notion of conditional probability (see section 1.2) will give us zero divided by zero. Somewhat as in l’Hôpital’s rule in calculus, we can nonetheless make sense of it. Definition 5.18. Let X, Y be jointly continuous with PDF f_{X,Y} (x, y). The conditional density of X given Y is

f_{X|Y} (x|y) = \begin{cases}\frac{f_{X,Y} (x,y)}{f_{Y} (y)}, & f_{Y} (y) ≠ 0 \\ 0, & f_{Y} (y) = 0. \end{cases}

Remark 5.19. Recall that

f_{Y} (y) = ∫_{x=−∞}^{x=∞} f_{X,Y} (x, y)dx

so we can think of the conditional density of X given Y as being

f_{X|Y} (x|y) = \frac{f_{X,Y} (x, y)}{∫_{x=−∞}^{x=+∞} f_{X,Y} (x, y)dx}

whenever the denominator is non-zero. Definition 5.20. Let X, Y be jointly continuous with PDF f_{X,Y} (x, y). The conditional expectation of X given Y is

E[X|Y = y] = ∫_{x=−∞}^{x=+∞} f_{X|Y} (x|y)dx.

Definition 5.21. E[X|Y = y] is a function of y; it must depend only on y. Call it g(y). Then g(Y) is a random variable, which we write as

E[X|Y].

This new random variable has the following properties. Theorem 5.22. Let X, Y, Z be random variables, a, b ∈ ℝ, and g : ℝ → ℝ. Then

• E[a|Y] = a.

• E[aX + bZ|Y] = eE[X|Y] + bE[Z|Y]. (Note: this is linearity on the left; linearity on the right emphatically does not hold.)

• If X ≥ 0 then E[X|Y] ≥ 0.

• If X, Y are independent then E[X|Y] = E[X]. (Mnemonic: Y gives no information about X.)

• E[E[X|Y]] = E[X]. (This is the partition theorem in disguise. See below.)

• E[Xg(Y)|Y] = g(Y)E[X|Y]. (Mnemonic: given a specific y, g(y) is constant.)

• Special case: E[g(Y)|Y] = g(Y).

5.9 The bivariate normal distribution

If X and Y are independent and standard normal, then their joint PDF is

f_{X,Y} (x, y) = \frac{1}{2π} exp (−\frac{x^{2} + y^{2}}{2} ) . (∗)

It is possible for X and Y to not be independent, while their marginals are still standard normal. In fact, there is a 1-parameter family of such X, Y pairs.

Definition 5.23. Let −1 < ρ < 1. The bivariate normal distribution with parameter ρ has PDF

f_{X,Y} (x, y)\frac{1}{2π\sqrt{1 − ρ^{2}}} exp (−\frac{x^{2} − 2ρxy + y^{2}}{2(1 − ρ^{2}} ) .

Remark 5.24. Note the following:

• It is straightforward but tedious to verify that ∫ ∫ f_{X,Y} (x, y) = 1.

• With ρ = 0 we obtain equation (*) as a special case.

• One may complete the square and use translation invariance of the integral to find that the marginals are in fact univariate standard normals.

• Again completing the square, one finds that f_{Y |X}(y|x) is normal with μ = ρx and σ^{2} = 1 − ρ^{2}.

5.10 Covariance and correlation

Definition 5.25. Let X and Y be random variables with means μ_{X} and μ_{Y}, respectively. The covariance of X and Y is

Cov(X, Y) = E[(X − μ_{X})(Y − μ_{Y})] = E[XY] − E[X]E[Y].

Mnemonic 5.26. With Y = X we recover the familiar formula (definition 4.19) for the variance of X: E[X^{2}] − E[X]^{2}.

Theorem 5.27. Let X and Y be random variables. Then

Var(X + Y) = Var(X) + 2Cov(X, Y) + Var(Y).

Remark 5.28. Bill Faris calls this the “most important theorem in probability”.

Corollary 5.29. If Cov(X, Y) = 0 then Var(X + Y) = Var(X) + Var(Y).

Theorem 5.30. If X and Y are independent then Cov(X, Y) = 0. The converse does not hold.

Definition 5.31. Let X and Y be random variables with variances σ_{X}^{2} and σ_{Y}^{2} , respectively. The correlation coefficient of X and Y is

ρ(X, Y) = \frac{Cov(X, Y)}{σ_{X}σ_{Y}}.

Remark 5.32. The covariance is quadratic in X and Y (with respect to linear rescaling); the correlation coefficient is scale-invariant.

Theorem 5.33. The correlation coefficient satisfies

−1 ≤ ρ(X, Y) ≤ 1.

Proof. It suffices to show |ρ(X, Y)| ≤ 1, which is equivalent to showing |Cov(X, Y)| ≤ σ_{X}σ_{Y}. Faris claims that this follows from the Schwarz inequality (|u · v| ≤ ∥u∥ ∥v∥), although I don’t see the immediacy.

He then sketches another route, which I complete here. Normalize X and Y as follows. Let μ_{X}, μ_{Y}, σ_{X}, and σ_{Y} be their means and standard deviations, respectively. Then

\frac{X − μ_{X}}{σ_{X}} and \frac{Y − μ_{Y}}{σ_{Y}}

each have zero mean and unit standard deviation. (In particular this will mean, below, that their second moments are 1.) We can create a new pair of random variables

(\frac{X − μ_{X}}{σ_{X}} ± \frac{Y − μ_{Y}}{σ_{Y}} )^{2} .

Since each takes non-negative values, the means are non-negative as well [xxx xref forward to where this is proved … it seems obvious but actually requires proof]:

E [(\frac{X − μ_{X}}{σ_{X}} ± \frac{Y − μ_{Y}}{σ_{Y}} )^{2}] ≥ 0.

FOILing out we have

E [(\frac{X − μ_{X}}{σ_{X}} )^{2} ± \frac{2(X − μ_{X})(Y − μ_{Y})}{σ_{X}σ_{Y}} + (\frac{Y − μ_{Y}}{σ_{Y}} )^{2}] ≥ 0.

Using the linearity of expecation and recalling that the normalized variables have second moments equal to 1, we have

2 ± 2E [\frac{(X − μ_{X})(Y − μ_{Y})}{σ_{X}σ_{Y}}] ≥ 0
−1 ≤ E [\frac{(X − μ_{X})(Y − μ_{Y})}{σ_{X}σ_{Y}}] ≤ 1
−σ_{X}σ_{Y} ≤ E [(X − μ_{X})(Y − μ_{Y})] ≤ σ_{X}σ_{Y}
−σ_{X}σ_{Y} ≤ Cov(X, Y) ≤ σ_{X}σ_{Y}
|Cov(X, Y)| ≤ σ_{X}σ_{Y} .

6 Laws of averages

Here is a statistics paradigm. Run an experiment n with IID random variables X_{n} (whether continuous or discrete). The n-tuple (X_{1}, …, X_{n}) is called a sample. The average of X_{1} through X_{n} is called the sample mean, written \overline{X}_{n}; it is also a random variable.

The big question is: what does \overline{X}_{n} look like as n gets large? For example, roll a 6-sided die (so μ = 3.5) a million times. What is the probability of the event |\overline{X}_{n} − 3.5| > 0.01? One would hope this probability would be small, and would get smaller as n increases.

We have two main theorems here:

• The law of large numbers says that \overline{X}_{n} → μ, although we need to define the notion of convergence of a random variable to a real number. There are two flavors of convergence: weak and strong.

• The central limit theorem describes the PDF of \overline{X}_{n}.

6.1 The weak law of large numbers

Definition 6.1. Let X_{n} and X be random variables. We say X_{n} → X in probability if for all ε > 0,

lim_{n→∞} P ({ω ∈ Ω : |X_{n}(ω) − X(ω)| > ε}) = 0.

More tersely, we may write

P (|X_{n} − X| > ε) → 0.

Theorem 6.2 (Weak law of large numbers). Let X_{n} be an IID sequence with common mean μ and finite variance σ^{2}. Then

\overline{X}_{n} = \frac{1}{n} ∑_{i=1}^{n} X_{i} → μ

in probability.

Here is another notion of convergence.

Definition 6.3. Let X_{n} and X be random variables. We say X_{n} → X in mean square if

E[(X_{n} − X)^{2}] → 0.

Theorem 6.4 (Chebyshev’s inequality). Let X be a random variable with finite variance. Let a > 0. Then

P (|X − μ| ≥ a) ≤ \frac{E[(X − μ)^{2}]}{a^{2}}

Remark 6.5. This means

P (|X − μ| ≥ a) ≤ \frac{Var(X)}{a^{2}}.

Proof. Use the partition theorem with two partitions on some as-yet-unspecified event A:

E[(X − μ)^{2}] = E [(X − μ)^{2} | A] P (A) + E [(X − μ)^{2} | A^{c}] P (A^{c}).

Regardless of what A is, the last term is non-negative. So we have

E[(X − μ)^{2}] ≥ E [(X − μ)^{2} | A] P (A).

Now let A be the particular event that |X − μ| ≥ a. Then we have

E[(X − μ)^{2}] ≥ E [(X − μ)^{2} | |X − μ| ≥ a] P (|X − μ| ≥ a)
= E [(X − μ)^{2} | (X − μ)^{2} ≥ a^{2}] P (|X − μ| ≥ a)
≥ a^{2}P (|X − μ| ≥ a).

Dividing through by a^{2} we have

P (|X − μ| ≥ a) ≤ \frac{E[(X − μ)^{2}]}{a^{2}}

as desired. Theorem 6.6. Convergence in mean square implies convergence in probability.

Proof. Let ε > 0. We need to show P (|X_{n} − X| > ε) → 0. By Chebyshev’s inequality,

P (|X_{n} − X| > ε) ≥ \frac{1}{ε^{2}} E[(X_{n} − X)^{2}].

Remark 6.7. Notes about Chebyshev’s inequality:

• It is used in the proof of the weak law, which I am omitting.

• The bounds provided by Chebyshev’s inequality are rather loose, but they are certain. The central limit theorem gives tighter bounds, but only probabilistically.

6.2 The strong law of large numbers

Here is a third notion of convergence. Definition 6.8. We say X_{n} → X with probability one (w.p. 1) or almost surely (a.s.) if

P ({ω ∈ Ω : lim_{n→∞} X_{n}(ω) = X(ω)}) = 1.

More tersely, we may write

P (X_{n} → X) = 1.

Theorem 6.9 (Strong law of large numbers). Let X_{n} be an IID sequence with common mean μ. Then \overline{X}_{n} → μ with probability 1. Theorem 6.10. X_{n} → X w.p. 1 implies X_{n} → X in probability. Remark 6.11. This means the strong law is stronger than the weak law.

6.3 The central limit theorem

Motivation. Let X_{n} be an IID sequence and let S_{n} = ∑ X_{n}. We know from section 5.4 that E[S_{n}] = nμ and Var(S_{n}) = nσ^{2}. We expect the PDF of S_{n} to be centered at nμ with width approximately \sqrt{n}σ. Likewise, if \overline{X}_{n} = ∑ X_{n}/n then we know that E[\overline{X}_{n}] = μ and Var(\overline{X}_{n}) = σ^{2}/n. We expect the PDF of S_{n} to be centered at nμ with width approximately σ/\sqrt{n}. For various distributions, one finds empirically that these PDFs look approximately normal if n is large.

Definition 6.12. Let X be a random variable with mean μ and variance σ^{2}. The standardization or normalization of X is

\frac{X − μ}{σ}.

In particular, if we standardize S_{n}, we get

Z_{n} = \frac{S_{n} − nμ}{σ\sqrt{n}}

with mean 0 and variance 1:

Var(Z_{n}) = \frac{1}{σ^{2}n}Var(S_{n} − nμ) = \frac{1}{σ^{2}n}Var(S_{n}) = \frac{nσ^{2}}{nσ^{2}} = 1.

Likewise, if we standardize \overline{X}_{n}, we get

\frac{\overline{X}_{n} − μ}{σ\sqrt{n}}.

The central limit theorem says that the standardizations of S_{n} and \overline{X}_{n} both approach standard normal for large n.

Definition 6.13. Let Φ(x) be the CDF of the standard normal:

Φ(x) = \frac{1}{\sqrt{2π}} ∫_{−∞}^{+∞} e^{−x^{2}/2}dx.

Theorem 6.14. Let X_{n} be an IID sequence with finite mean μ and finite non-zero variance σ^{2}. Let Z_{n} be the standardization of S_{n} as above. Then

P (Z_{n} ≤ x) → Φ(x)

for all x.

Remark 6.15. This convergence is called convergence in distribution.

xxx include some examples here.

6.4 Confidence intervals

Here is an application of the Central Limit Theorem to statistics. The population is a random variable X. A sample of size n is n IID copies of X. The random variable X has a (true) population mean μ_{X} but we do not know what it is; all we have is the sample mean \overline{X}_{n} = ∑_{k=1}^{n} X_{k}/n, which is an estimate of the population mean. We would like to put some error bars on this estimate.

We quantify this problem using the notion of confidence intervals. We look for ε > 0 such that

P (|\overline{X}_{n} − μ_{X}| ≥ ε) = 0.05

or, alternatively,

P (|\overline{X}_{n} − μ_{X}| < ε) = 0.95.

(Five percent is a conventional value in statistics.)

Using the CLT, we treat \overline{X}_{n} as being approximately normal. We standardize it (statisticians call this taking the z-score) in the usual way:

Z = \frac{\overline{X}_{n} − μ_{\overline{X}_{n}}}{σ_{\overline{X}_{n}}} = \frac{\overline{X}_{n} − μ_{X}}{σ_{X}/\sqrt{n}} .

Then

P (|\overline{X}_{n} − μ_{X}| ≥ ε) = P (|\overline{X}_{n} − μ_{X}| ≥ ε)

= P (\frac{|\overline{X}_{n} − μ_{X}|}{σ_{X}/\sqrt{n}} ≥ \frac{ε}{\sqrt{n}})

≈ P (Z ≥ \frac{ε}{\sqrt{n}}) = 0.05.

It’s worth memorizing (or you can compute it if you prefer) that the standard normal curve has area 0.95 for Z running from −1.96 to +1.96. So, ε/(σ_{X}/\sqrt{n}) should be 1.96. Solving for ε in terms of n gives

ε = \frac{1.96σ_{X}}{\sqrt{n}} .

Note that this requires the population standard deviation to be known. (We can compute the sample standard deviation and use that as an estimate of the population standard deviation σ_{X}, but we’ve not developed any theory as to the error in that estimate.)

Example 6.16. ▷ Let X have the Bernoulli distribution with parameter p — flip a coin with probability p of heads; assign the value 0 to tails and 1 to heads. Recall from section 2.2 that X has mean p. (In section 2.2 we took tails to be 1; I have changed the convention.) Suppose you flip the coin 1000 times (i.e. n = 1000) and obtain 520 heads. Then \overline{X}_{n} = 0.520. Then

ε = \frac{1.96\sqrt{p(1 − p)}}{\sqrt{1000}} ≈ 0.0619\sqrt{p(1 − p)}.

For p = 0.5, ε ≈ 0.031. Thus we are 95% certain that μ_{X} is within 0.031 on either side of 0.520, i.e. between 0.489 and 0.551. ◁

A The coin-flipping experiments

This section is an extended worked example, tying together various concepts. We apply the Central Limit Theorem first to repeated tosses of a single coin, then to repeated collections of tosses.

A.1 Single coin flips

The first experiment is tossing a single coin which has probability p of heads. Then Ω = {T, H}. Let X be the random variable which takes value 0 for tails and 1 for heads. As discussed in section 2.2, X has the Bernoulli distribution with parameter p. I will allow p to vary throughout this section, although I will focus on p = 0.5 and p = 0.6. Recall that X has mean

μ_{X} = p.

(In section 2.2 we took 1 for tails which is the opposite convention from the one here.) Its standard deviation is

σ_{X} = \sqrt{p(1 − p)},

which is \sqrt{0.25} = 0.5 and \sqrt{0.24} ≈ 0.4899 for p = 0.5 and p = 0.6, respectively.

Now flip the coin a large number n of times — say, n = 1000 — and count the number of heads. Using the notation of section 5.4, the number of heads is S_{n}. There are two ways to look at this.

• On one hand, from section 2.2 we know that S_{n} is geometric with parameters p and n — if we think of the 1000 tosses as a single experiment. (This is precisely what we will do in the next section.) The PMF of S_{n} is the one involving binomial coefficients; we would expect

μ_{S_{n}} = np

i.e. 500 or 600 and

σ_{S_{n}} = \sqrt{np(1 − p)}

which is \sqrt{250} ≈ 15.81 or 240 ≈ 15.49 for p = 0.5 and p = 0.6, respectively.

• On the other hand, the Central Limit Theorem (section 6.3) says that as n increases, the distribution of S_{n} begins to look normal. This PDF involves the exponential function, as shown in section 5.4. The mean of the sums S_{n} is

μ_{S_{n}} ≈ nμ_{X} = np

(again 500 or 600). The standard deviation of those sums about the means 500 or 600 is

σ_{S_{n}} ≈ \sqrt{n}σ_{X} = \sqrt{np(1 − p)}

which are again 15.81 and 15.49, respectively.

Note that the binomial PMF and the normal PDF are not the same, even though they produced the same means and standard deviations: the geometric random variable has an integer-valued PMF; P (499.1 ≤ S_{n} ≤ 499.9) = 0 and likewise S_{n} can never be anything out of the range from 0 to 1000. The normal PDF, on the other hand, gives P (499.1 ≤ S_{n} ≤ 499.9) ≠ 0 since we are taking area under a curve where the function is non-negative. Since the output of the exponential function is never 0, the normal PDF gives non-zero (although admittedly very, very tiny) probability of S_{n} being less than 0 or greater than 1000. (See also [MM] for some very nice plots.)

Now we can ask about fairness of coins. The probabilistic point of view is to fix p and ask about the probabilities of various values of S_{n}. If the coin is fair, what are my chances of flipping anywhere between 470 and 530 heads? Using the geometric PMF is a mess — in fact, my calculator can’t compute \binom{1000}{470} without overflow. Using the normal approximation, though, is easy. I asked my TI-83 to integrate its normalpdf function, with μ = 500 and σ = 15.81, from 470 to 530 and it told me 0.9422.

How surprised should I be if I toss 580 heads? The standardization, which [MM] call the z-score, of S_{n} is (definition 6.12)

z = \frac{S_{n} − μ_{S_{n}}}{σ_{S_{n}}} .

This counts how many standard deviations away from the mean a given observation is. I have 80/15.81 ≈ 5.06 so this result is more than five standard deviations away from the mean. I would not think the coin is fair. If I re-do that computation with p = 0.6, μ_{S_{n}} = 600, and σ_{S_{n}} = 15.49, I get a z-score of −1.29 which is not surprising if the coin has parameter p = 0.6.

The point of view used in statistics is to start with the data, and from that try to estimate with various levels of confidence what the parameters are. Given a suspicious coin, what experiments would we have to run to be 95% sure that we’ve find out what the coin’s parameter p is, to within, say, ±0.01? Continuing the example from section 6.4, we ask for ε = 0.01. We had

ε = \frac{1.96σ_{X}}{\sqrt{n}}

so, setting ε = 0.01 and solving for n, we have

n = (\frac{1.96σ_{X}}{0.01} )^{2} = (\frac{1.96\sqrt{p(1 − p)}}{0.01})^{2} ≈ 38416 p(1 − p).

Now, p(1 − p) has a maximum at p = 0.5, for which n = 9604, so that many flips would determine p to within ±0.01 with 95% confidence. Re-doing the arithmetic with 0.001 in place of 0.01 gives n = 960, 400. Generalizing, we see that each additional decimal place costs 100 times as many runs.

A.2 Batches of coin flips

The second experiment is 1000 tosses of a coin where each coin has probability p of heads. (Or, think of simultaneously tossing 1000 identical such coins.) Then #Ω = 2^{1000} ≈ 10^{301}. Let Y : Ω → ℝ be the random variable which counts the number of heads. This is an example where the random variable is far easier to deal with than the entire sample space (which is huge).

As discussed in section 2.2, Y has the binomial distribution with parameters p and n = 1000. Recall from the previous section that that Y has mean

μ_{Y} = 1000p,

e.g. 500 or 600. Likewise, its standard deviation is

σ_{Y} = \sqrt{1000p(1 − p)},

which is \sqrt{250} ≈ 15.81 or 240 ≈ 15.49 for p = 0.5 and p = 0.6, respectively.

Let \overline{Y}_{N} be the average of N runs of this experiment — that is, the sample mean. The Central Limit Theorem (section 6.3) says that as N increases, the distribution of \overline{Y}_{N} begins to look normal. The mean of the sample means is

μ_{\overline{Y}_{N}} ≈ μ_{Y} = 1000p,

which is again 500 or 600. The standard deviation of the sample means is

σ_{\overline{Y}_{N}} ≈ \frac{σ_{Y}}{\sqrt{N}} = \frac{\sqrt{np(1 − p)}}{N}.

This is 15.81/\sqrt{N} or 15.49/\sqrt{N}, respectively.

Here is the (crucial) interpretation: Given the parameters p and n of Y, there is a true population mean and a true population standard deviation. If p = 0.5, then σ_{Y} ≈ 15.81 and even if we’re on the three millionth iteration of the flip-1000-coins experiment, it’s still going to be quite likely as ever that we’ll get a 514 or a 492 and so on. If we don’t know the true p of the coins then, while the true population mean μ_{Y} and the true population standard deviation σ_{Y} exist, we don’t know what they are. All we have is some suspicious-looking identical coins and our laboratory equipment. As we run and re-run the flip-1000-coins experiment, the following happens:

• The sample mean μ_{\overline{Y}_{N}}, for increasingly larger N, will approach the population mean μ_{Y}.

• The variations of the sample mean will decrease. We might say the error in our estimate of the population mean is shrinking.

• The population standard deviation appears in the above formulas via its effects on the standard deviation of the sample mean.

• Nothing we have done so far has given us a reliable connection between the sample standard deviation and the population standard deviation. We can guess that the sample standard deviation approaches the population standard deviation, but (in this course) we have not developed any information about the error in that computation.

Here is a numerical example. I run (simulated on a computer) the flip-1000-coins experiment 400 times. The first time I get 482, so the sample mean is 482. The second time I get 521, so the sample mean is (482 + 521)/2. The third time I get 494, so the sample mean is (482 + 521 + 494)/3 and so on.

Here is p = 0.5:

N  Y \overline{Y}_{N}  Sample std. dev.
1 482 482.000  N/A
2 521 501.500  27.577
3 494 499.000  19.975
4 512 502.250  17.557
5 485 498.800  17.050
6 507 500.167  15.613
⋮  ⋮ ⋮  ⋮
395 493 500.258  16.163
396 505 500.270  16.144
397 501 500.272  16.124
398 494 500.256  16.107
399 501 500.258  16.086
400 474 500.192  16.120

Here is p = 0.6:

N  Y \overline{Y}_{N}  Sample std. dev.
1 616 616.000  N/A
2 584 600.000  22.627
3 620 606.667  19.732
4 617 609.250  16.919
5 583 604.000  18.775
6 613 605.500  17.190
⋮  ⋮ ⋮  ⋮
395 608 599.484  17.031
396 615 599.523  17.027
397 609 599.547  17.013
398 607 599.565  16.995
399 604 599.576  16.975
400 611 599.605  16.964

B Bayes’ theorem

Bayes’ theorem is so important that it merits multiple points of view: algebraic, graphical, and numerical.

B.1 Algebraic approach

Recall from definition 1.12 that if A is an event, and if B is another event with non-zero probability, the conditional probability of A given B is

P (A|B) = \frac{P (A ∩ B)}{P (B)}.

Bayes’ theorem tells us how to invert this: how to compute the probability of B given A. First, the algebraic treatment.

Theorem B.1 (Bayes’ theorem). Let A and B be events with non-zero probability. Then

P (B|A) = P (A|B) \frac{P (B)}{P (A)}.

Proof. Using the definition (intersection over given), we have

P (B|A) = \frac{P (B ∩ A)}{P (A)}.

Multiplying top and bottom by P (B) (which is OK since P (B) ≠ 0) we get

P (B|A) = \frac{P (B ∩ A)}{P (A)} \frac{P (B)}{P (B)}.

Now notice that B ∩ A is the same as A ∩ B, so in particular P (B ∩ A) is the same as P (A ∩ B). Transposing the terms in the denominator gives us

P (B|A) = \frac{P (A ∩ B)}{P (B)} \frac{P (B)}{P (A)}
= P (A|B) \frac{P (B)}{P (A)}

as desired.

B.2 Graphical/numerical approach

The following example is adapted from [KK]. Suppose that 0.8% of the general population has a certain disease, and suppose that we have a test for it. Specifically, if a person actually has the disease, the test says so 90% of the time. If a person does not have the disease, the test gives a false diagnosis 7% of the time. When a particular patient tests positive, what is the probability they have the disease?

We can write this symbolically as follows. Let D be the event that the person has the disease and \overline{D} be its complement; let Y (for “yes”) be the event that the test says the person has the disease, with complement \overline{Y}. Writing the given information in these terms, we have:

P (D) = 0.008
P (Y |D) = 0.90
P (Y |\overline{D}) = 0.07.

Before computing any conditional probabilities, let’s find the probability of Y by itself. Using the partition theorem (theorem 1.18) we know this is

P (Y) = P (Y |D) P (D) + P (Y |\overline{D}) P (\overline{D})
= 0.90 · 0.008 + 0.07 · 0.992
= 0.077.

So the non-conditional probabilities are

P (\overline{D}) = 0.992  P (\overline{Y}) = 0.923
P (D) = 0.008  P (Y) = 0.077.

Looking at D and Y separately, we can think of the population at large as being split into those with and without the disease, and those for whom the test is positive or negative. Suppose in particular that we have a sample of 1000 people who are representative of the general population. Here are some (very rectangular) Venn diagrams:

\begin{matrix}\overline{D} & D \\ 992 & 8 \end{matrix}  \begin{matrix}923 & \overline{Y} \\ 77 & Y \end{matrix}

Bayes’ theorem has to do with how these two partitions intersect to make four groups:

\begin{matrix}\overline{D} & D \\ P (\overline{Y} |\overline{D}) · 992 =? & P (\overline{Y} |D) · 8 =? & \overline{Y} \\ P (Y |\overline{D}) · 992 =? & P (Y |D) · 8 =? & Y \end{matrix}  and  \begin{matrix}\overline{D} & D \\ P (\overline{D}|\overline{Y}) · 923 =? & P (D|\overline{Y}) · 923 =? & \overline{Y} \\ P (\overline{D}|Y) · 77 =? & P (D|Y) · 77 =? & Y \end{matrix}

We can use the theorem to find the probability our patient has the disease, given the positive test result:

P (D|Y) = P (Y |D) \frac{P (D)}{P (Y)}
= 0.90 · \frac{0.008}{0.077}
= 0.094.

That is, there’s only a one-in-eleven chance the patient actually has the disease. Kaplan and Kaplan’s idea is to look at this surprising result in the context of the other 999 people also tested. I will elaborate on this, working out all the math.

We have two conditional probabilities given: P (Y |D) and P (Y |\overline{D}). We found P (D|Y). What about P (D|\overline{Y})? We can use the partition theorem (theorem 1.18) again to solve for what we don’t know in terms of what we do know:

P (D) = P (D|Y) P (Y) + P (D|\overline{Y}) P (\overline{Y})
P (D|\overline{Y}) = \frac{P (D) − P (D|Y) P (Y)}{P (\overline{Y})}
= \frac{0.008 − 0.094 · 0.077}{0.923}
= 0.0008.

We now have all four conditional probabilities:

P (Y |\overline{D}) = 0.07  P (D|\overline{Y}) = 0.0008
P (Y |D) = 0.90  P (D|Y) = 0.094.

Now we can fill out the four-square table:

• Since P (Y |\overline{D}) = 0.07, seven percent of the 992 disease-free people (70 of them) get false positives; the rest (922) get a correct negative result.

• Since P (Y |D) = 0.90, ninety percent of the 8 people with the disease test positive (i.e. all but one of them); one of the 8 gets a false sense of security.

• Since P (D|\overline{Y}) = 0.0008, 0.08% of the 923 with negative test results (one person) does in fact have the disease; the other 922 (as we found just above) get a correct negative result.

• Since P (D|Y) = 0.094, only 9.4% of the 77 people with positive test results (7 people) have the disease; the other 70 get a scare (and, presumably, a re-test).

So, the sample of 1000 people splits up as follows:

\begin{matrix}\overline{D} & D \\ 922 & 1 & \overline{Y} \\ 70 & 7 & Y \end{matrix}

Moreover, we can rank events by likelihood:

(1) Healthy people correctly diagnosed: 92.2%.

(2) False positives: 7%.

(3) People with the disease, correctly diagnosed: 0.7%.

(4) False negatives: 0.1%.

Now it’s no surprise our patient got a false positive: this happens 10 times as often as a correct positive diagnosis.

B.3 Asymptotics

The specific example provided some insight, but what happens when we vary the parameters? We had

P (D|Y) = \frac{P (Y |D) P (D)}{P (Y)} = \frac{P (Y |D) P (D)}{P (Y |D) P (D) + P (Y |\overline{D}) P (\overline{D})}.

Let’s turn this into a design problem. Let

p = = P (D)
a = = P (Y |D)
b = = P (Y |\overline{D})
1 − ε = P (D|Y)
ε = P (\overline{D}|Y).

How would you choose the test-design parameters a and b (i.e. how good would your test have to be) to get ε small? What if the disease is rarer (p smaller)?

Suppose we want a high likelihood of correct detection, i.e. ε small. Then

P (D|Y) = \frac{P (Y |D) P (D)}{P (Y |D) P (D) + P (Y |\overline{D}) P (\overline{D})}
= \frac{ap}{ap + b(1 − p)}
P (\overline{D}|Y) = \frac{b(1 − p)}{ap + b(1 − p)}
\frac{b(1 − p)}{ap + b(1 − p)} < ε.

Solving for a and b we get

\frac{a}{b} > \frac{(1 − ε)(1 − p)}{εp}.

There are two free parameters, a and b, so I’ll just consider their ratio. Now, the function

\frac{1 − x}{x}

blows up near zero; for small x, it’s approximately 1/x. For small ε and p we have

\frac{b}{a} < εp.

If, say, we have p and ε both 0.001, then a and b need to differ by a factor of a million. Recall that a and b are both probabilities, and so range between zero and one. To test a one-in-a-million event with 99.99% confidence (p = 10^{−6} and ε = 10^{−4}), b must be less than 10^{−10}.

That tells us how to choose P (Y |\overline{D}) to in order to get P (\overline{D}|Y), i.e. the probability of false positives, small. What about false negatives: P (D|\overline{Y})? If you do similar algebra to the above you should find that getting less than ε requires

1 − a < \frac{ε}{p}.

This is a less strict constraint: P (Y |D) needs to be very close to 1 only when ε ≪ p.

B.4 Conclusions

Some points:

• P (Y |D) is information known to the person who creates the test — say, at a pharmaceutical company; P (D|Y) is information relevant to the people who give and receive the test — for example, at the doctor’s office. This duality between design and implementation suggests that Bayes’ theorem has important consequences in many practical situations.

• The results can be surprising — after all, in the example above the test was 90% accurate, was it not? Bayes’ theorem is important to know precisely because it is counterintuitive.

• We can see from the example and the asymptotics above that rare events are hard to test accurately for. If we want certain testing for rare events, the test might be impossible (or overly expensive) to design in practical terms.

C Probability and measure theory

Probability theory is measure theory with a soul. — Mark Kac.

Modern probability is a special case of measure theory, but this course avoids the latter. Here we draw the connections for the reader with a measure-theoretic background. (Full information may be found in [FG], but I like to have a brief, handy reference. See also [Fol], [Rud], or [Roy].)

Measure theory / analysis

Probability

The sample space Ω is simply a set.

Same.

Measure theory / analysis

Probability

A σ-field F on Ω is a subset of 2^{Ω} satisfying the axioms of definition 1.5; F must contain at least ∅ and Ω, and it must be closed under complements, countable unions, and countable intersections.

Same.

Note that even if Ω is uncountable (for example, Ω = ℝ), 2^{Ω} still satisfies the axioms for a σ-field. If Ω is a topological space (e.g. ℝ^{d}), the standard σ-field is the Borel σ-field which is the one generated by all the open sets of Ω.

Measure theory / analysis

Probability

The pair (Ω, F) is called a measurable space. This is an unfortunate misnomer since it may not be possible to put a measure on it — in which case we would certainly think of it as “unmeasurable”!

Same.

Measure theory / analysis Probability ; Elements of F are called measurable sets. This is also a misnomer because we haven’t defined measures yet! An event is nothing more than a measurable set.

Measure theory / analysis Probability ; A measure is a function μ : F → [0, +∞] with the following properties: • μ(∅) = 0. • For all A ∈ F, μ(A) ≥ 0. • If A_{1}, A_{2}, …, is a finite or countable sub- set of F, with the A_{i}’s all (pairwise) dis- joint, then P (∪_{i}A_{i}) = ∑_{i} P (A_{i}). This is the countable additivity property of the probability measure μ. A probability measure is a measure with the additional requirement that μ(Ω) = 1. Thus, we have μ : F → [0, 1].

Note that if Ω is finite or countably infinite, it is possible to define a measure on the biggest σ-field on Ω, namely, F = 2^{Ω}. If Ω = ℝ, then it is not possible to define a measure on F = 2^{Ω}. See [Fol] for a proof.

Measure theory / analysis Probability ; A measure space is a triple (Ω, F, μ) where μ is a measure on F. A probability space is a triple (Ω, F, P) where P is a probability measure on F.

Measure theory / analysis Probability ; A measurable function is a function f from one measurable space (Ω, F) to another measurable space (Ψ, G) such that the preimage under f of each measurable set in Ψ is a measurable set in Ω. That is, for all B ∈ G, f^{−1}(B) ∈ F. A random variable is a measurable function X from a probability space (Ω, F, P) to a measur- able space (Ψ, G). For this course, that measurable space has been Ψ = ℝ, with G being the Borel sets in ℝ.

Measure theory / analysis

Probability

Expectation: ∫ X(ω) dP (ω).

Expectation: E[X].

Remark C.1. In an undergraduate context, we use the terms probability density function and cumulative distribution function. In a graduate context, we use the following:

• We have a real-valued random variable X. That is, we have X : Ω → ℝ where (Ω, F, P) is a probability space and the measurable space is (ℝ, B), namely, the reals with the Borel σ-algebra.

• This gives us a probability measure μ_{X} on ℝ by μ_{X}(B) = P (X^{−1}(B)). This is called simply the distribution of X.

• We can then measure the particular Borel sets (−∞, x]. This defines a function F_{X}(x) = μ_{X}((−∞, x]). This (the CDF) is called the distribution function of X.

• If dμ_{X} is absolutely continuous with respect to Lebesgue measure, i.e. dμ_{X} = f_{X}(x) dx (where f_{X}(x) is the familiar PDF), we say f_{X}(x) is the density of X.

Measure theory / analysis Probability ; The Laplace and Fourier transforms, respectively, of f : ℝ → ℝ are (Lf)(t) = ∫_{ℝ} e^{tx} f(x) dt and (Ff)(t) = ∫_{ℝ} e^{itx} f(x) dt. The moment-generating and characteristic func- tions, respectively, of a real-valued random vari- able X are M_{X}(t) = E[e^{tX}] and β_{X}(t) = E[e^{itX}]. Let μ be the distribution of X. We say that the moment-generating and characteristic func- tions are the Laplace transform and Fourier transform, respectively, of the measure μ: Lμ = ∫_{ℝ} e^{tx} dμ and Fμ = ∫_{ℝ} e^{itx} dμ. If the distribution of X has a density function f(x), i.e. dμ = f(x)dx where dμ is absolutely continuous with respect to Lebesgue measure dx, then these are M_{X}(t) = E[e^{tX}] = ∫_{ℝ} e^{tx} f(x) dx = (Lf)(t) and β_{X}(t) = E[e^{itX}] = ∫_{ℝ} e^{itx} f(x) dx = (Ff)(t).

xxx 8-29 cty of finite measures. xxx three kinds of measures: discrete, cts, singular. xxx 9-5 and 9-24: MCTx2, DCTx2, Fub, Fatou xxx cvgce: a.s./w.p.1; i.p.; i.m.s.; in dist (10-29 & 10-31) flavors. xxx 9-14 Borel-Cantelli. xxx 9-26 σ-field indep. xxx 9-28 prod meas xxx 10-19 Kolm 0-1 and tail field?

D A proof of the inclusion-exclusion formula

Proposition (Inclusion-exclusion formula). Let A_{1}, …, A_{n} be events. Then

P (∪_{i=1}^{n}A_{i}) = ∑_{1≤i≤n} P (A_{i})− ∑_{1≤i<j≤n} P (A_{i} ∩A_{j})+ ∑_{1≤i<j<k≤n} P (A_{i} ∩A_{j} ∩A_{k})−…+(−1)^{n+1}P (A_{1} ∩…∩A_{n}).

Proof. The proof is by strong induction. For the base case n = 1, the left-hand side is P (A) and the right-hand side is also P (A).

* * *

A bonus case, n = 2, is not necessary but helps to illustrate what’s going on. The formula is

P (A ∪ B) = P (A) + P (B) − P (A ∩ B).

This is easy to prove using Venn diagrams and finite additivity of P on the disjoint sets A \ B, A ∩ B, and B \ A. I am not including a picture in this note. The point, though, is that if A and B overlap, then A ∩ B is counted twice (overcounted) in P (A ∩ B), so we need to subtract off P (A ∩ B) to compensate.

* * *

Now for the induction step. Suppose the inclusion-exclusion formula is true for 1, 2, …, n − 1 (we’ll only need 2 and n − 1), and show it’s true for n. Notationally, this is a mess. I’ll do the n = 3 case since it is easier to understand. This will illuminate how to proceed in the messier general case.

For n = 3, we are asked to show that

P (A ∪ B ∪ C) = P (A) + P (B) + P (C) − P (A ∩ B) − P (A ∩ C) − P (B ∩ C) + P (A ∩ B ∩ C).

Since we want to use induction, we can try to isolate C from A and B. We can write

P ((A ∪ B) ∪ C) = P (A) + P (B) +P (C)
−P (A ∩ B) −P (A ∩ C) − P (B ∩ C)
+P (A ∩ B ∩ C).

We have

P (A) + P (B) − P (A ∩ B) = P (A ∪ B)

by the induction hypothesis at n − 1 = 2. (By isolating terms with C, we have found terms involving one fewer set). For the moment, to make things a little clearer, write X = A ∪ B. Then we need to show that

P (X ∪ C) = P (X) + P (C) − P (A ∩ C) − P (B ∩ C) + P (A ∩ B ∩ C).

Using the induction hypothesis for the two sets X and C, we know that

P (X ∪ C) = P (X) + P (C) − P (X ∩ C).

Looking at these last two equations — the first of which we need to prove, and the second of which we already know is true — we see that we’ll be done if only we can show that

−P (A ∩ C) − P (B ∩ C) + P (A ∩ B ∩ C) = −P (X ∩ C).

Toggling the negative signs, this is

P (X ∩ C) = P (A ∩ C) + P (B ∩ C) − P (A ∩ B ∩ C).

I put X = A ∪ B only for convenience; I’m done with it now. The statement I need to prove is

P ((A ∪ B) ∩ C) = P (A ∩ C) + P (B ∩ C) − P (A ∩ B ∩ C).

The trick is that

A ∩ B ∩ C = (A ∩ C) ∩ (B ∩ C)

and

(A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C).

That is, I distribute the C’s. So, the statement I need to prove is

P ((A ∩ C) ∪ (B ∩ C)) = P (A ∩ C) + P (B ∩ C) − P ((A ∩ C) ∩ (B ∩ C)).

Now we again have one fewer set involved: this is the inclusion-exclusion formula for the two sets (A ∩ C) and (B ∩ C). Thus this statement is true by the induction hypothesis. And, that was the last thing we needed to prove.

* * *

Now, guided by the n = 3 case, we can confidently wade into the morass of subscripts which is the induction step. We are asked to show that

P (∪_{i=1}^{n}A_{i}) = ∑_{1≤i≤n} P (A_{i})− ∑_{1≤i<j≤n} P (A_{i} ∩A_{j})+ ∑_{1≤i<j<k≤n} P (A_{i} ∩A_{j} ∩A_{k})−…+(−1)^{n+1}P (A_{1} ∩…∩A_{n}).

Since we want to use induction, we can try to isolate A_{n} from the others. We can write

P ((∪_{i=1}^{n−1}A_{i}) ∪ A_{n}) = ∑_{1≤i≤n−1} P (A_{i})  +P (A_{n})
− ∑_{1≤i<j≤n−1} P (A_{i} ∩ A_{j})  − ∑_{1≤i≤n−1} P (A_{i} ∩ A_{n})
+ ∑_{1≤i<j<k≤n−1} P (A_{i} ∩ A_{j} ∩ A_{k}) + ∑_{1≤i<j≤n−1} P (A_{i} ∩ A_{j} ∩ A_{n})
− …  − …
+(−1)^{n}P (A_{1} ∩ … ∩ A_{n−1})  +(−1)^{n} ∑_{1≤i≤n−1} P (A_{1} ∩ … ∩ Â_{i} ∩ … ∩ A_{n−1} ∩ A_{n})
+(−1)^{n+1}P (A_{1} ∩ … ∩ A_{n}).

where the notation Â_{i} means omit the A_{i} from the intersection. We have

P (∪_{i=1}^{n−1}A_{i}) = ∑_{1≤i≤n−1} P (A_{i})− ∑_{1≤i<j≤n−1} P (A_{i}∩A_{j})+ ∑_{1≤i<j<k≤n−1} P (A_{i}∩A_{j}∩A_{k})−…+(−1)^{n}P (A_{1}∩…∩A_{n−1})

by the induction hypothesis at n − 1. (By isolating terms with A_{n}, we have again found terms involving one fewer set). As above, for clarity, temporarily write X = ∪_{i=1}^{n−1}. Then we need to show that

P (X ∪ A_{n}) = P (X) + P (A_{n})

− ∑_{1≤i≤n−1} P (A_{i} ∩ A_{n})

+ ∑_{1≤i<j≤n−1} P (A_{i} ∩ A_{j} ∩ A_{n})

− …

+(−1)^{n} ∑_{1≤i≤n−1} P (A_{1} ∩ … ∩ Â_{i} ∩ … ∩ A_{n−1} ∩ A_{n})

+(−1)^{n+1}P (A_{1} ∩ … ∩ A_{n}).

Using the induction hypothesis for the two sets X and A_{n}, we know that

P (X ∪ A_{n}) = P (X) + P (A_{n}) − P (X ∩ A_{n}).

Looking at these last two equations — the first of which we need to prove, and the second of which we already know is true — we see that we’ll be done if only we can show that

− ∑_{1≤i≤n−1} P (A_{i} ∩ A_{n})

+ ∑_{1≤i<j≤n−1} P (A_{i} ∩ A_{j} ∩ A_{n})

− …

+(−1)^{n} ∑_{1≤i≤n−1} P (A_{1} ∩ … ∩ Â_{i} ∩ … ∩ A_{n−1} ∩ A_{n})

+(−1)^{n+1}P (A_{1} ∩ … ∩ A_{n})

= −P (X ∩ A_{n}).

Toggling the negative signs, this is

P (X ∩ A_{n}) = ∑_{1≤i≤n−1} P (A_{i} ∩ A_{n})

− ∑_{1≤i<j≤n−1} P (A_{i} ∩ A_{j} ∩ A_{n})

+ …

−(−1)^{n} ∑_{1≤i≤n−1} P (A_{1} ∩ … ∩ Â_{i} ∩ … ∩ A_{n−1} ∩ A_{n})

−(−1)^{n+1}P (A_{1} ∩ … ∩ A_{n}).

Note that −(−1)^{n} is the same as (−1)^{n−1}. So we need to show

P (X ∩ A_{n}) = ∑_{1≤i≤n−1} P (A_{i} ∩ A_{n})

− ∑_{1≤i<j≤n−1} P (A_{i} ∩ A_{j} ∩ A_{n})

+ …

+(−1)^{n−1} ∑_{1≤i≤n−1} P (A_{1} ∩ … ∩ Â_{i} ∩ … ∩ A_{n−1} ∩ A_{n})

+(−1)^{n}P (A_{1} ∩ … ∩ A_{n}).

As before, I don’t need to write X = ∪_{i=1}^{n−1} anymore. The statement I need to prove is

P ((∪_{i=1}^{n−1}A_{i}) ∩ A_{n}) = ∑_{1≤i≤n−1} P (A_{i} ∩ A_{n})

− ∑_{1≤i<j≤n−1} P (A_{i} ∩ A_{j} ∩ A_{n})

+ …

+(−1)^{n−1} ∑_{1≤i≤n−1} P (A_{1} ∩ … ∩ Â_{i} ∩ … ∩ A_{n−1} ∩ A_{n})

+(−1)^{n}P (A_{1} ∩ … ∩ A_{n}).

The distribution tricks are

A_{1} ∩ … ∩ A_{n} = (A_{1} ∩ A_{n}) ∩ … ∩ (A_{n−1} ∩ A_{n})

and

(A_{1} ∪ … ∪ A_{n−1}) ∩ A_{n} = (A_{1} ∩ A_{n}) ∪ … ∪ (A_{n−1} ∩ A_{n}).

So, the statement I need to prove is

P (∪_{i=1}^{n−1}(A_{i} ∩ A_{n})) = ∑_{1≤i≤n−1} P (A_{i} ∩ A_{n})

− ∑_{1≤i<j≤n−1} P ((A_{i} ∩ A_{n}) ∩ (A_{j} ∩ A_{n}))

+ …

+(−1)^{n−1} ∑_{1≤i≤n−1} P ((A_{1} ∩ A_{n}) ∩ … ∩ (Â_{i} ∩ A_{n}) ∩ … ∩ (A_{n−1} ∩ A_{n}))

+(−1)^{n}P ((A_{1} ∩ A_{n}) ∩ … ∩ (A_{n−1} ∩ A_{n})).

Now we again have one fewer set involved: this is the inclusion-exclusion formula for the n−1 sets (A_{1} ∩A_{n}) through (A_{n−1}∩A_{n}). Thus this statement is true by the induction hypothesis. Since that is all that remained to be shown, we are done.

References

[Fol] Folland, G.B. Real Analysis: Modern Techniques and Their Applications (2nd ed.). Wiley-Interscience, 1999.

[FG] Fristedt, B. and Gray, L. A Modern Approach to Probability Theory. Birkhauser, 1997.

[GS] Grimmett, G. and Stirzaker, D. Probability and Random Processes, 3rd ed. Oxford, 2001.

[Kennedy] Kennedy, T. Math 564. Course at University of Arizona, spring 2007.

[KK] Kaplan, M. and Kaplan, E. Chances Are …: Adventures in Probability. Penguin, 2007.

[MM] Moore, D.S. and McCabe, G.P. Introduction to the Practice of Statistics. Freeman and Co., 2005.

[Roy] Royden, H.L. Real Analysis (2nd ed.). MacMillan, 1968.

[Rud] Rudin, W. Principles of Mathematical Analysis (3rd ed.). McGraw-Hill, 1976.

46

Index

A almost surely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

B Bayes’ theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34 Bernoulli distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 bimodal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 binomial distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 bivariate normal distribution . . . . . . . . . . . . . . . . . . . . 24 Borel σ-field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

C Cauchy distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 CDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 central limit theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . .28 change of variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 characteristic function . . . . . . . . . . . . . . . . . . . 12, 22, 40 Chebyshev’s inequality . . . . . . . . . . . . . . . . . . . . . . . . . . 26 coarsest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 conditional density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 conditional expectation . . . . . . . . . . . . . . . . . . . . . . . 9, 23 conditional PMF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 conditional probability . . . . . . . . . . . . . . . . . . . . . . . .4, 34 confidence intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 continuous random variable . . . . . . . . . . . . . . . . . . . . . 14 convergence in distribution . . . . . . . . . . . . . . . . . . . . . . 28 convergence in mean square . . . . . . . . . . . . . . . . . . . . . 26 convergence in probability . . . . . . . . . . . . . . . . . . . . . . .26 convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 correlation coefficient . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 countable additivity . . . . . . . . . . . . . . . . . . . . . . . . . . 4, 38 covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 cumulative distribution function . . . . . . . . . . . . . . . . .14

D density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 discrete random variable . . . . . . . . . . . . . . . . . . . . . . . . . 6 disjoint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 distribution function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

E event . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4, 38 event space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8, 18 expected value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8, 18 experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 exponential distribution . . . . . . . . . . . . . . . . . . . . . . . . . 15

F factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 finest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

G

gamma distribution . . . . . . . . . . . . . . . . . . . . . . . . . 16, 17 gamma function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 geometric distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 given . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

I

identically distributed . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 IID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 in distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 in mean square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26 in probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Inclusion-exclusion formula . . . . . . . . . . . . . . . . . . . . . .41 independent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5, 10, 20 integrate away . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

J

Jacobian matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22 joint CDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 joint density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 joint PDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 joint PMF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 jointly continuous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

L

Laplace transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 law of large numbers, strong . . . . . . . . . . . . . . . . . . . . 27 law of large numbers, weak . . . . . . . . . . . . . . . . . . . . . . 26 Law of the Unconscious Statistician … 8, 10, 18, 20

M

marginal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10, 19 mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6, 8, 14, 15, 18 measurable function . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 measurable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 measurable space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 measurable subset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38 measure space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17, 21 MGF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 moment-generating function . . . . . . . . . . . . . 12, 22, 40 N negative binomial distribution . . . . . . . . . . . . . . . . . . . . 7 normal distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 normalize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

O outcome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

P pairwise independent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 partition theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5, 9 PDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14, 39 PMF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Poisson distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 population . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 population mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11, 28 population variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 preimage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 probability density function . . . . . . . . . . . . . . . . . 14, 39 probability mass function . . . . . . . . . . . . . . . . . . . . . . . . .6 probability measure . . . . . . . . . . . . . . . . . . . . . . . 4, 38, 39 probability space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4, 39 product, expectation of . . . . . . . . . . . . . . . . . . . . . . 11, 24

R random variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6, 39 range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

S sample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26, 28 sample mean . . . . . . . . . . . . . . . . . . . . . 11, 21, 26, 28, 31 sample space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4, 38 σ-field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4, 38 standard deviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 standard normal distribution . . . . . . . . . . . . . . . . . . . . 16 standardization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28, 31 strong law of large numbers . . . . . . . . . . . . . . . . . . . . . 27

U uncorrelated . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 uniform distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

V variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6, 8, 15, 18

W weak law of large numbers . . . . . . . . . . . . . . . . . . . . . . 26 with probability one . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27

Z z-score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29, 31