Probability/Probability Spaces

Terminologies

The name of this chapter, probability space, is a mathematical construct that models a random experiment. To be more precise:

Definition. (Probability space) A probability space is a mathematical triplet $(\Omega ,{\mathcal {F}},\mathbb {P} )$ consisting of three elements: a sample space $\Omega$, an event space ${\mathcal {F}}$, and a probability measure $\mathbb {P} :{\mathcal {F}}\to [0,1]$.

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.

Definition. (Sample space and sample point) The sample space of a random experiment, denoted by $\Omega$, is a nonempty set consisting of all possible and indecomposable outcomes of the random experiment, called sample points.

Remark.

• A sample point is often denoted by $\omega$ (lowercase omega), in contrast with the uppercase omega $\Omega$ used for the notation of sample space.
• By an indecomposable outcome, we mean we are unable to split the outcome into multiple more specific outcomes ("smaller pieces"). So, in other words, indecomposable outcomes mean outcomes that are expressed in a way that is as specific as possible. Furthermore, the random experiment should only result in exactly one of the indecomposable outcomes.

• For instance, when rolling a dice and consider the number facing up, we may say the outcomes are "odd number" and "even number". But such outcomes are decomposable: we can split "odd number" to three more specific outcomes: 1,3,5, and "even number" to three more specific outcomes: 2,4,6.
• On the other hand, we may regard the outcomes as the numbers 1,2,3,4,5,6, which are indecomposable, and are expressed in the most specific way.

Example. A sample space of tossing a coin is $\Omega =\{H,T\}$ ($H$: heads come up, $T$: tails come up), and the sample points are $H,T$.

Definition. (Event) An event is a subset of the sample space.

Remark.

• So, an event is an aggregate of sample points.
• An event is said to be simple event if it consists of exactly one sample point.
• An event is said to be compound event if it consists of more than one sample point.

Definition. (Occurrence of events) An event occurs if it contains the outcome from the random experiment.

Example. We take the sample space of rolling a dice to be $\Omega =\{1,2,3,4,5,6\}$. Then, the sets $E_{1}=\varnothing ,E_{2}=\{1,2,3\},E_{3}=\Omega$ are events, while the set $\{0\}$ is not.

Suppose we get the number 3 from rolling the dice. Then, $E_{2}$ and $E_{3}$ occur, but $E_{1}$ does not occur.

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 independent 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, probability 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 probability axioms.) 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 subjective, since different people may assign different probabilities to the same event. Hence, we call such probability interpretation as subjectivism (also known as Bayesian probability).

Example. Amy and Bob assign the probabilities of winning the top prize from a lucky draw according to subjectivism:

• Amy thinks that she is lucky, and thus assign 0.7 to the probability of winning the top prize.
• Bob thinks that he is unlucky, and thus assign 0.1 to the probability of winning the top prize.

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 Bayes' theorem, 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 entirely objective way, since the adjusted value (known as posterior probability) still depends on the initial value (known as prior probability), which is assigned subjectively.

Frequentism

Another probability interpretation, which is objective, is called frequentism. We denote by $n(E)$ the number of occurrences of an event $E$ in $n$ repetitions of experiment. (An experiment is any action or process with an outcome that is subject to uncertainty or randomness.) Then, we call ${\frac {n(E)}{n}}$ as the relative frequency of the event $E$. Intuitively, we will expect 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 limiting relative frequency) as $n$ tends to infinity, i.e., the limiting relative frequency is $\lim _{n\to \infty }{\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 existence of such limiting relative frequency is an assumption or axiom 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.

Example. Suppose John is taking a course in probability theory, and the course can only be taken once. Consider the event "John passes the course". For this event, it is infeasible to repeat the experiment many times, since John can only take the course once, so there can be only one experiment. (Notice that we cannot use the experiences for other students taking the course as the experiments for this event, since we specify that the person taking the course must be John, but not others.)

Example. Consider a couple, Amy and Bob, and the event "this couple divorce eventually". For this event, it is again infeasible to repeat the experiment many times, since there is only one such pair of couples, and thus there can only be one experiment.

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 axiomatic approach, we mean defining probability quite broadly and abstractly as something that satisfy certain axioms (called probability axioms). 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 domain of the probability measure $\mathbb {P}$ to be the set containing all subsets of $\Omega$, i.e., the power set of $\Omega$, ${\mathcal {P}}(\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 $\Omega$ is uncountable.

Remark.

• A set is countable, if, intuitively and informally, we can "count" the elements of the set. E.g., every finite set is countable since we can "count" the elements in every finite set one by one. Also, $\mathbb {N} =\{1,2,\dotsc \},\mathbb {Z} =\{0,1,-1,2,-2,\dotsc \}$ are countable since we can still "count" the elements in these sets one by one. (A countable infinite set is also called a countably infinite set.)
• A set is uncountable if it is not countable.

• Some examples of uncountable sets include $\mathbb {R}$ and real intervals $(a,b),(a,b],[a,b),[a,b]$ ($b>a$).

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 ${\mathcal {P}}(\Omega )$, we set the domain to be a $\sigma$-algebra (sigma-algebra) containing some "sufficiently well-behaved" events:

Definition. ($\sigma$-algebra) Let $S$ be a set (considered to be the universal set), and ${\mathcal {P}}(S)$ be its power set. A set $\Sigma \subseteq {\mathcal {P}}(S)$ is a $\sigma$-algebra on the set $S$, if the following three properties are satisfied:

1. $S\in \Sigma$.
2. For every set $A$, if the set $A\in \Sigma$, then its complement $A^{c}\in \Sigma$. (closure under complementation)
3. For every infinite sequence of sets $A_{1},A_{2},\dotsc$, if the sets $A_{1},A_{2},\dotsc \in \Sigma$, then $\bigcup _{i=1}^{\infty }A_{i}\in \Sigma$. (closure under countable unions)

Remark.

• Elements of the $\sigma$-algebra are sometimes called measurable sets. Hence, whether a set is measurable or not actually depends on how we construct the $\sigma$-algebra. However, we usually construct $\sigma$-algebra to include "well-behaved" sets only, and exclude "badly behaved" sets. So, in this case, only "well-behaved" sets are measurable.
• A $\sigma$-algebra on the sample space $\Omega$, which consists of a family (or set) of events, is also called an event space, denoted by ${\mathcal {F}}$.
• We call $(S,\Sigma )$ as a measurable space. In the context of probability, the measurable space is $(\Omega ,{\mathcal {F}})$.
• When the property 3 is weakened to the closure under finite unions, that is, "For every finite sequence $A_{1},A_{2},\dotsc ,A_{n}$, if the sets $A_{1},A_{2},\dotsc ,A_{n}\in \Sigma$, then $\bigcup _{i=1}^{n}A_{i}\in \Sigma$.", then we call $\Sigma$ as an algebra over the set $S$. As we will see, the property 3 above implies this weakened property. Thus, a $\sigma$-algebra on the set $S$ is necessarily an algebra over the set $S$ (but not vice versa).
• In terms of probabilities, an intuitive meaning of each of the above three properties is

• property 1: we should be able assign the probability to the entire sample space (this comes from the probability axiom actually);
• property 2: if we are able to assign probability to an event ("chance" of the occurrence of the event), then we should also be able to assign a probability to its complement ("chance" of the non-occurrence of the event);
• property 3: if we are able to assign probabilities to the events $E_{1},E_{2},\dotsc$, then we should be able to assign a probability to their union ("chance" of the occurrence of one of the events).

• Actually, from these three properties, we can deduce some similar results for finitely many events and intersections.

Proposition. (Further properties of $\sigma$-algebra) Let $\Sigma$ be a $\sigma$-algebra of a set $S$. Then, we have

1. $\varnothing \in \Sigma$.
2. For every set $A_{1},A_{2},\dotsc ,A_{n}$, if the sets $A_{1},A_{2},\dotsc ,A_{n}\in \Sigma$, then $\bigcup _{i=1}^{n}A_{i}\in \Sigma$. (closure under finite unions)
3. For every infinite sequence of sets $A_{1},A_{2},\dotsc$, if the sets $A_{1},A_{2},\dotsc \in \Sigma$, then $\bigcap _{i=1}^{\infty }A_{i}\in \Sigma$. (closure under countable intersections)
4. For every set $A_{1},A_{2},\dotsc ,A_{n}$, if the sets $A_{1},A_{2},\dotsc ,A_{n}\in \Sigma$, then $\bigcap _{i=1}^{n}A_{i}\in \Sigma$. (closure under finite intersections)

Proof.

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

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

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

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

$\Box$

Remark.

• From these properties, it follows that (finite/countably infinite) (unions/intersections) of (complements of) (sets in $\sigma$-algebra) is also in $\sigma$-algebra. So, even after many operations on sets in $\sigma$-algebra, the resulting set is also in $\sigma$-algebra.

Exercise. Prove the property 4 in the proposition above.

Proof

Proof. By the closure under countable intersections (property 3 in proposition above), we have for every infinite sequence of sets $A_{1},A_{2},\dotsc$, if the sets $A_{1},A_{2},\dotsc \in \Sigma$, then $\bigcap _{i=1}^{\infty }A_{i}\in \Sigma$. So, in particular, we can choose the sequence to be $A_{1},A_{2},\dotsc ,A_{n},\varnothing ,\varnothing ,\dotsc$ ($\varnothing \in \Sigma$) where $A_{1},A_{2},\dotsc ,A_{n}$ is an arbitrary sequence such that $A_{1},A_{2},\dotsc ,A_{n}\in \Sigma$. Then, $$\bigcap _{i=1}^{n}A_{i}=\bigcap _{i=1}^{\infty }A_{i}\in \Sigma .$$ Thus, we have the desired result.

$\Box$

Example. (Smallest and largest $\sigma$-algebra) Let $\Omega$ be a sample space.

(a) Prove that the event space ${\mathcal {F}}=\{\varnothing ,\Omega \}$ (called trivial $\sigma$-algebra) is a $\sigma$-algebra on $\Omega$. This is the smallest $\sigma$-algebra on $\Omega$. (To be more precise, ${\mathcal {F}}\subseteq \Sigma$ for every $\sigma$-algebra $\Sigma$ on $\Omega$.)

(b) Prove that the event space ${\mathcal {F}}={\mathcal {P}}(\Omega )$ is a $\sigma$-algebra on $\Omega$. This is the largest $\sigma$-algebra on $\Omega$. (To be more precise, ${\mathcal {F}}\supseteq \Sigma$ for every $\sigma$-algebra $\Sigma$ on $\Omega$.)

Solution.

(a)

Proof. To prove that ${\mathcal {F}}$ is a $\sigma$-algebra, we need to show that ${\mathcal {F}}$ satisfies the three defining properties.

Property 1: Since $\Omega \in {\mathcal {F}}$, the property 1 is satisfied.

Property 2 (closure under complementation): Since ${\mathcal {F}}$ contains only $\varnothing$ and $\Omega$, it suffices to show that the complement of each of them also belongs to ${\mathcal {F}}$: $\varnothing ^{c}=\Omega \in {\mathcal {F}}$ and $\Omega ^{c}=\varnothing \in {\mathcal {F}}$. So, the property 2 is satisfied.

Property 3 (closure under countable unions): Since ${\mathcal {F}}$ contains only $\varnothing$ and $\Omega$, the union of countably infinitely many events ("$A_{1},A_{2},\dotsc$") in ${\mathcal {F}}$ (each of them is either $\varnothing$ or $\Omega$) is either $\varnothing$ or $\Omega$. In either case, the union belongs to ${\mathcal {F}}$. Thus, the property 3 is satisfied.

$\Box$

(b)

Proof.

Property 1: Since $\Omega \subseteq \Omega$, it follows that $\Omega \in {\mathcal {P}}(\Omega )$. Thus, the property is satisfied.

Property 2: Assume that $A\in {\mathcal {F}}={\mathcal {P}}(\Omega )$. Then, $A\subseteq \Omega$. By the definition of complement, we have $A^{c}=\Omega \setminus A\subseteq \Omega$. Hence, $A^{c}\in {\mathcal {F}}$, and thus the property is satisfied.

Property 3: For every infinite sequence of sets $A_{1},A_{2},\dotsc \in \Sigma$, we have $A_{1},A_{2},\dotsc \subseteq \Omega$. It follows by the property of union that $\bigcup _{i=1}^{\infty }A_{i}\subseteq \Omega$, and hence $\bigcup _{i=1}^{\infty }A_{i}\in {\mathcal {F}}$. Thus, the property is satisfied.

$\Box$

Exercise.

1 Let the sample space be $\Omega =\{1,2,3,4,5,6\}$. Which of the following is/are $\sigma$-algebra of $\Omega$?

	$\Omega$
	$\{\Omega \}$
	$\{\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}\}$
	$\{\varnothing ,\{1,2\},\{3,4,5,6\},\Omega \}$
	$\{\{1,2,3\},\{4,5,6\},\Omega \}$

2 Let the sample space be $\Omega =\mathbb {R}$. Which of the following is/are $\sigma$-algebra of $\Omega$?

	$\{\varnothing ,(-\infty ,0],(0,\infty ),\mathbb {R} \}$
	$\{\varnothing ,(-\infty ,0),\{0\},(0,\infty ),\mathbb {R} \}$
	$\{\varnothing ,\mathbb {Q} ,\mathbb {I} ,\mathbb {R} \}$ (where $\mathbb {Q}$ and $\mathbb {I}$ are sets of all rational numbers and irrational numbers respectively)
	${\mathcal {P}}(\mathbb {R} )$

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 other than $\varnothing$ and $\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 nonmeasurable)).

