Chapter 2 :Sets, Axioms of Probability¶

Now, let's begin the formal elementary probability theory's study.
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 word , it called 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 coutcomes 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,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 introduce to naive set theory as an begining? This course isn't a expectation.

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 interests: 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 them, there is also a very important law in the theory 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 the content in this class, just to know,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 addtivity)
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'm in high school, I am 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

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 countable infinite sequence of events \(\{E_i\}_{i\ge1}\)

Proof

We construct a new sequence of events \(\{F_i\}_{i=1}^{\infty}\) mutually exclusive.

$$ \color{Blue}Motivation example:Infinitely large urn and infinite balls $$

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 the \(\{E_n^c \ n\ge1 \}\) is increasing.

Now we prove the result for increasing \(E_n\) ,we do the same construction before.

Now let's focus on original example. We change the ball withdrawn to randomly.

We consider the ball number 1. Let \(E_n\) be the event that ball 1 is still in the urn after the \(n^{th}\) withdraw.

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 need n 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 throw 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 analysis the complement event at least one man selects his own hats

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 Talor 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\)

评论