💡 A discrete probability space is defined by the sample space/possibility space $\Omega =\{{\omega }_1,{\omega }_2,\dots \}$ of elementary events. An (elementary-) probability $\mathrm{Pr}[{\omega }_i]$ is assigned to every elementary event ${\omega }_i$, where we require $0\le \mathrm{Pr}[{\omega }_i]\le 1$ and

$$\sum _{\omega \in \Omega }\mathrm{Pr}[\omega ]=1.$$

A set $E\subseteq \Omega$ is called an event. The probability $\mathrm{Pr}[E]$ of an event is defined by

$$\mathrm{Pr}[E]=\sum _{\omega \in E}\mathrm{Pr}[\omega ].$$

If $E$ is an event, then we define $\bar{E}=\Omega \setminus E$ as the complementary event of $E$.

📌 For events $A,B$ the following hold:

1. $\mathrm{Pr}[\varnothing ]=0,\mathrm{Pr}[\Omega ]=1$
2. $0\le \mathrm{Pr}[A]\le 1$
3. $\mathrm{Pr}[\bar{A}]=1-\mathrm{Pr}[A]$
4. If $A\subseteq B$, then it follows that $\mathrm{Pr}[A]\le \mathrm{Pr}[B].$

📖 (Addition theorem).

If the events $A_1,\dots ,A_n$ are pairwise disjoint (i.e., if it holds for all pairs $i\ne j$ that $A_i\cap A_j=\varnothing$), then it holds that

$$\mathrm{Pr}\left[\bigcup _{i=1}^n{A}_i\right]=\sum _{i=1}^n\mathrm{Pr}[A_i].$$

For an infinite set of disjoint events $A_1,A_2,\dots$ it holds analogously

$$\mathrm{Pr}\left[\bigcup _{i=1}^{\infty }{A}_i\right]=\sum _{i=1}^{\infty }\mathrm{Pr}[A_i].$$

📖 (The sieve formula, Inclusion-Exclusion principle).

For events $A_1,\dots ,A_n(n\ge 2)$ the following holds:

$$\begin{array}{rl}\mathrm{Pr}\left[\bigcup _{i=1}^n{A}_i\right]& =\sum _{l=1}^n(-1{)}^{l+1}\sum _{1\le i_1<\dots <i_l\le n}\mathrm{Pr}[A_{i_1}\cap \dots \cap A_{i_l}]\\ & =\sum _{i=1}^n\mathrm{Pr}[A_i]-\sum _{1\le i_1<i_2\le n}\mathrm{Pr}[A_{i_1}\cap A_{i_2}]\\ & +\sum _{1\le i_1<i_2<i_3\le n}\mathrm{Pr}[A_{i_1}\cap A_{i_2}\cap A_{i_3}]-\dots \\ & +(-1{)}^{n+1}\cdot \mathrm{Pr}[A_1\cap \dots \cap A_n].\end{array}$$

📎 (Boole’s Inequality, Union Bound).

For events $A_1,\dots ,A_n$ the following holds:

$$\mathrm{Pr}\left[\bigcup _{i=1}^n{A}_i\right]\le \sum _{i=1}^n\mathrm{Pr}[A_i].$$

Analogously, the following holds for an infinite sequence of events $A_1,A_2,\dots$:

$$\mathrm{Pr}\left[\bigcup _{i=1}^{\infty }{A}_i\right]\le \sum _{i=1}^{\infty }\mathrm{Pr}[A_i].$$

💡 (Principle of Laplace).

If nothings indicates otherwise, we assume that all elementary events are equally likely.

Therefore, $\mathrm{Pr}[\omega ]=\frac{1}{|\Omega |}$ for all elementary events $\omega$.

It immediately follows for an arbitrary event $E$ that

$$\mathrm{Pr}[E]=\frac{|E|}{|\Omega |}.$$

We say, the event of the modeled experiment on $\Omega$ is uniformly distributed or equally distributed.