Fortunately, when the sample space $\Omega$ is countable, every set in ${\mathcal {P}}(\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 $\Omega$ is uncountable, even if the power set ${\mathcal {P}}(\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 nonnegativity.)
2. The limiting relative frequency of the whole sample space $\Omega$ ($\Omega$ is also an event) must be 1 (since by definition $\Omega$ contains all sample points, this event must occur in every repetition). (We call this property as unitarity.)
3. If the events $E_{1},E_{2},\dotsc$ are pairwise disjoint (i.e., $E_{i}\cap E_{j}=\varnothing$ for every $i,j$ with $i\neq j$), then the limiting relative frequency of the event $\bigcup _{i=1}^{\infty }E_{i}{\overset {\text{ def }}{=}}E_{1}\cup E_{2}\cup \dotsb$ (union of subsets of $\Omega$ is a subset of $\Omega$, so it can be called an event) is

$${\begin{aligned}\lim _{n\to \infty }{\frac {n(\bigcup _{i=1}^{\infty }E_{i})}{n}}&=\lim _{n\to \infty }{\frac {n(\bigcup _{i=1}^{\infty }E_{i})}{n}}\\&=\lim _{n\to \infty }{\frac {n(E_{1})+n(E_{2})+\dotsb }{n}}&({\text{the events are pairwise disjoint}})\\&=\lim _{n\to \infty }{\frac {n(E_{1})}{n}}+\lim _{n\to \infty }{\frac {n(E_{2})}{n}}+\dotsb &({\text{every limit exists by the axiom in frequentism}})\\&=\sum _{i=1}^{\infty }\lim _{n\to \infty }{\frac {n(E_{i})}{n}},\end{aligned}}$$

which is the sum of the limiting relative frequency of each of the events $E_{1},E_{2},\dotsc$. (We call this property as countable additivity.)

It is thus very natural to set the probability axioms to be the three properties mentioned above:

Definition. (Probability measure)

An illustration of probability measure.

Let $\Omega$ be the sample space of a random experiment, and ${\mathcal {F}}$ be an associated event space (which is a $\sigma$-algebra on $\Omega$). A probability measure is a function $\mathbb {P} :{\mathcal {F}}\to [0,1]$, with the following probability axioms satisified:

(P1) for every event $E\in {\mathcal {F}}$, the probability of the event $E$, $\mathbb {P} (E)\geq 0$; (nonnegativity)

(P2) $\mathbb {P} (\Omega )=1$; (unitarity)

(P3) for every infinite sequence of pairwise disjoint events $E_{1},E_{2},\dotsc$ (each of which is an element of ${\mathcal {F}}$), $\mathbb {P} \left(\bigcup _{i=1}^{\infty }E_{i}\right)=\sum _{i=1}^{\infty }\mathbb {P} (E_{i})$. (countable additivity)

Remark.

• For the axiom P3, we consider infinite sequences instead of finite sequences to add generality for infinite sample spaces. As we will see, we have result similar to the axiom P3 for finitely many pairwise disjoint events.
• When $\Omega$ is countable, we just set the associated event space to be ${\mathcal {F}}={\mathcal {P}}(\Omega )$.
• When $\Omega$ is uncountable, the event space is usually not set to be ${\mathcal {P}}(\Omega )$. Instead, it is common to set the event space to be the Borel $\sigma$-algebra on $\Omega$ (which is defined when $\Omega$ is a topological space). The details are omitted here, but the event space contains all "well-behaved" sets and most sets we can think of in the power set ${\mathcal {P}}(\Omega )$ anyway.
• The probability axiom P3 relates the events $E_{1},E_{2},\dotsc$ to their union $\bigcup _{i=1}^{\infty }E_{i}$. This matches with the closure under countable unions in the definition of $\sigma$-algebra.

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.

Theorem. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space and $A$ be a set in the event space ${\mathcal {F}}$. Then, $\mathbb {P} (\varnothing )=0$.

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

$\Box$

Using this result, we can obtain finite additivity from the countable additivity of probability:

Theorem. (Finite additivity) Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space. Then, for every event $E_{1},E_{2},\dotsc ,E_{n}\in {\mathcal {F}}$, if the events $E_{1},E_{2},\dotsc ,E_{n}$ are pairwise disjoint, then $$\mathbb {P} \left(\bigcup _{i=1}^{n}E_{i}\right)=\sum _{i=1}^{n}\mathbb {P} (E_{i}).$$

Proof. Consider the infinite sequence of events $E_{1},E_{2},\dotsc ,E_{n},\varnothing ,\varnothing ,\dotsc$ (recall that $\varnothing \in {\mathcal {F}}$ always). Then, $${\begin{aligned}\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)&=\mathbb {P} \left(\bigcup _{i=1}^{\infty }A_{i}\right)\\&=\sum _{i=1}^{\infty }\mathbb {P} (A_{i})&({\text{countable additivity}})\\&=\sum _{i=1}^{n}\mathbb {P} (A_{i})+\sum _{i=n+1}^{\infty }\mathbb {P} (\varnothing )\\&=\sum _{i=1}^{n}\mathbb {P} (A_{i}).\end{aligned}}$$ (The last equality follows since $\mathbb {P} (\varnothing )=0$, and it can be shown that $\sum _{i=n+1}^{\infty }\mathbb {P} (\varnothing )=0$ using some concepts in limit (to be mathematically rigorous).)

$\Box$

Finite additivity makes the proofs of some of the following results simpler.

Theorem. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $A$ and $B$ be sets in the event space ${\mathcal {F}}$. Then,

1. (complementary event) $\mathbb {P} (A^{c})=1-\mathbb {P} (A)$. (The complementary event is taken with respect to the universal set.)
2. (numeric bound) $0\leq \mathbb {P} (A)\leq 1$.
3. $\mathbb {P} (B)=\mathbb {P} (B\cap A)+\mathbb {P} (B\setminus A)$.
4. $\mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B)$.
5. (monotonicity) If $A\subseteq B$, then $\mathbb {P} (A)\leq \mathbb {P} (B)$.

Proof.

Property 1:

First, notice that by definition $\Omega =A\cup A^{c}$. Furthermore, since $A\in {\mathcal {F}}$, we have $A^{c}\in {\mathcal {F}}$ 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} (\Omega ){\overset {\text{ P2 }}{=}}1.$$ Thus, we have the desired result.

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

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

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

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

$\Box$

Remark.

• The numeric bound property ensures that the probability measure $\mathbb {P}$ is indeed a well-defined function (there is not a probability of event that is out of the codomain $[0,1]$).

Example. Let $C$ and $F$ the event of winning the champion in the competition, and entering the final of the competition respectively. Then, $C\subseteq F$ (when we win the champion, then we must enter the final), and so $\mathbb {P} (C)\leq \mathbb {P} (F)$ by monotonicity. That is, the probability of winning the champion in a competition is less than or equal to that of entering the final of the competition.

Example. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $A,B\in {\mathcal {F}}$. Show that if $\mathbb {P} (B)>0$, then $0\leq {\frac {\mathbb {P} (A\cap B)}{\mathbb {P} (B)}}\leq 1$.

Proof. Assume $\mathbb {P} (B)>0$. Then, we have ${\frac {\mathbb {P} (A\cap B)}{\mathbb {P} (B)}}\geq 0$ since $\mathbb {P} (A\cap B)\geq 0$ by the nonnegativity of probability. On the other hand, we have $A\cap B\subseteq B$. So, by monotonicity, $\mathbb {P} (A\cap B)\leq \mathbb {P} (B)$, and thus ${\frac {\mathbb {P} (A\cap B)}{\mathbb {P} (B)}}\leq {\frac {\mathbb {P} (B)}{\mathbb {P} (B)}}\leq 1$. Combining the inequalities we get yields the desired result.

$\Box$

Exercise. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $A,B\in {\mathcal {F}}$. Show that if $\mathbb {P} (B)>0$ and $A\subseteq B$, then ${\frac {\mathbb {P} (A\cap B)}{\mathbb {P} (B)}}=1$.

Proof

Proof. Assume $\mathbb {P} (B)>0$ and $A\subseteq B$. Then, $A\cap B=B$. Hence, $${\frac {\mathbb {P} (A\cap B)}{\mathbb {P} (B)}}={\frac {\mathbb {P} (B)}{\mathbb {P} (B)}}=1.$$

$\Box$

Exercise. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $A,B\in {\mathcal {F}}$. Show that $\mathbb {P} (A\cap B)\geq \mathbb {P} (A)+\mathbb {P} (B)-1$. (Hint: consider the property $\mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B)$.)

Proof

Proof. By the hint, we have $$\underbrace {\mathbb {P} (A\cup B)} _{\leq 1}=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B)\implies \mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B)\leq 1\implies \mathbb {P} (A\cap B)\geq \mathbb {P} (A)+\mathbb {P} (B)-1.$$

$\Box$

Example. Suppose you roll a loaded dice, and the corresponding probability space is $(\Omega ,{\mathcal {F}},\mathbb {P} )$. It is given that $\mathbb {P} (\{1\})=\mathbb {P} (\{3\})=\mathbb {P} (\{5\})$, and $\mathbb {P} (\{2\})=\mathbb {P} (\{4\})=\mathbb {P} (\{6\})$, and $\mathbb {P} (\{{\text{odd integer}}\})=2\mathbb {P} (\{{\text{even integer}}\})$. Calculate the probability of getting a 1 from the dice, i.e., $\mathbb {P} (\{1\})$.

Solution. First, notice that $\{{\text{odd integer}}\}=\{1,3,5\}$ and $\{{\text{even integer}}\}=\{2,4,6\}$. Furthermore, $\{1,3,5\}\cup \{2,4,6\}=\Omega$. Also, $\{1,3,5\}$ and $\{2,4,6\}$ are disjoint. Hence, $$\mathbb {P} (\{1,3,5\})+\mathbb {P} (\{2,4,6\})=1\implies \mathbb {P} (\{1,3,5\})+{\frac {1}{2}}\mathbb {P} (\{1,3,5\})=1\implies \mathbb {P} (\{1,3,5\})={\frac {2}{3}}.$$

Also, $\{1\},\{3\},\{5\}$ are disjoint, and hence $$\mathbb {P} (\{1,3,5\})=\mathbb {P} (\{1\})+\mathbb {P} (\{3\})+\mathbb {P} (\{5\})=3\mathbb {P} (\{1\})\implies \mathbb {P} (\{1\})={\frac {2}{9}}.$$

Exercise. Calculate the probability of getting a 2 from the dice.

Solution

