Probability Theory

Probability Theory is the study of predicting Samples from Population

Futhermore, it is essentially applied Set Theory and Combinatorics.

Set Theory with Probability

General Set Theory applies to probability. There are also special sets within probability theory.

Correspondance to Set Theory

In Probability Theory, there is a correspondance between the following:

Venn Diagrams $⟺$ Sets $⟺$ Probabilities

This is because, obviously Venn Diagrams correspond to Sets. But furthermore, probabilities also correspond to sets, because probabilities simply just exist within a special case of a Universe where the Universe is the Sample Space $S$ and a particular subset of that sample space is an Event $A$: $A\subset S$.

$$P(A)=\frac{|A|}{|S|}$$

Outcome

Outcome

A single element $\omega \in S$ of the Sample Space $S$; the result of one trial of an Experiment. Distinct from an Event $A\subseteq S$, which is a set of outcomes.

Link to original

Event

Event

A subset $A\subseteq S$ of the Sample Space $S$. $A$ occurs iff the outcome $\omega \in A$

Link to original

Experiment

Experiment

A repeatable procedure with uncertain outcome that determines a Sample Space $S$ (the Universe of all possible outcomes). Each trial yields one $\omega \in S$; an Event $A\subseteq S$ is said to occur if $\omega \in A$.

Link to original

Sample Space

Sample Space

The Set of all possible outcomes of an Experiment, usually denoted $S$ or $\Omega$. It is the Universe for Probability Theory where every Event $A$ satisfies $A\subseteq S$ (see Correspondance to Set Theory).

Finite Sample Space

A Sample Space where $|S|<\infty$

Means we can use Cardinality and Combinatorics with $P(A)=\frac{|A|}{|S|}$ to get Probability

Simple Sample Space

A Finite Sample Space where all singleton outcomes are equiprobable: $P(\{\omega \})=1/|S|$ for every $\omega \in S$, so $P(A)=|A|/|S|$ for any Event $A\subseteq S$

Link to original

Principle of Inclusion Exclusion

Principle of Inclusion-Exclusion for Probability

Based on the Principle of Inclusion-Exclusion, which relates to Cardinality. We can simply divide both sides by the cardinality of the Universe in order to get everything in terms of cardinality. See Correspondance to Set Theory

$$\begin{array}{rl}P(A_1\cup A_2\cup \cdots \cup A_n)& =\\ \sum _{i=1}^{n}P(A_i)& -\\ \sum _{1\le i<j\le n}P(A_i\cap A_j)& +\\ \sum _{1\le i<j<k\le n}P(A_i\cap A_j\cap A_k)& -\\ \dots & \\ & \\ +(-1{)}^{n+1}P(A_1\cap A_2\cap \cdots \cap A_n)& \end{array}$$Link to original

Disjoint Events

Disjoint

$$\text{Disjoint(A,B)}\equiv A\cap B=\varnothing$$

Disjoint Events

A special case of Principle of Inclusion-Exclusion for Probability, when all events are Disjoint. This is because all terms after the first term are the Empty Set $\varnothing$

$$P\left(\bigcup _{i=1}^{\infty }{A}_i\right)=\sum _{i=1}^{\infty }P(A_i)$$Link to original

Independent Events

Independent

$$\begin{array}{rl}\text{Independent}(A,B)⟺P(A\cap B)=P(A)P(B)& ⟹\\ P(A)>0\wedge P(B)>0⟹P(A|B)=P(A)\wedge P(B|A)=P(B)& \end{array}$$Link to original

Law of Total Probability

Law of Total Probability

If $A_{\mathrm{1..}n}$ for a Partition of Universe $S$ and $B$ is any event, then

$$P(B)=\sum _{i=1}^{n}P(A_i\cap B)=\sum _{i=1}^{n}P(A_i)\cdot P(B|A_i)$$

Link to original

Baye’s Theorem

Baye’s Theorem

$$P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$$

Partitioned Baye’s Theorem

If $A_{\mathrm{1..}n}$ for a Partition of Universe $S$ and $B$ is any event, then

$$\forall j\in [1,n]P(A_j\mid B)=\frac{P(A_j\cap B)}{P(B)}=\frac{P(A_j)\cdot P(B\mid A_j)}{{\sum }_{i=1}^{n}P(A_i)P(B\mid A_i)}$$

• where $P(A_j)$ is the prior probabilities, “before $B$”
• where $P(A_j\mid B)$ are the posterior probabilities, “after B”

See Conditional Probability

Link to original

Combinatorics with Probability

