lacunary - Mathnotes

Limit Theorems

I'm not sure which of these are proper limit theorems and which are preliminaries, but this is all a build up to the Central Limit Theorem.

Markov's Inequality

Theorem: Markov's Inequality \@{markovs-inequality}

Let X be a non-negative random variable (X≥0,) and t>0. Then,

P(X≥t)≤E[X]t.

Note \@{markovs-inequality-note}

That is, the probability that X is at least t has an upper-bound of the expectation (mean) of X divided by t. In simpler terms, the probability that X>t can't be too big.

Note that as t grows larger, the probability of X being greater than t grows smaller.

Proof \@{proof-of-markovs-inequality}

This follows from the Law of Total Expectation, which is

E[X]=E[X∣X≥t]P(X≥t)+E[X∣X<t]P(X<t).(a)

Here, we're partitioning X's sample space into a portion above t and a portion below t.

Now, E[X∣X≥t] is the expected value when X≥t, which is necessarily at least t, since X is restricted to taking on values of at least t. So, we have that E[X∣X≥t]≥t.

We can substitute this into (a) to get

E[X]≥tP(X≥t)+E[X∣X<t]P(X<t).(b)

Note that our equation has turned into an inequality; we must do this because the original RHS was equal to the original LHS, and the original RHS is greater than or equal to our new RHS, which means the original LHS is greater than or equal to our new RHS.

Now, since we said that X is non-negative, its expected value is also non-negative, including when X<t. We have by definition that P(X<t) is non-negative (because all probabilities are non-negative). Therefore, E[X∣X<t]P(X<t) must also be non-negative as it's the product of two non-negative numbers. Since the LHS of (b) is greater than the RHS with this non-negative value added to the RHS, the LHS is also bigger without it added, and therefore we can drop it to get

E[X]≥tP(X≥t)(c)

Dividing both sides by t and swapping sides gives us

P(X≥t)≤E[X]t.◻

◻
Referenced by (3 direct)

Direct references:

An Example

Example \@{markov-inequality-fish}

Suppose the size of a fish (measured in inches) is modeled as a nonnegative random variable X with an expected value

E[X]=12 inches.

We wish to bound the probability that the fish is at least 16 inches long, i.e.,

P(X≥16).

By Markov's Inequality, for any nonnegative random variable X and any t>0,

P(X≥t)≤E[X]t.

Setting t=16 inches, we have

P(X≥16)≤1216=0.75.

Thus, the probability of catching a fish of length at least 16 inches is at most 75%.

Remark: Interpretation \@{markov-inequality-fish-remark}

While Markov's inequality provides an upper bound of 75%, the actual probability of catching such a large fish could be much lower. This bound is derived solely from the expected value without any extra assumptions about the distribution of X.

Chebyshev's Inequality

Chebyshev's inequality gives an upper-bound on the probability of X taking on values more than t away from its mean (E[X]).

Theorem: Chebyshev's Inequality \@{chebyshevs-inequality}

Suppose t>0 and X is a random variable with the finite mean E[X] and standard deviation σ. Then

P(|X−E[X]|≥t)≤σ2t2.

Note \@{chebyshevs-inequality-note}

Intuitively, this means that the probability that X is far away from its mean can't be too big.

Note that the upper-bound on this probability is proportional to the variance of the random variable and inversely proportional to the distance t of X from its mean. So, as the variance increases, the probability of X taking on values further from its mean also increases, and as the distance from the mean increases, the probability of X taking on values at least that far from E[X] decreases.

Also note that while Markov's Inequality only requires knowledge of the mean E[X] (the first moment), Chebyshev's inequality requires knowledge of the variance E[X2]−E[X]2 (second moment). Also, Chebyshev's inequality works for any random variable with a variance defined, rather than just on non-negative random variables.

Proof \@{proof-of-chebyshevs-inequality}

Let X be a random variable with mean E[X] and variance σ2. Define the non-negative random variable

Y=(X−E[X])2.

By Markov's Inequality, for any a>0, we have

P(Y≥a)≤E[Y]a.

Set a=t2. Then,

P((X−E[X])2≥t2)≤E[(X−E[X])2]t2.

Since the variance of X is σ2=E[(X−E[X])2], it follows that

P((X−E[X])2≥t2)≤σ2t2.

Note that

(X−E[X])2≥t2⟺|X−E[X]|≥t.

Thus,

P(|X−E[X]|≥t)≤σ2t2.◻

◻
Referenced by (2 direct)

Direct references:

Example