From the example above, we have $\mathbb {P} (\{2,4,6\})={\frac {1}{2}}\mathbb {P} (\{1,3,5\})={\frac {1}{3}}$. Since $\{2\},\{4\},\{6\}$ are disjoint, it follows that $$\mathbb {P} (\{2,4,6\})=\mathbb {P} (\{2\})+\mathbb {P} (\{4\})+\mathbb {P} (\{6\})=3\mathbb {P} (\{2\})\implies \mathbb {P} (\{2\})={\frac {1}{9}}.$$

Remark.

• For simplicity, we may sometimes omit the curly braces $\{\}$ inside the probability measure. For example, we may write $\mathbb {P} ({\text{odd integer}})$ instead of $\mathbb {P} (\{{\text{odd integer}}\})$.

Example. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space. Suppose we have $\mathbb {P} (A)=0.6$ and $\mathbb {P} (B^{c})=0.55$ for events $A,B\in {\mathcal {F}}$. Can the events $A$ and $B$ be disjoint?

Solution. They cannot be disjoint. We may prove it by contradiction.

Proof. Assume to the contrary that $A$ and $B$ are disjoint. First, $\mathbb {P} (B)=1-\mathbb {P} (B^{c})=0.45$. Then, by the finite additivity of probability, we have $$\mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)=0.6+0.45=1.05>1,$$ causing a contradiction (violating the numeric bound property, and hence violating the probability axioms logically (by contrapositive)).

$\Box$

Exercise. What is the minimum probability of $\mathbb {P} (A\cap B)$ such that $\mathbb {P}$ can possibly be a valid probability measure? (Hint: it suffices to consider the bound on $\mathbb {P} (A\cap B)$ if $\mathbb {P}$ is a valid probability measure. The bound is a necessary condition (but may not be sufficient) for $\mathbb {P}$ to be a valid probability measure in logic terms.)

Solution

When $\mathbb {P}$ is a valid probability measure, we have $$\mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B)=1.05-\mathbb {P} (A\cap B).$$ Since $\mathbb {P}$ is a valid probability measure, it follows that $\mathbb {P} (A\cup B)\leq 1\implies \mathbb {P} (A\cap B)\geq 0.05$, meaning that the minimum probability is 0.05.

Exercise.

A graphical illustration of symmetric difference of two sets.

Define $A\triangle B$ be the symmetric difference of sets $A$ and $B$, that is, $(A\setminus B)\cup (B\setminus A)$.

Propose a formula for $\mathbb {P} (A\triangle B)$ in terms of $\mathbb {P} (A),\mathbb {P} (B),\mathbb {P} (A\cap B)$, and prove it. (Note: the occurrence of the event $A\triangle B$ corresponds to the occurrence of exactly one of the events $A$ and $B$.) (Hint: You may use without proof the fact that $(A\setminus B)\cap (B\setminus A)=\varnothing$. Also, you may use the property that $\mathbb {P} (A\setminus B)=\mathbb {P} (A)-\mathbb {P} (A\cap B)$.)

Solution

Proposition: $\mathbb {P} (A\triangle B)=\mathbb {P} (A)+\mathbb {P} (B)-2\mathbb {P} (A\cap B)$.

Proof. We have $$\mathbb {P} (A\triangle B)=\mathbb {P} (A\setminus B)+\mathbb {P} (B\setminus A)-\mathbb {P} ((A\setminus B)\cap (B\setminus A))=\mathbb {P} (A)-\mathbb {P} (A\cap B)+\mathbb {P} (B)-\mathbb {P} (B\cap A)-\mathbb {P} (\varnothing )=\mathbb {P} (A)+\mathbb {P} (B)-2\mathbb {P} (A\cap B).$$

$\Box$

Example. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $A,B,C\in {\mathcal {F}}$ be events such that $A\cup B\cup C=\Omega$. It is given that $$\mathbb {P} (A)=0.5,\quad \mathbb {P} (B)=0.5,\quad \mathbb {P} (C)=0.6,\quad \mathbb {P} (A\cap B)=0.2,\quad \mathbb {P} (B\cap C)=0.3,\quad \mathbb {P} (A\cap C)=0.2$$ Calculate

(a) $\mathbb {P} (A\cup B),\mathbb {P} (B\cup C),\mathbb {P} (A\cup C)$;

(b) $\mathbb {P} (A\cup B\cup C),\mathbb {P} (A\cap B\cap C)$ (without using inclusion-exclusion principle for three events directly).

Solution.

(a)

• $\mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B)=0.5+0.5-0.2=0.8$.
• $\mathbb {P} (B\cup C)=\mathbb {P} (B)+\mathbb {P} (C)-\mathbb {P} (B\cap C)=0.5+0.6-0.3=0.8$.
• $\mathbb {P} (A\cup C)=\mathbb {P} (A)+\mathbb {P} (C)-\mathbb {P} (A\cap C)=0.5+0.6-0.2=0.9$.

(b) First, $\mathbb {P} (A\cup B\cup C)=\mathbb {P} (\Omega )=1$. Then, we write $${\begin{aligned}\mathbb {P} (A\cup B\cup C)&=\mathbb {P} (A\cup (B\cup C))\\&=\mathbb {P} (A)+\mathbb {P} (B\cup C)-\mathbb {P} (A\cap (B\cup C))\\&=0.5+0.8-\mathbb {P} ((A\cap B)\cup (A\cap C))\\&=1.3-{\big (}\mathbb {P} (A\cap B)+\mathbb {P} (A\cap C)-\mathbb {P} (A\cap B\cap C){\big )}\\&=1.3-0.2-0.2+\mathbb {P} (A\cap B\cap C)\\&=0.9+\mathbb {P} (A\cap B\cap C).\\\end{aligned}}$$ It follows that $\mathbb {P} (A\cap B\cap C)=1-0.9=0.1$.

Note: to keep track of the probabilities of different events more easily, we may draw a Venn diagram:

|-------------| <--------- A
|             |
|        |----|----|
|  0.2   |    |    |
|        | 0.1| 0.2| <---- C
|        |    |    |
|--------|----|----|------|
|        |0.1 | 0.2|      | 
|   0.1  |    |    |  0.1 | <---- B
|        |----|----|      |
|-------------|-----------|

It also allows us to calculate the probabilities in a more systematic manner. (E.g., we know that $\mathbb {P} (A\cap B\cap C)=0.1$. Also, $\mathbb {P} (A\cap B)=0.2$. So, the "remaining piece" in $A\cap B$ has 0.1 probability (i.e., $\mathbb {P} ((A\cap B)\setminus C)=0.2-0.1=0.1$.)

Exercise. Calculate

(a) $\mathbb {P} (A\setminus B),\mathbb {P} (B\setminus A),\mathbb {P} (A\setminus C),\mathbb {P} (C\setminus A),\mathbb {P} (B\setminus C),\mathbb {P} (C\setminus B)$;

(b) $\mathbb {P} (A\setminus (B\cap C)),\mathbb {P} (A\setminus (B\cup C)),\mathbb {P} ((B\cap C)\setminus A),\mathbb {P} ((B\cup C)\setminus A)$.

Solution

(a)

• $\mathbb {P} (A\setminus B)=\mathbb {P} (A)-\mathbb {P} (A\cap B)=0.5-0.2=0.3$.
• $\mathbb {P} (B\setminus A)=\mathbb {P} (B)-\mathbb {P} (A\cap B)=0.5-0.2=0.3$.
• $\mathbb {P} (A\setminus C)=\mathbb {P} (A)-\mathbb {P} (A\cap C)=0.5-0.2=0.3$.
• $\mathbb {P} (C\setminus A)=\mathbb {P} (C)-\mathbb {P} (A\cap C)=0.6-0.2=0.4$.
• $\mathbb {P} (B\setminus C)=\mathbb {P} (B)-\mathbb {P} (B\cap C)=0.5-0.3=0.2$.
• $\mathbb {P} (C\setminus B)=\mathbb {P} (C)-\mathbb {P} (B\cap C)=0.6-0.3=0.3$.

(b)

• $\mathbb {P} (A\setminus (B\cap C))=\mathbb {P} (A)-\mathbb {P} (A\cap B\cap C)=0.5-0.1=0.4$.
• We have $\mathbb {P} (A\cap (B\cup C))=\mathbb {P} (A)+\mathbb {P} (B\cup C)-\mathbb {P} (A\cup B\cup C)=0.5+0.8-1=0.3$. Thus, $\mathbb {P} (A\setminus (B\cup C))=\mathbb {P} (A)-\mathbb {P} (A\cap (B\cup C))=0.5-0.3=0.2$.
• $\mathbb {P} ((B\cap C)\setminus A)=\mathbb {P} (B\cap C)-\mathbb {P} (B\cap C\cap A)=0.3-0.1=0.2$.
• $\mathbb {P} ((B\cup C)\setminus A)=\mathbb {P} (B\cup C)-\mathbb {P} ((B\cup C)\cap A)=0.8-0.3=0.5$.

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:

Example. (Coin tossing) Consider a random experiment where we toss a coin (fair or unfair). Suppose we want to define a probability space for this random experiment. Three elements are needed: sample space, event space, and probability measure.

Here, we define the sample space as $\Omega =\{H,T\}$ ($H$ and $T$ stands for "heads comes up" and "tails comes up" respectively). Since $\Omega$ is finite, the event space is chosen to be its power set, that is, ${\mathcal {F}}=\{\varnothing ,\{H\},\{T\},\{H,T\}\}$. It then remains to construct the probability measure $\mathbb {P}$, subject to the probability axioms. Since the domain of the probability measure is ${\mathcal {F}}$, we need to define the "output" of $\mathbb {P}$ (that is, assigning probability) for every event in ${\mathcal {F}}$.

For the empty set, by a property of probability, the probability assigned to it has to be zero. Similarly, for the set $\{H,T\}$, the probability assigned to it has to be one by the probability axiom P2. But for the remaining two sets $\{H\},\{T\}$, there are no properties/axioms of probability that tell us what probability must we assign to each of them. Despite this, the sum of the two probabilities assigned has to be one, by the finite additivity property: $$\mathbb {P} (\{H\})+\mathbb {P} (\{T\})=\mathbb {P} (\{H,T\}){\overset {\text{ P2 }}{=}}1.$$ Also, by the numeric bound of probability, the two probabilities assigned has to be between zero and one.

So, without further information, we can set $\mathbb {P} (\{H\})=x$ where $x\in [0,1]$ (and thus $\mathbb {P} (\{T\})=1-x$). Hence, we can see that there are infinitely many ways to construct a probability measure for this random experiment!

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 exactly one way to construct a probability measure. Consider the coin tossing example again:

Example. (Coin tossing, continued) Suppose we are told that the coin is fair, so based on this message, we assign the probability of "head comes up" and "tail comes up" to be ${\frac {1}{2}}$ respectively. In this case, the way of constructing the probability measure is fixed: $$\mathbb {P} (\varnothing )=0,\quad \mathbb {P} (\{H\})={\frac {1}{2}},\quad \mathbb {P} (\{T\})={\frac {1}{2}},\quad \mathbb {P} (\{H,T\})=1.$$ This is the only way to construct a probability measure (satisfying the probability axioms) with this further information.

In general, it is not necessary to assign probability to every 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.

Example. (Rolling dice) Consider a random experiment where we roll a dice (loaded or unloaded). Then, we define the sample space as $\Omega =\{1,2,3,4,5,6\}$ where each number represents the number coming up. It follows that the event space is ${\mathcal {F}}={\mathcal {P}}(\Omega )$ since $\Omega$ is finite. (Since there are $2^{6}=64$ sets in the event space, we will not list out them.) Now, we proceed to construct a probability measure $\mathbb {P}$ (satisfying the probability axioms). Similarly, we need to consider all 64 events in the event space ${\mathcal {F}}$.

First, for the empty set and the sample space, we have $\mathbb {P} (\varnothing )=0$ and $\mathbb {P} (\Omega )=1$. Now, let us consider the singletons (i.e., sets consisting one element) in the event space: $\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}$. Similarly, without further information, there are infinitely many possible ways to assign probability to each of them, subject to the constraint that their sum has to be one by the probability axiom P2. For now, let us denote $$\mathbb {P} (\{1\})=p_{1},\quad \mathbb {P} (\{2\})=p_{2},\quad \mathbb {P} (\{3\})=p_{3},\quad \mathbb {P} (\{4\})=p_{4},\quad \mathbb {P} (\{5\})=p_{5},\quad \mathbb {P} (\{6\})=p_{6}.$$