💡 In an information-theoretical sense such a probability space ($\mathrm{Pr}[\omega ]=\frac{1}{|\Omega |}$ for all $\omega \in \Omega$) has the largest-possible entropy. Every deviation from uniform probability distribution requires that we put more information into the model (and therefore decrease entropy).

💡 Let $A$ and $B$ be events with $\mathrm{Pr}[B]>0$. The conditional probability $\mathrm{Pr}[A|B]$ of $A$ given $B$ is defined by

$$\mathrm{Pr}[A|B]=\frac{\mathrm{Pr}[A\cap B]}{\mathrm{Pr}[B]}.$$

💡 The conditional probabilities of the form $\mathrm{Pr}[\cdot |B]$ form a new probability space over $\Omega$ for an arbitrary event $B\subseteq \Omega$ with $\mathrm{Pr}[B]>0$.

The probabilities of the elementary events ${\omega }_i$ are calculated through $\mathrm{Pr}[{\omega }_i|B]$. Then

$$\sum _{\omega \in \Omega }\mathrm{Pr}[\omega |B]=\sum _{\omega \in \Omega }\frac{\mathrm{Pr}[\omega \cap B]}{\mathrm{Pr}[B]}=\sum _{\omega \in B}\frac{\mathrm{Pr}[\omega ]}{\mathrm{Pr}[B]}=\frac{\mathrm{Pr}[B]}{\mathrm{Pr}[B]}=1.$$

the definition of a discrete probability space is still fulfilled and therefore all rules for probabilities still apply to conditional probabilities.

📖 (Multiplication theorem).

Let the events $A_1,\dots ,A_n$ be given. If $\mathrm{Pr}[A_1\cap \dots \cap A_n]>0$ then the following holds:

$$\mathrm{Pr}[A_1\cap \dots \cap A_n]=\mathrm{Pr}[A_1]\cdot \mathrm{Pr}[A_2|A_1]\cdot \mathrm{Pr}[A_3|A_1\cap A_2]\cdot \dots \cdot \mathrm{Pr}[A_1\cap \dots \cap A_{n-1}].$$

📖 (Law of total probability).

Let the events $A_1,\dots ,A_n$ be pairwise disjoint and let $B\subseteq A_1\cup \dots \cup A_n.$ Then it follows that

$$\mathrm{Pr}[B]=\sum _{i=1}^n\mathrm{Pr}[B|A_i]\cdot \mathrm{Pr}[A_i].$$

Analogously, for pairwise disjoint events $A_1,A_2,\dots$ with $B\subseteq {\bigcup }_{i=1}^{\infty }{A}_i$ it follows that

$$\mathrm{Pr}[B]=\sum _{i=1}^{\infty }\mathrm{Pr}[B|A_i]\cdot \mathrm{Pr}[A_i].$$

📖 (Bayes’ theorem).

Let the events $A_1,\dots ,A_n$ be pairwise disjoint. Furthermore, let $B\subseteq A_1\cup \dots \cup A_n$ be an event with $\mathrm{Pr}[B]>0$. Then it holds for an arbitrary $i=1,\dots ,n$ that

$$\mathrm{Pr}[A_i|B]=\frac{\mathrm{Pr}[A_i\cap B]}{\mathrm{Pr}[B]}=\frac{\mathrm{Pr}[B|A_i]\cdot \mathrm{Pr}[A_i]}{{\sum }_{j=1}^n\mathrm{Pr}[B|A_j]\cdot \mathrm{Pr}[A_j]}.$$

Analogously, for pairwise disjoint events $A_1,A_2,\dots$ with $B\subseteq {\bigcup }_{i=1}^{\infty }{A}_i$ it holds that

$$\mathrm{Pr}[A_i|B]=\frac{\mathrm{Pr}[A_i\cap B]}{\mathrm{Pr}[B]}=\frac{\mathrm{Pr}[B|A_i]\cdot \mathrm{Pr}[A_i]}{{\sum }_{j=1}^{\infty }\mathrm{Pr}[B|A_j]\cdot \mathrm{Pr}[A_j]}.$$