Example \@{chebyshev-fish}

Suppose the length X of a fish is a random variable measured in inches with mean

E[X]=μ=20 inches

and variance

σ2=9 inches2

Chebyshev's Inequality states that for any t>0:

P(|X−μ|≥t)≤σ2t2

For t=4 inches, the inequality becomes:

P(|X−20|≥4)≤916

This tells us that the probability of a fish's length deviating from 20 inches by at least 4 inches is at most 916.

Law of Large Numbers

Theorem: Law of Large Numbers \@{law-of-large-numbers}

Suppose X1,X2,… are independent and identically distributed random variables with finite mean μ. Then for any ϵ>0,

limn→∞P(|X1+⋯+Xnn−μ|≥ϵ)=0.

Note \@{law-of-large-numbers-note}

Intuitively, this means that the more identically distributed random variables we have, the closer their average value will get to the mean for the random variables. If we think of each random variable as an identical sample from the same population, another way to think of this is the more samples we get, the closer the average value across all samples will be to the true average value for the population, and we can get as close as we like to the true average value for the population by taking more samples.

Proof \@{proof-of-law-of-large-numbers}

We assume that the variance of the random variables is also finite. Then, note that

E[X1+⋯Xnn]=μ,

and

V[X1+⋯Xnn]=σ2n.

Then, by Chebyshev's Inequality, we have

P(|X1+⋯+Xnn−μ|≥ϵ)≤σ2nϵ2.

Now, as n increases, the term on the right approaches 0, which by the Squeeze Theorem implies the term on the left also approaches 0, and is 0 at the limit. ◻

◻

Moment Generating Functions

Definition: Moment Generating Function \@{moment-generating-function}

If X is a random variable, then its moment generating function is a real-valued function on the reals defined as

MX(t)=E[etX].

If X is discrete, this is then

MX(t)=∑xetxf(x)

and if X is continuous, then this is

MX(t)=∫−∞∞etxf(x).

Referenced by (1 direct)

Direct references:

Now, note that MX(0)=E[e0⋅X]=E[1]=1.

In general, for the random variable X with the moment generating function MX(t), we have that MX′(0)=E[X] and MX(n)(0)=E[Xn] if the derivatives exist at 0.

Moment generating functions are unique and completely specify random variables.

Theorem: Moment Generating Function of a Sum \@{mgf-of-sum}

The moment generating function for the sum of two random variables is the product of the moment generating functions of the two random variables. More generally, if X1,X2,…Xn are independent random variables, then

MX1+X2+⋯+Xn(t)=MX1(t)⋅MX2(t)⋯MXn(t).

Proof \@{proof-of-mgf-of-sum}

We'll prove the case where n=2; the general proof is exactly the same but more tedious.

MX+Y(t)=E[et(X+Y)]=E[etXetY]=E[etX]E[etY]=MX(t)MY(t).◻

◻

Continuity Theorem For Moment Generating Functions

In essence, The Continuity Theorem For Moment Generating Functions says that if you have a sequence of random variables whose MGFs converge “nicely” (in a neighborhood of zero) to a limit function, then that limit function is the MGF of some random variable and the distributions of your sequence converge to the distribution of that random variable.

Theorem: Continuity Theorem for Moment Generating Functions \@{mgf-continuity-theorem}

Let {Xn} be a sequence of random variables with moment generating functions defined by

MXn(t)=E[etXn]

for all ‖t‖<ϵ for some ϵ>0.

Suppose there exists a function M(t), finite for ‖t‖<ϵ, such that

limn→∞MXn(t)=M(t)

for all ‖t‖<ϵ, and that M(t) is the moment generating function of some random variable X.

Then the distributions of {Xn} converge in distribution to X, i.e.,

Xn→dX.

Central Limit Theorem

The intuitive version of the Central Limit Theorem is that if n values are sampled from a distribution with a mean μ and standard deviation σ, then the sample mean of these values, X¯, is approximately normal with mean μ and standard deviation σn for large n.

This means that no matter what the underlying distribution of a population is, any sufficiently large sample from the population will be approximately normal. How large is sufficiently large depends on the shape of the distribution - for symmetric distributions it is lower and for asymmetric it is higher, but a common value is n≥30.

A compact way to write this is

X¯−μσn∼Z,n≥30.

A more precise version of the theorem follows.

Theorem: Central Limit Theorem \@{central-limit-theorem}

If c is a real constant and X1,X2,… are independent random variables with mean μ and standard deviation σ, then

TODO: the precise statement is cut off in the source; complete it.