Probability Flashcards
What does it mean for X_n to converge to X almost surely?
P(X_n -> X as n -> infinity) = 1
What does it mean for X_n to converge to X in probability?
For all e>0, P(|X_n - X| < e) -> 1 as n -> infinity
What does it mean for X_n to converge to X in distribution?
For every x such that F is continuous at x, F_n(x) -> F(x) as n -> infinity
Rank convergence in probability, in distribution and almost surely in order from strongest to weakest
- almost surely
- in probability
- in distribution
Prove that almost sure convergence implies convergence in probability
- Fix e>0
- Define the event A_N = {|X_n - X| < e for all n >= N}
- Suppose X_n -> X a.s.
- P(U A_N) = 1
- Also, lim N - > infinity P(A_N) = 1
- A_N implies|X_N - X| < e
- So P(|X_N - X| < e) -> 1
Prove that convergence in probability implies convergence in distribution
- Fix x such that F is continuous at x, and fix e>0
- F_n(x) = P(X_n <= x)
<= P(X_n <= x+e or |X_n - X| > e)
<= P(X_n <= x+e) + |X_n - X| > e)
-> F(x+e) as n -> infinity - So F_n(x) < F(x+e) + e for large enough n
- Similarly, using 1-F_n(x), F_n(x) > F(x-e) - e
- This implies F_n(x) -> F(x)
Prove that if X_n -> c, constant, in distribution, then X_n -> c in probability
- lim n->∞ F_Xn(c-e) = 0
- lim n->∞ F_Xn(c+e/2) = 1
lim n->∞ P(|Xn-X|>=e)
= lim n->∞ P(Xn <= c-e + Xn>=c+e)
= lim n->∞ P(Xn <= c-e) + P(Xn>=c+e)
= 0 + lim n->∞ P(Xn>=c+e)
<= lim n->∞ P(Xn>c+e/2)
= lim n->∞ 1 - F_Xn(c+e/2)
= 1-1
= 0
So lim n->∞ P(|Xn-X|>=e) <= 0
Also know lim n->∞ P(|Xn-X|>=e) >= 0
Hence lim n->∞ P(|Xn-X|>=e) = 0
State the weak law of large numbers
- X_1, X_2, … iid with finite mean µ
- S_n = X_1 + X_2 + … + X_n
- Then S_n / n converges in probability to µ as n -> infinity
Prove the weak law of large numbers
P(|Sn/n-µ|>=e)
<= Var(Sn / n)/e^2 (Chebyshevs)
= Var(X1)/ne^2 (Var(Sn/n) = σ^2/n)
-> 0 as n -> infinity
State Markov’s inequality
- X random variable taking non-negative values
- Then P(X >= z) <= E[X] / z
Prove Markov’s inequality
- Let X_z = z I{X ≥ z}.
- So X_z takes the value 0 whenever
X is in [0, z) and the value z whenever X is in [z, ∞). - So X ≥ X_z always
- Then E[X] ≥ E[X_z] = z E[I{X ≥ z}] = z P(X ≥ z).
- Rearrange
State Chebyshev’s inequality
- Y random variable with finite mean and variance
- Then for any e>0,
P(|Y - E[Y]| >= e) <= var(Y) / e^2
Prove Chebyshev’s inequality
P(|Y - E[Y]| >= e) = P((Y - E[Y])^2 >= e^2)
(by Markov’s) <= E[(Y - E[Y])^2] / e^2
= Var(Y) / e^2
State the Strong Law of Large Numbers
- X_1, X_2, … iid with mean µ
- S_n = X_1 + X_2 + …
- Then S_n / n converges almost surely to µ as n -> infinity
What are the differences between the WLLN and the SLLN?
- WLLN requires finite mean, SLLN doesn’t
- WLLN gives convergence in probability, SLLN gives convergence almost surely
State the Central Limit Theorem
- X_1, X_2, … iid with mean µ and variance σ^2 > 0
- S_n = X_1 + X_2 + … + X_n
- Then (S_n - nµ) / σsqrt(n) converges in distribution to N(0,1)
State the uniqueness theorem for PGFs
If X and Y have the same PGF, then they have the same distribution.
State the convergence theorem for PGFS
G_Xn (s) → G_X (s) as n → ∞, for all s ∈ [0, 1], if and only if p_Xn (k) → p_X (k), as n → ∞, for all k = 0, 1, 2, . . .
State the uniqueness theorem for MGFs
If X and Y are random variables with the same moment generating function,
which is finite on [−t0, t0] for some t0 > 0, then X and Y have the same distribution.
State the continuity theorem for MGFs
- MY and MX1, MX2, . . . are all finite on [−t0, t0] for some t0 > 0.
- If MXn (t) → MY (t) as n → ∞, for all t ∈ [−t0, t0],
- Then Xn → Y in distribution as n → ∞.
State the change of variables formula for changing from X,Y to U,V
-Let D, R ⊂ R^2
-Let T : D → R be a bijection with continuously differentiable inverse
S : R → D.
-If (X, Y) is a D-valued pair of random variables with joint density function f_X,Y
Then (U, V) = T(X, Y) is jointly continuous with joint density function:
f_U,V (u, v) = f_X,Y (S(u, v))|J(u, v)|, where J(u, v) = x_u y_v - x_v y_u
If f_X,Y is the joint density of X and Y, what is the conditional distribution of X given Y?
f_X,Y / f_Y
If X_1, … X_n are independent, with MGFs M_X1, … M_Xn, what is the mgf of X_1+…+X_n?
The product of the MGFs
What is the pdf of the exponential distribution?
λe^(-x) x>=0
What is the pdf of the gamma distribution?
λ^r/gamma(λ) x^(r-1) e^(-λx)
What is the pdf of the normal distribution?
(2πσ^2)^-1/2 * exp[(-1/2σ^2) * (x − µ)^2]
What is the pmf of the poisson distribution?
E^(-λ) λ^x / x! x = 0,1,…
What is a transition matrix P?
All entries non-negative, each row sums to 1.
How would you find the pdf of X+Y given their joint pdf f_X,Y ?
- Change variables to U=X+Y, V=X
- Has jacobian 1
- So fU,V (u, v) = fX,Y (v, u − v)
- Then integrate over v to get the marginal distribution of U=X+Y
What is a Markov chain?
Let X = (X0, X1, X2, . . .) be a sequence of random variables taking values in I.
For any n ≥ 0 and any i0, i1, . . . , in+1 ∈ I,
P(Xn+1 = i_n+1 | Xn = in, . . . , X0 = i0)
= P(Xn+1 = i_n+1 | Xn = in)
What does it mean for a markov chain to be time-homogeneous?
p_ij = P(Xn+1 = j | Xn = i)
depends only on i and j, not on n
What are the transition probabilities of a markov chain?
p_ij = P(Xn+1 = j | Xn = i)
What is the markov property?
The future is independent of the past, given the present
What is the n-step transition probability of a markov chain?
p^(n)ij = P(Xr+n = j | Xr = i)
If λ is the distribution of X_0, what is the distribution of X_n?
λ P^n
What is a communicating class?
The partitions obtained from the equivalence relation “i communicates with j” (i.e. p_ij^(n) > 0 and p_ji^(n) > 0)
What does it mean for a communicating class C to be closed?
pij = 0 whenever i is in C and j is not in C
What does it mean for a communicating class to be open?
Not closed
What is an absorbing state?
A closed class consisting of a single element (i.e. p_ii = 1)
What does it mean for a markov chain to be irreducible?
All entries of P are non-zero (i.e. one communicating class)
What is the period of a state i?
the GCD of {n : p_ij^(n) > 0}
What does it mean for a state to be periodic?
period > 1
What does it mean for a state to be aperiodic?
period = 1
What is the hitting probability of A starting from state i?
h_i ^ A= Pi (Xn ∈ A for some n ≥ 0)
What does it mean for a state to be transient?
Pi(hit i infinitely often) = 0.
What does it mean for a state to be recurrent?
Pi(hit i infinitely often) = 1
What is the mean return time to a state i?
mi
: = E i (min{n ≥ 1 : Xn = i})
What does it mean for i to be null recurrent?
i is recurrent but mi = ∞
What does it mean for i to be positive recurrent?
mi < ∞
What does it mean for π to be a stationary distribution of a markov chain?
π = πP
When does P have a stationary distribution?
When P is positive recurrent
What is the stationary distribution?
π_i = 1/m_i
What is the convergence to equilibrium theorem?
- P irreducible and aperiodic, stationary dist. π
- Then P(Xn = j) → πj as n → ∞.