In order to calculate probabilities, you usually need to determine the cardinality of the Event using Combinatorics.

Addition Rule

Addition Rule

A special case of Disjoint Events.

$$\begin{array}{rl}A\cap B=\varnothing & ⟹|A\cup B|=|A|+|B|\\ & ⟹P(A\cup B)=P(A)+P(B)\end{array}$$Link to original

Multiplication Rule

Multiplication Rule

If a process has sequential stages where stage i has $c_i$ paths to stage i+1, then the number of paths from $c_0$ to $c_{n-1}$ is ${\prod }_{i=0}^{n-1}{c}_i$

This is a result of Conditional Probability

Link to original

Permutation

Permutation

An arrangment of the order of a Set

A permutation is an Isomorphism of a set

Partial Permutation

$$P(n,k)=P_{n,k}=\frac{n!}{(n-k)!}=C(n,k)\cdot P(k,k)$$

Repetitious Permutation

$$n^k$$

Multiset Permutation

a.k.a Multinomial Coefficients

The formula to find the number of distinct arrangements of a set of objects, some of which are indistinguishable

• where $n$ is the count of items
• where each $k_i$ is the number of repetitions of an object

$$\frac{n!}{k_1!\cdot k_2!\cdot \cdots \cdot k_n!}=\frac{\text{Orderings ignoring repeats}}{\text{Product of orderings of each repeated item}}$$

For example, How many distinct arrangements can be made using the letters in the word: BANANA?

Solution

• Pretend like there are no duplicate letters: $6!$ arrangements
• Of those arrangements some will be exactly the same Consider BANANA. We want to elimate the repeated arrangements How many ways can you arrange 3 As? $3!$ How many ways can you arrange 2 Ns? $2!$

$$\frac{6!}{3!2!}=60$$

Link to original

Combination

Combination

A selection of elements from a Set where order doesn’t matter. “n choose k”.

$$C(n,k)=C_{n,k}=\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!}=\frac{P(n,k)}{P(k,k)}$$

It is also called “Binomial Coefficient”, as it forms the terms in Pascal’s Triangle, which are coefficients of $n^{\text{th}}$ degree binomial when expanded into a Polynomial.

Stars and Bars

How many ways are there to seperate some amount of stars with some amount of bars?

$$C(\star +┃,┃)$$Link to original

Probability Distribution

Probability Distribution

In Probability Theory, a Probability Distribution is a Function that maps a Sample Space to a Probability Space.

Sampling with Replacement

aka Binomial Distribution

• Of a sample drawn from a finite population, drawing $n$ objects with replacement from the set of typed objects, containing a objects of type 1 and b objects of type 2, and get exactly $k$ of type 1

$$\begin{array}{rl}P(\text{k type 1 were picked})=& \\ (\text{\# ways to choose k 1s and n-k 2s})\cdot P(\text{choose k 1s in a row, then n-k 2s in a row})& =\\ C(n,k){\left(\frac{a}{a+b}\right)}^k{\left(\frac{b}{a+b}\right)}^k& \end{array}$$

Sampling without Replacement

aka Hypergeometric Distribution

• Of a sample drawn from a finite population, drawing $n$ objects without replacement from the set of typed objects, containing a objects of type 1 and b objects of type 2, and get exactly $k$ of type 1

$$\begin{array}{rl}P(\text{k type 1 were picked})=& \\ \frac{(\text{\# ways to choose k 1s})(\text{choose n - k 2s})}{\text{\# ways to choose n out of a + b}}=& \\ \frac{C(a,k)C(b,n-k)}{C(a+b,n)}& \end{array}$$Link to original

Conditional Probability

Conditional Probability

The Probability of $A$, $P(A)$, given $B$ has occurred ($P(B)>0$)

$$P(A\mid B)=\frac{P(A\cap B)}{P(B)}$$

Simple Sample Space

If the Sample Space is a Simple Sample Space, i.e. where $\forall \omega \in S,P(\{\omega \})=\frac{1}{|S|}$, and all of the above is already true, then the following is valid.

$$P(A\mid B)=\frac{P(A\cap B)}{P(B)}=\frac{\frac{|A\cap B|}{|S|}}{\frac{|B|}{|S|}}=\frac{|A\cap B|}{|B|}$$

Disjoint Events

$$\text{djt(A,B)}⟹P(A|B)=\frac{0}{P(B)}=0$$

Independent Events

$$\text{djt(A,B)}⟹P(A|B)=\frac{P(A)P(B)}{P(B)}=P(A)$$Link to original