Probability Theory

Probability Theory is the study of predicting Samples from Population

Futhermore, it is essentially applied Set Theory and Combinatorics. At least on the surface level. It gets its rigor from Measure Theory, believe it or not, even though that is more of a Geometry/Topology adjacent field.

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 a well-defined set of possible Outcomes, which form 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

Random Variables

Random Experiment

Random Experiment

A Random Experiment is a kind of Experiment with unpredictable Outcomes; where identical conditions can lead to different outcomes.

Link to original

Random Variable

Random Variable

A Random Variable is a Function $X$ that maps each Outcome $\omega$ of the Sample Space $S$ of a Random Experiment to a Real Number $x\in \mathbb{R}$

$$X:\omega \in S\to x\in \mathbb{R}$$

• the Random Variable is always denoted with a capital letter, and the real number is the corresponding lowercase letter, e.g. $X$ and $x$, $Y$ and $y$, etc.
• a Random Variable can be discrete or continuous

Link to original

Probability Mass Function

Probability Mass Function

A Probability Mass Function is a Probability Function for a Discrete Distribution, that is, where the Random Variable is Discrete. It is called a mass function, because each probability value per discrete Outcome is like a point mass.

• $|S|\le {\aleph }_0$
• $\forall x\in S,f(x)=P(X=x)$
• $\forall x\in S,f(x)\ge 0$
• ${\sum }_{-\infty }^{\infty }f(x)=1$

Link to original

Probability Density Function

Probability Density Function

A Probability Density Function is a Probability Function for a Continuous Distribution, that is, where the Random Variable is Continuous. It is called a density function, because each probability value doesn’t have a value at its exact Outcome, just zero, rather, only continuous ranges of outcomes produce a probability. Just like how a single point in a solid doesn’t have a mass, only over a region with a density is there a mass.

• $|S|>{\aleph }_0$
• $\forall x\in S,f(x)\ge 0$
• $\forall x\in \mathbb{R},P(X=x)=0$
• ${\int }_{-\infty }^{\infty }f(x)dx=1$
• $P(a\le X\le b)={\int }_a^{b}f(x)dx=F(b)-F(a)$

Link to original

Cumulative Density Function

Cumulative Density Function

A Cumulative Density Function is just the Integral of a Probability Density Function from its lower bound, to a certain point.

$$F(x)={\int }_{-\infty }^{b}f(x)dx$$

• $F(x)\in [0,1]$
• $x\le y⟹F(x)\le F(y)$
• $F(-\infty )=0,F(\infty )=1$

Link to original

Expectations

Expected Value

Expected Value

$$E(X)={\text{sum}}_{S}xf(x)={\int }_{S}xdF$$ $$E(h(x))={\text{sum}}_{S}h(x)f(x)={\int }_{S}h(x)dF$$

• where $f(x)$ is the PMF/PDF depending on if the Random Variable is Discrete or Continuous
• $E(aX+b)=aE(X)+b$

Link to original

Variance

Variance

$${\sigma }^2=\text{Var}(X)=E((X-\mu {)}^2)=E(X^2)-E^2(X)$$

• $\text{Var}(aX+b)=a^2\text{Var}(X)$
• $\text{Var}(c)=0$

Link to original

Distributions

Distribution

• Distribution
  • Discrete Distribution, A Distribution with a Discrete Random Variable
    • Discrete Uniform Distribution
    • Discrete Bernoulli Distribution, for the probability of a single successful Bernoulli Trial
    • Discrete Binomial Distribution, like Bern but repeated; probability of x successes in n trials
    • Discrete Geometric Distribution, like Bern but probability of x trials being the first success
    • Discrete Negative Binomial Distribution, like Geo, but the rth success rather than the first
    • Discrete Poisson Distribution, probability of x Poisson Events occuring in a fixed interval of time, for which $\lambda$ is the average rate of occurences per interval
  • Continuous Distribution
    • Continuous Uniform Distribution
    • Continuous Exponential Distribution, probability density of the next Poisson Event being within x amount of domain time, given an average rate of occurence of $\lambda$, CDF for probability
    • Continuous Normal Distribution, probability density of normal distribution, CDF for probability
      • Continuous Standard Normal Distribution, Norm, but standardized.

Link to original

Central Limit Theorem

Central Limit Theorem

The Central Limit Theorem states that no matter the shape or distribution of the original data, if you take a large enough random sample, and average the values, those sample averages will form a Normal Distribution. Furthermore, the sample mean will approach the population mean, and sample mean variance will shrink to 0.

$$\text{Let }P=X_{\mathrm{1..}n}\forall i,j\in [1,n],X_i{\sim }^{iid}{X}_{j}E[X_i]=\mu \text{Var}(X_i)={\sigma }^{2}n\to \infty$$ $$\frac{P}{Z_n=\frac{{\sum }_{k=1}^n{X}_k-n\mu }{\sigma \sqrt{n}}=\frac{\bar{X}-\mu }{\sigma /\sqrt{n}}=\frac{\bar{X}-E[\bar{X}]}{\sqrt{\text{Var}(\bar{X})}}{\to }^d\text{Nor}(0,1)}$$ $$\frac{P}{\overline{X}\approx \text{Nor}\left(\mu ,(\frac{\sigma }{\sqrt{n}}{)}^2\right)}$$Link to original

