Probability/Probability Spaces

Terminologies

The name of this chapter, Template:Colored em, is a mathematical construct that models a random experiment. To be more precise: Template:Colored definition Let us first give the definitions related to sample space. For the definitions of event space and probability, we will discuss it in later sections. Template:Colored definition Template:Colored remark Template:Colored example Template:Colored definition Template:Colored remark Template:Colored definition Template:Colored example

Probability interpretations

In this chapter, we will discuss probability mathematically, and we will give an axiomatic and abstract definition to probability (function). By axiomatic definition, we mean defining probability to be a function that satisfying some axioms, called probability axioms. But such axiomatic definition does not tell us how should we interpret the term "probability", so the definition is said to be Template:Colored em from the interpretation of probability. Such independence make the formal definition always applicable, no matter how you interpret probability.

However, the axiomatic definition does not suggest a way to construct a probability measure (i.e., assigning probabilities to events): it just states that probability is a function satisfying certain axioms, but how can we construct such function in the first place? In this section, we will discuss two main types of probability interpretations: subjectivism and frequentism, where the method of assigning probabilities to events is mentioned in each of them.

Subjectivism

Intuitively and naturally, Template:Colored em of an event is often regarded as a numerical measure of the "chance" of the occurrence of the event (that is, how likely the event will occur). So, it is natural for us to assign probability to an event based on our own assessment on the "chance". (In order for the probability to be valid according to the axiomatic definition, the assignment needs to satisfy the Template:Colored em.) But different people may have different assessment on the "chance", depending on their personal opinions. So, we can see that such interpretation of probability is somewhat Template:Colored em, since different people may assign different probabilities to the same event. Hence, we call such probability interpretation as Template:Colored em (also known as Template:Colored em). Template:Colored example The main issue of the subjectivism is the lack of objectivity, since different probabilities can be assigned to the same event based on personal opinion. Then, we may have difficulties in choosing which of the probabilities should be used for that event. To mitigate the issue of the lack of objectivity, we may adjust our degrees of belief on an event from time to time when there are more observed data through Template:Colored em, which will be discussed in later chapter, so that the value is assigned in a more objective way. However, even after the adjustment, the assignment of value is still not in an Template:Colored em objective way, since the adjusted value (known as Template:Colored em) still depends on the initial value (known as Template:Colored em), which is assigned subjectively.

Frequentism

Another probability interpretation, which is objective, is called Template:Colored em. We denote by $n(E)$ the number of occurrences of an event $E$ in $n$ repetitions of experiment. (An Template:Colored em is any action or process with an Template:Colored em that is subject to uncertainty or randomness.) Then, we call $\frac{n(E)}{n}$ as the Template:Colored em of the event $E$. Intuitively, we will Template:Colored em that the relative frequency fluctuates less and less as $n$ gets larger and larger, and approach to a constant limiting value (we call this as Template:Colored em) as $n$ tends to infinity, i.e., the limiting relative frequency is $\underset{n\to \mathrm{\infty }}{\lim }\frac{n(E)}{n}$. It is thus natural to take the limiting relative frequency as the probability of the event $E$. This is exactly what the definition of probability in the frequentism. In particular, the Template:Colored em of such limiting relative frequency is an assumption or Template:Colored em in frequentism. (As a side result, when $n$ is large enough, the relative frequency of the event $E$ may be used to approximate the probability of the event $E$.)

However, an issue of frequentism is that it may be infeasible to conduct experiments many times for some events. Hence, for those events, no probability can be assigned to them, and this is clearly a limitation for frequentism. Template:Colored example Template:Colored example Because of these issues, we will instead use a modern axiomatic and abstract approach to define probability, which is suggested by a Russian mathematician named Andrey Nikolaevich Kolmogorov in 1933. By Template:Colored em, we mean defining probability quite broadly and abstractly as something that satisfy certain axioms (called Template:Colored em). Such probability axioms are the mathematical foundation and the basis of modern probability theory.

Probability axioms

