1 Discrete Probability

1.1 Probability Spaces and Event

Discrete Probability Space

A discrete probability space is a pair $\mathcal{P} = (\Omega, p)$ consisting of:

• A non-empty finite set $\Omega$, called the sample space, whose elements represent all possible outcomes of an experiment.
• A function $p : \Omega \to [0, 1]$, called the probability mass function, which assigns probabilities to outcomes and satisfies $\sum_{\omega \in \Omega} p(\omega) = 1$. That is, the total probability of all outcomes is 1.

Event

An event $A$ is a subset of $\Omega$ ($A \subseteq \Omega$), and its probability is defined as

$$\begin{equation*} Pr[A] := \sum_{\omega \in A} p(\omega). \end{equation*}$$

1.2 Asymptotic Notations

Big-$\mathcal{O}$ notation

Let $f,g : \mathbb{N} \to \mathbb{R}$ be functions defined on $\mathbb{N}$. We write $f(n) = \mathcal{O}(g(n))$ if there exist constants $C > 0$ and $N \in \mathbb{N}$ such that

$$\begin{equation*} |f(n)| \le Cg(n), \quad \forall n \ge N. \end{equation*}$$ $$\begin{equation*} \mathcal{O}(g) := \{f : \exists C > 0, \exists N \in \mathbb{N} \text{ s.t. } |f(n)| \le Cg(n), \text{ for all } n \ge N\}. \end{equation*}$$

Theorem 1.1. Let $f, g : \mathbb{N} \to \mathbb{R}$ and $c \in \mathbb{R}$. If $f(n), g(n) \ge 0$ for all $n$, then

$$\begin{align*} f(n) &= \mathcal{O}(f(n)) \\ c \cdot f(n) &= \mathcal{O}(f(n)) \\ \mathcal{O}(\mathcal{O}(f(n))) &= \mathcal{O}(f(n)) \\ \mathcal{O}(f(n)) + \mathcal{O}(g(n)) &= \mathcal{O}(f(n) + g(n)) \\ \mathcal{O}(f(n)) + \mathcal{O}(g(n)) &= \mathcal{O}(\max\{f(n), g(n)\}) \\ \mathcal{O}(f(n)) \cdot \mathcal{O}(g(n)) &= \mathcal{O}(f(n) \cdot g(n)) \\ \mathcal{O}(f(n)g(n)) &= f(n) \cdot \mathcal{O}(g(n)). \\ \end{align*}$$

Big-$\mathcal{O}$ notation over a domain

Let $f,g : D \to \mathbb{R}$ be functions defined on a domain $D$. We say that $f(n) = \mathcal{O}(g(n))$ for all $n \in D$ if there exists a constant $C > 0$ such that

$$\begin{equation*} |f(n)| \le Cg(n), \quad \forall n \in D. \end{equation*}$$

Big-$\mathcal{O}$ notation for multivariate functions

Let $f,g : \mathbb{N}^d \to \mathbb{R}$ be functions defined on $\mathbb{N}^d$. We write

$$\begin{equation*} f(n_1,\dots,n_d) = \mathcal{O}(g(n_1,\dots,n_d)) \end{equation*}$$

if there exist constants $C > 0$ and $N \in \mathbb{N}$ such that

$$\begin{equation*} |f(n_1,\dots,n_d)| \le Cg(n_1,\dots,n_d), \quad \forall n_1,\dots,n_d \ge N. \end{equation*}$$

Big-$\mathcal{O}$ notation for $x \to 0$

Let $f,g : \mathbb{R} \to \mathbb{R}$ be functions defined on $\mathbb{R}$. We say that $f(x) = \mathcal{O}(g(x))$ as $x \to 0$ if there exist constants $C > 0$ and $\delta > 0$ such that

$$\begin{equation*} |f(x)| \le Cg(x), \quad \forall x \in \mathbb{R} \text{ with } 0 < |x| < \delta. \end{equation*}$$

Big-$\mathcal{O}$ notation defined using $\limsup$

Let $f, g : \mathbb{N} \to \mathbb{R}$, where $g(n) > 0$ for all sufficiently large $n$. We write $f(n) = \mathcal{O}(g(n))$ if

$$\begin{equation*} \limsup_{n \to \infty} \frac{|f(n)|}{g(n)} < +\infty. \end{equation*}$$

$\Omega, \Theta, \sim$ Notations

Let $f,g : \mathbb{N} \to \mathbb{R}$, where $g(n) > 0$ for all sufficiently large $n$.

• We write $f(n) = \Omega(g(n))$ if $\liminf\limits_{n \to \infty} \frac{|f(n)|}{g(n)} > 0$.
• We write $f(n) = \Theta(g(n))$ if $f(n) = \mathcal{O}(g(n))$ and $f(n) = \Omega(g(n))$.
• We write $f(n) \sim g(n)$ if $\lim\limits_{n \to \infty} \frac{|f(n)|}{g(n)} = 1$.

Little-$o$ and Little-$\omega$ Notations

Let $f,g : \mathbb{N} \to \mathbb{R}$, where $g(n) > 0$ for all sufficiently large $n$.

• We write $f(n) = o(g(n))$ if $\lim\limits_{n \to \infty} \frac{|f(n)|}{g(n)} = 0$.
• We write $f(n) = \omega(g(n))$ if $\lim\limits_{n \to \infty} \frac{|f(n)|}{g(n)} = +\infty$.

Theorem 1.2. Let $f,g : \mathbb{N} \to \mathbb{R}$ with $g(n) > 0$ for all $n \ge 1$. If

$$\begin{equation*} f(k) = \mathcal{O}(g(k)) \quad \text{as } k \to \infty, \end{equation*}$$

then

$$\begin{equation*} \sum_{k=1}^n f(k) = \mathcal{O}\left(\sum_{k=1}^n g(k)\right) \quad \text{as } n \to \infty. \end{equation*}$$

Theorem 1.3. Let $f,g : \mathbb{N}^2 \to \mathbb{R}$ with $g(m,n) > 0$ for all $m,n \ge 1$. If for some function $U(m) \ge 1$, we have

$$\begin{equation*} f(m,k) = \mathcal{O}(g(m,k)), \quad \text{for } 1 \le k \le U(m), \text{ as } m \to \infty, \end{equation*}$$

Then,

$$\begin{equation*} \sum_{k=1}^n f(m,k) = \mathcal{O}\left(\sum_{k=1}^n g(m,k)\right), \quad \text{for } 1 \le n \le U(m), \text{ as } m \to \infty. \end{equation*}$$