Probability

WIP

1. Terminology:

Experiment: A controlled, repeatable investigation of some random process.
Trial: One particular act of a random experiment (An experiment is composed of several of trials).
Outcome: The result of a trial.
Event $(A, B)$ : Set of outcomes of a random experiment (subset of the Sample space).
Union of Events $(A \cup B)$ : The union of events $A$ and $B$ is the event, which takes place when at least one out of the two events happen.
Intersection of Events $(A \cap B)$ : The intersection of events $A$ and $B$ occurs when both events occur simultaneously. Often denoted as: $(A, B)$
Mutual Exclusivity: Events $A$ and $B$ are mutually exclusive if $A \cap B = \emptyset$ .
Mean ( $\mu$ ): The average value of an experiment.

$\mu = \sum_i^n \frac{x_i}{n}$

Median: In a sorted list, the number exactly from the middle.
Mode: The object, which appears the most frequently in the dataset.
Absolute Frequency: How many times a given event has occurred while carrying out an experiment.
Relative Frequency: Absolute frequency divided how many times we carried out the experiment.
Sample space ( $\Omega$ ): The set of all possible outcomes of a random experiment. (might be discrete or continuous)
$\sigma$ -algebra ( $F$ ): Collection of Events, Subsets of the Sample space that satisfies the $\sigma$ -algebra properties. (The allowable events)
Probability measure ( $P$ ): Is a real - valued function, which maps elements of the $\sigma$ -algebra, set of events to the interval $[0, 1]$ and satisfies the Kolmogorov axioms.
Probability space: The triple $(\Omega, F, P)$ consisting the Sample Space, $\sigma$ -algebra and Probability measure.

$\sigma$ -algebra properties:

$\Omega \in F$
$A \in F \Rightarrow A^c \in F$
$A_1, A_2, ... \in F \Rightarrow \cup_{i\geq 1}A_i \in F$

Kolmogorov axioms:

$A \in F \rightarrow P(A) \geq 0$
$P(\Omega) = 1$
$A_1, A_2, ... \in F,\enspace A_i \cap A_j = \emptyset \enspace \forall i \neq j \Rightarrow P(\cup_{i\geq1}A_i) = \sum_{i\geq1}P(A_i)$

More basics:

Probability of co-occurrence of two events: The probability of the union of events $A$ and $B$ is the sum of their probabilities minus the probability of their co-occurrence.

$P(A\cup B) = P(A) + P(B) - P(A\cap B)$

Union bound: The probability of the union of events is bounded by the sum of their probabilities.

$P(\cup_{i\geq 1} A_i) \leq \sum_{i\geq 1}P(A_i)$

Conditional probability: Probability of Event $A$ happening given that Event $B$ has already happened:

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

Independece: Two events are independent if the occurrence of one event does not affect the other’s probability to happen. Event $A$ and Event $B$ are independent iff

$P(A\cap B) = P(A) \cdot P(B) \leftrightarrow P(A|B) = P(A)$

Conditional independence: Two events are conditionally independent given a third event if the occurrence of the two events are independent of the third event in their conditional probability distribution. Event $A$ and $B$ are conditionally independent given an event $C$ iff

$P(A,B | C) = P(A|C) \cdot P(B|C) \leftrightarrow P(A| B, C) = P(A|C)$

Chain rule: The probability of the co-occurrence of events can be written as the conditional probabilites of these events.

$P(\cap_{i \geq 1} A_i) = P(A_1) \cdot P(A_2|A_1) \cdot P(A_3|A_1, A_2) \cdot \dotsc = \prod_{i \geq 1}(S_i|\cap_{j=1}^{i-1}Aj)$

The law of total probability: The probability of an event can be written up as a Sum of the probability of co-occurring events.

$A_1, A_2, ..., A_n \in F, \enspace A_i \cap A_j = \emptyset \enspace \forall i \neq j, \enspace \cup_{i=1}^n A_i = \Omega \Rightarrow P(B) = \sum_{i=1}^{n} P(B \cap A_i) = \sum_{i=1}^{n} P(B|A_i) \cdot P(A_i)$

Bayes rule: Finding the conditional probability of an event by knowing certain other probabilities.

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

Random Variable ( $X$ ): Is a function defined on the sample space. Most of the time it maps outcomes, events to numbers. (The codomain might be continuous or discrete)

$X: \Omega \to \mathbb{N}$

Expected value ( $E(X)$ ): The long-run avereage value of repetitively carrying out an experiment (the same as mean).

$E(X) = \sum_{x\in X} x \cdot P(x)$

Variance ( $Var(X)$ ): The average of the squared differences from the mean.

$Var(X) = \sum_{x\in X} (x - E(X))^2$

Standard deviation ( $\sigma(X)$ ): Is a measure for quantifying how spread the dataset is.

$\sigma(X) = \sqrt{Var(X)}$

Covariance ( $Cov(X, Y)$ ): Is a measure for quantifying how two Random Variables vary together.

$Cov(X, Y) = \sum_{x\in X} \sum_{y\in Y} (x-E(X))\cdot (y-E(Y))$

Correlation ( $Corr(X, Y)$ ): Is a measure for quantifying how well two Random Variables are linearly related.

$Corr(X, Y) = \frac{Cov(X, Y)}{\sigma(X) \cdot \sigma(Y)}$

Note:

Bayes’ rule proof: By Conditional probability definition:

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

Proof of Expected Value = Mean:

$\mu = \sum_{i=1}^n \frac{x_i}{n} = \frac{x_1}{n} + \frac{x_2}{n} + ... + \frac{x_n}{n}$

Let’s say, that some of the observations have the same value (e.g.: $x_1 = x_2$ ), then we count the frequency $f_i$ for each unique observation value $y_i \in Y$ . Then:

$\mu = y_1 \cdot \frac{f_1}{n} + y_2\cdot \frac{f_2}{n} + ... + y_i\cdot \frac{f_i}{n} = y_1 \cdot P(y_1) + ... + y_i \cdot P(y_i) = E(X)$ $\mu = \sum_{y_i \in Y} y_i \cdot \frac{f_i}{n} = \sum_{y_i \in Y} y_i \cdot P(y_i) = E(X)$ You can find appendices for this algorithm here:

Examples

You can find the corresponding scripts (if applicable), here:

Table of contents:

WIP