Since we want use the probability measure $\mathbb{P}$ to assign probability $\mathbb{P}(E)$ to every event $E$ in the sample space, it seems natural for us to set Template:Colored em of the probability measure $\mathbb{P}$ to be the set containing Template:Colored em subsets of $\mathrm{\Omega }$, i.e., the power set of $\mathrm{\Omega }$, $𝒫(\mathrm{\Omega })$. Unfortunately, this situation is not that simple, and there are some technical difficulties if we set the domain like this, when the sample space $\mathrm{\Omega }$ is Template:Colored em. Template:Colored remark This is because the power set of such uncountable sample space includes some "badly behaved" sets, which causes problems when assigning probabilities to them. (Here, we will not discuss those sets and these technical difficulties in details.) Thus, instead of setting the domain of the probability measure to be $𝒫(\mathrm{\Omega })$, we set the domain to be a Template:Colored em (sigma-algebra) containing some "sufficiently well-behaved" events: Template:Colored definition Template:Colored remark Template:Colored proposition

Proof.

Property 1: By the closure under complementation, since $S\in \mathrm{\Sigma }$, it follows that $\varnothing =S^c\in \mathrm{\Sigma }$.

Property 2: By the closure under countable unions, we have for Template:Colored em infinite sequence of sets $A_1,A_2,\dots$, if the sets $A_1,A_2,\dots \in \mathrm{\Sigma }$, then $\bigcup _{i=1}^{\mathrm{\infty }}{A}_i\in \mathrm{\Sigma }$. So, in particular, we can choose the sequence to be $A_1,A_2,\dots ,A_n,\varnothing ,\varnothing ,\dots$ ($\varnothing \in \mathrm{\Sigma }$) where $A_1,A_2,\dots ,A_n$ is an arbitrary sequence such that $A_1,A_2,\dots ,A_n\in \mathrm{\Sigma }$. Then, $$\bigcup _{i=1}^n{A}_i=\bigcup _{i=1}^{\mathrm{\infty }}{A}_i\in \mathrm{\Sigma }.$$ Thus, we have the desired result.

Property 3: For every infinite sequence of sets $A_1,A_2,\dots \in \mathrm{\Sigma }$, by the closure under complementation, we have $$A_1^c,A_2^c,\dots \in \mathrm{\Sigma }.$$ Then, by the closure under countable unions, we have $\bigcup _{i=1}^{\mathrm{\infty }}{A}_i^c\in \mathrm{\Sigma }$. After that, we use the De Morgan's law: $${\left(\bigcap _{i=1}^{\mathrm{\infty }}{A}_i\right)}^c=\bigcup _{i=1}^{\mathrm{\infty }}{A}_i^c\in \mathrm{\Sigma }.$$ Using the closure under complementation property again, we have $$\bigcap _{i=1}^{\mathrm{\infty }}{A}_i\in \mathrm{\Sigma }$$ as desired.

Property 4: The proof is similar to that of property 2, and hence left as an exercise.

$◻$

Template:Colored remark Template:Colored exercise Template:Colored example Template:Colored exercise We have seen two examples of $\sigma$-algebra in the example above. Often, the "smallest" $\sigma$-algebra is not chosen to be the domain of the probability measure, since we usually are interested in events Template:Colored em $\varnothing$ and $\mathrm{\Omega }$.

For the "largest" $\sigma$-algebra, on the other hand, it contains every event, but we may not be interested in some of them. Particularly, we are usually interested in events that are "well-behaved", instead of those "badly behaved" events (indeed, it may be even impossible to assign probabilities to them properly (those events are called Template:Colored em)).

Fortunately, when the sample space $\mathrm{\Omega }$ is Template:Colored em, every set in $𝒫(\mathrm{\Omega })$ is "well-behaved", so we can take this power set to be a $\sigma$-algebra for the domain of probability measure.

