LECTURE 2

Sums of independent random variables. Suppose X_{1}, X_{2}, … is a sequence of independent, identically distributed random variables (i.i.d.) , with common mean m. We expect

ξ_{n} = \frac{X_{1} + ⋯ + X_{n}}{n} − m → 0.

But what does it mean exactly for ξ_{n} → ξ for random variables? Three possibilities (out of many) are

1. P (ξ_{n} → ξ) = 1 (almost sure convergence).

2. P (|ξ_{n} − ξ| > ϵ) → 0 as n → ∞ for each fixed ϵ > 0 (convergence in probability).

3. ∫ fdF_{n} → ∫ fdF for every continuous bounded function f where F_{n} is the distribution function of ξ_{n}, and F is the distribuition function of ξ. (convergence in distribution). One writes F_{n} ⇒ F. Note that it has to be almost surely in the first and not everywhere because changing

a random variable on a set of measure zero does not really change anything. Each type of convergence above implies those below it, but not vice versa. Lemma. (Tchebyshev’s inequality) For any random variable X,

P (X ≥ a) ≤ E[X^{2}]/a^{2}.

Proof. P (X ≥ a) = ∫_{X≥a} dP ≤ ∫_{X≥a} \frac{X^{2}}{a^{2}} dP ≤ ∫ \frac{X^{2}}{a^{2}} dP. Theorem. (Weak law of large numbers) Let X_{1}, X_{2}, … be i.i.d. with mean m

and variance σ^{2} < ∞. Then \frac{X_{1}+···+X_{n}}{n} → m in probability.

Proof. Let Y_{i} = X_{i} − m. Then Y_{i} are i.i.d. with mean 0 and variance σ^{2} and \frac{X_{1}+···+X_{n}}{n} − m = \frac{Y_{1}+···+Y_{n}}{n}. Now

E[(Y_{1} + ⋯ + Y_{n})^{2}] = ∑_{i,j=1}^{n} E[Y_{i}Y_{j}].

If i ≠ j we have E[Y_{i}Y_{j}] = E[Y_{i}]E[Y_{j}] = 0 since they are independent and mean 0. So only the diagonal terms E[Y_{i}^{2}] survive. So

E[(\frac{X_{1} + ⋯ + X_{n}}{n} − m)^{2}] = σ^{2}/n.

Let ϵ > 0. By Tchebyshev,

P (|\frac{X_{1} + ⋯ + X_{n}}{n} − m| > ϵ) ≤ E[(\frac{X_{1} + ⋯ + X_{n}}{n} − m)^{2}]/ϵ^{2} = σ^{2}/nϵ^{2} → 0

as n → ∞.

Borel-Cantelli Lemma. Let A_{1}, A_{2}, … be events in F. Suppose that

∑_{i=1}^{∞} P (A_{i}) < ∞.

Then

P ( ⋂_{k=1}^{∞} ⋃_{n=k}^{∞} B_{n}) = 0.

Proof. P (⋃_{n=k}^{∞} B_{n}) ≤ ∑_{n=k}^{∞} P (B_{n}) → 0 as k → ∞.

The set ⋂_{k=1}^{∞} ⋃_{n=k}^{∞} B_{n} is the event that B_{n} occurs infinitely many times. It is called B_{n} infinitely often, or B_{n} i.o. for short.

Theorem. (Strong law of large numbers) Let X_{1}, X_{2}, … be a sequence of i.i.d. random variables in L^{4}. Then \frac{X_{1}+···+X_{n}}{n} → m a.s. (Note: Actually L^{1} is enough, but it is hard to prove.)

Proof. The transformation Y_{i} = X_{i} − m makes it clear that we can assume without loss of generality that m = 0. Now

E [(X_{1} + ⋯ + X_{n})^{4}] = ∑_{i,j,k,ℓ} E[X_{i}X_{j}X_{k}X_{ℓ}].

If any one of i, j, k, ℓ is different from the others, than that variable pops out of the expectation by independence, and you get 0. Otherwise either you have two pairs and you get a square of second moments, or you have four of a kind and you get a fourth moment. Whatever you get is bounded by some number we can call C. The number of two-pairs is n(n − 1) and the number of four-of-a-kinds is n. So E [(X_{1} + ⋯ + X_{n})^{4}] ≤ Cn^{2} and therefore by Tchebyshev,

P (|\frac{X_{1} + ⋯ + X_{n}}{n} | ≥ ϵ) ≤ E [(\frac{X_{1} + ⋯ + X_{n}}{n} )^{4}] /ϵ^{4} ≤ C/n^{2}ϵ^{4}.