If we think more carefully, then we will find out that once these six probabilities are fixed, the probabilities for all other $64-2-6=56$ events are fixed, based on the property of finite additivity (which must be satisfied when the probability measure satisfies the probability axioms), since all other 56 events are just finite unions of some of these six events, and thus their probabilities can be obtained by adding up some of the above probabilities.

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:

Theorem. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, where the sample space $\Omega$ is countable. Assume that the probability of each of the singleton events (i.e., $\mathbb {P} (\{\omega \})$ for every $\omega \in \Omega$) is given such that they are nonnegative and their sum is one (to satisfy the probability axioms). Then, the probability measure $\mathbb {P} :{\mathcal {F}}\to [0,1]$ is given by $$\mathbb {P} (E)=\sum _{\omega \in E}^{}\mathbb {P} (\{\omega \})$$ for every event $E\in {\mathcal {F}}$.

Proof.

Case 1: $\Omega$ is finite. Then, we can write $\Omega =\{\omega _{1},\omega _{2},\dotsc ,\omega _{n}\}$. It follows that every event $E\in {\mathcal {F}}$ 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 {\mathcal {F}}$, $$\mathbb {P} (E)=\sum _{i}^{}\mathbb {P} (\{\omega _{i}\})=\sum _{\omega \in E}^{}\mathbb {P} (\{\omega \}).$$

Case 2: $\Omega$ is countably infinite. Then, we can write $\Omega =\{\omega _{1},\omega _{2},\dotsc \}$. It follows that every event $E\in {\mathcal {F}}$ 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 {\mathcal {F}}$, $$\mathbb {P} (E)=\sum _{i}^{}\mathbb {P} (\{\omega _{i}\})=\sum _{\omega \in E}^{}\mathbb {P} (\{\omega \}).$$

$\Box$

Example. Consider a random experiment where we draw an integer from all positive integers. Then, the probability space is $(\Omega ,{\mathcal {F}},\mathbb {P} )$ where $\Omega =\mathbb {N} ,{\mathcal {F}}={\mathcal {P}}(\mathbb {N} )$. Suppose it is given that $$\mathbb {P} (\{n\})=2^{-n}$$ for every $n\in \mathbb {N}$. Since the probabilities are nonnegative, and also their sum is $$2^{-1}+2^{-2}+\dotsb ={\frac {1/2}{1-1/2}}=1,$$ it follows that the probability measure is given by $$\mathbb {P} (E)=\sum _{n\in E}^{}\mathbb {P} (\{n\})$$ for every event $E\in {\mathcal {F}}$.

Exercise. Calculate the probability $\mathbb {P} (\{{\text{odd integer}}\})$.

Solution

We have by above formula $$\mathbb {P} (\{{\text{odd integer}}\})=\mathbb {P} (\{1\})+\mathbb {P} (\{3\})+\dotsb =2^{-1}+2^{-3}+\dotsb ={\frac {2^{-1}}{1-2^{-2}}}={\frac {1/2}{3/4}}={\frac {2}{3}}.$$

The following is an important special case for the above theorem.

Corollary. (Formula for combinatorial probability) Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, where the sample space is finite. Assume that the probability of each of the singleton events ($|\Omega |$ of them) is the same: ${\frac {1}{|\Omega |}}$. (we say that all outcomes are equally likely in this case). Then, the probability measure $\mathbb {P} :{\mathcal {F}}\to [0,1]$, called combinatorial probability (or classical probability) is given by $$\mathbb {P} (E)={\frac {|E|}{|\Omega |}}={\frac {{\text{number of sample points in }}E}{{\text{number of sample points in }}\Omega }}.$$ for every event $E\in {\mathcal {F}}$.

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

$\Box$

Remark.

• By principle of indifference, unless there exists evidence showing that all outcomes are not equally likely, e.g. it is given that a coin is biased, such that it is more likely that head comes up, we should assume that the outcomes are equally likely.

Example. Suppose we roll a fair red dice and a fair blue dice. Then, we can define the sample space be $\Omega =\{(a,b):a,b=1,2,\dotsc ,{\text{ or }}6\}$, where $(a,b)$ means $a$ comes up for red dice, and $b$ comes up for blue dice.

Calculate the probability $\mathbb {P} (\{(1,1)\})$.

Solution. The number of sample points is $\underbrace {6} _{\text{red}}\times \underbrace {6} _{\text{blue}}=36$. Since the outcomes should be equally likely, the desired probability is ${\frac {1}{36}}$ (there is only one sample point for this event).

Exercise. Suppose the blue dice is colored red, such that the two dice become indistinguishable.

Then, student A claims that the probability $\mathbb {P} (\{(1,1)\})={\frac {1}{21}}$, and he reasons as follows:

Recall that when the two dices become indistinguishable, the number of possible distinct pairs of numbers facing up becomes $_{6}H_{2}=21$ (shown in previous chapter about combinatorics). So, there are only 21 sample points in the sample space, and hence the probability is ${\frac {1}{21}}$.

On the other hand, student B claims that the probability should still be ${\frac {1}{36}}$ and he reasons as follows:

Notice that in this case, the number 1 comes up for both dice correspond to exactly one outcome in the distinguishable case: $(1,1)$. Also, changing the color of the dice should not affect the randomness of the experiment. So, the probability in this case should be the same as the probability $\mathbb {P} (\{(1,1)\})={\frac {1}{36}}$.

Which of the students is correct? Also, explain why the other student is wrong.

Solution

Student B is correct. Student A is wrong, since in this case, not all outcomes in the experiment are equally likely. Particularly, some of the sample points in this case actually correspond to two original sample points, e.g. "1 comes up for one dice, 2 comes up for another" corresponds to $(1,2)$ and $(2,1)$.

Example. Consider a random experiment where a fair coin is tossed twice. Calculate the probability of getting heads in a row.

Solution. There are $2\times 2=4$ outcomes in this experiment. They should be equally likely, and hence the probability of getting two heads is ${\frac {1}{4}}$.

Exercise. Suppose we toss a fair coin five times.

(a) Calculate the probability $\mathbb {P} (\{HHHHH\})$ ($HHHHH$ means 5 heads in a row).

(b) Calculate the probability $\mathbb {P} (\{HHHHT\})$ ($HHHHT$ means 4 heads in a row, then 1 tails).

(c) Calculate the probability $\mathbb {P} (\{{\text{4 heads and 1 tails}}\})$. (Answer: ${\frac {5}{32}}$)

(d) Calculate the probability $\mathbb {P} (\{{\text{3 heads and 2 tails}}\})$. (Answer: ${\frac {10}{32}}$)

Solution

There should be $2^{5}=32$ equally likely outcomes.

(a) The probability is ${\frac {1}{32}}$. (The event contains one sample point only.)

(b) The probability is ${\frac {1}{32}}$. (The event contains one sample point only.)

(c) The event $\{{\text{4 heads and 1 tails}}\}=\{HHHHT,HHHTH,HHTHH,HTHHH,THHHH\}$, containing five sample points. Thus, the probability is ${\frac {5}{32}}$.

(d) We can count the number of sample points in the event by regarding the five outcomes from tossing five times as five distinguishable cells, and 2 tails as 2 indistinguishable balls. Then, we place 2 indistinguishable balls into 5 distinguishable cells (the remaining empty cells are for heads). So, the number is ${\binom {5}{2}}=10$. Hence, the probability is ${\frac {10}{32}}$.

Example. (Capture-mark-recapture) Suppose we are fishing in a lake, containing $N$ distinct fishes. First, we catch $k$ fishes from the lake (capture), and give them each a marker (mark), and after that place them back into the lake.

Then, we catch fishes from the lake again (recapture), and catch $n$ fishes this time. Show that the probability that there is $r$ marked fishes in the $n$ fishes caught is $${\frac {{\binom {k}{r}}\times {\binom {N-k}{n-r}}}{\binom {N}{n}}},$$ assuming that the outcomes in the sample space are equally likely.

Proof. We regard the $N$ fishes as $N$ distinguishable cells, and $n$ catches (in the second time) as $n$ indistinguishable balls (the order of the catch is not important, we are considering what $n$ fishes are caught only). Then, there are ${\binom {N}{n}}$ equally likely sample points in the sample space.

It now remains to consider the number of sample points in the event. We now count the number of ways to have $r$ marked fishes in the $n$ fishes. We regard the $k$ marked distinct fishes as $k$ distinguishable cells, and $N-k$ non-marked fishes as $N-k$ distinguishable cells. (These two groups of cells are put separately.)

• Step 1: placing $r$ indistinguishable balls (catches) into $k$ distinguishable cells. (${\binom {k}{r}}$ ways)
• Step 2: placing $n-r$ indistinguishable balls (catches) into $N-k$ distinguishable cells. (${\binom {N-k}{n-r}}$ ways)

Hence, the number of sample points in the event is ${\binom {k}{r}}\times {\binom {N-k}{n-r}}$. The result follows.

$\Box$

Example. There are 9 distinguishable balls in a box, consisting of 3 red balls, 2 blue balls and 4 green balls.

(a) Calculate the probability that a red ball is drawn from the box if 1 ball is drawn from the box.

(b) Calculate the probability that exactly 2 red balls and exactly 3 green balls are drawn from the box if 6 balls are drawn from the box.

Solution.

(a) Since one ball is drawn from the box, there are 9 outcomes in the sample space, corresponding to the 9 different draws. We shall assume that the outcomes are equally likely. Then, the probability that a red ball is drawn is ${\frac {3}{9}}={\frac {1}{3}}$ since there are 3 different draws (3 sample points) in the event.

(b) Although the question does not state whether the drawing of ball is unordered or ordered, the probability obtained with either assumption is actually the same, when the 9 balls are distinguishable. This is because every unordered draw of 6 balls corresponds to $6!$ ordered draw of 6 balls. So if the ordered draws are equally likely, then the unordered draws must also be equally likely, vice versa. Here, let us regard the draws as unordered for simplicity.

Then, the number of sample points in the sample space is ${\binom {9}{6}}=84$. (9 balls: 9 distinguishable cells with capacity 1; 6 draws: 6 indistinguishable "balls"). For the event, there are $$\underbrace {\binom {3}{2}} _{\text{red}}\times \underbrace {\binom {4}{3}} _{\text{green}}\times \underbrace {2} _{\text{blue}}=24$$ sample points. It follows that the probability is ${\frac {24}{84}}={\frac {2}{7}}$.

Exercise. Three (distinguishable) orange balls are added to the box. Calculate the probability that 2 red balls and 3 green balls are drawn from the box if 6 balls are drawn from the box again. (Answer: ${\frac {5}{77}}$)

Solution

With 3 additional orange balls, the number of sample points in the sample space becomes ${\binom {12}{6}}=924$. The number of sample points in the event becomes $$\underbrace {\binom {3}{2}} _{\text{red}}\times \underbrace {\binom {4}{3}} _{\text{green}}\times \underbrace {5} _{\text{blue/orange}}=60$$ sample points. Thus, the probability is ${\frac {60}{924}}={\frac {5}{77}}$.

Example. Suppose there are 20 couples in a room, and we pick two people randomly from the room (such that all outcomes in the sample space are equally likely). Calculate the probability that the two people picked are a couple.

Solution.

We regard the two picks to be indistinguishable (or unordered). Then, there are ${\binom {20}{2}}=190$ equally likely sample points in the sample space (place 2 indistinguishable picks into 20 people with capacity 1). Also, the event that the two people picked are a couple has 20 sample points since there are 20 couples.

It follows that the probability is ${\frac {20}{190}}={\frac {2}{19}}$.

Exercise. Regard the two picks as ordered and calculate the probability again (which should also be ${\frac {2}{19}}$).

Solution

In this case, there are $20\times 19=380$ equally likely sample points in the sample space. Also, the event has $20\times 2=40$ sample points (20 couples, two possible orderings for each couple). Hence, the probability is ${\frac {40}{380}}={\frac {2}{19}}$.