However, when the sample space $\mathrm{\Omega }$ is Template:Colored em, even if the power set $𝒫(\mathrm{\Omega })$ is a $\sigma$-algebra, it contains "too many" events, particularly, it even includes some "badly behaved" events. Therefore, we will not choose such power set to the domain of the probability measure. Instead, we just choose a $\sigma$-algebra that includes the "well-behaved" events to be the domain, so that we are able to assign probability properly to every event in the $\sigma$-algebra of the domain. Particularly, those "well-behaved" events are often the events of interest, so all events of interest are contained in that $\sigma$-algebra, that is, the domain of the probability measure.

To motivate the probability axioms, we consider some properties that the "probability" in frequentism (as a limiting relative frequency) possess:

1. The limiting relative frequency must be nonnegative. (We call this property as Template:Colored em.)
2. The limiting relative frequency of the whole sample space $\mathrm{\Omega }$ ($\mathrm{\Omega }$ is also an event) must be 1 (since by definition $\mathrm{\Omega }$ contains all sample points, this event must occur in every repetition). (We call this property as Template:Colored em.)
3. If the events $E_1,E_2,\dots$ are pairwise disjoint (i.e., $E_i\cap E_j=\varnothing$ for every $i,j$ with $i\ne j$), then the limiting relative frequency of the event $\bigcup _{i=1}^{\mathrm{\infty }}{E}_i\stackrel{\text{ def }}{=}{E}_1\cup E_2\cup \cdots$ (union of subsets of $\mathrm{\Omega }$ is a subset of $\mathrm{\Omega }$, so it can be called an event) is

$$\begin{array}{cc}\underset{n\to \mathrm{\infty }}{\lim }\frac{n(\bigcup _{i=1}^{\mathrm{\infty }}{E}_i)}{n}& =\underset{n\to \mathrm{\infty }}{\lim }\frac{n(\bigcup _{i=1}^{\mathrm{\infty }}{E}_i)}{n}\\ & =\underset{n\to \mathrm{\infty }}{\lim }\frac{n(E_1)+n(E_2)+\cdots }{n}& (\text{the events are pairwise disjoint})\\ & =\underset{n\to \mathrm{\infty }}{\lim }\frac{n(E_1)}{n}+\underset{n\to \mathrm{\infty }}{\lim }\frac{n(E_2)}{n}+\cdots & (\text{every limit exists by the axiom in frequentism})\\ & =\sum _{i=1}^{\mathrm{\infty }}\underset{n\to \mathrm{\infty }}{\lim }\frac{n(E_i)}{n},\end{array}$$

which is the sum of the limiting relative frequency of each of the events $E_1,E_2,\dots$. (We call this property as Template:Colored em.)

It is thus very natural to set the probability axioms to be the three properties mentioned above: Template:Colored definition Template:Colored remark Using the probability axioms alone, we can prove many well-known properties of probability.

Basic properties of probability

Let us start the discussion with some simple properties of probability. Template:Colored theorem

Proof. Consider the infinite sequence of events $\mathrm{\Omega },\varnothing ,\varnothing ,\dots$ (recall that $\varnothing$ and $\mathrm{\Omega }$ must be in the $\sigma$-algebra $ℱ$). We can see that the events are pairwise disjoint. Also, the union of these events is $\mathrm{\Omega }$. Hence, by the countable additivity of probability, we have $$\underset{=1}{\underbrace{\mathbb{P}(\mathrm{\Omega })}}=\underset{=1}{\underbrace{\mathbb{P}(\mathrm{\Omega })}}+\mathbb{P}(\varnothing )+\mathbb{P}(\varnothing )+\cdots ⟹\mathbb{P}(\varnothing )+\mathbb{P}(\varnothing )+\cdots =1-1=0⟹\sum _{i=1}^{\mathrm{\infty }}\mathbb{P}(\varnothing )=0.$$ It can then be shown that $\mathbb{P}(\varnothing )=0$.

$◻$

Using this result, we can obtain Template:Colored em from the countable additivity of probability: Template:Colored theorem