So P (|\frac{X_{1}+···+X_{n}}{n} | ≥ ϵ) are summable, and therefore by Borel-Cantelli, P (|\frac{X_{1}+···+X_{n}}{n} | ≥ ϵ i.o.) = 0 which is the same thing as \frac{X_{1}+···+X_{n}}{n} → m a.s.

Lemma. Let F_{n} be a sequence of distribution functions and ϕ_{n}(z) = ∫ e^{izx}dF_{n}(x) the corresponding sequence of characteristic functions. Then F_{n} ⇒ F if and only if ϕ_{n}(z) → ϕ(z) for each z ∈ R.

Central limit theorem. Let X_{1}, X_{2}, … be a sequence of i.i.d. random variables with mean m and variance σ^{2} < ∞. Then \frac{X_{1}+···+X_{n}−nm}{σ\sqrt{n}} converges in distribution to a standard normal.

Proof. By transforming to z−scores Z_{i} = \frac{X_{i}−m}{σ} we can assume without loss of generality that the X_{i} have mean 0 and variance 1. Let ϕ be the characteristic function of X_{i} and ϕ_{n} be the characteristic function of \frac{X_{1}+···+X_{n}}{\sqrt{n}}. Then we have

ϕ_{n}(z) = [ϕ(z/\sqrt{n})]^{n}.

But

ϕ(z) = E[e^{izX}] = E[1 + izX − \frac{z^{2}X^{2}}{2} + o(z^{2}X^{2})] = 1 + \frac{z^{2}}{2} + o(z^{2})

where o(h) means something that goes to zero faster than h as h goes to zero (or sometimes as h goes to infinity). So

ϕ_{n}(z) = [1 + \frac{z^{2}}{2n} + o(\frac{1}{n})]^{n} → e^{−z^{2}/2}

as n → ∞ for each fixed z.

3. DEPENDENT RANDOM VARIABLES. Let S_{n} be a simple symmetric random walk on the integers Z. Clearly if S_{n} is very large then S_{n+1} will be as well. The sequence of differences X_{n} = S_{n} − S_{n−1} are independent, but the S_{n} are not.

Conditional probability. Suppose (Ω, F, P) is a probability space and A and B are events with P (A) > 0. The conditional probability of B given A is

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

Problem. A family has two children. What is the probability that both are girls given that one of them is a girl?

Solution. The sample space is Ω = {bb, bg, gb, gg} where for example bg means the younger child is a boy and the older a girl. So each event has probability 1/4 (this would not be the case if the children were unordered).

P (\{gg\} |\{bg, gb, gg\}) = \frac{P (\{gg\})}{P (\{bg, gb, gg\})} = \frac{1/4}{3/4} = 1/3.

