Mathursday: Dynkin’s π-λ Theorem and CDF (Part 2)

The aim of this post is to prove that a cummulative distribution function (CDF) uniquely determines the probability distribution. This is a well known fundamental result that is quite intuitive but requires some advanced techniques to prove. In this post, we provide a complete proof using Dynkin’s π-λ Theorem. The previous post on this topic covered basic of topology and measure theory. If you are unfamiliar with concepts like measure, open set, Borel algebra then please see the previous post.

The main result we want to prove is the following.

Theorem: Let f: (X, \Sigma, P_1) \rightarrow (\mathbb{R}, \mathbb{B}) and g: (X, \Sigma, P_2) \rightarrow (\mathbb{R}, \mathbb{B}) be two random variables with CDF F, G respectively. If F(x) = G(x), \,\, \forall x \in \mathbb{R} then P_1(A)=P_2(A), \,\, \forall A \in \mathbb{B}(\mathbb{R}).

Notice that we want to prove something P_1 = P_2 which essentially means proving P_1(E) = P_2(E) \forall E \in \Sigma. Proving this for every member of the σ-algebra is difficult. Instead we will prove it for a subset of σ-algebra and show that it holds for the entire σ-algebra. The last step will be achieved using the powerful Dynkin’s π-λ Theorem. This is going to be our first stop.

Dynkin’s π-λ Theorem

To state the theorem we will have to define two more things:

Definition (π-system): A collection of subsets S of X is called a π-system if it is nonempty and closed under intersection i.e., \forall A, B \in S \rightarrow A \cap B \in S.

It is trivial to verify that every algebra of subsets is a π-system.

Definition (λ-system): A collection of subsets S of X is called a λ-system if:
1. X \in S.
2. For any A, B \in S such that A \subseteq B we have B - A \in S.
3. For any \{A_i\}_{i=1}^\infty where \forall i \in \mathbb{N}, A_i \in S and A_i \subseteq A_{i+1} then \cup_{i=1}^\infty A_i \in S.

This definition looks quite similar to that of a σ-algebra. Similarly a λ-system is closed under complement. Why? Let S be a λ-system and let A \in S. Then as X \in S and A \subseteq X therefore, A^c = X - A \in S. However, unlike a σ-algebra which is closed under countable union of arbitrary sets, the condition (3) above only holds for increasing sequence of sets (A_i \subseteq A_{i+1}). It is however straightforward to show the following:

Lemma 1: Every σ-algebra is both a π-system and a λ-system
Proof: Trivial

With these two definition we are ready to state the Dynkin’s π-λ Theorem.

Dynkin’s π-λ Theorem: If A is a π-system and B is a λ-system and A \subseteq B then A \subseteq \sigma(A) \subseteq B

The proof of this theorem is short but tricky. We defer the proof for now to first demonstrate the usefulness of the above result.

Usefulness: The way we use Dynkin’s π-λ Theorem is by showing that the property holds for a π-system and which generates the σ-algebra of interest. Then we show that the collection of sets where the property holds is a λ-system. Dynkin’s π-λ Theorem then will show that the property holds for the entire σ-algebra.

CDF Uniquely Determines the Distribution

Theorem: Let f: (X, \Sigma, P_1) \rightarrow (\mathbb{R}, \mathbb{B}) and g: (X, \Sigma, P_2) \rightarrow (\mathbb{R}, \mathbb{B}) be two random variables with CDF F, G respectively. If F(x) = G(x), \,\, \forall x \in \mathbb{R} then P_1(A)=P_2(A), \,\,\ \forall A \in \mathbb{B}(\mathbb{R}).

Proof: Let S be the collection of sets where the two probabiltiy measures agree, i.e., S = \left\{ A \in \mathbb{B}(\mathbb{R}) \mid P_1(A) = P_2(A)\right\}. We will construct a π-system where the property holds.

Claim 1: Let T = \left\{ \left(-\infty, x\right] \mid x \in (-\infty, \infty] \right\} be the collection of closed rays on real number line. Then T is a π-system, T \subseteq S and \sigma(T) = \mathbb{B}(\mathbb{R}).
Proof of Claim 1: The proof directly exploits the relation between closed rays and CDF. For any value of x \in (-\infty, \infty] we have

P_1((-\infty, x]) = F(x) = G(x) = P_2((-\infty, x]).

