↑ index§3 Notes

STAT410

Revised 2026-09-17

Lecture 1

Random Experiments

Definition: Random Experiment (experiment done without predictable outcomes, but have an enumerated outcome space.

Example: for a coin toss, sample space is $$S=\{H,T\}\leftarrow \text{set of all possible outcomes sometimes denoted }\Omega$$

and for two consecutive tosses, the sample space is $$S=\{HH,HT,TH,TT\}$$

A more complex example: toss until the first heads, which has a countably infinite cardinality$$S=\{H,TH,TTH,TTTH,\dots \}$$

Another one: record the height of all the people in the class, which is continuum and not countable$$S=(0,100)\text{assuming people are between 0 and 100m tall}$$

Recall Definition: Countable refers to having bijection with $\mathbb{N}$.

One more example: the evolution of a stock price during one week, which is considerably more difficult and has higher cardinality than the height example. This time, we have a function space which is also outside the scope of the class$$S=C([0,1])\text{continuous functions between 0 and 1}$$

Example: Need to select a committee of 2 students from 3 juniors and 4 seniors.

The sample space could be$$S_1=\{JJ,JS,SJ,SS\}\text{where order matters}$$ $$S_2=\{0,1,2\}\text{when checking how many juniors are included}$$

We could even enumerate all the juniors and seniors, making a sample space of size $\left(\genfrac{}{}{0ex}{}{7}{2}\right)$

Events

Recall that the power set is the family of all subsets of a set. Let $$S=\varnothing ,P(S)=\text{power set of S}$$$$\mathfrak{F}\subseteq P(S)$$

Definition:

$\mathfrak{F}$ is a $\sigma$-algebra on $S$ if

• $S\in \mathfrak{F}$

• $A\in \mathfrak{F}\Rightarrow A^C\in \mathfrak{F}$

• $A_1,A_2,A_3,\dots ,A_n\in \mathfrak{F}\Rightarrow {\bigcup }_n{A}_i\in \mathfrak{F}$ (union of countable sequence exists)

Example:

Find the smallest $\mathfrak{F}$ given $S$.

Solution: $\boxed{\mathfrak{F}=\{S,\varnothing \}}$

What about one that also contains $A\in P(S)$?

Solution: $\boxed{\mathfrak{F}=\{\varnothing ,S,A,A^C\}}$

(All $\sigma$-algebras will contain $S$ and $\varnothing$)

Definition: an EVENT is a subset of $S$. (of course, not all $\sigma$-algebra is subset, but this is good enough for now).

An event is a collection of outcomes. We look at whether or not it occurs. So if $S$ is the outcome, does $S\in A$ or $S\notin A$.

Example:

Toss two dice and sum the results. The sample space will be$$S=\{2,3,4,\dots ,12\}$$$$A=\{\text{obtaining a multiple of three}\}=\{3,6,9,12\}$$

For a simple outcome $s\in S$, does $s\in A$?

Lecture 2

De Morgan’s Law

Let $(A_{\alpha }{)}_{\alpha \in I}$ be some collection of events in $S$.

1. $${\left(\bigcup _{\alpha \in I}{A}_{\alpha }\right)}^C=\bigcap _{\alpha \in I}{A}_{\alpha }^C$$

2. $${\left(\bigcap _{\alpha \in I}{A}_{\alpha }\right)}^C=\bigcup _{\alpha \in I}{A}_{\alpha }^C$$

Actually, the two statements are equivalent– a simple change of variables along with the identity $(A^C{)}^C=A$.

Probability

$$\mathbb{P}:P(S)⟶[0,1]\text{such that}$$

1. $\mathbb{P}(S)=1$

2. $A_1,A_2,\dots$ disjoint events in $S\Rightarrow \mathbb{P}({\bigcup }_{i=1}^{\infty }{A}_i)={\sum }_{i=1}^{\infty }\mathbb{P}(A_i)$

Example:

Let us use a fair coin, $S=\{H,T\}$. We can then define the individual probabilities $\mathbb{P}(H)=\mathbb{P}(T)=\frac{1}{2}$.

Now for example, we want to compute the probability of $\mathbb{P}(\{HH\})$ if $\mathbb{P}(\{H\})=p$, then we get $p^2$. Very simple, well defined.

Slightly more interesting case: keep tossing a coin until we obtain heads. Our sample space can be represented by the number of tosses: $S=\{1,2,3,\dots \}$, and we would like to compute $\mathbb{P}(\{i\})$. It’s very reasonable to compute $\mathbb{P}(\{i\})=(1-p{)}^{i-1}p$.

By our definitions earlier, we can describe $\mathbb{P}(A)$ for a general $A$. $$\mathbb{P}(A)=\mathbb{P}\left(\bigcup _{S\in A}\{S\}\right)=\sum _{S\in A}\mathbb{P}(\{s\})$$

In the discrete case, the above formula is a simple sum of singletons, which is the usual definition.

Let us verify that our solution is indeed correct. $$\sum _{i=1}^{\infty }(1-p{)}^{i-1}p=p\sum _{j=0}^{\infty }(1-p{)}^j\text{(power series)}$$$$\text{(defn.)}{S}_k=\sum _{n=0}^k{a}_n=\frac{1-a^{k+1}}{1-a}⟶S_{\infty }=\frac{1}{1-a}$$$$\Rightarrow \mathbb{P}(S)=1$$

Another Proof: We should ensure that $\mathbb{P}(\varnothing )=0$.

Let $A_1=S,A_2=A_3=\cdots =\varnothing$. These disjoint sets can be arranged$$\mathbb{P}\left(\bigcup _{i=1}^{\infty }{A}_i\right)=\sum _{i=1}^{\infty }\mathbb{P}(A_i)=\mathbb{P}(S)=1$$$$=\mathbb{P}(S)+\sum _{i=2}^{\infty }\mathbb{P}(A_i)\Rightarrow \sum _{i=2}^{\infty }\mathbb{P}(\varnothing )=0\Rightarrow \mathbb{P}(\varnothing )=0$$

Further, we ask for $A_1,\dots ,A_n$ disjoint, does $$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{i=1}^n\mathbb{P}(A_i)$$

(i.e. does the property hold for a finite set where it already does for a countable one?) Yes, since we can simply replace with an infinite number of empty sets. This is known as additivity.

So we can see that $\sigma$-additivity implies additivity.

Definition:

A sequence is bounded if there is a supremum and infimum value. Define:

$$l^{\infty }=\{x=(x_n{)}_{n\in \mathbb{N}}\text{ bounded}\}$$$$V_0=\{x\in l^{\infty }:\text{ all but a finite number of terms is zero}\}$$$$1=(1,1,1,1,\dots )\in l^{\infty }$$$$V_1=\{\alpha 1+x,\alpha \in \mathbb{R},x\in V_0\}$$$$\lambda :\lambda (\alpha 1+x)=\alpha$$

Theorem:

$$\exists \Lambda :l^{\infty }⟶\mathbb{R}\text{ linear such that }$$

1. $$\Lambda (x)=\lambda (x)\forall x\in V_1$$

2. $$\inf x_n\le \Lambda (x)\le \sup x_n$$

Now, we have the tools to define probability types that are additive but not $\sigma$-additive.

Take $S=\mathbb{N},A\subseteq \mathbb{N}$. Define$$x_n^A=\{\begin{array}{ll}1& \text{if }n\in A\\ 0& \text{if }n\notin A\end{array}$$

We know: $x^A\in l^{\infty },\#A<+\infty ,x^A\in V_1$ with $\alpha =0$.

Now, define $\mathbb{P}(A)=\Lambda (x^A)\in [0,1]$ (by definition), and $\#A<+\infty \Rightarrow \mathbb{P}(A)=0\Rightarrow \Lambda (x^A)=\lambda (x^A)=0$

But does $\mathbb{P}(\mathbb{N})=1=\Lambda (x^{\mathbb{N}})$? Yes! Clearly, $\Lambda (1)=\lambda (1)=1$ since all elements are 1 as all $\mathbb{N}$ is in $\mathbb{N}$. $$1=\sum \mathbb{P}(\{n\})=0$$

This is not $\sigma$-additive, but additive. And now it is well-defined!

Lecture 3

Define $p(s)$ as $\mathbb{P}(\{s\})$ given $\{s\}\subset S$.

Basic properties:

1. For $A\subseteq S$, $\mathbb{P}(A^C)=1-\mathbb{P}(A)$

2. For $A\subseteq B$, $\mathbb{P}(A)\le \mathbb{P}(B)$

3. For $A,B\subseteq S$, $\mathbb{P}(A\cup B)=\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(A\cap B)$

4. $\mathbb{P}(A_1\cup \cdots \cup A_n)={\sum }_{r=1}^n(-1{)}^{r+1}{\sum }_{j_1<\cdots <j_n}\mathbb{P}(A_{j_1}\cap \cdots \cap A_{j_r})$

5. $\mathbb{P}({\bigcup }_{i=1}^n{A}_i)\le {\sum }_{i=1}^n\mathbb{P}(A_i)$

Theorem:

Let $\mathbb{P}:P(S)⟶[0,1]$ be finite additive with $\mathbb{P}(S)=1$. Then the following are equivalent.

1. $\mathbb{P}$ is $\sigma$-additive.

2. If $A_1\subseteq A_2\subseteq A_3\dots$, then $\mathbb{P}({\bigcup }_{i=1}^{\infty }{A}_i)={\lim }_{n\to \infty }\mathbb{P}(A_n)$.

3. If $A_1\supseteq A_2\supseteq A_3\dots$, then $\mathbb{P}({\bigcap }_{i=1}^{\infty }{A}_i={\lim }_{n\to \infty }\mathbb{P}(A_1)$.

Example Application:

You have an infinite number of balls, numbered, and a box arbitrarily large. 1 minute before 12pm, you put 10 balls numbered 1-10 in the box and then remove one. 1/2 minutes before 12pm, you put 10 more balls numbered 11-20 in then remove one. In general, every $(\frac{1}{2}{)}^2$ minutes before noon you put 10 balls, $n\cdot 10+1$ to $(n+1)\cdot 10$, in and remove one.

Question: What is the probability that at noon the box is empty?

Solution:

$$\boxed{\mathbb{P}(\text{urn is empty at noon})=1}$$

Consider the event $F_k=\{\text{ball k is still in the urn at noon}\}$. Then $\{\text{urn is empty}\}={\left({\bigcup }_{k=1}^{\infty }{F}_k\right)}^C$. $$\Rightarrow \mathbb{P}(\text{urn is empty})=1-\mathbb{P}(\bigcup _{k=1}^{\infty }{F}_k)\ge 1-\sum _{k=1}^{\infty }\mathbb{P}(F_k)$$

Since we have $\mathbb{P}(F_k)=0\forall k$, then our probability will be $\ge 1\Rightarrow =1$.

Let’s prove this for $k=1$:

Let $E_n=\{\text{ball \#1 is still in the box after n steps}\}$, then ${\bigcap }_{n=1}^{\infty }{E}_n=F_1$. We know that $E_n\supseteq E_{n+1}$, so we can use the continuity principles. $$\mathbb{P}(F_1)=\mathbb{P}(\bigcup _n{E}_n)=\underset{n\to \infty }{\lim }\mathbb{P}(E_n)$$$$\mathbb{P}(E_n)=\frac{9}{10}\frac{18}{19}\dots \frac{9n}{9n+1}=\prod _{k=1}^n\frac{9k}{9k+1}$$$$=\frac{1}{{\prod }_{k=1}^n(1+\frac{1}{9k})}$$$$\ln (\prod _{k=1}^n(1+\frac{1}{9k}))=\sum _{k=1}^n\ln (1+\frac{1}{9k})\sim \sum _{k=1}^n\frac{1}{9k}\text{goes to }\infty$$

Lecture 4

Example:

Prove that $\forall A\subseteq S$, $\mathbb{P}(A)\mathbb{P}(A^c)\le \frac{1}{4}$.

Solution: $$\mathbb{P}(A)\mathbb{P}(A^c)=\mathbb{P}(A)(1-\mathbb{P}(A))$$

Since $\mathbb{P}(A)\in [0,1]$, let $f(x)=x(1-x)$ represent our situation. It can be shown that the maximum is achieved at $x=\frac{1}{2}$ with $f(x)=\frac{1}{4}$.

Example:

Show that $\mathbb{P}(A\cap B)\le \mathbb{P}(A)\mathbb{P}(B)+\frac{1}{4}$

Solution:$$\mathbb{P}(A\cap B)(\mathbb{P}(A)+\mathbb{P}(A^c))\le \mathbb{P}(B)\mathbb{P}(A)+\mathbb{P}(A)\mathbb{P}(A^c)\le \mathbb{P}(A)\mathbb{P}(B)+\frac{1}{4}$$

Example:

Given a sequence $A_1,A_2,\cdots \subseteq S$, with $\mathbb{P}(A_n)=1\forall n$. Then $\mathbb{P}({\bigcap }_n{A}_n)=1$.

Solution:

Strategy: we can show that complement is zero$$\mathbb{P}((\bigcap _n{A}_n{)}^c)=0\Rightarrow \mathbb{P}(\bigcup _n{A}_n^c)\le \sum _n\mathbb{P}(A_n^c)=0$$

Example:

Three people toss a coin. If the outcome of one of the three tosses is different from one of the others, the game stops. Otherwise, keep going.

What is the probability that the game will end at the first round?

Solution:

$\mathbb{P}(\text{stop first round})=1-\mathbb{P}(\text{all same outcomes})=1-\frac{1}{8}-\frac{1}{8}=\frac{3}{4}$.

Example:

What if the coin is not fair, with $\mathbb{P}(\{H\})=\frac{3}{4}$?

Solution:

$1-{\frac{3}{4}}^3-{\frac{1}{4}}^3=\frac{9}{16}$.

Example:

Two dice are rolled. What is the probability that at least one rolls a six?

Solution:

$S=\{(a_i,a_j),a_i,a_j\in \{1,\dots ,6\}\},\#S=36$$$A=\{(6,a_j),a_j\in \{1,\dots ,5\},(6,6),(a_i,6),a_i\in \{1,\dots ,5\}\},\#A=11$$$$\mathbb{P}(\text{at least one six})=\frac{11}{36}.$$

Example:

Compute the same probability if you know that the two tosses are different.

Solution:

$S=\{(a_i,a_j),a_i,a_j\in \{1,\dots ,6\},a_i\ne a_j\},\#S=30$$$A=\{(6,a_j),a_j\in \{1,\dots ,5\},(a_i,6),a_i\in \{1,\dots ,5\}\},\#A=10$$$$\mathbb{P}(\text{one six})=\frac{10}{30}=\frac{1}{3}$$

Example:

Given that $\mathbb{P}(A)=0.9,\mathbb{P}(B)=0.8$, show that $\mathbb{P}(A\cap B)\ge 0.7$.

Solution:

$\mathbb{P}(A\cap B)\ge 0.7\iff \mathbb{P}((A\cap B{)}^c)\le 0.3$$$\mathbb{P}(A^c\cup B^c)\le \mathbb{P}(A^c)+\mathbb{P}(B^c)=0.1+0.2=\mathrm{0.3.}$$

Another solution:$$\mathbb{P}(A\cup B)=\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(A\cap B)\Rightarrow \mathbb{P}(A\cap B)\ge 0.9+0.8-1$$

Problem:

We know that 60% of families own a car, 30% own a home, and 20% own both. What is the probability that a family owns a car or a home but not both?

Solution:

Define $C=\{\text{own car}\},H=\{\text{own home}\}$.$$\mathbb{P}((C\cup H)\backslash (C\cap H))=\mathbb{P}(C)+\mathbb{P}(H)-2\mathbb{P}(C\cap H)=0.5$$

More Theory

Given that $S$ is a sample space where $\#S<+\infty$ and every outcome is equally likely, for some $A\subseteq S$ we have $P(A)=\frac{\#A}{\#S}$, and for a singleton $s\in S$ we have $\mathbb{P}(\{s\})=\frac{1}{\#S}$.

If you perform $r$ experiments, the number of outcomes for the first experiment is $k_1$. Once you have done the first experiment, the second experiment has $k_2$ possible outcomes. After the $n$-th experiment, the $(n+1)$-th experiment has $k_{n+1}$ outcomes.

Question: How many outcomes are there for the $r$ experiments together? Obviously, it is $k_1\cdot k_2\cdot \cdots \cdot k_r$ outcomes.

Permutations

You have $n$ objects which are distinguishable. You want to count how many different ways you can pick $r$, if there is replacement. Clearly, this is just $n^r$.

Let us add some complexity. Consider the same experiment with no replacement. We have $$n(n-1)(n-2)\dots (n-r+1)=\frac{n!}{(n-r)!}=:P(n,r)\text{ or }{P}_{n,r}$$

Now, let’s add even more complexity. We have $n$ objects not all distinguishable– there are $k$ groups whose elements are indistinguishable. Let’s say that $\#\text{Group }i=r_i$, with $r)1+\cdots +r_k=n$. In how many different ways can they be arranged?

If they are all distinguishable, the answer would be $n!$. However, this ends up overcounting. We must divide individually the number of orderings of each group:$$\frac{n!}{r_1!r_2!\dots r_k!}.$$

Combinations

Once again, we consider $n$ distinguishable objects, and we want to select $r$ without replacement. Now, we don’t care about order anymore, just that the subset selected is unique. $$C_{n,r}=\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{(n-r)!r!}.$$

Example:

I have 5 white balls numbered 1-5 and 8 black balls numbered 1-8. In how many different ways can I select two white and three black balls?

Solution:

$\left(\genfrac{}{}{0ex}{}{5}{2}\right)\left(\genfrac{}{}{0ex}{}{8}{3}\right)=560$.

Example:

There are two candidates A and B. A got $n$ votes, and B got $m$ votes, where the total number of votes is simply $n+m$, and $m<n$. You check votes one at a time. What is the probability that $A$ is never behind $B$ during the counting?

Solution:

Let ${\xi }_i=\{\begin{array}{ll}1& \text{voted for A}\\ -1& \text{voted for B}\end{array}$. Then we can define $$S=\{({\xi }_i,\dots ,{\xi }_n),{\xi }_i\in \{1,-1\},\sum _{i=1}^{n+m}{\xi }_i=n-m\}$$

Consider $(k,{\sum }_{i=1}^k{\xi }_i)$. We want $D=\{\text{A never falls behind B}\}$, or in other words$$D=\{({\xi }_1,\dots ,{\xi }_{n+m})\in S:\sum {\xi }_i\ge 0$$