Conditional probability given a σ−field. Recall that for any event A, P (A) = E[1_{A}] where 1_{A}(ω) = \{ \begin{matrix}1 & if ω ∈ A; \\ 0 & otherwise. \end{matrix} Last time I called it χ_{A} but I noticed it looks lousy. Sometimes its also called I_{A}.

We could also make the following equivalent definition of conditional probability. Let G = {∅, A, A^{C}, Ω}, the smallest σ−field containing A. We define the random variable P (B | G) in any of the following equivalent ways:

1. P (B | G) is the projection of 1_{B} ∈ L^{2}(Ω, F, P) onto the subspace L^{2}(Ω, G, P).

2. For each C in G define Q(C) = ∫_{C} 1_{B}dP = P (C∩B). Then Q is a measure on (Ω, G, P) which is absolutely continuous with respect to P, i.e. P (C) = 0 ⇒ Q(C) = 0. By the Radon-Nikodym theorem there exists a random variable P (B | G) on (Ω, G, P) such that for any C in G,

Q(C) = ∫_{C} P (B | G)dP.

3. P (B | G)(ω) = \{ \begin{matrix}\frac{P (B∩A)}{P (A)} & if ω ∈ A; \\ \frac{P (B∩A^{C})}{P (A^{C})} & if ω ∈ A^{C}. \end{matrix}

Conditional expectation. In the equivalent definitions 1 and 2 above one can replace the random variable 1_{B} by more or less any random variable (all you need is X ∈ L^{2} in 1 and X ∈ L^{1} in 2) and the special σ−field G by any sub-σ−field of F. Since 2 is the most general we use it as the definition.

Let X ∈ L^{1}(Ω, F, P) and G ⊂ F a σ−field. The conditional expectation of X given G is the unique random variable E[X | G] ∈ L^{1}(Ω, G, P) satisfying

∫_{A} E[X | G]dP = ∫_{A} XdP for all A ∈ G.

E[X | G] is the best estimate of X given only the information G.

If X and Y are two random variables then the conditional expectation E[X | Y] of X given Y means E[X | σ(Y)] where σ(Y) is the σ−field generated by Y. Similarly E[X | Y_{1}, …, Y_{n}] is defined to be the conditional expectation of X given the smallest σ-field with respect to which Y_{1}, …, Y_{n} are all measurable.

Basic properties of conditional expectation.

1. If X is G measurable then E[X | G] = E[X].

2. If G is the trivial σ−field {∅, Ω} then E[X | G] = E[X].

3. (linearity) E[aX + bY | G] = aE[X | G] + bE[Y | G].

4. If Y is G - measurable then E[Y X | G] = Y E[X | G].

5. (repeated conditioning) If H is a sub-σ−field of G then E[E[X | G] | H] = E[X | H].

6. (Jensen’s inequality) If ϕ is a convex function then ϕ(E[X | G]) ≤ E[ϕ(X) | G].

Proof. We use the fact that ϕ is convex if and only if ϕ(x) = sup_{ℓ linear ℓ(x)≤ϕ(x) for all x} ℓ(x). We

have

ℓ(E[X | G]) = E[ℓ(X) | G] ≤ E[ϕ(X) | G].

Taking the sup on the left hand side gives the result. Note that all the equality signs above only hold up to sets of measure 0. The condi-

tional expectation is anyway only defined and unique up to sets of measure 0.

Variance of sums of i.i.d. ’s. Suppose X_{1}, X_{2}, … is a sequence of i.i.d. random variables with mean 0 and variance 1. Think of them as the amount a game pays back if you bet $1. So if you keep betting $1 repeatedly your fortune at time n is S_{n} = ∑_{j=1}^{n} X_{j}. But suppose that you bet $a_{j} dollars on the jth game. Then your fortune is

S_{n} = ∑_{j=1}^{n} a_{j}X_{j}.

a_{j} could be a function of what has happened up to time j − 1, i.e. a_{j} = a_{j}(X_{1}, …, X_{j−1}). We want to compute the mean and variance of S_{n}. By linearity

E[∑_{j=1}^{n} a_{j}X_{j}] = ∑_{j=1}^{n} E[a_{j}X_{j}].

By repeated conditioning

E[a_{j}X_{j}] = E[E[a_{j}X_{j} | X_{1}, …, X_{j−1}]].

Since a_{j} is measurable with respect to the σ-field generated by X_{1}, …, X_{j−1},

E[a_{j}X_{j} | X_{1}, …, X_{j−1}] = a_{j}E[X_{j} | X_{1}, …, X_{j−1}].

But X_{j} is independent of X_{1}, …, X_{n} so this gives a_{j}E[X_{j}] = 0. So E[S_{n}] = 0. Now we do the variance the same way.

E[(∑_{j=1}^{n} a_{j}X_{j})^{2}] = 2 ∑_{1≤i<j≤n}^{n} E[(a_{j}X_{j})(a_{i}X_{i})] + ∑_{j=1}^{n} E[(a_{j}X_{j})^{2}].

But if i < j,

E[(a_{j}X_{j})(a_{i}X_{i})] = E[E[(a_{j}X_{j})(a_{i}X_{i}) | X_{1}, …, X_{j−1}]].

Everything except X_{j} pops out of the inner conditional expectation, so inside we are left with E[X_{j} | X_{1}, …, X_{j−1}] = 0. We conclude that all of the off-diagonal terms vanish. So we are left with

∑_{j=1}^{n} E[(a_{j}X_{j})^{2}].

But

E[(a_{j}X_{j})^{2}] = E[E[(a_{j}X_{j})^{2} | X_{1}, …, X_{j−1}]] = E[a_{j}^{2}E[X_{j}^{2} | X_{1}, …, X_{j−1}]] = E[a_{j}^{2}].

So E[S_{n}^{2}] = ∑_{j=1}^{n} E[a_{j}^{2}].

The above calculation is very important and it is worth looking at what we really used. Let F_{n} = σ(X_{1}, …, X_{n}). We assumed a_{j} was measurable with respect to F_{j−1} and all we used for the X_{i} was that

E[X_{i} | F_{i−1}] = 0.

Such a sequence is called a sequence of martingale differences.

Martingales. Let M_{1}, M_{2}, … be a sequence of random variables on a probability space (Ω, F, P) and let F_{j}, j = 1, 2, … be a filtration. The sequence M_{j} is called a martingale with respect to F_{j} if M_{j} is F_{j}-measurable and

E[M_{j} | F_{j−1}] = M_{j−1}.

If a_{j} is F_{j−1}-measurable and

N_{j} = ∑_{j=1}^{n} a_{j}(M_{j} − M_{j−1})

then the first calculation above shows that N_{j} is another martingale and the second shows that

E[N_{j}^{2}] = ∑_{j=1}^{n} E[a_{j}^{2}σ_{j}^{2}]

where σ_{j}^{2} = E[(M_{j} − M_{j−1})^{2} | F_{j−1}]. N_{j} is called the martingale transform of M_{j}. We can write it as

ΔN = aΔM.

Stochastic differential equations are just continuous time versions of this.

If you are playing a fair game and M_{n} is your fortune after the nth game then M_{n} is a martingale.

Submartingales. If we are in the situation above but we only have we have E[M_{j} | F_{j−1}] ≥ M_{j−1} then we say M_{j} is a submartingale. If the inequality goes the other way then it is called a supermartingale.

Suppose M_{j} is a martingale and ϕ is a convex function. Then by Jensen’s inequality, X_{j} = ϕ(M_{j}) is a submartingale.

Suppose M_{j} is a martingale and A_{j} is F_{j−1} measurable and increasing in j. Then

E[M_{j} + A_{j} | F_{j−1}] = M_{j−1} + A_{j} ≥ M_{j−1} + A_{j−1}

so X_{j} = M_{j} + A_{j} is a submartingale. Suppose that X_{j} is a submartingale and let

A_{j} = ∑_{i=1}^{j} E[X_{i} − X_{i−1} | F_{i−1}].

Then A_{j} are increasing F_{j−1} measurable, and

E[X_{j}−A_{j} | F_{j−1}] = X_{j−1}+E[X_{j}−X_{j−1} | F_{j−1}]−A_{j−1}−E[X_{j}−X_{j−1} | F_{j−1}] = X_{j−1}−A_{j−1}

so M_{j} = X_{j} − A_{j} is a martingale. This shows that X_{j} is a submartingale if and only if it is the sum of a martingale and an increasing predictable process.

PROBLEMS.

1. On Let’s make a deal there are three doors. Behind two are goats and behind one is a car. Lets say the car is worth $30, 000 and the goats are worth $200. You pick a door at random. Then Monty Hall opens one of the other doors to show you a goat and asks you if you want to pay $1000 to change your door to the remaining one. Should you change it?

2. An urn contains two coins. One is fair and the other has probability 1/3 of falling heads. You draw a coin at random and toss it. It falls heads. What is the probability it is the fair coin?

3. Let X_{1}, X_{2}, … be independent random variables with P (X_{i} = 1) = P (X_{i} = −1) = 1/2 (i.e. Bernoulli trials). Let S_{N} = X_{1} + ⋯ + X_{N} (i.e. symmetric simple random walk). Calculate E[S_{m} | S_{n}] for all values of n and m.

4. Let Ω = [0, 1), B = the Borel sets, and P = Lebesgue measure. For each positive integer n let F_{n} be the smallest σ−field containing the dyadic intevals at level n, i.e., [0, 1/2^{n}), [1/2^{n}, 2/2^{n}), …, [(2^{n} − 1)/2^{n}, 1). Let f ∈ L^{1}(Ω, B, P). Calculate f_{n} = E[f | F_{n}].

5. Let X_{1}, X_{2}, … be random variables in L^{2} with common mean m which are negatively correlated, i.e. Cov(X_{i}, X_{j}) < 0. Show that they satisfy the weak law of large numbers.

6.

i. Let X and Y be two random variables. We want to estimate X given knowledge of Y. For any Borel measurable function f we call f(Y) an estimator of X in terms of Y and E[(X − f(Y))^{2}] the error of the estimator. An estimator f^{∗}(Y) is called an optimal estimator if

E[(X − f^{∗}(Y))^{2}] ≤ E[(X − f(Y))^{2}]

for any other estimator f(Y). Show that such an optimal estimator always exists and is unique (up to sets of measure zero). (Hint: conditional expectation.)

ii. Show that if (X, Y) is a Gaussian vector then the optimal estimator of X in terms

of Y is a linear function of Y.

7. Suppose that X is a random variable which is uniformly distributed between 0 and 1. Find a transformation Y = g(X) such that Y has a standard normal distribution.