Probability Theory

3. Zero-One Laws

3.1 Almost Sure Events

Definition 3.1 (Almost Sure Event): Let A∈F\evA \in \sigmaF. We say that A\evA occurs almost surely or a.s. if P ⁣(A)=1\probP{\evA} = 1.
Note: This notion can be extended to any set A⊂ΩA \subset \Omega which is not necessarily an event, i.e. A∉FA \not\in \sigmaF might be possible. We say that A\evA occurs almost surely if there exists an event A′∈F\evA' \in \sigmaF such that A′⊂A\evA' \subset A and P ⁣(A′)=1\probP{\evA'} = 1.

Since random variables are often defined up to a null set, the notion of almost sure occurence is particularly usefule when we manipulate random variables. For example if X,YX, Y are two random variables, we write X≤Y  a.s.X \leq Y \sep \as if P ⁣(X≤Y)=1\probP{X \leq Y} = 1.

Note: For readability, we will write events related to random variables by omitting ω∈Ω\omega \in \Omega in the set definition, e.g. we write {ω∈Ω:X(ω)<Y(ω)}\set{\omega \in \Omega : X(\omega) < Y(\omega)} as {X<Y}\set{X < Y}.
Example (Single point in continuous rv): Let U∼U⁡([0,1])U \sim \lawU([0,1]). For every x∈[0,1]x \in [0,1] we have Ax={U≠x}  a.s.\evA_x = \set{U \neq x} \sep \as since P ⁣(Ax)=P ⁣(U∈[0,1]∖{x})=λ([0,1]∖{x})=1 \probP{\evA_x} = \probP{U \in [0,1] \setminus \set{x}} = \lambda([0,1] \setminus \set{x}) = 1
Proposition 3.2 (Countable Intersection of a.s. events): Let (An)n∈I(\evA_n)_{n \in \setI} be a collection of events, where I\setI is a finite or countable index set. If for all n∈In \in \setI the event An\evA_n occurs almost surely, then the intersection ⋂n∈IAn\bigcap_{n \in \setI} \evA_n also occurs almost surely.
Example (Uniform rv is irrational): Let U∼U⁡([0,1])U \sim \lawU([0,1]), Ax={U≠x}\evA_x = \set{U \neq x}. Since the event that UU is irrationial A=⋂x∈QAx={U∈[0,1]∖Q} \evA = \bigcap_{x \in \Q} \evA_x = \set{U \in [0,1] \setminus \Q} is the intersection of countably many almost-sure events, it also occurs almost surely. This example illustrates the importance that the intersection is at most countable. If one considers the uncountable intersection among all x∈[0,1]x \in [0,1], we have P ⁣(∩x∈[0,1]Ax)=P ⁣(∅)=0\probP{\cap_{x \in [0,1]} \evA_x} = \probP{\varnothing} = 0 despite P ⁣(Ax)=1\probP{A_x} = 1.

3.2 Borel-Cantelli I

Let (pn)n∈N\sequence{p} be a sequence of parameters in [0,1][0,1]. For every nn, let Xn∼Ber⁡(pn)X_n \sim \lawBer(p_n) be a Bernoulli random variable with paramter pnp_n. How many of these random variables are equal to 11? Finitely many or infinitely many? Borel-Cantelli Theorems provide simple criteria to answer such questions. We first define the event corresponding to the occurence of infinetly many events.

Definition 3.3 (Occurence of infinetly many events): Let (An)n∈N\sequence{A} be an infinite sequence of events, we define the event lim sup⁡n→∞An=⋂n≥1⋃m≥nAm \limsupinfty \evA_n = \bigcap_{n \geq 1} \bigcup_{m \geq n} \evA_m
Note:
  • If we write the event in terms of ω\omega, we have lim sup⁡n→∞An={ω∈Ω | ∀n≥1  ∃m≥n:ω∈Am} \limsupinfty \evA_n = \set{\omega \in \Omega \mid \forall n \geq 1 \sep \exists m \geq n : \omega \in \evA_m}
  • lim sup⁡n→∞An\limsupinfty \evA_n occurs iff the event An\evA_n occurs for infinitely many nn
  • lim sup⁡n→∞An\limsupinfty \evA_n does not occur iff the event An\evA_n occurs for at most finitely many nn
Example (Bernoulli rvs): If we consider the sequence of Bernoulli random variables at the beginning of the section, we can define An={Xn=1}\evA_n = \set{X_n = 1}. In this case, the event lim sup⁡n→∞An\limsupinfty \evA_n is equal to the event that infintely many XnX_n are equal to 11, i.e. lim sup⁡n→∞An={lim sup⁡n→∞Xn=1}={∑n∈NXn=∞} \limsupinfty \evA_n = \set{\limsupinfty X_n = 1} = \set{\sumN X_n = \infty}
Theorem 3.4 (Borel-Cantelli I): Let A1,A2,…∈F\evA_1, \evA_2, \ldots \in \sigmaF. If ∑n∈NP ⁣(An)<∞\sumN \probP{\evA_n} < \infty then P(lim sup⁡n→∞An)=0 \probP*{\limsupinfty A_n} = 0
Note: In this theorem, there is no independence assumption: the events An\evA_n are arbitrary.

This theorem asserts that, if the probability of the events are small enough, then almost surely at most finitely many AnA_n occur.

Example (Finitely many occurences): If we consider the Bernoulli example with pn=1n2p_n = \frac{1}{n^2}, then we get ∑n∈NP ⁣(An)=π26<∞\sumN \probP{\evA_n} = \frac{\pi^2}{6} < \infty and thus P ⁣({∑n∈NXn<∞})=1\probP{\set{\sum_{n\in\N} X_n < \infty}} = 1.

3.3 Borel-Cantelli II

Theorem 3.5 (Borel-Cantelli II): Let A1,A2,…∈F\evA_1, \evA_2, \ldots \in \sigmaF be independent events. If ∑n∈NP ⁣(An)=∞\sumN \probP{\evA_n} = \infty, then P(lim sup⁡n→∞An)=1 \probP*{\limsupinfty \evA_n} = 1
Example (Infinitely many occurunces): If we consider the Bernoulli example with pn=1np_n = \frac 1 n then we get ∑n∈NP ⁣(An)=∞\sumN \probP{\evA_n} = \infty and thus P ⁣({∑n∈NXn=∞})=1\probP{\set{\sum_{n\in\N} X_n = \infty}} = 1.

Consider a sequence of events (An)n∈N\sequence{\evA} and define s=∑n∈NP ⁣(An)s = \sumN \probP{\evA_n}. If the events are independent, then Borel-Cantelli I and II give the following dichotomy: P ⁣(lim sup⁡n→∞An)={0if s<∞1if s=∞ \probP{\limsupinfty \evA_n} = \begin{cases} 0 & \text{if } s < \infty \\ 1 & \text{if } s = \infty \end{cases} We say that the event lim sup⁡n→∞An\limsupinfty \evA_n satisfies a 0–1 law. This 0–1 law relies strongly on the independence of the events. It turns out that lim sup⁡n→∞An\limsupinfty \evA_n is an instance of much larger class of events, called “tail events”, who all satisfy this 0–1 law under an independence assumption. This will be the topic of the rest of the chapter.

3.4 Tail σ\sigma-algebra

Definition 3.6 (Tail σ\sigma-algebra): Let (Xn)n∈N\sequence{X} be a sequence of random variables, let N∈NN \in \N and let TN=σ(XN,XN+1,…)\setT_N = \sigma(X_N, X_{N+1}, \ldots) be the σ\sigma-algebra generated by the random variables form XNX_N onwards. The tail σ\sigma-algebra T\setT is defined as T=⋂N=1∞TN \setT = \bigcap_{N = 1}^{\infty} \setT_N
Note: T\setT is indeed a σ\sigma-algebra as it is the intersection of σ\sigma-algbras.

The tail σ\sigma-algebra contains the events A\evA whose occurence does not depend on any fixed finite subfamily of the sequence (Xn)n∈N\sequence{X}. To put it differently, for any N∈NN \in \N we can arbitrarily change the values of X1,…,XNX_1, \ldots, X_N without changing whether A∈T\evA \in \setT occurs or not.

Example (Limsup event): Let An∈σ(Xn)\evA_n \in \sigma(X_n) for all n∈Nn \in \N. We show that lim sup⁡n→∞An∈T\limsupinfty \evA_n \in \setT. For that let L=lim sup⁡n→∞An\evL = \limsupinfty \evA_n and LN=⋂n≥N⋃m≥nAm\evL_N = \bigcap_{n \geq N} \bigcup_{m \geq n} \evA_m. Note:
  1. L⊂LN\evL \subset \evL_N: This follows trivially from L=lim sup⁡n→∞An=⋂n≥1⋃m≥nAm⊂⋂n≥N⋃m≥nAm=LN \evL = \limsupinfty \evA_n = \bigcap_{n \geq 1} \bigcup_{m \geq n} \evA_m \subset \bigcap_{n \geq N} \bigcup_{m \geq n} \evA_m = \evL_N
  2. LN⊂L\evL_N \subset L: Let Bn=⋃n≥1Am\evB_n = \bigcup_{n \geq 1} \evA_m. Note that B1⊃B2⊃B3⊃⋯\evB_1 \supset \evB_2 \supset \evB_3 \supset \cdots. Thus ω∈LN  ⟹  ∀n≥N:ω∈Bn  ⟹  (∀n≥N:ω∈Bn)and(ω∈BN−1⊃BN)  ⟹  (∀n≥N:ω∈Bn)and(ω∈BN−1)and…and(ω∈B1)  ⟹  ∀n≥1:ω∈Bn  ⟹  ω∈L\begin{align*} & \omega \in \evL_N \\ \implies & \forall n \geq N : \omega \in \evB_n \\ \implies & \pa{\forall n \geq N : \omega \in \evB_n} \qand \pa{\omega \in \evB_{N-1} \supset \evB_N} \\ \implies & \pa{\forall n \geq N : \omega \in \evB_n} \qand \pa{\omega \in \evB_{N-1}} \qand \ldots \qand \pa{\omega \in \evB_1} \\ \implies & \forall n \geq 1 : \omega \in \evB_n \\ \implies & \omega \in \evL \end{align*}
Hence L=LN\evL = \evL_N. Since LN\evL_N is a countable union of countable intersections of events AN∈σ(XN)⊂σ(XN,XN+1,…)=TN\evA_N \in \sigma(X_N) \subset \sigma(X_N, X_{N+1}, \ldots) = \setT_N we have ∀N∈N:L=LN∈TN\forall N \in \N : \evL = \evL_N \in \setT_N and thus L∈T\evL \in \setT.

3.5 Kolmogorov's 0–1 Law

Theorem 3.7 (Kolmogorov's 0–1 Law): Let (Xn)n∈N\sequence{X} be an independent sequence of random variables and let T\setT be the respective tail σ\sigma-algebra, then ∀A∈T:P ⁣(A)∈{0,1} \forall \evA \in \setT : \probP{\evA} \in \set{0,1}
Note: We say that the sequence is tail-trivial.