Hence, (-\infty, x] \in T i.e., all closed rays are in T. Secondly, T is closed under intersection as intersection of closed rays is another closed ray (\,\, (-\infty, x] \cap (-\infty, y] = (-\infty, \min(x,y)] \,\,). As T is nonempty therefore, it is a π-system. As we proved in the last post, the collection of closed rays generates the Borel σ-algebra i.e., \sigma(T) = \mathbb{B}(R).

Great! so now we have a π-system where the desired result holds and that generates \mathbb{B}(\mathbb{R}) which in this case is the σ-algebra of interest.

Claim 2: S is a λ-system
Proof of Claim 2: We prove each required property of a λ-system below.

  • From unitarity property of a probability measure we have P_1(X) = 1 = P_2(X). Therefore, X \in S.
  • Let A, B \in S and A \subseteq B. Let C = B-A then C and A are disjoint. Therefore, for any probability measure P we have P(C \cup A) = P(A) + P(C) \Rightarrow P(C) = P(B) - P(A). Then
    P_1(C) = P_1(B) - P_1(A) = P_2(B) - P_2(B) = P_2(C). Therefore, C=B-A \in S.
  • Let \{A_i\}_{i=1}^\infty be a sequence of increasing sets and \forall i \in \mathbb{N}, \,\, A_i \in S. For any probability measure P we have: P(\cup_{i=1}^\infty A_i) = \lim_{n \rightarrow \infty} P(A_n). We have P_1(A_n) = P_2(A_n) for every value of n. If two sequences have the same members then they have the same limit. Hence, \lim_{n \rightarrow \infty} P_1(A_n) = \lim_{n \rightarrow \infty} P_2(A_n) \Rightarrow P_1(\cup_{i=1}^\infty A_i) = P_2(\cup_{i=1}^\infty A_i). Therefore, \cup_{i=1}^\infty A_i \in S.

Wrapping up: We showed that T \subseteq S where T is a π-system and S is a  λ-system. Therefore, using Dynkin’s π-λ theorem we get \sigma(T) = \mathbb{B}(\mathbb{R}) \subseteq S. What does this mean? It means that for any A \in \mathbb{B}(\mathbb{R}) we have A \in S and therefore, by definition of S we have P_1(A) = P_2(A). This is exactly what we wanted to prove.

Proof of Dynkin’s π-λ Theorem

In order to proof this result we will make use of a couple of basic lemma:

Lemma 2: Intersection of λ-systems is a λ-system.
Proof: The proof is trivial. For example, let \{S_i\}_1^\infty be a set of λ-systems (so this is a set of set of set #inception). Now let A, B \in \cap_{i=1}^\infty S_i and A \subseteq B. As each S_i is a λ-system therefore, B-A \in S_i for every i \in \mathbb{N}. This implies, B-A \in \cap_{i=1}^\infty S_i.

Lemma 3: Intersection of σ-algebra is a σ-algebra
Proof: Trivial to verify.

Lemma 4: If a collection of subsets of X is both a π-system and a λ-system then it is a σ-algebra
Proof:  Let S be both a π-system and a λ-system. Then we will show it satisfies all three properties of a σ-algebra

  • As S) is a λ-system therefore, X \in S. Similarly, using the second property of a λ-system we have, X \subseteq X \Rightarrow \emptyset = X - X \in S.
  • Let E \in S then E \subseteq X \Rightarrow E^c = X - A \in S.
  • Let \{E_i\}_{i=1}^\infty be a collection of subsets of X. Define a sequence of increasing sets as follows: Y_1 = E_1 and Y_i = E_i \cup Y_{i-1}. Further, Y_1 \subseteq Y_2 \subseteq Y_3 \cdots. If somehow we could show that Y_i \in S then we can show that \cup_{i=1}^\infty Y_i = \cup_{i=1}^\infty E_i \in S. This would be interesting since we will show that every λ-system is a σ-algebra as we haven’t used the property of a π-system so far. However, as we will see we need the property to show Y_i \in S. We make an inductive argument: Y_1 = E_1 \in S. Assume Y_k \in S for all values of $k <= i$. Now Y_{i+1} = E_{i+1} \cup Y_i = \left( E_{i+1}^c \cap Y_i^c \right)^c. As S is closed under complement (point 2 above) and intersection (S is a π-system) therefore, Y_{i+1} \in S. Hence, proved.

Dynkin’s π-λ Theorem: If A is a π-system and B is a λ-system and A \subseteq then A \subseteq \sigma(A) \subseteq B.

