1.1 \sigma-algebras

The state space or sample space \Omega is some abstract space and we denote subsets of \Omega by capital letters A,B,\cdots. We use the language of set theory A^c= \Omega \setminus A, \quad A \cap B, \quad A \cup B, \quad A \setminus B, \quad A \supset B, \quad \emptyset,

1.2 Axioms of Probability

Two simple axioms underlie probability theory.

1.3 Consequence of the axioms

1.4 Countable additivity and limits

Monotone limits for sets

A_n \searrow A \quad \text{ means } \quad A_1 \supset A_2 \supset A_3 \,\,\text{ and } \,\, A= \bigcap_{n=1}^\infty A_n

A_n \nearrow A \quad \text{ means } \quad A_1 \subset A_2 \subset A_3 \,\,\text{ and } \,\, A= \bigcup_{n=1}^\infty A_n

1.5 More on limits of sets

limsup and liminf of sets: For an arbitrary collection of sets A_n we define the limsup and liminf by

\begin{aligned} \limsup_{n\to \infty} A_n &= \bigcap_{n=1}^\infty \bigcup_{m \ge n} A_m = \left\{ \omega \in \Omega \,; \omega \in A_n \text {for infinitely many } n \right\} \\ \liminf_{n\to \infty} A_n &= \bigcup_{n=1}^\infty \bigcap_{m \ge n} A_m = \left\{ \omega \in \Omega \,; \omega \in A_n \text {for all but finitely many } n \right\} \end{aligned} The fact that the two definitions coincide requires some thoughts (see homework for more details). For example if \omega \in \bigcap_{n=1}^\infty \bigcup_{m \ge n} A_m then \omega \in \bigcup_{m \ge n} A_m for every n. Taking n=1 we find that there exist some k_1\ge 1 such that \omega \in A_{k_1}. Taking next n=k_1+1 we see that there exists k_2 >k_1 such that \omega \in A_{k_2}, and so on. Therefore \omega belongs to infinitely many A_n.