Example. Amy and Bob are playing a game where each of them roll the same fair dice once, and the player who gets a greater number from the roll wins. If both players get the same number from the roll, then they draw.

(a) Calculate the probability that Amy and Bob draw.

(b) Hence or otherwise, calculate the probability that Amy wins.

Solution.

(a) There are $\underbrace {6} _{\text{Amy's roll}}\times \underbrace {6} _{\text{Bob's roll}}=36$ outcomes in total. There are 6 outcomes where Amy and Bob draw (both get 1,2,3,4,5, or 6). It follows that the probability is ${\frac {6}{36}}={\frac {1}{6}}$.

(b) To calculate the probability, clearly one can count the number of outcomes where Amy wins. But here we offer an alternative and more convenient approach, which makes use the symmetry of the game. Notice that the situation for Amy and Bob is basically the same in the game (for each of them, there is another player doing the same thing as him/her, and the winning conditions are the same). So, the game is kind of symmetric. Thus, by the natural symmetry of the game, the probability that Amy wins and the probability that Bob wins are equal.

But we can notice that the events that Amy wins, Bob wins, and they draw are disjoint. Also, their union is the whole sample space. It follows that the sum of their probabilities is 1. Hence, letting $p$ be the probability that Amy wins, we have $$p+p+{\frac {1}{6}}=1\implies p={\frac {5}{12}}.$$

Exercise. Consider a modified version of the above game, where if both players get the same number from the roll, then each of them roll the same fair dice once more. (We can see that the game must end after a finite number of dice rolling. It is impossible to keep having draw infinitely.)

Calculate the probability that Amy wins (eventually).

Solution

In this case, the probability of ending up with a draw is 0, since the game mechanism does not allow a draw. By the symmetry of the game, the desired probability is thus ${\frac {1}{2}}$.

Example. Consider a simple game for children. Initially, a child is given a paper with 4 dots on it, with a rectangular shape:

*     *
1     2


3     4
*     *

Then, the child is allowed to draw (exactly) 3 different line segments between two dots on the paper. The aim for the child is to draw a triangle, formed by the 3 line segments, where each vertex of the triangle has to be a dot on the paper. For instance, in this case:

 *    *       
  \  /
   \/
   /\
  /  \
 *----*         

the lower triangle is not counted as a valid one, since one of its vertices is not a dot on the paper (instead, it is made by intersection of two line segments).

Suppose we draw the 3 different line segments randomly. Calculate the probability that there is a (valid) triangle in the resulting diagram.

Solution.

Let us regard the 3 draws of line segment as unordered. Notice that there are ${\binom {4}{2}}=6$ places to draw a line segment. (To draw a line segment, we choose two dots from the four dots (without considering the order).) Then, there are ${\binom {6}{3}}=20$ ways to draw 3 different line segments (which should be equally likely).

Among the 20 ways, there are ${\binom {4}{3}}=4$ ways where a valid triangle is formed. (joining 123, 124, 134, or 234. We choose 3 dots from the 4 dots to form a triangle (without considering order), and there are four ways.) Hence, the probability is ${\frac {4}{20}}={\frac {1}{5}}$.

Exercise. Suppose there are 5 dots on the paper, forming a shape like a regular pentagon.

        * 1    
               
  5 *        * 2
               
      *    *     
     4      3  

Suppose we draw 3 different line segments randomly. Calculate the probability that there is a (valid) triangle in the resulting diagram. (Answer: ${\frac {1}{12}}$)

Solution

Similarly, we regard the 3 draws as unordered. In this case, there are ${\binom {5}{2}}=10$ places to draw a line segment. Thus, there are ${\binom {10}{3}}=120$ ways to draw 3 different line segments.

Among the 120 ways, there are ${\binom {5}{3}}=10$ ways where a valid triangle is formed. Hence, the probability is ${\frac {10}{120}}={\frac {1}{12}}$.

Example. Suppose we are drawing 5 cards from a poker deck consisting of 52 cards.

(a) Calculate the probability for getting a flush, that is, all 5 cards drawn are of the same suit, and not all are of sequential rank. (Note: sequential rank means A2345,23456,..., or 10JQKA. JQKA2, etc. are not counted as sequential rank.)

(b) Calculate the probability that all 5 cards drawn are of the same color.

(c) Calculate the probability for getting a four of a kind, that is, 4 cards are of the same kind among the 5 cards drawn.

Solution. We regard the 5 draws to be unordered, so there are in total ${\binom {52}{5}}=2598960$ outcomes, which should be equally likely.

(a) To form a flush, we first consider the 2-step process:

1. Choose a suit from the 4 suits. (4 ways)
2. Placing the 5 indistinguishable draws into the 13 cards with the suit chosen in step 1. (${\binom {13}{5}}=1287$ ways)

But among these ways, for each of the 4 ways in step 1, there are 10 ways in step 2 that are of sequential rank. So, we need to subtract $4\times 10=40$ from the above ways. Hence, the probability is ${\frac {4\times 1287-40}{2598960}}\approx 0.00197$.

(b) For the 5 cards to be of the same color, we consider this as a 2-step process:

1. Choose a color from the 2 colors. (2 ways)
2. Placing the 5 indistinguishable draws into the 26 cards with the color chosen in step 1. (${\binom {26}{5}}=65780$ ways)

Hence, the probability is ${\frac {2\times 65780}{2598960}}\approx 0.0506$.

(c) To form a four of a kind, we consider this as a 2-step process:

1. Choose a kind from 13 kinds for the four cards with the same kind (13 ways)
2. Choose a card from the remaining 48 cards in the deck (48 ways)

Then, the probability is ${\frac {13\times 48}{2598960}}\approx 0.00024$.

Exercise.

(a) Calculate the probability for getting a straight, that is, the 5 cards drawn consists of five cards of sequential rank, and not all are of the same suit. (Note: A2345, 23456, ..., 10JQKA are counted as straight, but e.g., JQKA2 is not counted as straight. This also applies to straight flush below.) (Answer: approximately 0.00392)

(b) Calculate the probability for getting a straight flush, that is, the 5 cards drawn consists of five cards of sequential rank, and all are of the same suit. (Answer: approximately 0.0000154)

(c) Calculate the probability for getting a full house, that is, the 5 cards drawn contains 3 cards of a rank, and 2 cards of another rank. (Answer: approximately 0.00144)

Solution

(a) To form a straight, we first consider the following 6-step process:

1. Choose a sequential rank from 10 possible sequential ranks (A2345,23456, ..., 10JQKA) for the straight. (10 ways)
2. Choose a suit from the 4 suits for the first card in the sequence. (4 ways)
3. Choose a suit from the 4 suits for the second card in the sequence. (4 ways)
4. Choose a suit from the 4 suits for the third card in the sequence. (4 ways)
5. Choose a suit from the 4 suits for the fourth card in the sequence. (4 ways)
6. Choose a suit from the 4 suits for the fifth card in the sequence. (4 ways)

But in these steps, it is possible that all cards drawn are also of the same suit. So, we need to exclude those cases, and there are $10\times 4=40$ of them, since for each of the 10 ways in step 1, we may choose the same suit from 4 suits throughout the steps 2-6 (4 ways). Hence, the probability is $${\frac {10\times 4^{5}-40}{2598960}}\approx 0.00392.$$ (b) To form a straight flush, the number of ways is the same as the number of cases excluded in (a) (i.e., 40). So, the probability is $${\frac {40}{2598960}}\approx 0.0000154.$$ (c) To form a full house, we consider this as a 4-step process:

1. Choose a rank from the 13 ranks for the 3 cards with the same rank. (13 ways)
2. Place 3 indistinguishable draws into the 4 cards with that rank, for the rank chosen in step 1. (${\binom {4}{3}}=4$ ways)
3. Choose a rank from the remaining 12 ranks for the 2 cards with the same rank. (12 ways)
4. Place 2 indistinguishable draws into the 4 cards with that rank, for the rank chosen in step 1. (${\binom {4}{2}}=6$ ways)

Thus, the probability is $${\frac {13\times 4\times 12\times 6}{2598960}}\approx 0.00144$$

Example. (Raffle) Suppose there are 10000 distinct raffle tickets for a raffle. After all 10000 raffle tickets are sold out, 3 different tickets from the 10000 raffle tickets will be chosen randomly as 3 winning tickets, and the holder of each of these 3 winning tickets will receive a prize (it is possible that one person receives multiple prizes, if the person owns multiple winning tickets).

(a) If Amy purchases 10 of the 10000 raffle tickets, then what is the probability for Amy to win at least one prize?

(b) If Amy purchases 100 of the 10000 raffle tickets, then what is the probability for Amy to win at least one prize?

(c) If Amy purchases 1000 of the 10000 raffle tickets, then what is the probability for Amy to win at least one prize?

(Hint: Consider complementary events.)

Solution.

All outcomes for the raffle should be equally likely. Let us regard the winning tickets choices as indistinguishable.

• The number of outcomes in total is ${\binom {10000}{3}}=166616670000$. (Placing 3 indistinguishable balls (winning ticket choices) into 10000 distinguishable cells (raffle tickets) with capacity one.)
• For Amy to not win any prize, we are placing 3 indistinguishable balls (winning ticket choices) into $10000-k$ distinguishable cells (raffle tickets that are not purchased by Amy) with capacity one, assuming Amy purchases $k$ tickets.

• This is the complementary event of "Amy wins at least one prize".

(a) The probability is $1-{\frac {\binom {10000-10}{3}}{\binom {10000}{3}}}=1-{\frac {166117269780}{166616670000}}\approx 0.002997$.

(b) The probability is $1-{\frac {\binom {10000-100}{3}}{\binom {10000}{3}}}=1-{\frac {161667498300}{166616670000}}\approx 0.0297$.

(c) The probability is $1-{\frac {\binom {10000-1000}{3}}{\binom {10000}{3}}}=1-{\frac {121459503000}{166616670000}}\approx 0.2710243$.

Exercise. Suppose a single raffle ticket may be chosen to be a winning ticket multiple times. That is, some of the 3 winning tickets chosen may be the same.

Calculate the probability for Amy to win at least one prize if Amy purchases 1000 of 10000 raffle tickets. (Answer: 0.271 exactly)

Solution

In this case, let us regard the winning tickets choices as distinguishable and ordered for convenience. Then, the number of outcomes in total is $10000^{3}$. (Placing 3 distinguishable balls (winning ticket choices) into 10000 distinguishable cells (raffle tickets) with unlimited capacity.) The number of sample points in the event for Amy not winning any prize is $9000^{3}$ (Placing 3 distinguishable balls (winning ticket choices) into 9000 distinguishable cells (raffle tickets not purchased by Amy) with unlimited capacity.) So, the probability is $$1-{\frac {9000^{3}}{10000^{3}}}=0.271.$$ (Notice that the answer is exactly 0.271 this time.)

Remark.

• The answer is expected to be quite close to the one in (c), since even a single raffle ticket may be chosen to be a winning ticket more than once, it is quite unlikely for that to happen. So, we will expect that the effect on the randomness should be quite small.

Example. Consider a game which involves repeated tossing of a fair coin. There are two players in the game: player A and B. The fair coin is tossed repeatedly until one of the player wins. Player A wins if the outcome pattern "THH" appears first, and player B wins if the outcome pattern "HHH" appear first. (H: heads come up; T: tails come up) For example, if the outcome sequence is "HHTHTHTTHTTHH", then player A wins after the last toss. On the other hand, if the outcome sequence is "HHH", then player B wins after the last toss.

(a) Can the game continue forever?

(b) Calculate the probability that player A wins.

Solution.

(a) No. Either outcome pattern must appear eventually.

(b) Notice that the player B wins if and only if a head comes up for each of the first three tosses.

Proof. "if" part: It is easy to see that player B wins if the first three tosses result in "HHH". This is just the winning condition for player B.

"only if" part: We prove it by contrapositive. So, we start with assuming that a tail comes up for some of the first three tosses. Then, we focus on the toss with outcome "T". If "HH" appears afterward, then player A wins (so player B does not win). Otherwise, if the next toss is with outcome "T", then we focus on the outcome "T". If "HT" appears afterward, we focus on the toss with outcome "T". Through this argument, we can see that the only way to terminate the game is that player A wins. So, player B never win in this case.