Proof: Let \ell(A) be the smallest λ-system containing A.  As intersection of λ-systems is another λ-system therefore, we can define \ell(A) as the intersection of every λ-system containing A. As the power set of X is a λ-system therefore, \ell(A) is well defined. As B is another λ-system containing A and therefore, |\ell(A)| <= |B|. However, we can go further and claim \ell(A) \subseteq B. As if this wasn’t the case then the intersection \ell(A) \cap B will be a smaller λ-system containing A which is a contradiction. This argument will be repeated again and again so make sure you understand it!

Now every σ-algebra is a λ-system and as \sigma(A) contains A therefore, \ell(A) \subseteq \sigma(A). Here we have used the above argument to show containment. At this point we have shown \ell(A) \subseteq B and \ell(A) \subseteq \sigma(A). If we can show that \ell(A) = \sigma(A) then we will be done. This is exactly what we will show.

Now this is where the proof gets tricky. We first define a rather unintuitive set:

For any E \subseteq X we define D_E = \{ F \mid F \subseteq X, E \cap F \in \ell(A) \}. We will now make a couple of claims:

Claim 1: D_E is a λ-system  for any E \in \ell(A).
Proof of Claim 1:
We prove each property of a λ-system below:

  • X \cap E = E \in \ell(A) therefore, X \in D_E
  • Let F_1, F_2 \in D_E and F_1 \subseteq F_2. This implies F_1 \cap E \in \ell(A) and F_2 \cap E \in \ell(A). Further, F_1 \subseteq F_2 \Rightarrow F_1 \cap  E \subseteq F_2 \cap E.
    As \ell(A) is a λ-system therefore, F_2 \cap E - F_1 \cap E = (F_2 - F_1) \cap E \in \ell(A). From the definition of D_E this implies F_2 - F_1 \in D_E.
  • Let \{F_i\}_{i=1}^\infty be a countable collection of sets in D_E. This implies, F_i \cap E \in \ell(A). As \ell(A) is a λ-system therefore, \cap_{i=1}^\infty (F_i \cap E) = \left( \cap_{i=1}^\infty F_i \right) \cap E \in \ell(A). This implies, \cap_{i=1}^\infty F_i \in D_E.

So far we have not use the fact that A is a π-system. The next claim will exploit this property:

Claim 2: A \subseteq D_E for every E \in A.
Proof of Claim 2: As A is a π-system therefore, F \in A \Rightarrow F \cap E \in A. As A \subseteq \ell(A) therefore, F \cap E \in \ell(A). This implies F \in D_E.

Claim 3: Define A \cap \ell(A) = \left\{ E \cap F \mid E \in A, F \in \ell(A)\right\}. Then A \cap \ell(A) \subseteq \ell(A).
Proof of Claim 3:  For E \in A \subseteq \ell(A) we have D_E as a λ-system (Claim 1) containing A (Claim 2). This implies \ell(A) \subseteq D_E for every E \in A. Therefore, for any F \in \ell(A) we have F \in D_E which implies F \cap E \in \ell(A).

Using Claim 3 we will now strengthen Claim 2.

Claim 4: A \subseteq D_E for every E \in \ell(A).
Proof of Claim 4:  Let E \in \ell(A) and F \in A then F \cap E \in \ell(A) (Claim 3). This implies F \in D_E.

Claim 5: \ell(A) is closed under intersection.
Proof of Claim 5: For E \in \ell(A) we have D_E as a λ-system (Claim 1) containing A (Claim 4). This implies \ell(A) \subseteq D_E for every E \in \ell(A). Now let F \in \ell(A). Then F \in D_E and therefore, by definition of D_E we have F \cap E \in \ell(A). Proof is completed by observing that E, F are arbitrary members of \ell(A).

At this point, take a moment to observe the interesting pattern in Claim 2-5.

Wrapping Up: Claim 5 implies \ell(A) is both a π-system and a λ-system. From Lemma 4, this implies it is a σ-algebra. Further, A \subseteq \ell(A) hence we must have \sigma(A) \subseteq \ell(A) otherwise, we can create a smaller σ-algebra \ell(A) \cap \sigma(A) which is smaller than \sigma(A) and contains A (Lemma 3). However, we also showed earlier that \ell(A) \subseteq \sigma(A). This implies \sigma(A) = \ell(A).

At the beginning of the proof, we showed A \subseteq \ell(A) and \ell(A) \subseteq B. Therefore, we have A \subseteq \ell(A) = \sigma(A) \subseteq B. Hence, proved.

Further Reading

If you are interested in learning more about probability theory then John Pike‘s lecture notes are a useful resource:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s