Chapter 2: Sets, Axioms of Probability⚓︎
Now, let's begin the formal study of elementary probability theory. Normally, we will establish the fundamental framework by showing the axioms of probability. Before doing this, we must ensure that you have a certain understanding of basic sets and set operations.
Sets⚓︎
Motivations
-
the sex of a newborn child
-
flipping two coins
-
tossing two coins
-
etc
We can't answer the above questions but know all the possibilities—— In other words, it is called the sample space.
Definition 2.1 (Sample Space) A random experiment is a phenomenon whose outcome is not predictable with certainty, but the set of all possible outcomes is known. The set of all possible outcomes is known as the sample space of the experiment and is denoted by \(\mathcal{S}\). Any item \(ω ∈ \mathcal{S}\) is called a sample point.
Remark 2.2 \(\mathcal{S}\) can be finite, countably infinite, or uncountably infinite.
We may think deeper after learning more Real Analysis.
Cases(previous experiments)
- S={boy,girl} finite
- S={(head, head), (head, tail), (tail, head), (tail,tail)} finite
- S={(i, j) : i, j = 1, 2, 3, 4, 5, 6} finite
Every course seems to give an introduction to naive set theory at the beginning? This course isn't an exception.
Subset/Superset⚓︎
Definition 2.3 If every point of A belongs to B, then A is contained or included in B and A is a subset of B, while B is a superset of A.
Symbolically,\(A\subset B,B \supset A\)
Event⚓︎
Definition 2.4 An event \(E\) is a set consisting of possible outcomes of the experiment that satisfy a given property. Thus, \(E\) is a subset of \(\mathcal{S}\). If the outcome of the experiment is contained in \(E\), then we say that \(E\) has been realized or that \(E\) has occurred.
Remark 2.5
- \(S:\) the sure event
- \(\emptyset :\) the impossible event
Still use the cases mentioned before, the newborn child is a girl means \(E\)={girl}.
Operations, Relations and Notations⚓︎
Union⚓︎
The union \(E ∪ F\) of two sets \(E, F\) is the set of points that belong to at least one of them. Symbolically,\(E\cup F\)={ \(\omega | \omega\in E \ or \ \omega \in F\) } \(E\cup F\) is realized if either \(E\) or \(F\) occurs.
Intersection⚓︎
The intersection \(E ∩ F( or EF)\) of two sets \(E, F\) is the set of points that belong to both of them. Symbolically,\(EF\)={\(\omega | \omega\in E \ and \ \omega \in F\) } \(EF\) is realized if \(E\) and \(F\) both occur.
Countable union/intersection⚓︎
\(\{E_i\}_{i\ge 1}\) is a countable sequence of events.
- The union of these events denoted \(\bigcup\limits_{i=1}^{\infty}E_i\) is defined to be the event which consists of all outcomes that are in at least one event \(E_i\) ,\(i=1,2...,\infty\) \(\omega \in \bigcup\limits_{1}^{\infty}E_i\Longleftrightarrow \exists i \ s.t. \omega \in E_i\)
- The intersection of these events denoted \(\bigcap\limits_{i=1}^{\infty}E_i\) is defined to be the event which consists of all outcomes that are in all of the events \(E_i\) ,\(i=1,2...,\infty\) \(\omega \in \bigcap\limits_{1}^{\infty}E_i\Longleftrightarrow \omega \in E_i \ \forall \ i\)
Mutually exclusive⚓︎
\(E,F\) are mutually exclusive if \(E\cap F= \emptyset\) \(E\) and \(F\) can not both occur at the same time.
Complement⚓︎
For a set \(E \subset S\) ,the complement of \(E\) is denoted by \(E^c\) and is the set of points that do not belong to \(E\).
Symbolically,\(E^c=\{ \omega \in S|\omega \notin E\}\)
\(E\cup E^c=S,E \cap E^c=\emptyset,(E^c)^c=E\)
Difference⚓︎
For events E, F, \(E\setminus F\) is the set of points that belong to E but not to F.
Symbolically,\(E\setminus F=\{\omega| \omega \in E\ and \ \omega \notin F\}\)
\(E\setminus F =E\setminus(E\cap F),E^c=S\setminus E\)
Symmetric difference⚓︎
\(E \bigtriangleup F\) is the set of points that belong to exactly one of them. Symbolically,\(E \bigtriangleup F =\{ \omega| \omega \in E\setminus F \ or \ \omega \in F\setminus E\}\)
Venn diagram⚓︎
\(\mathcal{S}\):a large rectangle events \(E,F\)... :represented by circles events of interest: shading the appropriate regions of the diagram
Laws on sets⚓︎
Commutativity⚓︎
\(E\cup F=F \cup E \ and \ E \cap F=F \cap E\)
Associativity⚓︎
\(E \cup(F\cup G)=(E\cup F)\cup G \ and \ E\cap(F \cap G)=(E\cap F) \cap G\)
Distributivity⚓︎
\(E \cup(F\cap G)=(E\cup F)\cap (E\cup G) \ and \ E\cap(F \cup G)=(E\cap F) \cup (E \cap G)\)
Transitivity⚓︎
If \(E \subset F \ and\ F \subset G\) ,then \(E \subset G\)
After these, there is also a very important law in the theory of set operations.
Proposition 2.5 (De Morgan’s laws) \((1)(\bigcup\limits_{i=1}^{n}E_i)^c=\bigcap\limits_{i=1}^{n}E_i^c\) \((2)(\bigcap\limits_{i=1}^{n}E_i)^c=\bigcup\limits_{i=1}^{n}E_i^c\)
Proof
It suffices to show (1) since if (1) holds , then we consider \((\bigcup\limits_{i=1}^{n}E_i^c)^c=\bigcap\limits_{i=1}^{n}(E_i^c)^c=\bigcap\limits_{i=1}^{n}E_i\)
We get (2) by applying complement to both sides.
So we only need to proof (1)
\(\subset\)
\(\omega \notin \bigcup_{i=1}^{n}E_i\) , For any \(\omega \notin E_i \to\omega \in E_i^c \ for \ all \ i\)
\(s.t. \ \omega \in \bigcap_{i=1}^{n}E_i^c\)
\(\supset\)
\(\omega \in \bigcap_{i=1}^{n}E_i^c\) , For any i , \(\omega \notin E_i \to \omega \notin \bigcup_{i=1}^{n}E_i\),\(\omega \in (\bigcup_{i=1}^{n}E_i)^c \ \forall \ i\)
\(s.t. \ \omega \in (\bigcup_{i=1}^{n}E_i)^c\)
Axioms of Probability⚓︎
Remark 2.6 This part is not covered in this class; it is just for your information. You can read more about this in Real Analysis (Royden) if you want.
σ-algebra and Measurable space⚓︎
Definition 2.7 (σ-algebra) A σ-algebra A ⊂ P(S) is a family of sets over S satisfying the following properties: + \(\emptyset \in \mathcal{A}\) + \(\mathcal{A}\) is closed under complementation: If \(E \in \mathcal{A}\) , then \(E^c \in \mathcal{A}\) , \(\mathcal{A}\) is closed under countable union: if \((E_i)_{i\ge1}\)is a countable sequence of sets in \(\mathcal{A}\) ( \(E_i\in \mathcal{A}\ for \ i\in N^*)\), then \(\bigcup_{i=1}^{\infty}E_i\in \mathcal{A}\)
Definition 2.8 (Measurable space) Let us consider a random experiment with sample space \(S\) endowed with \(\sigma - algebra \ \mathcal{A}\), \((S,\mathcal{A})\) is called a measurable space and elements of \(\mathcal{A}\) are called events.
Under this is the most important part in this chapter——Axioms of Probability
Axioms⚓︎
Definition 2.9 (Probability, Kolmogorov, 1933) Let \((S, \mathcal{A})\) be a measurable space of events. A probability measure is a real-valued function mapping \(\mathcal{P} : \mathcal{A} → \mathcal{R}\) satisfying:
- for any event \(E\in \mathcal{A},\mathcal{P}\in(E)\ge0\) (nonnegativity)
- \(\mathcal{P}(S)=1\)
- for any countably infinite sequence of events \((E_i)_{i\ge1}\) that are mutually exclusive,
(\(\sigma\)-additivity or countable additivity) Then \((S,\mathcal{A},\mathcal{P})\) is called a probability space.
Properties of probability⚓︎
Some properties⚓︎
Remark 2.10 We write down all the proofs because we first learn the rigorous parts of probability theory, in the chapters after this, I will omit some.
Property 1 (Probability of the impossible event)
Proof
Let \(\ E_1=S\) ,\(E_i=\emptyset \ for\ all \ i\ge2\), \(\{ E_i\}_{i=1}^{\infty} \ is \ a \ mutually \ exclusive \ sequence\)
Property 2 (Probability of a finite union of mutually exclusive events) For any finite sequence of events \(E_1,...,E_n\in \mathcal{A}\) that are mutually exclusive (that is, \(E_i\cap E_j=\emptyset \ if \ i \neq j\)),
Proof
Let \(E_k=\emptyset\) for all \(k>n\) \(\{E_i\}_{i=1}^{\infty}\) countable, mutually exclusive
Property 3 (Probability of included events)
For any two events \(E, F \in A\),
Proof
Property 4 For any event \(E\in \mathcal{A}\),
Proof
Property 5 (Law of total probability) Let \(F\in \mathcal{A}\) be an event and \((E_i)_{i\ge 1}\) be a countable partition of the sample space \(S\) (that is, \(\bigcup_{i=1}^{\infty}E_i=S\ and \ E_i\cap E_j=\emptyset \ for \ i \neq j\)),
Proof
Property 6 (Probability of the complement) For any event \(E\in \mathcal{A}\),
Proof
Property 7 (Probability of the union of 2 events) For any two events \(E,F\in \mathcal{A}\),
Proof
The identity below is a very famous trick (when I was in high school, I was amazed by it).
Property 8 (Inclusion-Exclusion Identity/Poincaré’s formula) For any two events \(E,F\in \mathcal{A}\),
where \(\sum\limits_{1\le i_1<...<i_k\le n}\) means the sum for all subsets of \((1,...,n)\) of size k.
Proof
The proof by induction is easy.
Property 9 For events \(E,F\)
Proof
Property 10 (A generalization)
For a finite sequence of events \(E_1,...,E_n,\)
Proof
Property 11 (Boole’s Inequality) For a countably infinite sequence of events \(\{E_i\}_{i\ge1}\)
Proof
We construct a new sequence of events \(\{F_i\}_{i=1}^{\infty}\) mutually exclusive.
Suppose we have an infinitely large urn, and an infinite collection of balls labeled as number 1, 2, 3, and so on. Consider an experiment as follows:
- At 1 minute to 12pm, balls numbered 1 through 10 are placed in the urn and ball number 1 is withdrawn;
- At \(\frac{1}{2}\) to 12pm, balls numbered 11 through 20 are placed in the urn and ball number 2 withdrawn;
- At \(\frac{1}{4}\) to 12pm, balls numbered 21 through 30 are placed in the urn and ball number 3 withdrawn;
- ...
and so on. How many balls are there in the urn at 12pm ? (the answer is 0 and why?) If we place the 1 to 10 balls and withdraw 10,place the 11 to 20 balls and withdraw 20,there are infinite balls(contrast two situations).
Continuity property⚓︎
Definition 2.11 (Increasing/Decreasing sequences) A sequence of events \(\{E_n,n\ge1\}\) is said to be an increasing sequence if
and we define a new event { \(\lim\limits_{n\to \infty}E_n \ by \ \lim\limits_{n\to \infty}E_n=\bigcup\limits_{n=1}^{\infty}E_n\) } A sequence of events \(\{E_n,n\ge1\}\) is said to be an increasing sequence if
and we define a new event \({\lim\limits_{n\to \infty}}E_n \ by \ \lim\limits_{n\to \infty}E_n=\bigcap\limits_{n=1}^{\infty}E_n\)
Proposition 2.12 (Continuity property) If \(\{E_n,n\ge1\}\) is either an increasing or a decreasing sequence, then
Proof
It suffices to discuss the increasing case since,
if \(\{E_n \ n\ge1\}\) is decreasing, then \(\{E_n^c \ n\ge1 \}\) is increasing.
Now we prove the result for increasing \(E_n\); we use the same construction as before.
Now let's focus on the original example. We change the procedure to withdraw a ball randomly.
We consider ball number 1. Let \(E_n\) be the event that ball 1 is still in the urn after the \(n^{th}\) withdrawal.
The discussion for other balls is the same. So we can get the conclusion.
Uniform probability measure⚓︎
We first study finite sample space
Definition 2.9 (uniform probability measure) Let \(S\) be a finite sample space \(S = \{\omega_1,...,\omega_n\}\) with \(|S|=n\in N,n\ge1\) and \((S,P(S),P)\) be a probability space. Probability measure \(P\) is said to be uniform if all outcomes \(\omega_i\) in the sample space are equally likely to occur, that is,\(P(\{\omega_i\})=\alpha\) for \(i=1,...,n,\) with \(\alpha\ge 0\) .
Properties
Let \((S,P(S),P)\) be a probability space with uniform probability measure \(P\) on a finite sample space \(S=\{ \omega_1,...,\omega _n\}\). Then
Proof
Interesting Examples⚓︎
Poker Problem⚓︎
In the game of bridge, the entire deck of 52 cards is dealt out to 4 players. What is the probability that + one of the players receives all 13 spades; + each player receives 1 ace?
Solution
\(S=\{all \ possibel\ distribution\ to \ 4\ players\}\) \(|S|=\binom{52}{13,13,13,13}\)
Birthday Problem⚓︎
Recall that Pigeonhole principle tells us that among 366 people, there are at least 2 people celebrating their birthday on the same day (we ignore the Feb. 29 case). Now we want to study, for n people, what is the probability that no two of them celebrate their birthday on the same day? How large does n need to be so that this probability is less than \(\frac{1}{2}\)?
Solution
For n people,\(S=\{all \ possibel\ birthday\ of \ n\ people\}\)
\(|S|=365^n\)
Matching Problem⚓︎
Suppose that each of N men at a party throws his hat into the center of the room. The hats are first mixed up, and then each man randomly selects a hat. What is the probability that none of the men selects his own hat?
Solution
We analyze the complement event: at least one man selects his own hat.
Let \(E_i=the \ i^{th}\ man\ selects\ his\ own\ hats\)
Note that \(E_{i_1}E_{i_2}..E_{i_n}\) represents the event that \(i_1^{th}...i_{n}^{th}\) men get their own hats
the probability that no one selects his own hat is
Recall the Taylor expansion of \(e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}\). When N is large the probability is close to \(e^{-1}\approx0.3679\)