Proof. Consider the infinite sequence of events $E_1,E_2,\dots ,E_n,\varnothing ,\varnothing ,\dots$ (recall that $\varnothing \in ℱ$ always). Then, $$\begin{array}{cc}\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)& =\mathbb{P}\left(\bigcup _{i=1}^{\mathrm{\infty }}{A}_i\right)\\ & =\sum _{i=1}^{\mathrm{\infty }}\mathbb{P}(A_i)& (\text{countable additivity})\\ & =\sum _{i=1}^n\mathbb{P}(A_i)+\sum _{i=n+1}^{\mathrm{\infty }}\mathbb{P}(\varnothing )\\ & =\sum _{i=1}^n\mathbb{P}(A_i).\end{array}$$ (The last equality follows since $\mathbb{P}(\varnothing )=0$, and it can be shown that $\sum _{i=n+1}^{\mathrm{\infty }}\mathbb{P}(\varnothing )=0$ using some concepts in limit (to be mathematically rigorous).)

$◻$

Finite additivity makes the proofs of some of the following results simpler. Template:Colored theorem

Proof.

Property 1:

First, notice that by definition $\mathrm{\Omega }=A\cup A^c$. Furthermore, since $A\in ℱ$, we have $A^c\in ℱ$ by the closure under complementation of $\sigma$-algebra. Also, the sets $A$ and $A^c$ are disjoint. Thus, by the finite additivity, we have $$\mathbb{P}(A\cup A^c)=\mathbb{P}(A)+\mathbb{P}(A^c).$$ On the other hand, $$\mathbb{P}(A\cup A^c)=\mathbb{P}(\mathrm{\Omega })\stackrel{\text{ P2 }}{=}1.$$ Thus, we have the desired result.

Property 2: By property 1, we have $\mathbb{P}(A)=1-\underset{\ge 0\text{ by P1}}{\underbrace{\mathbb{P}(A^c)}}\le 1$. We then have the desired numeric bound on $\mathbb{P}(A)$ since $\mathbb{P}(A)\ge 0$ also by the nonnegativity of probability.

Property 3: $$\begin{array}{ccc}\mathbb{P}(B)& =\mathbb{P}(B\cap \mathrm{\Omega })& (B\subseteq \mathrm{\Omega },\text{ so }B=B\cap \mathrm{\Omega })\\ & =\mathbb{P}(B\cap (A\cup A^c))& (\text{definition})\\ & =\mathbb{P}((B\cap A)\cup (B\cap A^c))& (\text{distributive law})\\ & =\mathbb{P}(B\cap A)+\mathbb{P}(B\setminus A)& (B\cap A,B\cap A^c\in ℱ,\text{ and are disjoint. Also, }B\setminus A=B\cap A^c)\end{array}$$

Property 4: By property 3, we have $$\begin{array}{ccc}\mathbb{P}(A\cup B)& =\mathbb{P}((A\cup B)\cap A)+\mathbb{P}((A\cup B)\setminus A)& (\text{property 3})\\ & =\mathbb{P}(A)+\mathbb{P}(B\setminus A)& (\text{possibly through Venn diagram informally})\\ & =\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(B\cap A).& (\text{property 3})\\ \end{array}$$

Property 5: Assume that $A\subseteq B$. Then, $A\cap B=A$. Hence, by property 3, $$\mathbb{P}(B)=\mathbb{P}(B\cap A)+\underset{\ge 0\text{ by P1}}{\underbrace{\mathbb{P}(B\setminus A)}}=\mathbb{P}(A).$$

$◻$

Constructing a probability measure