Inequalities

Chebyshev

Chebyshev's Inequality

Chebyshev’s Inequality is used to give the Probability of a Sample being beyond/within $k$ standard deviations of the mean.

$$\frac{E[X]=\mu \text{Var}(X)={\sigma }^{2}k>0}{P(|X-\mu |\ge k\sigma )\le \frac{1}{k^2}P(|X-\mu |<k\sigma )\ge 1-\frac{1}{k^2}}$$

or equivalently

$$\frac{E[X]=\mu \text{Var}(X)={\sigma }^{2}k>0}{\max (P(|X-\mu |\ge k\sigma ))=\frac{1}{k^2}\min (P(|X-\mu |<k\sigma ))=1-\frac{1}{k^2}}$$Link to original

Markov

Markov's Inequality

Markov’s Inequality uses Expected Value to find the upper bound of the Probability of a nonnegative Random Variable being at least $c$

$$\frac{X\text{ is RV}P(X\ge 0)=1c>0}{P(X\ge c)\le \frac{E[X]}{c}}$$

Proof

$$\begin{array}{rl}E[X]={\int }_0^{\infty }xf(x)dx\ge & {\int }_c^{\infty }xf(x)dx\ge c{\int }_c^{\infty }f(x)dx=cP(X\ge c)\\ E[X]& \ge cP(X\ge c)\\ \frac{E[X]}{c}& \ge P(X\ge c)\\ & \square \end{array}$$Link to original

Bivariate Random Variables

Bivariate Random Variables

A bivariate random variable $(X,Y)$ models two random variables simultaneously when they are related.

The joint CDF for all BRVs is

$F(x,y)\equiv P(X\le x,Y\le y)$

Discrete Bivariate Random Variables

If $X$ and $Y$ are discrete RVs, $(X,Y)$ is a jointly discrete bivariate RV.

• PMF: $f(x,y)=P(X=x,Y=y)$
  • $0\le f(x,y)\le 1$
  • ${\sum }_x{\sum }_{y}f(x,y)=1$
  • $P((X,Y)\in A)=\sum {\sum }_{(x,y)\in A}f(x,y)$

Continuous Bivariate Random Varibales

If $X$ and $Y$ are continuous RVs, $(X,Y)$ is a jointly continuous RV if there exists a joint probability density function (PDF) $f(x,y)$:

• $f(x,y)\ge 0,\forall x,y$
• ${\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f(x,y)dxdy=1$
• $P((X,Y)\in A)={\iint }_{A}f(x,y)dxdy$

$f(x,y)=\frac{{\partial }^2}{\partial x\partial y}F(x,y)$

Link to original

Marginal Distribution

Marginal Distribution

The marginal distribution isolates the probability distribution of one variable while ignoring the value of the other variable.

Discrete Case (Marginal PMF)

• $f_X(x)=P(X=x)={\sum }_{y}f(x,y)$
• $f_Y(y)=P(Y=y)={\sum }_{x}f(x,y)$

Continuous Case (Marginal PDF)

• $f_X(x)={\int }_{-\infty }^{\infty }f(x,y)dy$
• $f_Y(y)={\int }_{-\infty }^{\infty }f(x,y)dx$

Marginal CDF

• $F_X(x)=P(X\le x)={\lim }_{y\to \infty }F(x,y)$
• $F_Y(y)=P(Y\le y)={\lim }_{x\to \infty }F(x,y)$

Link to original

Conditional Distribution

Conditional Distribution

Given two jointly distributed random variables, the conditional PMF/PDF of $X$ given $Y=y$ (where $f_Y(y)>0$) is defined as:

$f_{X|Y}(x|y)=\frac{f(x,y)}{f_Y(y)}$

Similarly, the conditional distribution of $Y$ given $X=x$ is:

$f_{Y|X}(y|x)=\frac{f(x,y)}{f_X(x)}$

Finding Marginal from Conditional:

1. Find joint distribution: $f(x,y)=f_X(x)f(y|x)$
2. Integrate/Sum out $x$: $f_Y(y)={\int }_{\mathbb{R}}f(x,y)dx$

Link to original

Covariance

Covariance

Covariance measures the direction of the linear relationship between two random variables.

$$\text{Cov}(X,Y)\equiv {\sigma }_{XY}\equiv E\left[(X-E[X])(Y-E[Y])\right]E[XY]-E[X]E[Y]$$

• $\text{Cov}(X,X)=\text{Var}(X)$
• $\text{Cov}(X,Y)>0⟹$ Variables move in the same direction.
• $\text{Cov}(X,Y)<0⟹$ Variables move in opposite directions.
• $X$ and $Y$ are independent $⟹\text{Cov}(X,Y)=0$

Link to original

Correlation

Correlation

Correlation measures the linear association between two variables in a unitless scale.

$\rho =\text{Corr}(X,Y)\equiv \frac{\text{Cov}(X,Y)}{\sqrt{\text{Var}(X)\text{Var}(Y)}}=\frac{{\sigma }_{XY}}{{\sigma }_X{\sigma }_Y}$

• $|\rho |\le 1$
• If $X,Y$ are independent $⟹\rho =0$.

Link to original