💡 The events $A$ and $B$ are called independent if

$$\mathrm{Pr}[A\cap B]=\mathrm{Pr}[A]\cdot \mathrm{Pr}[B]$$

💡 The events $A_1,\dots ,A_n$ are called independent if it holds for all subsets $I\subseteq \{1,\dots ,n\}$ with $I=\{i_1,\dots ,i_k\}$ that

$$\mathrm{Pr}[A_{i_1}\cap \dots \cap A_{i_k}]=\mathrm{Pr}[A_{i_1}]\cdot \dots \cdot \mathrm{Pr}[A_{i_k}].$$

An infinite family of events $A_i$ with $i\in \mathbb{N}$ is called independent if the above condition is met for all finite subsets $I\subseteq \mathbb{N}$.

📌 The events $A_1,\dots ,A_n$ are independent if and only if it holds for all $(s_1,\dots ,s_n)\in \{0,1{\}}^n$ that

$$\mathrm{Pr}[A_1^{s_1}\cap \dots \cap A_n^{s_n}]=\mathrm{Pr}[A_1^{s_1}]\cdot \dots \cdot \mathrm{Pr}[A_n^{s_n}],$$

where $A_i^0={\bar{A}}_i$ and $A_i^1=A_i$.

📌 Let $A$, $B$ and $C$ be independent events. Then $A\cap B$ and $C$ respectively $A\cup B$ and $C$ independent.

💡 A random variable is a transformation $\mathrm{X}:\Omega ⟶\mathbb{R}$, where $\Omega$ is the possibility space of a probability space.

💡 In discrete probability spaces the codomain of a random variable

$$W_{\mathrm{X}}=\mathrm{X}(\Omega )=\{\chi \in \mathbb{R}|\exists \omega \in \Omega \mathrm{X}(\omega )=\chi \}$$

is in all cases finite or countably infinite, depending on $\Omega$ being finite or countably infinite.

💡 When researching a random variable $\mathrm{X}$ one is interested in the probabilities with which $\mathrm{X}$ assumes a specific value. For $W_{\mathrm{X}}=\{{\chi }_1,\dots ,{\chi }_n\}$ respectively $W_{\mathrm{X}}=\{{\chi }_1,{\chi }_2,\dots \}$ for an arbitrary $1\le i\le n$ respectively ${\chi }_i\in \mathbb{N}$ we regard the event ${\mathrm{X}}^{-1}({\chi }_i)=\{\omega \in \Omega |\mathrm{X}(\omega )={\chi }_i\}$. We abbreviate ${\mathrm{X}}^{-1}({\chi }_i)$ as $"\mathrm{X}={\chi }_i"$.

Therefore, we can define

$$\mathrm{Pr}[\mathrm{X}\le {\chi }_i]=\sum _{\chi \in W_{\mathrm{X}}|\chi \le {\chi }_i}\mathrm{Pr}[\mathrm{X}=\chi ]=\mathrm{Pr}[\{\omega \in \Omega |\mathrm{X}(\omega )\le {\chi }_i\}].$$

💡 The function

$$\begin{array}{rl}{f}_{\mathrm{X}}:\mathbb{R}& ⟶[0,1]\\ \chi & ⟼\mathrm{Pr}[\mathrm{X}=\chi ]\end{array}$$

is called the density (function) of $\mathrm{X}$.

💡 The function

$$\begin{array}{rl}{F}_{\mathrm{X}}:\mathbb{R}& ⟶[0,1]\\ \chi & ⟼\mathrm{Pr}[\mathrm{X}\le \chi ]=\sum _{{\chi }^{\prime }\in W_{\mathrm{X}}|{\chi }^{\prime }\le \chi }\mathrm{Pr}[\mathrm{X}={\chi }^{\prime }]\end{array}$$

is called the distribution (function) of $\mathrm{X}$.

💡 For a random variable $\mathrm{X}$ we define the expected value $\mathbb{E}[\mathrm{X}]$ as