As we have said, the axiomatic definition does not suggest us a way to construct a probability measure. Actually, even for the same experiment, there can be many ways to construct a probability measure that satisfies the above probability axioms if there are not sufficient information provided: Template:Colored example However, we have previously mentioned that we may assign probabilities to events subjectively (as in subjectivism), or according to its limiting relative frequency (as in frequentism). Through these two probability interpretations, we may provide some background information for a random experiment, by assigning probabilities to some of the events before constructing the probability measure, to the extent that there is Template:Colored em way to construct a probability measure. Consider the coin tossing example again: Template:Colored example In general, it is not necessary to assign probability to Template:Colored em event in the event space in the background information for us to able to construct the probability measure in exactly one way. Consider the following example. Template:Colored example We can see from this example that to provide sufficient background information to the extent that the probability measure can be constructed in exactly one way, we just need the probability of each of the singleton events (which should be nonnegative and sum to one to satisfy the probability axioms). After that, we can calculate the probability for each of the other events in the event space, and hence construct the only possible probability measure.

This is true when the sample space is countable, in general: Template:Colored theorem

Proof.

Case 1: $\mathrm{\Omega }$ is finite. Then, we can write $\mathrm{\Omega }=\{{\omega }_1,{\omega }_2,\dots ,{\omega }_n\}$. It follows that every event $E\in ℱ$ can be expressed as $E=\bigcup _i\{{\omega }_i\}$ (which $i$s are taken over for the union depends on the event $E$). Notice also that the sets "$\{{\omega }_i\}$"s are disjoint. (Every set contains a different sample point, and so the intersection of any pair of them is an empty set.) Then, by the finite additivity of probability, we have for every event $E\in ℱ$, $$\mathbb{P}(E)=\sum _i^{}\mathbb{P}(\{{\omega }_i\})=\sum _{\omega \in E}^{}\mathbb{P}(\{\omega \}).$$

Case 2: $\mathrm{\Omega }$ is countably infinite. Then, we can write $\mathrm{\Omega }=\{{\omega }_1,{\omega }_2,\dots \}$. It follows that every event $E\in ℱ$ can be expressed as $E=\bigcup _i\{{\omega }_i\}$ (which $i$s are taken over for the union depends on the event $E$). Notice also that the sets "$\{{\omega }_i\}$"s are disjoint. Then, by the countable additivity/finite additivity of probability, we have for every event $E\in ℱ$, $$\mathbb{P}(E)=\sum _i^{}\mathbb{P}(\{{\omega }_i\})=\sum _{\omega \in E}^{}\mathbb{P}(\{\omega \}).$$

$◻$

Template:Colored example The following is an important special case for the above theorem. Template:Colored corollary

Proof. Under the assumptions, the probability of every singleton event is nonnegative. Also, the sum of the probabilities is $$\underset{|\mathrm{\Omega }|\text{ times}}{\underbrace{\frac{1}{|\mathrm{\Omega }|}+\frac{1}{|\mathrm{\Omega }|}+\cdots +\frac{1}{|\mathrm{\Omega }|}}}=1.$$ Thus, for every event $E$, we have by the previous theorem $$\mathbb{P}(E)=\sum _{\omega \in E}^{}\mathbb{P}(\{\omega \})=\underset{|E|\text{ times}}{\underbrace{\frac{1}{|\mathrm{\Omega }|}+\frac{1}{|\mathrm{\Omega }|}+\cdots +\frac{1}{|\mathrm{\Omega }|}}}=\frac{|E|}{|\mathrm{\Omega }|}.$$

$◻$

More advanced properties of probability

Recall the Template:Colored em in combinatorics. We have similar results for probability: Template:Colored theorem

Proof. We can prove this by mathematical induction.

Let $P(n)$ be the statement $$\mathbb{P}(E_1\cup E_2\cup \cdots \cup E_n)=\sum _{i_1}^{}\mathbb{P}(E_{i_1})-\sum _{i_1<i_2}^{}\mathbb{P}(E_{i_1}\cap E_{i_2})+\sum _{i_1<i_2<i_3}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{i_3})-\cdots +(-1{)}^{n+1}\sum _{i_1<i_2<\cdots <i_n}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap \cdots \cap E_{i_n}).$$ We wish to prove that $P(n)$ is true for every positive integer $n$.