Characteristic function of a set A: 1_A(\omega)= \left\{ \begin{array}{cl} 1 & \omega \in A \\ 0 & \omega \notin A \end{array} \right.

Limits of sets: We say that A_n converge to A if \lim_{n} 1_{A_n}(\omega) = 1_A(\omega) for all \omega.

1.6 Conditional Probability and Independence

The intuition behing conditional probabilities is as follows. Suppose you observe that the vent B has occurred (e.g. “it rained yesterday”). How does that influence the probability of another event A (e.g. there was wind yesterday or it is raining today)?

For \omega \in A to be a possible outcome we must have \omega \in A \cap B. So only events of the form A \cap B are relevant. Normalizing the probabilities leads to the following

If the occurence of B does not influence the probability that A occurs, that is if P(A|B)=P(A) then we will call theses events independent. This means P(A|B) = P(A) \iff P(A \cap B) = P(A) P(B) \iff P(B|A) = P(A).

1.7 Conditional probability model

Given a probability P and any (fixed) event A we can build a new probability

One can then extend the concepts of independence to conditional independence.

This concept is important in Markov chain, Markov and Bayesian networks (graphical models) (see e.g. https://en.wikipedia.org/wiki/Graphical_model and https://en.wikipedia.org/wiki/Bayesian_network, and later examples in the class).

1.8 Take-home messages

• \sigma-algebra would not be necessary if we work only with discrete sample space.

• But to describe sample space like \mathbb{R} or a countable collection of discrete models (think coin flip) they are necessary (recall that 2^\mathbb{N} has the same cardinality as \mathbb{R}). In the dark corners of real numbers various monsters are lurking that need to be tamed (and then ignored).

• At a deeper and more interesting level \sigma-algebra will occur later in conditional expectation, martingales and stochastic processes, they will be use as information-theoretic tool and will describe sets of questions or inquiries you can perform on a model.

2.1 Probabilities on countable state spaces

• If \Omega=(\omega_1, \omega_2, \dots) is countable sample space take as \sigma-algebra \mathcal{A}=2^{\Omega} to the collection of all susbets of \Omega.

• Specifying a probability on \mathcal{A} is equivalent to choosing a collection of numbers p_n=P(\{\omega_n\}) which the probability of the event \{\omega_n\} with p_n \ge 0 \quad \text{ and } \quad \sum_{i} p_n =1 and then for any A \subset \Omega we have P(A) = \sum_{\omega \in A} P(\{\omega\})

• Countable additivity reduces to the fact that for absolutely convergent series we can freely interchange of summations P( \cup_{i} A_i) = \sum_{\omega \in \cup_{i} A_i} p(\omega) =\sum_{i} \sum_{\omega \in A_i} p(\omega) = \sum_i P(A_i) if the A_i are pairwise disjoint.

2.2 Poisson approximation

If the number of trial n \gg 1 is large and the probability of success if small p \ll 1, then the binomial distribution can be approximated by a Poisson distribution with parameter \lambda = np. A formal mathematical result is the following (proof in the homework)

Example: Birthday problem

• There are N students in class. Event A=“at least two students share the same birthday”.

• p= probability that one pair of students have the same birthday? It is p=\frac{1}{365}.

• Number of trials here is the number of pair of students n = {N \choose 2}= \frac{N(N-1)}{2}. Note:T rials are weakly dependent here.

• Poisson approximation \lambda=np={N \choose 2}\frac{1}{365} and so P(A^c) \approx e^{-{N \choose 2} \frac{1}{365}}.

• Exact value P(\text{no pair share the same birthday}) = \frac{365}{365} \frac{364}{365} \cdots \frac{ 365 -N+1}{365}

See more in the nice book Understanding Probability by Henk Tijms

2.3 Random variable on countable state spaces

You should think as a random variable as associating a quantity (a number or maybe a vector) (hence the name “variable”) to an each outcomes \omega \in \Omega. The probability defined on \Omega implies that this variable is random, hence the name “random variable”.

2.4 Sampling with or without replacement

• A urn with N balls, b blue balls and r=N-b red balls. We select n balls out of the N balls either with or without replacing balls after choosing them.

• Sample space \Omega=\{0,1\}^n with \omega =(\omega_1, \cdots, \omega_n) where \omega_i=0 means getting a red ball and \omega_i=1 means getting a blue ball on the i^{th} selection.

• Random variable X(\omega)= \|\omega\|_1 = \sum_i \omega_i which is the number of blue balls and take values in \{0,1,\cdots,n\}

2.5 Expectation

2.8 Variance of a RV

• If E[X^2] is finite then X has finite mean and thus finite variance because of the elementary inequality |x|\le 1 + x^2.

• If X and Y are independent random variables then V[X+Y]=V[X]+V[Y]

• Suppose X_1, \cdots, X_n are independent random variables with common mean E[X_i]=\mu and common variance V[X_i]=\sigma^2. Let S_n=X_1+ \cdots X_n be their sum and \frac{S_n}{n} their average. Then E\left[\frac{S_n}{n}\right]= \mu \quad \text{ and }\quad V\left[\frac{S_n}{n}\right]= \frac{\sigma^2}{n}

2.9 Conditional expectation

Conditioning on event, random variables, and eventually \sigma-algebras is at the center of probability theory. We start with afew examples for discrete random variables and we will extend to the general case later on.

Note that this is simply the expectation with respect to the probability P(\cdot|B) which we have seen in Theorem 1.6 is a probability in its own right.

Moreover since P(X=i|B) \le \frac{P(X=i)}{P(B)} the sum in Equation 2.2 well defined if g(X) is integrable wioth respect to P.

We can push this a little more by considering two discrete RVs X and Y and condition on the event Y=j.

2.10 Homework problems

3.1 Frequentist vs Bayesian

There are two broad interpretation of probability frequentist versus Bayesian (see e.g https://en.wikipedia.org/wiki/Probability_interpretations)

• In the Bayesian approach (subjective probability) the probability of an event P(A) measure the degree of belief assigned by the probabilist to the ocurrence of the event. A good example of that approach in sports betting: How do you compute the probability that the Kansas City Chiefs will win the superbowl? It really measure the degree of belief assigned by a bettor (or by a bookmaker) to that event.
  This approach works well with Bayes formula \underbrace{P(A|B)}_{\text{Posterior}} = \underbrace{\frac{P(B|A)}{P(B)}}_{} \underbrace{P(A)}_{\text{prior}} which describes how information (here the occurence of B) modify your belief about the occurence of A.

• In the frequentist approach the probability of an event is assigned by observing its frequency over time when repeating the same experiment multipl times. This works well if you want to compute the probability that the roulette wheel lands on the number 23. But this work not so well to compute the probbaility that an earthquake of magnituyde more than 6 will hit San Francisco area.
  Underlying the frequentist approach is the strong law of large number which we prove in this section: if we repeat the same experiment N times in the same conditions, and independetly of each other then \frac{\# \textrm{ of occurrences of the event $A$} }{N} \longrightarrow P(A) \quad \text{ as } N \to \infty

3.2 Borel-Cantelli Lemma

Recall that \limsup_{n} A_n = \cap_{n\ge 1} \cup_{k \ge n} A_k = \{ \omega \in \Omega\,;\; \omega \text{ belongs to infinitely many} A_n \}

3.3 Markov inequality and the weak law of large numbers

Let X_i be a sequence of IID discrete random variables with expected value p ((e.g take independent copies of the indicator function X=1_A for some set). Then we set S_n = X_1 + \cdots + X_n

3.4 Strong Law of Large numbers

We prove now the strong Law of Large numbers for sum of independent discrete random variables. Once we have develop the theory of integration a bit more we will see that the same proof applies to general random variables (with finite mean and variance).

The proof is based on the following Lemma which is a consequence of Borel Cantelli Lemma

3.5 Homework problems