$$\mathbb{E}[\mathrm{X}]=\sum _{\chi \in W_{\mathrm{X}}}\chi \cdot \mathrm{Pr}[\mathrm{X}=\chi ]$$

if that sum converges absolutely. Otherwise the expected value is said to be undefined.

📌 If $\mathrm{X}$ is a random variable then the following holds:

$$\mathbb{E}[\mathrm{X}]=\sum _{\omega \in \Omega }\mathrm{X}(\omega )\cdot \mathrm{Pr}[\omega ].$$

📖 Let $\mathrm{X}$ a random variable with $W_{\mathrm{X}}\subseteq {\mathbb{N}}_0$. Then it holds that

$$\mathbb{E}[\mathrm{X}]=\sum _{i=1}^{\infty }\mathrm{Pr}[\mathrm{X}\le i].$$

💡 Conditional Random Variables

Let $\mathrm{X}$ be a random variable and $A$ an event with $\mathrm{Pr}[A]>0$. By $\mathrm{X}|A$ we denote that we calculate probabilities with which the random variable $\mathrm{X}$ assumes specific values with respect to the on $A$ conditional probabilities. It thus holds that

$$\mathrm{Pr}[(\mathrm{X}|A)\le \chi ]=\mathrm{Pr}[\mathrm{X}\le \chi |A]=\frac{\mathrm{Pr}[\{\omega \in A|\mathrm{X}(\omega )\le \chi \}]}{\mathrm{Pr}[A]}$$

📖 Let $\mathrm{X}$ be a random variable. For pairwise disjoint events $A_1,\dots ,A_n$ with $A_1\cup \dots \cup A_n=\Omega$ and $\mathrm{Pr}[A_1],\dots ,\mathrm{Pr}[A_n]>0$ it holds that

$$\mathbb{E}[\mathrm{X}]=\sum _{i=1}^n\mathbb{E}[\mathrm{X}|A_i]\cdot \mathrm{Pr}[A_i].$$

For pairwise disjoint events $A_1,A_2,\dots$ with ${\bigcup }_{i=1}^{\infty }{A}_k=\Omega$ and $\mathrm{Pr}[A_1],\mathrm{Pr}[A_2],..>0$ it holds analogously that

$$\mathbb{E}[\mathrm{X}]=\sum _{i=1}^{\infty }\mathbb{E}[\mathrm{X}|A_i]\cdot \mathrm{Pr}[A_i].$$

💡 Linearity of the Expected Value

Assume, we have defined $n$ random variables:

$${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n:\Omega ⟶\mathbb{R}.$$

For an $\omega \in \Omega$ we thus receive $n$ real numbers ${\mathrm{X}}_1(\omega ),\dots ,{\mathrm{X}}_n(\omega )$. When we define a function $f:{\mathbb{R}}^n⟶\mathbb{R}$ we immediately see that the concatenation $f({\mathrm{X}}_1,\dots ,{\mathrm{X}}_n)$ in turn is also a random variable, for it holds that:

$$f({\mathrm{X}}_1,\dots ,{\mathrm{X}}_n):\Omega ⟶\mathbb{R}.$$

This holds for arbitrary functions $f:{\mathbb{R}}^n⟶\mathbb{R}$, in particular for affine linear functions:

$$\begin{array}{rl}f:{\mathbb{R}}^n& ⟶\mathbb{R}\\ ({\chi }_1,\dots ,{\chi }_n)& ⟼a_1{\chi }_1+\dots +a_n{\chi }_n+b,\end{array}$$

where $a_1,\dots ,a_n,b\in \mathbb{R}$ are arbitrary real numbers. In this case we usually denote the random variable $f({\mathrm{X}}_1,\dots ,{\mathrm{X}}_n)$ explicitly as

$$\mathrm{X}=a_1{\mathrm{X}}_1+\dots +a_n{\mathrm{X}}_n+b.$$

📖 (Linearity of the Expected Value).

For random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ and $\mathrm{X}=a_1{\mathrm{X}}_1+\dots +a_n{\mathrm{X}}_n+b$ with $a_1,..,a_n,b\in \mathbb{R}$ it holds that

$$\mathbb{E}[\mathrm{X}]=a_1\mathbb{E}[\mathrm{X}]+\dots +a_n\mathbb{E}[{\mathrm{X}}_n]+b.$$

💡 For an event $A\subseteq \Omega$ the corresponding indicator variable ${\mathrm{X}}_A$ is defined by:

$${\mathrm{X}}_A(\omega )=\{\begin{array}{ll}1,& \text{if}\omega \in A,\\ 0,& \text{else}.\end{array}$$

For the expected value of ${\mathrm{X}}_A$ it holds that: $\mathbb{E}[{\mathrm{X}}_A]=\mathrm{Pr}[A]$.

💡 For a random variable $\mathrm{X}$ with $\mu =\mathbb{E}[X]$ we define the variance $\text{Var}[\mathrm{X}]$ as

$$\text{Var}[\mathrm{X}]=\mathbb{E}[(\mathrm{X}-\mu {)}^2]=\sum _{\chi \in W_{\mathrm{X}}}(\chi -\mu {)}^2\cdot \mathrm{Pr}[\mathrm{X}=\chi ].$$

The quantity $\sigma =\sqrt{\text{Var}[\mathrm{X}]}$ is called the standard deviation of $\mathrm{X}$.

📖 For an arbitrary random variable $\mathrm{X}$ it holds that

$$\text{Var}[\mathrm{X}]=\mathbb{E}[{\mathrm{X}}^2]-\mathbb{E}[\mathrm{X}{]}^2.$$

📖 For an arbitrary random variable $\mathrm{X}$ and $a,b\in \mathbb{R}$ it holds that

$$\text{Var}[a\cdot \mathrm{X}+b]=a^2\cdot \text{Var}[\mathrm{X}].$$

💡 For a random variable $\mathrm{X}$ we call $\mathbb{E}[{\mathrm{X}}^k]$ the $\ast k$-th moment* and $\mathbb{E}[(\mathrm{X}-\mathbb{E}[\mathrm{X}]{)}^k]$ the $k$-th central moment.

The expected value is therefore identical to the first moment, and the variance identical to the second central moment.

💡 Recall the probability density function $f_{\mathrm{X}}$ and the probability distribution function $F_{\mathrm{X}}$:

$$\begin{array}{rl}{f}_{\mathrm{X}}:\mathbb{R}& ⟶[0,1]\\ \chi & ⟼\mathrm{Pr}[\mathrm{X}=\chi ]=\mathrm{Pr}[\{\omega |\mathrm{X}(\omega )=\chi \}].\\ F_{\mathrm{X}}:\mathbb{R}& ⟶[0,1]\\ \chi & ⟼\mathrm{Pr}[\mathrm{X}\le \chi ]=\mathrm{Pr}[\{\omega |\mathrm{X}(\omega )\le \chi \}].\end{array}$$

💡 A random variable $\mathrm{X}$ with $W_{\mathrm{X}}=\{0,1\}$ and density

$$f_{\mathrm{X}}(\chi )=\{\begin{array}{ll}p& \text{for}\chi =1,\\ 1-p& \text{for}\chi =0,\\ 0& \text{else}\end{array}$$

is called Bernoulli distributed. The parameter $p$ is called the probability of success of the Bernoulli distribution.

If a random variable $\mathrm{X}$ is Bernoulli distributed with parameter $p$, then it is denoted by

$$\mathrm{X}\sim \text{Bernoulli}(p).$$

For a Bernoulli distributed random variable $\mathrm{X}$ the following hold:

$$\mathbb{E}[\mathrm{X}]=p\text{and}\text{Var}[\mathrm{X}]=p(1-p).$$

💡 A random variable $\mathrm{X}$ with $W_{\mathrm{X}}=\{0,1,\dots ,n\}$ and density

$$f_{\mathrm{X}}(\chi )=\{\begin{array}{ll}\left(\genfrac{}{}{0ex}{}{n}{\chi }\right)p^{\chi }(1-p{)}^{n-\chi }& \text{for}\chi \in \{0,1,\dots ,n\},\\ 0& \text{else}\end{array}$$

is called binomially distributed. The parameter $n$ is called the number of trials, the parameter $p$ is called the probability of success of the binomial distribution.

If a random variable $\mathrm{X}$ is binomially distributed with parameters $n$ and $p$, then it is denoted by

$$\mathrm{X}\sim \text{Bin}(n,p).$$

For a binomially distributed random variable $\mathrm{X}$ the following hold:

$$\mathbb{E}[\mathrm{X}]=np\text{and}\text{Var}[\mathrm{X}]=np(1-p).$$

💡 A random variable $\mathrm{X}$ with density

$$f_{\mathrm{X}}=\{\begin{array}{ll}p(1-p{)}^{i-1}& \text{for}i\in \mathbb{N},\\ 0& \text{else}\end{array}$$

is called geometrically distributed. The parameter $p$ is called the probability of success of the geometric distribution.

If a random variable $\mathrm{X}$ is geometrically distributed with parameter $p$, then it is denoted by

$$\mathrm{X}\sim \text{Geo}(p).$$

For a geometrically distributed random variable $\mathrm{X}$ the following hold:

$$\mathbb{E}[\mathrm{X}]=\frac{1}{p}\text{and}\text{Var}[\mathrm{X}]=\frac{1-p}{p^2}.$$

📖 If $\mathrm{X}\sim \text{Geo}(p)$, then for all $s,t\in \mathbb{N}$ the following holds:

$$\mathrm{Pr}[\mathrm{X}\ge s+t|\mathrm{X}>s]=\mathrm{Pr}[\mathrm{X}\ge t].$$

💡 Let $Z$ be the random variable that counts how often we have to repeat an experiment with probability of success $p$ until the $n$-th success. For $n=1$, $Z\sim \text{Geo}(p)$. For $n\ge 2$, $Z$ is called negatively binomially distributed with order $n$.

The density of $Z$ is

$$f_Z(z)=\left(\genfrac{}{}{0ex}{}{z-1}{n-1}\right)\cdot p^n(1-p{)}^{z-n}.$$

Let ${\mathrm{X}}_i$ denote the number of experiments strictly after the $(i-1)$-st success up until (including) the $i$-th success. Then, each of the ${\mathrm{X}}_i$ is geometrically distributed with parameter $p$.

If a random variable $Z$ is negatively binomially distributed with parameters $n$ and $p$, then it is denoted by

$$Z\sim \text{NB}(n,p).$$

Thus, by linearity of the expected value, it holds for the expected value $\mathbb{E}[Z]$ that

$$\mathbb{E}[Z]=\sum _{i=1}^n\mathbb{E}[{\mathrm{X}}_i]=\frac{n}{p}.$$

💡 A random variable $\mathrm{X}$ with density

$$f_{\mathrm{X}}=\{\begin{array}{ll}\frac{e^{-\lambda }{\lambda }^i}{i!}& \text{for}i\in {\mathbb{N}}_0,\\ 0& \text{else}\end{array}$$

is called Poisson distributed. The parameter $\lambda$ is equal to the mean and variance of the Poisson distribution.

If a random variable $\mathrm{X}$ is Poisson distributed with parameter $\lambda$, then it is denoted by

$$\mathrm{X}\sim \text{Po}(\lambda ).$$

For a Poisson distributed random variable $\mathrm{X}$ the following hold:

$$\mathbb{E}[\mathrm{X}]=\text{Var}[\mathrm{X}]=\lambda .$$

💡 The binomial distribution $\text{Bin}(n,\frac{\lambda }{n})$ converges towards the Poisson distribution $\text{Po}(\lambda )$ for $n\to \infty$.

💡 We are interested in random variables $\mathrm{X}$ and $Y$ and probabilities of the form

$$\mathrm{Pr}[\mathrm{X}=\chi ,Y=y]=\mathrm{Pr}[\{\omega \in \Omega |\mathrm{X}(\omega )=\chi ,Y(\omega )=y\}].$$

💡 The function

$$f_{\mathrm{X},Y}=\mathrm{Pr}[\mathrm{X}=\chi ,Y=y]$$

is called joint density of the random variables $\mathrm{X}$ and $Y$.

If the joint density is given one can extract the density of the random variables themselves using

$$f_{\mathrm{X}}(\chi )=\sum _{y\in W_Y}{f}_{\mathrm{X},Y}(\chi ,y)\text{respectively}{f}_Y(y)=\sum _{x\in W_{\mathrm{X}}}{f}_{\mathrm{X},Y}(\chi ,y).$$

The functions $f_{\mathrm{X}}$ and $f_Y$ are called marginal densities.

💡 The function

$$\begin{array}{rl}{F}_{\mathrm{X},Y}(\chi ,y)& =\mathrm{Pr}[\mathrm{X}\le \chi ,Y\le y]=\mathrm{Pr}[\{\omega \in \Omega |\mathrm{X}(\omega )\le \chi ,Y(\omega )\le y\}]\\ & =\sum _{{\chi }^{\prime }\le \chi }\sum _{y^{\prime }\le y}{f}_{\mathrm{X},Y}({\chi }^{\prime },y^{\prime }).\end{array}$$

is called joint distribution of the random variables $\mathrm{X}$ and $Y$.

If the joint distribution is given one can extract the distribution of the random variables themselves using

$$F_{\mathrm{X}}(\chi )=\sum _{{\chi }^{\prime }\le \chi }{f}_{\mathrm{X}}({\chi }^{\prime })=\sum _{{\chi }^{\prime }\le \chi }\sum _{y\in W_Y}{f}_{\mathrm{X},Y}({\chi }^{\prime },y).$$

The functions $F_{\mathrm{X}}$ and $F_Y$ are called marginal distributions.

💡 Random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ are called independent, if and only if it holds for all $({\chi }_1,\dots ,{\chi }_n)\in W_{{\mathrm{X}}_1}\times \dots \times W_{{\mathrm{X}}_n}$ that

$$\mathrm{Pr}[{\mathrm{X}}_1={\chi }_1,\dots ,{\mathrm{X}}_n={\chi }_n]=\mathrm{Pr}[{\mathrm{X}}_1={\chi }_1]\cdot \dots \cdot \mathrm{Pr}[{\mathrm{X}}_n={\chi }_n].$$

📌 For independent random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ and arbitrary sets $S_1,\dots ,S_n$ with $S_i\subseteq W_{\mathrm{X}}$ it holds that

$$\mathrm{Pr}[{\mathrm{X}}_1\in S_1,\dots ,{\mathrm{X}}_n\in S_n]=\mathrm{Pr}[{\mathrm{X}}_1\in S_1]\cdot \dots \cdot \mathrm{Pr}[{\mathrm{X}}_n\in S_n].$$

📎 For independent random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ and the set $I=\{i_1,\dots ,i_k\}\subseteq [n]$, then ${\mathrm{X}}_{i_1},\dots ,{\mathrm{X}}_{i_k}$ are also independent.

📖 Let $f_1,\dots ,f_n$ be real-values functions ($f_i:\mathbb{R}⟶\mathbb{R}$ for $i=1,\dots ,n$). If the random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ are independent then so are $f_1({\mathrm{X}}_1),\dots ,f_n({\mathrm{X}}_n)$.

📖 For two independent random variables $\mathrm{X}$ and $Y$ let $Z=\mathrm{X}+Y$. It holds that

$$f_Z(z)=\sum _{\chi \in W_{\mathrm{X}}}{f}_{\mathrm{X}}(\chi )\cdot f_Y(z-\chi ).$$

💡 The expression ${\sum }_{\chi \in W_{\mathrm{X}}}{f}_{\mathrm{X}}(\chi )\cdot f_Y(z-\chi )$ is called convolution, analogously to the corresponding terms for power series.

📖 (Linearity of the Expected Value).

For random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ and $\mathrm{X}=a_1{\mathrm{X}}_1+\dots +a_n{\mathrm{X}}_n$ with $a_1,\dots ,a_n\in \mathbb{R}$ it holds that

$$\mathbb{E}[\mathrm{X}]=a_1\mathbb{E}[{\mathrm{X}}_1]+\dots +a_n\mathbb{E}[{\mathrm{X}}_n].$$

📖 (Multiplicativity of the Expected Value).

For independent random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ it holds that

$$\mathbb{E}[{\mathrm{X}}_1\cdot \dots \cdot {\mathrm{X}}_n]=\mathbb{E}[{\mathrm{X}}_1]\cdot \dots \cdot \mathbb{E}[{\mathrm{X}}_n].$$

📖 For independent random variables ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ and $\mathrm{X}={\mathrm{X}}_1+\dots +{\mathrm{X}}_n$ it holds that

$$\text{Var}[\mathrm{X}]=\text{Var}[{\mathrm{X}}_1]+\dots +\text{Var}[{\mathrm{X}}_n].$$

📖 (Wald’s Identity).

Let $N$ and $\mathrm{X}$ be two independent random variables, where $W_N\subseteq \mathbb{N}$ holds for the codomain of $N$. Furthermore, let

$$Z=\sum _{i=1}^N{\mathrm{X}}_i,$$

where ${\mathrm{X}}_1,{\mathrm{X}}_2,\dots$ are independent copies of $\mathrm{X}$. Then the following holds:

$$\mathbb{E}[Z]=\mathbb{E}[N]\cdot \mathbb{E}[\mathrm{X}].$$

📖 (Markov’s Inequality).

Let $\mathrm{X}$ be a random variable, that only assumes non-negative values. Then it holds for all $t\in \mathbb{R}$ with $t>0$ that

$$\mathrm{Pr}[\mathrm{X}\ge t]\le \frac{\mathbb{E}[\mathrm{X}]}{t}.$$

Or equivalently: $\mathrm{Pr}[\mathrm{X}\ge t\cdot \mathbb{E}[\mathrm{X}]]\le \frac{1}{t}$.

📖 (Chebyshev’s Inequality).

Let $\mathrm{X}$ be a random variable and $t\in \mathbb{R}$ with $t>0$. It then holds that

$$\mathrm{Pr}[|\mathrm{X}-\mathbb{E}[\mathrm{X}]|\ge t]\le \frac{\text{Var}[\mathrm{X}]}{t^2}.$$

Or equivalently: $\mathrm{Pr}[|\mathrm{X}-\mathbb{E}[\mathrm{X}]|\ge t\sqrt{\text{Var}[\mathrm{X}]}]\le \frac{1}{t^2}.$

📖 (Chernoff-Bounds).

Let ${\mathrm{X}}_1,\dots ,{\mathrm{X}}_n$ be independent Bernoulli distributed random variables with $\mathrm{Pr}[{\mathrm{X}}_i=1]=p_i$ and $\mathrm{Pr}[{\mathrm{X}}_i=0]=1-p_i$.

For $\mathrm{X}={\sum }_{i=1}^n{\mathrm{X}}_i:$

1. $\mathrm{Pr}[\mathrm{X}\ge (1+\delta )\mathbb{E}[\mathrm{X}]]\le e^{-\frac{1}{3}{\delta }^2\mathbb{E}[\mathrm{X}]}$ for all $0<\delta \le 1$,
2. $\mathrm{Pr}[\mathrm{X}\le (1-\delta )\mathbb{E}[\mathrm{X}]]\le e^{-\frac{1}{2}{\delta }^2\mathbb{E}[\mathrm{X}]}$ for all $0<\delta \le 1$,
3. $\mathrm{Pr}[\mathrm{X}\ge t]\le 2^{-t}$ for $t\ge 2e\mathbb{E}[\mathrm{X}]$.