Basis Step: When $n=1$, $P(n)$ is clearly true since it merely states that $\mathbb{P}(E_1)=\mathbb{P}(E_1)$.

Inductive Hypothesis: Assume that $P(k)$ is true for an arbitrary positive integer $k$.

Inductive Step:

Case 1: $k=1$. Then, $P(k+1)=P(2)$ is true by a property of probability (recall that we have "$\mathbb{P}(A\cup B)=\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(A\cap B)$").

Case 2: $k\ge 2$. We wish to prove that $P(k+1)$ is true. The main idea of the steps is to regard $E_1\cup E_2\cup \cdots E_k\cup E_{k+1}$ as $(E_1\cup E_2\cup \cdots \cup E_k)\cup E_{k+1}$, and then we apply the above property of probability, and eventually we will apply the inductive hypothesis twice, on two probabilities involving union of $k$ events. Ultimately, through some (somewhat complicated) algebraic manipulations, we finally get the desired result. The details are as follows (may be omitted): $$\begin{array}{cc}\mathbb{P}(E_1\cup E_2\cup \cdots \cup E_k\cup E_{k+1})& =\mathbb{P}((E_1\cup E_2\cup \cdots \cup E_k)\cup E_{k+1})\\ & =\mathbb{P}(E_1\cup E_2\cup \cdots \cup E_k)+\mathbb{P}(E_{k+1})-\mathbb{P}((E_1\cup E_2\cup \cdots \cup E_k)\cap E_{k+1})(\text{using the above property of probability again})\\ & =\mathbb{P}(E_1\cup E_2\cup \cdots \cup E_k)+\mathbb{P}(E_{k+1})-\mathbb{P}((E_1\cap E_{k+1})\cup (E_2\cap E_{k+1})\cup \cdots \cup (E_k\cap E_{k+1}))(\text{distributive law})\\ & =\sum _{i_1}^{}\mathbb{P}(E_{i_1})-\sum _{i_1<i_2}^{}\mathbb{P}(E_{i_1}\cap E_{i_2})+\sum _{i_1<i_2<i_3}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{i_3})-\cdots +(-1{)}^{k+1}\sum _{i_1<i_2<\cdots <i_k}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap \cdots \cap E_{i_k})\\ & +\mathbb{P}(E_{k+1})-\sum _{i_1}^{}\mathbb{P}(E_{i_1}\cap E_{k+1})+\sum _{i_1<i_2}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{k+1})-\cdots +(-1{)}^{k+1}\sum _{i_1<i_2<\cdots <i_{k-1}}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{i_3}\cap \cdots \cap E_{i_{k-1}}\cap E_{k+1})\\ & +(-1{)}^{k+2}\sum _{i_1<i_2<\cdots <i_k}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap \cdots \cap E_{i_k}\cap E_{k+1})(\text{using inductive hypothesis twice})\\ & =\sum _{i_1}^{}\mathbb{P}(E_{i_1})-\sum _{i_1<i_2}^{}\mathbb{P}(E_{i_1}\cap E_{i_2})+\sum _{i_1<i_2<i_3}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{i_3})-\cdots +(-1{)}^{k+1}\sum _{i_1<i_2<\cdots <i_k}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap \cdots \cap E_{i_k})\\ & +\mathbb{P}(E_{k+1})-\sum _{i_1}^{}\mathbb{P}(E_{i_1}\cap E_{k+1})+\sum _{i_1<i_2}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{k+1})-\cdots +(-1{)}^{k+1}\sum _{i_1<i_2<\cdots <i_{k-1}}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{i_3}\cap \cdots \cap E_{i_{k-1}}\cap E_{k+1})\\ & +(-1{)}^{k+2}\sum _{i_1<i_2<\cdots <i_k}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap \cdots \cap E_{i_k}\cap E_{k+1})(\text{just changing colors})\\ & =\sum _{i_1}^{}\mathbb{P}(E_i)-\sum _{i_1<i_2}^{}\mathbb{P}(E_{i_1}\cap E_{i_2})+\sum _{i_1<i_2<i_3}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap E_{i_3})-\cdots +(-1{)}^{k+1}\sum _{i_1<i_2<\cdots <i_k}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap \cdots \cap E_{i_k})\\ & +(-1{)}^{k+2}\sum _{i_1<i_2<\cdots <i_k<i_{k+1}}^{}\mathbb{P}(E_{i_1}\cap E_{i_2}\cap \cdots \cap E_{i_k}\cap E_{i_{k+1}})(\text{sum is wrt }k+1\text{ case, which involves }{E}_1,E_2,\dots ,E_{k+1})\\ \end{array}$$ So, $P(k+1)$ is true.