$\Box$

It follows that the probability that player B wins is the same as the probability that a head comes up for each of the first three tosses, which is ${\frac {1}{2^{3}}}={\frac {1}{8}}$. (2 outcomes in each toss)

From (a), we know that the game must terminate eventually, that is, either player must win eventually. Hence, the probability that player A wins is $1-{\frac {1}{8}}={\frac {7}{8}}$.

Example. Consider a experiment where we draw two integers from the integers 1,2,3 with replacement. Here, we define the sample space be $\Omega =\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$, where the ordered pair $(a,b)$ indicates that the integer $a$ and $b$ is drawn in first and second draw respectively.

It is given that the probability $$\mathbb {P} (\{(m,n)\})={\frac {m+n}{36}}$$ for every $(m,n)\in \Omega$.

(a) Verify that the sum of the probabilities of all singleton events is 1.

(b) Calculate the probability for the sum of the two integers drawn to be even.

Solution.

(a) The sum is $${\frac {1+1+1+2+1+3+2+1+2+2+2+3+3+1+3+2+3+3}{36}}=1.$$ (b) Notice that the event for the sum of the two integers drawn to be even is $\{(1,1),(1,3),(2,2),(3,1),(3,3)\}$. So, the probability of this event is $$\mathbb {P} (\{(1,1)\})+\mathbb {P} (\{(1,3)\})+\mathbb {P} (\{(2,2)\})+\mathbb {P} (\{(3,1)\})+\mathbb {P} (\{(3,3)\})={\frac {2+4+4+4+6}{36}}={\frac {20}{36}}={\frac {5}{9}}.$$

Exercise. Suppose we disregard the order of the draws, and hence define the sample space to be $\Omega ={\big \{}\{1,1\},\{1,2\},\{1,3\},\{2,2\},\{2,3\},\{3,3\}{\big \}}$, where $\{a,b\}$ means the integers $a$ and $b$ are drawn in the two draws.

(a) Suppose the probability $$\mathbb {P} (\{\{m,n\}\})={\frac {m+n}{c}}$$ for every $\{m,n\}\in \Omega$ and for some constant $c$. Determine the constant $c$ such that the sum of the probabilities of all singleton events is 1.

(b) Calculate the probability for the sum of the two integers drawn to be even with the constant $c$ determined in (a). (Answer: ${\frac {2}{3}}$)

Solution

(a) Since $${\frac {1+1+1+2+1+3+2+2+2+3+3+3}{c}}=1\implies c=24,$$ the constant $c$ is 24.

(b) The event for the sum of the two integers drawn to be even is ${\big \{}\{1,1\},\{1,3\},\{2,2\},\{3,3\}{\big \}}$. So, the probability of this event is $$\mathbb {P} (\{\{1,1\}\})+\mathbb {P} (\{\{1,3\}\})+\mathbb {P} (\{\{2,2\}\})+\mathbb {P} (\{\{3,3\}\})={\frac {2+4+4+6}{24}}={\frac {16}{24}}={\frac {2}{3}}.$$

More advanced properties of probability

Recall the inclusion-exclusion principle in combinatorics. We have similar results for probability:

Theorem. (Inclusion-exclusion principle) Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $E_{1},E_{2},\dotsc ,E_{n}$ be sets in the event space ${\mathcal {F}}$ ($n$ is an arbitrary positive integer). Then, $${\begin{aligned}\mathbb {P} (E_{1}\cup E_{2}\cup \dotsb \cup E_{n})&=\sum _{j=1}^{n}(-1)^{j+1}\sum _{i_{1}<\dotsb <i_{j}}^{}\mathbb {P} (E_{i_{1}}\cap \dotsb \cap E_{i_{j}})\\&=\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}})-\dotsb +(-1)^{n+1}\sum _{i_{1}<i_{2}<\dotsb <i_{n}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{n}})\\&=\mathbb {P} (E_{1})+\dotsb +\mathbb {P} (E_{n})\\&\quad -{\big (}\mathbb {P} (E_{1}\cap E_{2})+\mathbb {P} (E_{1}\cap E_{3})+\dotsb +\mathbb {P} (E_{n-1}\cap E_{n}){\big )}\\&\quad +{\big (}\mathbb {P} (E_{1}\cap E_{2}\cap E_{3})+\mathbb {P} (E_{1}\cap E_{2}\cap E_{4})+\dotsb +\mathbb {P} (E_{n-2}\cap E_{n-1}\cap E_{n}){\big )}\\&\quad -\dotsb \\&\quad +(-1)^{n+1}\mathbb {P} (E_{1}\cap \dotsb \cap E_{n}).\end{aligned}}$$

Proof. We can prove this by mathematical induction.

Let $P(n)$ be the statement $$\mathbb {P} (E_{1}\cup E_{2}\cup \dotsb \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}})-\dotsb +(-1)^{n+1}\sum _{i_{1}<i_{2}<\dotsb <i_{n}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \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\geq 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 \dotsb E_{k}\cup E_{k+1}$ as $(E_{1}\cup E_{2}\cup \dotsb \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{aligned}\mathbb {P} (E_{1}\cup E_{2}\cup \dotsb \cup E_{k}\cup E_{k+1})&=\mathbb {P} {\big (}(E_{1}\cup E_{2}\cup \dotsb \cup E_{k})\cup E_{k+1}{\big )}\\&=\mathbb {P} (E_{1}\cup E_{2}\cup \dotsb \cup E_{k})+\mathbb {P} (E_{k+1})-\mathbb {P} {\big (}(E_{1}\cup E_{2}\cup \dotsb \cup E_{k})\cap E_{k+1}{\big )}\quad ({\text{using the above property of probability again}})\\&={\color {red}\mathbb {P} (E_{1}\cup E_{2}\cup \dotsb \cup E_{k})}+\mathbb {P} (E_{k+1})-{\color {blue}\mathbb {P} {\big (}(E_{1}\cap E_{k+1})\cup (E_{2}\cap E_{k+1})\cup \dotsb \cup (E_{k}\cap E_{k+1})}{\big )}\quad ({\text{distributive law}})\\&={\color {red}\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}})-\dotsb +(-1)^{k+1}\sum _{i_{1}<i_{2}<\dotsb <i_{k}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{k}})}\\&\quad +\mathbb {P} (E_{k+1}){-\color {blue}\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})-\dotsb +(-1)^{k+1}\sum _{i_{1}<i_{2}<\dotsb <i_{k-1}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap E_{i_{3}}\cap \dotsb \cap E_{i_{k-1}}\cap E_{k+1})}\\&\quad {\color {blue}+(-1)^{k+2}\sum _{i_{1}<i_{2}<\dotsb <i_{k}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{k}}\cap E_{k+1})}\quad ({\text{using inductive hypothesis twice}})\\&={\color {purple}\sum _{i_{1}}^{}\mathbb {P} (E_{i_{1}})}{\color {brown}-\sum _{i_{1}<i_{2}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}})}{\color {darkgreen}+\sum _{i_{1}<i_{2}<i_{3}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap E_{i_{3}})}-\dotsb {+\color {deeppink}(-1)^{k+1}\sum _{i_{1}<i_{2}<\dotsb <i_{k}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{k}})}\\&\quad {\color {purple}+\mathbb {P} (E_{k+1})}{\color {brown}-\sum _{i_{1}}^{}\mathbb {P} (E_{i_{1}}\cap E_{k+1})}{\color {darkgreen}+\sum _{i_{1}<i_{2}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap E_{k+1})}-\dotsb +{\color {deeppink}(-1)^{k+1}\sum _{i_{1}<i_{2}<\dotsb <i_{k-1}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap E_{i_{3}}\cap \dotsb \cap E_{i_{k-1}}\cap E_{k+1})}\\&\quad {\color {blue}+(-1)^{k+2}\sum _{i_{1}<i_{2}<\dotsb <i_{k}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{k}}\cap E_{k+1})}\quad ({\text{just changing colors}})\\&={\color {purple}\sum _{i_{1}}^{}\mathbb {P} (E_{i})}{\color {brown}-\sum _{i_{1}<i_{2}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}})}{\color {darkgreen}+\sum _{i_{1}<i_{2}<i_{3}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap E_{i_{3}})}-\dotsb +{\color {deeppink}(-1)^{k+1}\sum _{i_{1}<i_{2}<\dotsb <i_{k}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{k}})}\\&\quad {\color {blue}+(-1)^{k+2}\sum _{i_{1}<i_{2}<\dotsb <i_{k}<i_{k+1}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{k}}\cap E_{i_{k+1}})}\quad ({\text{sum is wrt }}k+1{\text{ case, which involves }}E_{1},E_{2},\dotsc ,E_{k+1})\\\end{aligned}}$$ So, $P(k+1)$ is true.

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

$\Box$

Remark.

• "$\sum _{i_{1}<\dotsb <i_{j}}^{}$" means summing over every vector $(i_{1},\dotsc ,i_{j})$ such that $i_{1}<\dotsb <i_{j}$. It follows that every term in the sum is chosen from $E_{1},E_{2},\dotsc ,E_{n}$ where for every sum, we place indistinguishable choices (we sort them ascendingly)into the $n$ events. Hence, the number of terms in the "$\sum _{i_{1}<\dotsb <i_{j}}^{}$" is ${\binom {n}{j}}$ (when the inclusion-exclusion principle applies to $n$ events).

Example. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space. When $n=3$, the inclusion-exclusion principle becomes $$\mathbb {P} (E_{1}\cup E_{2}\cup E_{3})=\mathbb {P} (E_{1})+\mathbb {P} (E_{2})+\mathbb {P} (E_{3})-\mathbb {P} (E_{1}\cap E_{2})-\mathbb {P} (E_{1}\cap E_{3})-\mathbb {P} (E_{2}\cap E_{3})+\mathbb {P} (E_{1}\cap E_{2}\cap E_{3})$$ where $E_{1},E_{2},E_{3}\in {\mathcal {F}}$.

Exercise. Write out the formula for inclusion-exclusion principle explicitly for 4 events $E_{1},E_{2},E_{3},E_{4}\in {\mathcal {F}}$. (Suggestion: check that the number of terms in each sum is correct (see the remark above).)

Solution

$${\begin{aligned}\mathbb {P} (E_{1}\cup E_{2}\cup E_{3}\cup E_{4})&=\mathbb {P} (E_{1})+\mathbb {P} (E_{2})+\mathbb {P} (E_{3})+\mathbb {P} (E_{4})&\left({\binom {4}{1}}=4{\text{ terms}}\right)\\&\quad -\mathbb {P} (E_{1}\cap E_{2})-\mathbb {P} (E_{1}\cap E_{3})-\mathbb {P} (E_{1}\cap E_{4})-\mathbb {P} (E_{2}\cap E_{3})-\mathbb {P} (E_{2}\cap E_{4})-\mathbb {P} (E_{3}\cap E_{4})&\left({\binom {4}{2}}=6{\text{ terms}}\right)\\&\quad +\mathbb {P} (E_{1}\cap E_{2}\cap E_{3})+\mathbb {P} (E_{1}\cap E_{2}\cap E_{4})+\mathbb {P} (E_{1}\cap E_{3}\cap E_{4})+\mathbb {P} (E_{2}\cap E_{3}\cap E_{4})&\left({\binom {4}{3}}=4{\text{ terms}}\right)\\&\quad -\mathbb {P} (E_{1}\cap E_{2}\cap E_{3}\cap E_{4}).&\left({\binom {4}{4}}=1{\text{ term}}\right)\\\end{aligned}}$$

Example. We select a student from some university students. It is given that

• the selected student has a major in mathematics with a probability 0.4;
• the selected student has a major in statistics with a probability 0.55;
• the selected student has a major in accounting with a probability 0.3;
• the selected student has a major in statistics and accounting with a probability 0.2;
• the selected student has a major in accounting and mathematics with a probability 0.15;
• the selected student has a major in mathematics and statistics with a probability 0.2;
• the selected student has a major in mathematics, statistics and accounting with a probability 0.1.

Then, the probability that the selected student does not have any of these majors is $1-(0.4+0.55+0.3-0.2-0.15-0.2+0.1)=0.2$.

Proof. Let $M$, $S$, $A$ be the event that the selected student among them has a major in mathematics, statistics and accounting respectively. Then, $${\begin{aligned}\mathbb {P} (M^{c}\cap S^{c}\cap A^{c})&=\mathbb {P} {\big (}(M\cup S\cup A)^{c}{\big )}=1-\mathbb {P} (M\cup S\cup A)\\&=1-(\mathbb {P} (M)+\mathbb {P} (S)+\mathbb {P} (A)-\mathbb {P} (M\cap S)-\mathbb {P} (M\cap A)-\mathbb {P} (S\cap A)+\mathbb {P} (M\cap S\cap A))\\&=1-(0.4+0.55+0.3-0.2-0.15-0.2+0.1)\\&=1-0.8=0.2.\end{aligned}}$$ Alternatively, we can consider the following Venn diagram:

Construction of this Venn diagram.

We can see from this diagram that $\mathbb {P} (M\cup S\cup A)=0.05+0.05+0.15+0.1+0.1+0.1+0.25=0.8$, and thus the desired probability is $1-0.8=0.2$.

$\Box$

Exercise.

(a) Calculate the probability that the selected student has at least two of those three majors. (Answer: 0.25)

(b) Calculate the probability that the selected student has exactly one major. (Answer: 0.45)

(Hint: you may consider the Venn diagram above.)

Solution

(a) From Venn diagram, we can observe that the probability is $\underbrace {0.05} _{\text{only A and M}}+\underbrace {0.1} _{\text{only M and S}}+\underbrace {0.1} _{\text{only A and S}}=0.25$.

(b) From Venn digram, the probability is $\underbrace {0.05} _{\text{only A}}+\underbrace {0.15} _{\text{only M}}+\underbrace {0.25} _{\text{only S}}=0.45$.

The following is a classical example for demonstrating the application of inclusion-exclusion principle.

Example. (Letters and envelopes) Suppose we randomly place $n$ letters to $n$ different people into $n$ pre-addressed envelopes (with addresses for the $n$ people).

(a) Calculate the probability that none of the $n$ letters are placed into the correct envelopes.

(b) Calculate the probability that exactly $k$ letters are placed into the correct envelopes (of course, $k\leq n$).

Solution.

(a) Let $E_{1},E_{2},\dotsc ,E_{n}$ be the event that 1st,2nd,...,$n$-th letter are placed into the correct envelope respectively. Then, the desired probability is given by $1-\mathbb {P} \left(\bigcup _{i=1}^{n}E_{i}\right)$.

Now, notice that the intersection of $j$ of the $n$ events means that (at least) $j$ letters are placed into the correct envelopes ($j\leq n$). Then, we can regard the situation as $j$ cells with capacity one (correct envelopes) are occupied with one corresponding ball (correct letter) already (one way to do this), and we place the remaining $n-j$ distinguishable balls (letters) into the remaining $n-j$ distinguishable cells (envelopes) with capacity one. The number of ways of such placement (number of sample points in the intersection of the $j$ events) is thus $(n-j)!$.

On the other hand, to get the number of sample points in the sample space can be obtained by considering the situation as placing $n$ distinguishable balls (letters) into $n$ distinguishable cells (envelopes) with capacity one. Thus, the number of sample points in the sample space is $n!$.

It follows that the probability of the intersection of $j$ of the $n$ events is ${\frac {(n-j)!}{n!}}$ (assuming that all placements are equally likely).

Hence, by the inclusion-exclusion principle, the probability $${\begin{aligned}\mathbb {P} \left(\bigcup _{i=1}^{n}E_{i}\right)&=\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}})-\dotsb +(-1)^{n+1}\sum _{i_{1}<i_{2}<\dotsb <i_{n}}^{}\mathbb {P} (E_{i_{1}}\cap E_{i_{2}}\cap \dotsb \cap E_{i_{n}})\\&=\sum _{i_{1}}^{}{\frac {(n-1)!}{n!}}-\sum _{i_{1}<i_{2}}^{}{\frac {(n-2)!}{n!}}+\sum _{i_{1}<i_{2}<i_{3}}^{}{\frac {(n-3)!}{n!}}-\dotsb +(-1)^{n+1}\sum _{i_{1}<i_{2}<\dotsb <i_{n}}^{}{\frac {(n-n)!}{n!}}\\&={\binom {n}{1}}{\frac {(n-1)!}{n!}}-{\binom {n}{2}}{\frac {(n-2)!}{n!}}+{\binom {n}{3}}{\frac {(n-3)!}{n!}}-\dotsb +(-1)^{n+1}{\binom {n}{n}}{\frac {(n-n)!}{n!}}&({\text{consider the number of terms in each sum}})\\&={\frac {\cancel {n!}}{1!{\cancel {(n-1)!}}}}\cdot {\frac {\cancel {(n-1)!}}{\cancel {n!}}}-{\frac {\cancel {n!}}{2!{\cancel {(n-2)!}}}}\cdot {\frac {\cancel {(n-2)!}}{\cancel {n!}}}+{\frac {\cancel {n!}}{3!{\cancel {(n-3)!}}}}\cdot {\frac {\cancel {(n-3)!}}{\cancel {n!}}}-\dotsb +(-1)^{n+1}{\frac {\cancel {n!}}{n!{\cancel {(n-n)!}}}}\cdot {\frac {\cancel {(n-n)!}}{\cancel {n!}}}\\&={\frac {1}{1!}}-{\frac {1}{2!}}+{\frac {1}{3!}}-\dotsb +(-1)^{n+1}{\frac {1}{n!}}.\end{aligned}}$$ It follows that the desired probability is $$1-\left({\frac {1}{1!}}-{\frac {1}{2!}}+{\frac {1}{3!}}-\dotsb +(-1)^{n+1}{\frac {1}{n!}}\right)=1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+\dotsb +(-1)^{n}{\frac {1}{n!}}=\sum _{j=0}^{n}{\frac {(-1)^{j}}{j!}}.$$

Remark.

• Recall that $e^{x}=\sum _{j=0}^{\infty }{\frac {x^{j}}{j!}}$. So, $e^{-1}=\sum _{j=0}^{\infty }{\frac {(-1)^{j}}{j!}}$. From this, we can see that the answer in (a) is a partial sum of this infinite series. Hence, when $n$ is large, the answer in (a) is approximately $e^{-1}\approx 0.3679$.

(b) Notice that "exactly $k$ letters are placed into the correct envelopes" is equivalent to "(at least) $k$ letters are placed into the correct envelopes and none of the other $n-k$ letters are placed into the correct envelopes". Thus, to get the probability, it suffices to calculate the number of sample points in the latter event, and divide it by the number of sample points in the sample space (which is $n!$ by (a)).

We can get the number of sample points in the latter event by considering it as a three-step process:

1. Fix which $k$ letters are to be placed into the correct envelopes. (${\binom {n}{k}}$ ways)
2. Place the $k$ letters into the correct envelopes. (1 way)
3. Place the other $n-k$ letters such that none of them are placed into the correct envelopes. ($(n-k)!\sum _{j=0}^{n-k}{\frac {(-1)^{j}}{j!}}$ ways. Here, we consider the situation in (a) but with $n-k$ letters. By (a), the probability is $\sum _{j=0}^{n-k}{\frac {(-1)^{j}}{j!}}$. To get the number of ways for such placement (number of sample points in the event), we multiply it by the number of sample points in the sample space in this case ($(n-k)!$).)

It follows that the number of sample points in the event is $${\binom {n}{k}}\times (n-k)!\sum _{j=0}^{n-k}{\frac {(-1)^{j}}{j!}}.$$ Hence, the desired probability is $${\frac {{\binom {n}{k}}\times (n-k)!\sum _{j=0}^{n-k}{\frac {(-1)^{j}}{j!}}}{n!}}={\frac {\cancel {n!}}{k!{\cancel {(n-k)!}}}}\cdot {\frac {\cancel {(n-k)!}}{\cancel {n!}}}\sum _{j=0}^{n-k}{\frac {(-1)^{j}}{j!}}={\frac {1}{k!}}\sum _{j=0}^{n-k}{\frac {(-1)^{j}}{j!}}\to {\frac {e^{-1}}{k!}}{\text{ as }}n\to \infty .$$

Remark.

• It turns out that this is a special case for the Poisson limit theorem, which acts as an approximation to the binomial distribution, where the rate parameter $\lambda =1$. (The general formula is ${\frac {e^{-\lambda }\lambda ^{k}}{k!}}$.) We will discuss these in later chapter.

Theorem. (Continuity from below) Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $E_{1},E_{2},\dotsc$ be events in the event space ${\mathcal {F}}$, such that $E_{n}\uparrow E$, that is, $E_{1}\subseteq E_{2}\subseteq \dotsb$ and $\bigcup _{n=1}^{\infty }E_{n}=E$. (The events $E_{1},E_{2},\dotsc$ are said to be increasing in this case.) Then, $$\lim _{n\to \infty }\mathbb {P} (E_{n})=\mathbb {P} (E).$$

Proof. Assume that $E_{n}\uparrow E$. Now, define $$F_{1}=E_{1},\quad F_{2}=E_{2}\setminus E_{1},\quad F_{3}=E_{3}\setminus E_{2},\dotsc .$$ Claim: $F_{1},F_{2},\dotsc \in {\mathcal {F}}$ are pairwise disjoint.

Proof. We wish to prove that $F_{i}\cap F_{j}=\varnothing$ for every $i,j$ such that $i\neq j$. $${\begin{aligned}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{aligned}}$$ 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.

$\Box$

Also, we have $\bigcup _{i=1}^{n}F_{i}=E_{n}$, and $\bigcup _{i=1}^{\infty }F_{i}=\bigcup _{i=1}^{\infty }E_{i}\in {\mathcal {F}}$. Then, we have $${\begin{aligned}\lim _{n\to \infty }\mathbb {P} (E_{n})&=\lim _{n\to \infty }\mathbb {P} \left(\bigcup _{i=1}^{n}F_{i}\right)&({\text{above}})\\&=\lim _{n\to \infty }\sum _{i=1}^{n}\mathbb {P} (F_{i})&({\text{finite additivity}})\\&=\sum _{i=1}^{\infty }\mathbb {P} (F_{i})&({\text{definition}})\\&=\mathbb {P} \left(\bigcup _{i=1}^{\infty }F_{i}\right)&({\text{countable additivity}})\\&=\mathbb {P} \left(\bigcup _{i=1}^{\infty }E_{i}\right)&({\text{above}})\\&=\mathbb {P} (E).\\\end{aligned}}$$

$\Box$

Corollary. (Continuity from above) Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $E_{1},E_{2},\dotsc$ be events in the event space ${\mathcal {F}}$, such that $E_{n}\downarrow E$, that is, $E_{1}\supseteq E_{2}\supseteq \dotsb$ and $\bigcap _{n=1}^{\infty }E_{n}=E$. (The events $E_{1},E_{2},\dotsc$ are said to be decreasing in this case.) Then, $$\lim _{n\to \infty }\mathbb {P} (E_{n})=\mathbb {P} (E).$$

Proof. Assume that $E_{n}\downarrow E$ as $n\to \infty$. Then, by De Morgan's law and a property of subset, $E_{n}^{c}\uparrow E^{c}$. So, $${\begin{aligned}\lim _{n\to \infty }\mathbb {P} (E_{n})&=1-\lim _{n\to \infty }\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{aligned}}$$

$\Box$

Example. Suppose Bob is given a task to work on. Let $T$ be the time (which is positive, and in days) taken for Bob to finish the task. Assume that the probability for $T\in \left[{\frac {1}{n}},n\right]$ is ${\frac {3n-1}{5n+2}}$ for every $n\in \mathbb {N}$. Here, we define the sample space to contain all the possible time taken: $\Omega =(0,\infty ]$ (in extended real number sense). (Time $\infty$ indicates that the task is never finished.) We also denote by $E_{n}$ the event $\left[{\frac {1}{n}},n\right]$ for every $n\in \mathbb {N}$. Then, we have $\mathbb {P} (E_{n})={\frac {3n-1}{5n+2}}$ for every $n\in \mathbb {N}$.