Hence, by the principle of mathematical induction, $P(n)$ is true for every positive integer $n$.

$◻$

Template:Colored remark Template:Colored example Template:Colored example The following is a classical example for demonstrating the application of inclusion-exclusion principle. Template:Colored example Template:Colored theorem

Proof. Assume that $E_n\uparrow E$. Now, define $$F_1=E_1,F_2=E_2\setminus E_1,F_3=E_3\setminus E_2,\dots .$$ Claim: $F_1,F_2,\dots \in ℱ$ are pairwise disjoint.

Proof. We wish to prove that $F_i\cap F_j=\varnothing$ for every $i,j$ such that $i\ne j$. $$\begin{array}{cc}{F}_i\cap F_j& =(E_i\cap E_{i-1}^c)\cap (E_j\cap E_{j-1}^c)\\ & =(E_i\cap E_j)\cap (E_{i-1}\cup E_{j-1}{)}^c.& (\text{De Morgan's law})\\ \end{array}$$ Case 1: $i<j$. Then, $E_i\cap E_j=E_i$ ($E_i\subseteq E_j$) and $E_{i-1}\cup E_{j-1}=E_{j-1}$ ($E_{i-1}\subseteq E_{j-1}$). Hence, $F_i\cap F_j=E_i\setminus E_{j-1}=\varnothing$. (Since $i<j$, $E_i\subseteq E_{j-1}$ ($i$ can be at most $j-1$).)

Case 2: $i>j$. Then, $E_i\cap E_j=E_j$ ($E_j\subseteq E_i$) and $E_{i-1}\cup E_{j-1}=E_{i-1}$. Hence, $F_i\cap F_j=E_j\setminus E_{i-1}=\varnothing$ similarly.

$◻$

Also, we have $\bigcup _{i=1}^n{F}_i=E_n$, and $\bigcup _{i=1}^{\mathrm{\infty }}{F}_i=\bigcup _{i=1}^{\mathrm{\infty }}{E}_i\in ℱ$. Then, we have $$\begin{array}{ccc}\underset{n\to \mathrm{\infty }}{\lim }\mathbb{P}(E_n)& =\underset{n\to \mathrm{\infty }}{\lim }\mathbb{P}\left(\bigcup _{i=1}^n{F}_i\right)& (\text{above})\\ & =\underset{n\to \mathrm{\infty }}{\lim }\sum _{i=1}^n\mathbb{P}(F_i)& (\text{finite additivity})\\ & =\sum _{i=1}^{\mathrm{\infty }}\mathbb{P}(F_i)& (\text{definition})\\ & =\mathbb{P}\left(\bigcup _{i=1}^{\mathrm{\infty }}{F}_i\right)& (\text{countable additivity})\\ & =\mathbb{P}\left(\bigcup _{i=1}^{\mathrm{\infty }}{E}_i\right)& (\text{above})\\ & =\mathbb{P}(E).\\ \end{array}$$

$◻$

Proof. Assume that $E_n\downarrow E$ as $n\to \mathrm{\infty }$. Then, by De Morgan's law and a property of subset, $E_n^c\uparrow E^c$. So, $$\begin{array}{ccc}\underset{n\to \mathrm{\infty }}{\lim }\mathbb{P}(E_n)& =1-\underset{n\to \mathrm{\infty }}{\lim }\mathbb{P}(E_n^c)& (\text{complementary event property})\\ & =1-\mathbb{P}(E^c)& (\text{continuity from below})\\ & =1-(1-\mathbb{P}(E))& (\text{complementary event property})\\ & =\mathbb{P}(E).\end{array}$$

$◻$

Proof. Define $$F_1=E_1,F_2=E_2\setminus E_1,F_3=E_3\setminus (E_2\cup E_1),\dots F_k=E_k\setminus (E_{k-1}\cup E_{k-2}\cup \cdots \cup E_2\cup E_1),\dots .$$ Claim: $F_1,F_2,F_3,\dots \in ℱ$ are pairwise disjoint.

Proof. We wish to prove that $F_i\cap F_j=\varnothing$ for every $i,j$ such that $i\ne j$. $$\begin{array}{cc}{F}_i\cap F_j& =(E_i\cap {(E_{i-1}\cup E_{i-2}\cup \cdots \cup E_1)}^c)\cap (E_j\cap {(E_{j-1}\cup E_{j-2}\cup \cdots \cup E_1)}^c)\\ & =(E_i\cap E_{i-1}^c\cap E_{i-2}^c\cap \cdots \cap E_1^c)\cap (E_j\cap E_{j-1}^c\cap E_{j-2}^c\cap \cdots \cap E_1^c).& (\text{De Morgan's law})\\ \end{array}$$ Case 1: $i<j$. Then, $E_j\cap E_{j-1}^c\cap E_{j-2}^c\cap \cdots \cap E_1^c=E_j\cap E_{j-1}^c\cap E_{j-2}^c\cap \cdots \cap E_i^c\cap \cdots \cap E_1^c\subseteq E_i^c$. So, it follows that $$(E_i\cap E_{i-1}^c\cap E_{i-2}^c\cap \cdots \cap E_1^c)\cap (E_j\cap E_{j-1}^c\cap E_{j-2}^c\cap \cdots \cap E_1^c)\subseteq (E_i\cap E_{i-1}^c\cap E_{i-2}^c\cap \cdots \cap E_1^c)\cap E_i^c=\varnothing ,$$ which means $F_i\cap F_j=\varnothing$ (since the only subset of $\varnothing$ is $\varnothing$).

Case 2: $i>j$. Then, $E_i\cap E_{i-1}^c\cap E_{i-2}^c\cap \cdots \cap E_1^c=E_i\cap E_{i-1}^c\cap E_{i-2}^c\cap \cdots \cap E_j^c\cap \cdots \cap E_1^c\subseteq E_j^c$. So, it follows that $$(E_i\cap E_{i-1}^c\cap E_{i-2}^c\cap \cdots \cap E_1^c)\cap (E_j\cap E_{j-1}^c\cap E_{j-2}^c\cap \cdots \cap E_1^c)\subseteq E_j^c\cap (E_j\cap E_{j-1}^c\cap E_{j-2}^c\cap \cdots \cap E_1^c)=\varnothing ,$$ which means $F_i\cap F_j=\varnothing$ (since the only subset of $\varnothing$ is $\varnothing$).

$◻$

Furthermore, we have $F_i\subseteq E_i$ for every $i=1,2,\dots$, and $\bigcup _{j=1}^{\mathrm{\infty }}{F}_j=\bigcup _{j=1}^{\mathrm{\infty }}{E}_j\in ℱ$. Hence, $$\begin{array}{cc}\mathbb{P}\left(\bigcup _{i=1}^{\mathrm{\infty }}{E}_i\right)& =\mathbb{P}\left(\bigcup _{i=1}^{\mathrm{\infty }}{F}_i\right)\\ & =\sum _{i=1}^{\mathrm{\infty }}\mathbb{P}(F_i)& (\text{countable additivity})\\ & \le \sum _{i=1}^{\mathrm{\infty }}\mathbb{P}(E_i).& (\text{monotonicity})\end{array}$$

$◻$