(a) Calculate the probability that Bob finishes the task eventually.

(b) Calculate the probability that Bob never finishes the task.

Solution.

(a) First, the event that Bob finishes the task eventually can be expressed by $\bigcup _{i=1}^{\infty }E_{i}=(0,\infty )$. (Informally, we may assert this "by inspection" (looking at the pattern for $\bigcup _{i=1}^{n}E_{i}$ when $n$ gets larger and larger). We may also prove it more rigorously, but this is out of scope for here.) Also, notice that $E_{n}\uparrow (0,\infty )$. It follows that the desired probability is given by $$\mathbb {P} ((0,\infty ))=\lim _{n\to \infty }\mathbb {P} (E_{n})=\lim _{n\to \infty }{\frac {3n-1}{5n+2}}=\lim _{n\to \infty }{\frac {3-1/n}{5+2/n}}={\frac {3}{5}}.$$

(b) First, the event that Bob never finishes the task is the complementary event of the event in (a), that is, it can be expressed by $\{\infty \}$. It follows that $$\mathbb {P} (\{\infty \})=1-\mathbb {P} ((0,\infty ))={\frac {2}{5}}.$$

Exercise. Consider a random experiment where the sample space is $\Omega =(-1,1]$. Let $A(t)$ be the event $\left(-t,t\right)$ for every $t\in (0,1)$. It is given that $$\mathbb {P} (A(t))={\frac {t^{2}+3t+6}{12}}$$ for every $t\in (0,1)$.

(a) Calculate the probability $\mathbb {P} (\{0\})$. (Hint: Define event $E_{n}=A\left({\frac {1}{n+1}}\right)$ for every $n\in \mathbb {N}$.) (Answer: ${\frac {1}{2}}$) (We cannot define the event $E_{n}$ as $A\left({\frac {1}{n}}\right)$. Why?)

(b) Calculate the probability $\mathbb {P} ((-1,1))$. (Hint: Define event $F_{n}=A\left(1-{\frac {1}{n+1}}\right)$ for every $n\in \mathbb {N}$.) (Answer: ${\frac {5}{6}}$)

(c) Calculate the probability $\mathbb {P} (\{1\})$.

Solution

(a) Define event $E_{n}=A\left({\frac {1}{n+1}}\right)$ for every $n\in \mathbb {N}$. Then, $E_{n}\downarrow \{0\}$ ("by inspection"). So, the probability is given by $$\mathbb {P} (\{0\})=\lim _{n\to \infty }\mathbb {P} (E_{n})=\lim _{n\to \infty }\mathbb {P} \left(A\left({\frac {1}{n+1}}\right)\right)=\lim _{n\to \infty }{\frac {(n+1)^{-2}+(n+1)^{-1}+6}{12}}={\frac {6}{12}}={\frac {1}{2}}.$$ (We cannot define $E_{n}$ as $A\left({\frac {1}{n}}\right)$ since when $n=1$, this gives $E_{1}=A(1)$, which is undefined.)

(b) Define event $F_{n}=A\left(1-{\frac {1}{n+1}}\right)$ for every $n\in \mathbb {N}$. Then, $F_{n}\uparrow (-1,1)$ ("by inspection"). So, the probability is given by $$\mathbb {P} ((-1,1))=\lim _{n\to \infty }\mathbb {P} (F_{n})=\lim _{n\to \infty }\mathbb {P} \left(A\left(1-{\frac {1}{n+1}}\right)\right)=\lim _{n\to \infty }{\frac {(1-(n+1)^{-1})^{2}+3(1-(n+1)^{-1})+6}{12}}={\frac {1^{2}+3+6}{12}}={\frac {5}{6}}.$$

(c) Notice that $\{1\}$ is the complementary event of $(-1,1)$. Hence, $$\mathbb {P} (\{1\})=1-\mathbb {P} ((-1,1))={\frac {1}{6}}.$$

Example. Suppose John will take the final examination of the course probability theory tomorrow. Here, we define the sample space to contain all his possible scores (expressed in percentage): $\Omega =[0,1]$. (Suppose his possible score (in percentage) is any real number in $[0,1]$.) ($0=0\%$ means 0 mark, and $1=100\%$ means full mark.) Let $A(x)$ be the event that John gets at least $x\%$ in the final exam. In other words, the event $A(x)$ is given by $[x,1]$. It is given that the probability for $A(x)$ is $$\mathbb {P} (A(x))={\frac {(3-x)^{2}}{16}}$$ for every $x\in (0,1)$.

(a) Calculate the probability $\mathbb {P} (A(0))$.

(b) Calculate the probability that John gets zero mark in the exam, that is, $\mathbb {P} (\{0\})$.

Solution.

(a) Since $A(0)=[0,1]=\Omega$, the probability is $\mathbb {P} (A(0))=\mathbb {P} (\Omega )=1$.

(b) Define event $E_{n}=A\left({\frac {1}{n+1}}\right)$ for every $n\in \mathbb {N}$. Then, we can see that $E_{n}\uparrow (0,1]$. Thus, the probability $$\mathbb {P} ((0,1])=\lim _{n\to \infty }\mathbb {P} \left(A\left({\frac {1}{n+1}}\right)\right)=\lim _{n\to \infty }{\frac {(3-(n+1)^{-1})^{2}}{16}}={\frac {3^{2}}{16}}={\frac {9}{16}}.$$ It follows that $$\mathbb {P} (\{0\})=1-{\frac {9}{16}}={\frac {7}{16}}.$$

Exercise. Calculate the probability that John gets full mark in the exam, that is, $\mathbb {P} (\{1\})$. (Hint: Define event $F_{n}=A(?)$ for every $n\in \mathbb {N}$.) (Answer: ${\frac {1}{4}}$)

Solution

Define event $F_{n}=A\left(1-{\frac {1}{n+1}}\right)$ for every $n\in \mathbb {N}$. Then, we can see that $F_{n}\downarrow \{1\}$. Hence, $$\mathbb {P} (\{1\})=\lim _{n\to \infty }\mathbb {P} \left(A\left(1-{\frac {1}{n+1}}\right)\right)=\lim _{n\to \infty }{\frac {(3-(1-(n+1)^{-1}))^{2}}{16}}={\frac {(3-1)^{2}}{16}}={\frac {1}{4}}.$$

Theorem. (Boole's inequality/Subadditivity) Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $E_{1},E_{2},\dotsc$ be events in the event space ${\mathcal {F}}$. Then, $$\mathbb {P} \left(\bigcup _{i=1}^{\infty }E_{i}\right)\leq \sum _{i=1}^{\infty }\mathbb {P} (E_{i}).$$

Proof. Define $$F_{1}=E_{1},\quad F_{2}=E_{2}\setminus E_{1},\quad F_{3}=E_{3}\setminus (E_{2}\cup E_{1}),\quad \dotsc \quad F_{k}=E_{k}\setminus \left(E_{k-1}\cup E_{k-2}\cup \dotsb \cup E_{2}\cup E_{1}\right),\dotsc .$$ Claim: $F_{1},F_{2},F_{3},\dotsc \in {\mathcal {F}}$ are pairwise disjoint.

Proof. We wish to prove that $F_{i}\cap F_{j}=\varnothing$ for every $i,j$ such that $i\neq j$. $${\begin{aligned}F_{i}\cap F_{j}&=\left(E_{i}\cap \left(E_{i-1}\cup E_{i-2}\cup \dotsb \cup E_{1}\right)^{c}\right)\cap \left(E_{j}\cap \left(E_{j-1}\cup E_{j-2}\cup \dotsb \cup E_{1}\right)^{c}\right)\\&=(E_{i}\cap E_{i-1}^{c}\cap E_{i-2}^{c}\cap \dotsb \cap E_{1}^{c})\cap (E_{j}\cap E_{j-1}^{c}\cap E_{j-2}^{c}\cap \dotsb \cap E_{1}^{c}).&({\text{De Morgan's law}})\\\end{aligned}}$$ Case 1: $i<j$. Then, ${\color {blue}E_{j}\cap E_{j-1}^{c}\cap E_{j-2}^{c}\cap \dotsb \cap E_{1}^{c}}=E_{j}\cap E_{j-1}^{c}\cap E_{j-2}^{c}\cap \dotsb \cap {\color {blue}E_{i}^{c}}\cap \dotsb \cap E_{1}^{c}\subseteq {\color {blue}E_{i}^{c}}$. So, it follows that $$({\color {blue}E_{i}}\cap E_{i-1}^{c}\cap E_{i-2}^{c}\cap \dotsb \cap E_{1}^{c})\cap {\color {blue}(E_{j}\cap E_{j-1}^{c}\cap E_{j-2}^{c}\cap \dotsb \cap E_{1}^{c})}\subseteq ({\color {blue}E_{i}}\cap E_{i-1}^{c}\cap E_{i-2}^{c}\cap \dotsb \cap E_{1}^{c})\cap {\color {blue}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, ${\color {blue}E_{i}\cap E_{i-1}^{c}\cap E_{i-2}^{c}\cap \dotsb \cap E_{1}^{c}}=E_{i}\cap E_{i-1}^{c}\cap E_{i-2}^{c}\cap \dotsb \cap {\color {blue}E_{j}^{c}}\cap \dotsb \cap E_{1}^{c}\subseteq {\color {blue}E_{j}^{c}}$. So, it follows that $${\color {blue}(E_{i}\cap E_{i-1}^{c}\cap E_{i-2}^{c}\cap \dotsb \cap E_{1}^{c})}\cap ({\color {blue}E_{j}}\cap E_{j-1}^{c}\cap E_{j-2}^{c}\cap \dotsb \cap E_{1}^{c})\subseteq {\color {blue}E_{j}^{c}}\cap ({\color {blue}E_{j}}\cap E_{j-1}^{c}\cap E_{j-2}^{c}\cap \dotsb \cap E_{1}^{c})=\varnothing ,$$ which means $F_{i}\cap F_{j}=\varnothing$ (since the only subset of $\varnothing$ is $\varnothing$).

$\Box$

Furthermore, we have $F_{i}\subseteq E_{i}$ for every $i=1,2,\dotsc$, and $\bigcup _{j=1}^{\infty }F_{j}=\bigcup _{j=1}^{\infty }E_{j}\in {\mathcal {F}}$. Hence, $${\begin{aligned}\mathbb {P} \left(\bigcup _{i=1}^{\infty }E_{i}\right)&=\mathbb {P} \left(\bigcup _{i=1}^{\infty }F_{i}\right)\\&=\sum _{i=1}^{\infty }\mathbb {P} (F_{i})&({\text{countable additivity}})\\&\leq \sum _{i=1}^{\infty }\mathbb {P} (E_{i}).&({\text{monotonicity}})\end{aligned}}$$

$\Box$

Remark.

• The Boole's inequality also holds for finitely many events $E_{1},E_{2},\dotsc ,E_{n}\in {\mathcal {F}}$. This can be seen by setting $E_{n+1}=E_{n+2}=\dotsb =\varnothing$. Then, we have

$$\mathbb {P} \left(\bigcup _{i=1}^{n}E_{i}\right)\leq \sum _{i=1}^{n}\mathbb {P} (E_{i}).$$

Example. Let $(\Omega ,{\mathcal {F}},\mathbb {P} )$ be a probability space, and $A,B,C\in {\mathcal {F}}$ be events. Given that $\mathbb {P} (A)=0.9$, $\mathbb {P} (B)=0.8$ and $\mathbb {P} (C)=0.85$, what is the maximum value of $\mathbb {P} (A\cap B\cap C)$?

Solution. First, we have $\mathbb {P} (A^{c})=0.1,\mathbb {P} (B^{c})=0.2,\mathbb {P} (C^{c})=0.15$. It follows that $$\mathbb {P} (A^{c}\cup B^{c}\cup C^{c})\leq 0.1+0.2+0.15=0.45\implies \mathbb {P} (A\cap B\cap C)\leq 0.45\quad ({\text{De Morgan's law}}).$$ Hence, the maximum value is 0.45.