Acknowledgment: This document has been adapted from a similar review session for CS224W at Standard with substantial modifications by Yikun Zhang at Winter 2023 for CSE547 / STAT548 at UW. Some good references about writing proofs and basic probability theory include

• Greg Baker, “Introduction to Proofs”: https://www.cs.sfu.ca/~ggbaker/zju/math/proof.html.

• CS103 Winter 2016 at Stanford, “Guide to Proofs”: http://stanford.io/2dexnf9.

• Eugenia Cheng, “How to write proofs: a quick guide”: https://deopurkar.github.io/teaching/algebra1/cheng.pdf.

• “Quick tour to Basic Probability Theory”: http://snap.stanford.edu/class/cs224w-2015/recitation/prob_tutorial.pdf.

Proof Techniques

In this section, we will review several mathematical techniques for writing rigorous proofs. They are useful in the field of machine learning when we want to formally state and verify some theoretical properties of our proposed algorithms.

Terminologies

• Conjecture: a statement that we think might be true and can be proven (but hasn’t been proven yet).

• Theorem: a statement that has been rigorously proved.

• Proof: a valid argument for showing that a theorem is true.

• Premise: a condition for the theorem.

• Lemma: a small theorem (or preliminary result) that we need to prove the main theorems or results.

• Proposition: an intuitive theorem with a short proof.

• Corollary: a small theorem that follows from the main theorems or results.

Universal and Existence Statements

Universal statement: To prove a universal statement, like “the square of any odd number is odd”, it is always easy to show that this is true for some specific cases – for example, $3^2=9$, which is an odd number, and $5^2=25$, which is another odd number. However, to rigorously prove the statement, we must show that it works for all odd numbers, which is difficult as we cannot enumerate all of them.

On the contrary, if we want to disprove a universal statement, we only need to find one counterexample. For instance, if we want to disprove the statement “the square of any odd number is even”, it suffices to provide a specific example of an odd number whose square is not even. (For example, $3^2=9$, which is not an even number.)

As a summary, it leads to a rule of thumb for proving or disproving

• To prove a universal statement, we must show that it works for all cases.

• To disprove a universal statement, it suffices to find one counterexample.

Existence statement: The above rule of thumb is reversed when it comes to the “existence” statements. For example, if the statement to be proved is that “there exists at least one odd number whose square is odd, then proving the statement just requires finding one specific case, e.g., $3^2=9$, while disproving the statement would require showing that none of the odd numbers have squares that are odd.
Using the statement that “the square of any odd number is odd” as an example, we showcase how to prove a universal statement. To this end, we can pick an arbitrary odd number $x$ and try to prove the statement for that number. In the proof, we cannot assume anything about $x$ other than that it is an odd number. (In other words, we cannot simply set $x$ to be a specific number, like $3$, because then our proof might rely on special properties of the number $3$ that do not generalize to all odd numbers).

Special Proof Techniques

In addition to the technique of “picking an arbitrary element”, here are several other techniques commonly seen in proofs.

Proof by contrapositive: Consider the statement that

This is logically equivalent to the statement that

Therefore, if we want to prove statement (a), then it suffices to prove statement (b). Statement (b) is called the contrapositive of statement (a).

It is worth mentioning that statement (a) is not logically equivalent to the statement:

which is a converse of statement (a). This non-equivalence is also known as the fallacy of the converse.

Proof by contradiction: When proving a statement by contradiction, we would assume that our statement is not true and then derive a contradiction. This is a special case of proving by contrapositive (where our “if” is all of mathematics, and our “then” is the statement to be proved).

Proof by cases: Sometimes, it might be difficult to prove the entire theorem at once. As a result, we consider splitting the proof into several cases and proving the theorem separately for each case.

Proof by induction

We can prove a statement by induction when showing that the statement is valid for all positive integers $n$. Note that this is not the only situation in which we can use induction, and that induction is (usually) not the only way to prove a statement for all positive integers.

To use induction, we need to establish two results:

1. Base case: The statement is true when $n=1$.

2. Inductive step: If the statement is true for $n=k$, then the statement is also true for $n=k+1$.

It allows for an infinite chain of implications:

• The statement is true for $n=1$

• If the statement is true for $n=1$, then it is also true for $n=2$

• If the statement is true for $n=2$, then it is also true for $n=3$

• If the statement is true for $n=3$, then it is also true for $n=4$

• …

Together, these implications prove the statement for all positive integer values of $n$. (It does not prove the statement for non-integer values of $n$, or values of $n$ less than $1$.)

Strong induction

Strong induction (or complete induction) is a useful variant of induction. Here, the inductive step is changed to

1. Base case: The statement is true when $n=1$.

2. Inductive step: If the statement is true for all values of $1\le n<k$, then the statement is also true for $n=k$.

This also produces an infinite chain of implications:

• The statement is true for $n=1$

• If the statement is true for $n=1$, then it is true for $n=2$

• If the statement is true for both $n=1$ and $n=2$, then it is true for $n=3$

• If the statement is true for $n=1$, $n=2$, and $n=3$, then it is true for $n=4$

• …

Strong induction works on the same principle as weak induction, but is generally easier to prove theorems under its stronger induction hypothesis.

Useful Results in Calculus

The definition of the exponential function states that $$e^x=\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{x}{n})}^n.$$ In particular, it indicates that $\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{1}{n})}^n=e$ and $\underset{n\to \mathrm{\infty }}{lim}{(1-\frac{1}{n})}^n=\frac{1}{e}$.

Gamma Function and Stirling’s Formula: For $x\in (0,\mathrm{\infty })$, the Gamma function is $\mathrm{\Gamma }(x)={\int }_0^{\mathrm{\infty }}{t}^{x-1}{e}^{-t}dt$. While the exact value of $\mathrm{\Gamma }(x+1)$ is intractable for some $x\in (0,\mathrm{\infty })$, one can approximate $\mathrm{\Gamma }(x+1)$ when $x$ is large by Stirling’s formula: $$\underset{x\to \mathrm{\infty }}{lim}\frac{\mathrm{\Gamma }(x+1)}{(x/e{)}^x\sqrt{2\pi x}}=1.$$ This implies that when $x=n$ is a sufficiently large integer, we can approximate $\mathrm{\Gamma }(n+1)=n!$ by $\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$. More precisely, the following bound for $n!$ holds for all $n\ge 1$ rather than only asymptotically: $$\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n{e}^{\frac{1}{12n+1}}<n!<\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n{e}^{\frac{1}{12n}}.$$

Basic Probability Theory

Parts of this section are adapted from Chapter 1 of ¹ and lecture notes of STAT 512 by Professor Yen-Chi Chen’s ² and Professor Michael D. Perlman ³.

Probability Space

Sample space: The sample space $\mathrm{\Omega }$ is the collection of all possible outcomes of a random experiment. For example, if we roll a die with 6 faces, then the sample space will be $\{1,2,3,4,5,6\}$.

Events: A subset of the sample space, $A\subset \mathrm{\Omega }$, is called an event. For example, the event “the number from the above die is less than 4” can be represented by the subset $\{1,2,3\}$. The event “we roll a 6 from the above die” can be represented by the subset $\{6\}$.

$\sigma$-algebra: While the collection of all possible events (i.e., all subsets of $\mathrm{\Omega }$) is sometimes too large to define a valid probability space, we introduce the concept of $\sigma$-algebra $\mathcal{F}$ as a collections of subsets of $\mathrm{\Omega }$ satisfying:

1. (Nonemptiness) $\mathrm{\Omega }\in \mathcal{F}$ and $\mathrm{\varnothing }\in \mathcal{F}$, where $\mathrm{\varnothing }$ is the empty set.

2. (Closure under complementation) If $A\in \mathcal{F}$, then $A^c\in \mathcal{F}$.

3. (Closure under countable unions) If $A_1,A_2,...\in \mathcal{F}$, then ${\cup }_{i=1}^{\mathrm{\infty }}{A}_i\in \mathcal{F}$.

The subsets of $\mathrm{\Omega }$ in $\mathcal{F}$ are said to be measurable, and $(\mathrm{\Omega },\mathcal{F})$ is called measurable space.

Probability space: A probability measure (or probability function) $P$ is a mapping from $\sigma$-algebra $\mathcal{F}$ to real numbers in $[0,1]$ satisfying the following three axioms:

• $P(A)\ge 0$ for all $A\in \mathcal{F}$.

• $P(\mathrm{\Omega })=1$

• If $A_1,A_2,...\in \mathcal{F}$ are mutually exclusive events, then $P\left({\cup }_{i=1}^{\mathrm{\infty }}{A}_i\right)=\sum _{i=1}^{n}P(A_i)$.

The triplet $(\mathrm{\Omega },\mathcal{F},P)$ is called a probability space.

Properties of Probability Measure

Other useful properties of probability measure: Let $(\mathrm{\Omega },\mathcal{F},P)$ be a probability space.

• If $A\subset B$, then $P(A)\le P(B)$. More generally, $P(B\setminus A)=P(B)-P(A\cap B)$.

• For any $A\subset \mathcal{F}$ and some mutually exclusive $C_1,C_2,...$ with ${\cup }_{i=1}^{\mathrm{\infty }}{C}_i=\mathrm{\Omega }$, $$P(A)=\sum _{i=1}^{\mathrm{\infty }}P(A\cap C_i).$$

• Monotone continuity: For a sequence of subsets $\{A_n{\}}_{n=1}^{\mathrm{\infty }}\subset \mathcal{F}$ with $A_n\subset A_{n+1}$ for all $n$, we have that $P\left(\bigcup _{n=1}^{\mathrm{\infty }}{A}_n\right)=\underset{n\to \mathrm{\infty }}{lim}P(A_n)$. Similarly, if $A_n\supset A_{n+1}$ for all $n$, we have that $P\left(\bigcap _{n=1}^{\mathrm{\infty }}{A}_n\right)=\underset{n\to \mathrm{\infty }}{lim}P(A_n)$.

Conditional Probability, Independence, and Bayes’ Rule

Conditional Probability: For two events $A$ and $B$ with $P(B)>0$, the conditional probability of $A$ given $B$ is defined as: $$P(A|B)=\frac{P(A\cap B)}{P(B)}.$$ Notice that when the event $B$ is fixed, $P(\cdot |B)$ is another probability measure.

Independence and conditional independence: Two events $A$ and $B$ are independent if $$P(A|B)=P(A)\text{ or equivalently, }P(A\cap B)=P(A)\cdot P(B).$$ In other words, the occurrence of event $B$ does not affect the probability that event $A$ happens.

For three events $A,B,C$, we say that $A$ and $B$ are conditionally independent given $C$ if $$P(A\cap B|C)=P(A|C)\cdot P(B|C).$$ There are no implications between independence and conditional independence!

Bayes’ rule: Given an event $A$ and some mutually exclusive events $B_1,...,B_k$ with ${\cup }_{i=1}^k{B}_i=\mathrm{\Omega }$, the Bayes’ rule states that $$P(B_j|A)=\frac{P(B_j\cap A)}{P(A)}=\frac{P(A|B_j)P(B_j)}{\sum _{i=1}^{k}P(A|B_i)P(B_i)}\text{ for all }j=1,...,k.$$

Random variables

Random variable: Let $(\mathrm{\Omega },\mathcal{F},P)$ be a probability space. A random variable $X:\mathrm{\Omega }\to \mathbb{R}$ is a (measurable) function satisfying $$X^{-1}((-\mathrm{\infty },c]):=\{\omega \in \mathrm{\Omega }:X(\omega )\le c\}\in \mathcal{F}\text{ for all }c\in \mathbb{R}.$$ The probability that $X$ takes on a value in a Borel set⁵ $B\subset \mathbb{R}$ is written as: $$P(X\in B)=P(\{\omega \in \mathrm{\Omega }:X(\omega )\in B\}).$$

Cumulative distribution function (CDF): The CDF $F:\mathbb{R}\to [0,1]$ of a random variable $X$ is a right continuous and nondecreasing function with left limits satisfying $$F(x):=P(X\le x)=P(\{\omega \in \mathrm{\Omega }:X(\omega )\le x\}).$$ In particular, $\underset{x\to -\mathrm{\infty }}{lim}F(x)=0$ and $\underset{x\to \mathrm{\infty }}{lim}F(x)=1$.

Probability mass function (PMF) and probability density function (PDF):

• If the range $\mathcal{X}\subset \mathbb{R}$ of a random variable $X$ is countable, it is called a discrete random variable, whose distribution can be characterized by the PMF as: $$P(X=x)=F(x)-\underset{ϵ\to 0^{+}}{lim}F(x-ϵ)\text{ for all }x\in \mathcal{X}.$$

• If the range $\mathcal{X}\subseteq \mathbb{R}$ of a random variable $X$ has an absolutely continuous CDF $F$, then we can describe its distribution through the PDF as: $$p(x)=F^{\prime }(x)=\frac{d}{dx}F(x).$$ In this case, $F(x)=P(X\le x)={\int }_{-\mathrm{\infty }}^{x}p(u)du$, and $P(X=x)=0$ for a single number $x\in \mathbb{R}$.

Expectation and Variance

Expectation: The expected value (or mean) of a random variable $X$ with range $\mathcal{X}\subset \mathbb{R}$ can be interpreted as a weighted average.

• For a discrete random variable, $E(X)=\sum _{x\in \mathcal{X}}x\cdot P(X=x)$.

• For a continuous random variable with PDF $p_X$, $E(X)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}x\cdot p_X(x)dx$

Linearity of expectation: If $X,Y$ are two random variables and $a$ is a constant in $\mathbb{R}$, then $$E(X+Y)=E(X)+E(Y)\text{ and }E(aX)=a\cdot E(X).$$ This is true even if $X$ and $Y$ are not independent.

Variance and covariance: The variance of a random variable measures how far away it is, on average, from the mean. It is defined as $$\mathrm{Var}(X)=E[(X-E[X]{)}^2]=E(X^2)-E(X{)}^2.$$ The covariance between random variables $X,Y$ is defined as: $$\mathrm{Cov}(X,Y)=E\left[(X-E(X))(Y-E(Y))\right].$$ For a random variable $X$ and a constant $a\in \mathbb{R}$, we have $\mathrm{Var}(X+a)=\mathrm{Var}(X)$ and $\mathrm{Var}(aX)=a^2\cdot \mathrm{Var}(X)$. We do not have $\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)$ unless $X$ and $Y$ are uncorrelated (which means they have covariance $0$). In particular, independent random variables are always uncorrelated, although the reverse doesn’t hold in general.

Pearson’s correlation coefficient: For two random variables $X$ and $Y$, their (Pearson’s) correlation coefficient is defined as: $${\rho }_{XY}=\mathrm{Cor}(X,Y)=\frac{\mathrm{Cov}(X,Y)}{\sqrt{\text{Var}(X)\cdot \mathrm{Var}(Y)}},$$ where ${\rho }_{XY}\in [-1,1]$ by the Cauchy-Schwarz inequality; see Section 3.7. It measures the linear relation between two random variables.

Known Probability Distributions

Discrete random variables

Bernoulli: If $X$ is a Bernoulli random variable denoted by $X\sim \mathtt{Bernoulli}(p)$, then $$P(X=1)=p\text{ and }P(X=0)=1-p.$$ A Bernoulli random variable with parameter $p$ can be interpreted as a coin flip that comes up heads with probability $p$ and tails with probability $1-p$. We know that $$E(X)=p\text{ and }\mathrm{Var}(X)=p(1-p).$$

Binomial: If $X$ is a binomial random variable denoted by $X\sim \mathtt{Binomial}(n,p)$, then $$P(X=k)=(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k}\text{ for }k=0,1,...,n.$$ A binomial random variable with parameters $n$ and $p$ models the number of successes in $n$ trials, each of which has a successful probability $p$. When $n=1$, it reduces to a Bernoulli random variable. We know that $$E(X)=np\text{ and }\mathrm{Var}(X)=np(1-p).$$

Geometric: If $X$ is a geometric random variable denoted by $X\sim \mathtt{Geometric}(p)$, then $$P(X=k)=(1-p{)}^{k-1}p\text{ for }k=0,1,....$$ A geometric random variable with parameter $p$ models the number of trials until the first success occurs, where each trial has a successful probability $p$. We know that $$E(X)=\frac{1}{p}\text{ and }\mathrm{Var}(X)=\frac{1-p}{p^2}.$$

Poisson: If $X$ is a Poisson random variable denoted by $X\sim \mathtt{Poisson}(\lambda )$, then $$P(X=k)=\frac{{\lambda }^k{e}^{-\lambda }}{k!}\text{ for }k=0,1,....$$ A Poisson random variable often appears in counting processes. For instance, the number of laser photons hitting a detector in a particular time interval can be modeled as a Poisson random variable. We know that $$E(X)=\lambda \text{ and }\mathrm{Var}(X)=\lambda .$$

Indicator random variable: For an event $A$, an indicator random variable takes value 1 when $A$ occurs and 0 otherwise, i.e., $$I_A=\{\begin{array}{ll}1& \text{if event }A\text{ occurs}\\ 0& \text{otherwise}\end{array}$$

The expectation of an indicator random variable is just the probability of the event occurring, i.e., $$\begin{array}{rl}E[I_A]& =1\cdot P(I_A=1)+0\cdot P(I_A=0)\\ & =P(I_A=1)\\ & =P(A),\end{array}$$ and its variance is $\mathrm{Var}(I_A)=P(A)[1-P(A)]$.

Multinomial: Suppose that $Z$ is a categorical random variable with range $\{1,...,k\}$ and $P(Z=j)=p_j$ for $j=1,...,k$. We generate independently and identically distributed data $Z_1,...,Z_n$ with the above distribution and take $$X_j=\sum _{i=1}^n{I}_{\{Z_i=j\}}=\text{Number of observations in Category }j.$$ Then, the random vector $\mathbf{X}=(X_1,...,X_k)$ follows a multinomial distribution denoted by $\mathbf{X}\sim \mathtt{Multinomial}(n;p_1,...,p_k)$ with $\sum _{j=1}^k{p}_j=1$, whose PMF is given by $$P(X_1=x_1,...,X_k=x_k)=\frac{n!}{x_1!\cdots x_k!}\cdot p_1^{x_1}\cdots p_k^{x_k}.$$ Here, $\mathbf{X}$ takes integer values within a simplex $\{(x_1,...,x_k)\in \{0,1,...,k{\}}^n:\sum _{j=1}^n{x}_j=n\}$.

Continuous random variables

Uniform: If $X$ is a uniform random variable over the interval $[a,b]$ denote by $X\sim \mathtt{Uniform}[a,b]$, then its PDF is given by $$p(x)=\frac{1}{b-a}\cdot I_{[a,b]}(x)=\{\begin{array}{ll}\frac{1}{b-a}& a\le x\le b,\\ 0& \text{otherwise}.\end{array}$$ We know that $$E(X)=\frac{a+b}{2}\text{ and }\mathrm{Var}(X)=\frac{(b-a{)}^2}{12}.$$

Normal: If $X$ is a normal random variable with parameters $\mu$ and ${\sigma }^2$ denoted by $X\sim N(\mu ,{\sigma }^2)$, then its PDF is given by $$p(x)=\frac{1}{\sqrt{2\pi }\sigma }{e}^{-\frac{(x-\mu {)}^2}{2{\sigma }^2}},$$ where $x\in (-\mathrm{\infty },\mathrm{\infty })$. We know that $$E(X)=\mu \text{ and }\mathrm{Var}(X)={\sigma }^2.$$

Exponential: If $X$ is an exponential random variable with parameter $\lambda$ denoted by $X\sim \mathtt{Exp}(\lambda )$, then its PDF is given by $$p(x)=\lambda e^{-\lambda x}\cdot I_{[0,\mathrm{\infty })}(x).$$ We know that $$E(X)=\frac{1}{\lambda }\text{ and }\mathrm{Var}(X)=\frac{1}{{\lambda }^2}.$$ A double exponential random variable $Y$ satisfies that $|Y|\sim \mathtt{Exp}(\lambda )$, so its PDF is given by $$p(y)=\frac{\lambda }{2}{e}^{-\lambda |y|}\text{ with }y\in (-\mathrm{\infty },\mathrm{\infty }).$$ In particular, $E(Y)=0$ and $\mathrm{Var}(Y)=\frac{2}{{\lambda }^2}$. Sometimes, $Y$ is also called a Laplace random variable⁶.

Cauchy: If $X$ is a Cauchy random variable with parameters $\mu ,{\sigma }^2$ denoted by $X\sim \mathtt{Cauchy}(\mu ,{\sigma }^2)$, then its PDF is given by $$p(x)=\frac{1}{\pi \sigma }\left[\frac{{\sigma }^2}{{\sigma }^2+(x-\mu {)}^2}\right],$$ where $x\in (-\mathrm{\infty },\mathrm{\infty })$. Note that both the expectation and variance of a Cauchy distribution do not exist. The parameter $\mu$ represents its median.

Gamma: A Gamma random variable $X$ is characterized by two parameters $\alpha ,\lambda >0$ and has a PDF $$p(x)=\frac{{\lambda }^{\alpha }}{\mathrm{\Gamma }(\alpha )}{x}^{\alpha -1}{e}^{-\lambda x}\cdot I_{[0,\mathrm{\infty })}(x),$$ where $\mathrm{\Gamma }(\alpha )={\int }_0^{\mathrm{\infty }}{u}^{\alpha -1}{e}^{-u}du$ is the Gamma function; see Section 2. We denote $X\sim \mathtt{Gamma}(\alpha ,\lambda )$ and have that $$E(X)=\frac{\alpha }{\lambda }\text{ and }\mathrm{Var}(X)=\frac{\alpha }{{\lambda }^2}.$$

Beta: A Beta random variable $X$ with parameters $\alpha ,\beta >0$ has its PDF as: $$p(x)=\frac{1}{B(\alpha ,\beta )}{x}^{\alpha -1}(1-x{)}^{\beta -1}\cdot I_{[0,1]}(x),$$ where $B(\alpha ,\beta )=\frac{\mathrm{\Gamma }(\alpha )\mathrm{\Gamma }(\beta )}{\mathrm{\Gamma }(\alpha +\beta )}$. Given that the Beta random variable $X\sim \mathtt{Beta}(\alpha ,\beta )$ has a continuous distribution on $[0,1]$, it is often used to model a ratio or probability. We know that $$E(X)=\frac{\alpha }{\alpha +\beta }\text{ and }\mathrm{Var}(X)=\frac{\alpha \beta }{(\alpha +\beta {)}^2(\alpha +\beta +1)}.$$

Logistic: A logistic random variable $X$ with parameters $\alpha \in \mathbb{R},\beta >0$ has its CDF with the form of a logistic function as: $$F(x)=P(X\le x)=\frac{1}{1+e^{-\alpha -\beta x}}.$$ Thus, its PDF is given by $$p(x)=\frac{d}{dx}F(x)=\frac{\beta e^{-\alpha -\beta x}}{{(1+e^{-\alpha -\beta x})}^2}=\frac{\beta e^{\alpha +\beta x}}{{(1+e^{\alpha +\beta x})}^2}.$$

Dirichlet: A Dirichlet random vector $\mathbf{Z}=(Z_1,...,Z_k)$ generalizes the Beta distribution to its multivariate version (or extend the multinomial distribution to its continuous version). It has a PDF defined on the simplex $\{(z_1,...,z_k)\in [0,1{]}^k:\sum _{i=1}^k{z}_i=1\}$ as: $$p(z_1,...,z_k;{\alpha }_1,...,{\alpha }_k)=\frac{1}{B(\mathit{\alpha })}\prod _{i=1}^k{z}_i^{{\alpha }_i-1},$$ where $\mathit{\alpha }=({\alpha }_1,...,{\alpha }_k)$ with ${\alpha }_i>0,i=1,...,k$ is a $k$-dimensional parameter vector. The Dirichlet distribution is particularly useful in modeling the prior probabilities of a multinomial distribution that generates the latent topics of a document ⁷. When $\mathbf{Z}\sim \mathtt{Dirichlet}({\alpha }_1,...,{\alpha }_k)$, its mean vector is $E(\mathbf{Z})=(\frac{{\alpha }_1}{\sum _{i=1}^k{\alpha }_i},\dots ,\frac{{\alpha }_k}{\sum _{i=1}^k{\alpha }_i})$.

Inequalities

Markov’s inequality: Let $X$ be a nonnegative random variable. Then, for any $ϵ>0$, $$P(X\ge ϵ)\le \frac{E(X)}{ϵ}.$$

Chebyshev’s inequality: Let $X$ be a random variable with $\mathrm{Var}(X)<\mathrm{\infty }$. Then, for any $ϵ>0$, $$P(|X-E(X)|\ge ϵ)\le \frac{\mathrm{Var}(X)}{ϵ}.$$ The Chebyshev’s inequality can be proved by applying Markov’s inequality to the nonnegative random variable ${[X-E(X)]}^2$. It is a simple instance of general concentration inequalities that give a probabilistic bound on the deviation of $X$ away from its mean.

Chernoff bound: Suppose that there is a constant $b>0$ such that the moment generating function $\phi (\lambda )=E\left[e^{\lambda (X-\mu )}\right]$ of a random variable $X$ exists when $\lambda \le |b|$, where $\mu =E(X)$. Given that $$P[(X-\mu )>t]=P[e^{\lambda (X-\mu )}\ge e^{\lambda t}]\le \frac{E\left[e^{\lambda (X-\mu )}\right]}{e^{\lambda t}}\text{ for any }\lambda \in [0,b],$$ we can optimize our choice of $\lambda$ to obtain the Chernoff bound as: $$P[(X-\mu )>t]\le \underset{\lambda \in [0,b]}{inf}\frac{E\left[e^{\lambda (X-\mu )}\right]}{e^{\lambda t}}.$$

Cauchy-Schwarz inequality: Given two random variables $X$ and $Y$, $${|E(XY)|}^2\le E(X^2)\cdot E(Y^2),$$ where equality holds if and only if either $P(X=0)=0$, or $P(Y=0)=0$, or $P(X=cY)=1$ for some nonzero constant $c\in \mathbb{R}$. A useful corollary of the Cauchy-Schwarz inequality is that $$|\text{Cov}(X,Y){|}^2\le \text{Var}(X)\text{Var}(Y).$$

Hölder inequality: Given two random variables $X$ and $Y$, $$E|XY|\le {(E|X{|}^p)}^{\frac{1}{p}}{(E|Y{|}^q)}^{\frac{1}{q}}\equiv {\left|\left|X\right|\right|}_p{\left|\left|Y\right|\right|}_q$$ with $p,q\in [1,\mathrm{\infty }]$ and $\frac{1}{p}+\frac{1}{q}=1$, where equality holds if and only if $P(|X{|}^p=c|Y{|}^q)=1$ for some nonzero constant $c$. Specifically, when $p=\mathrm{\infty }$, ${\left|\left|X\right|\right|}_{\mathrm{\infty }}=inf\{M\ge 0:P(|X|>M)=0\}$.

Minkowski Inequality: Given two random variables $X$ and $Y$, $${[E|X+Y{|}^p]}^{\frac{1}{p}}\le {[E|X{|}^p]}^{\frac{1}{p}}+{[E|Y{|}^p]}^{\frac{1}{p}}$$ for $p\in [1,\mathrm{\infty })$, where equality holds if and only if $P(X=cY)=1$ for some nonzero constant $c$, or $P(Y=0)=1$, or $P(X=0)=1$.

Jensen’s Inequality: Given a convex function $\phi$ and a random variable $X$, $$\phi (E(X))\le E[\phi (X)],$$ where equality holds if and only if either $P(X=c)=1$ for some constant $c$ or for every line $a+bx$ that is tangent to $\phi$ at $E(X)$, $P(\phi (x)=a+bx)=1$.

Big $O$ and $O_P$ Symbols

In machine learning, big $O$ and little $o$ symbols are used to characterize the time or space complexity of our algorithm with respect to the sample size or data dimension. In general, these symbols describe the growth rate of functions as follows.

Let $f(x)$ be the function to be estimated on $\mathbb{R}$ and $g(x)$ be the comparison function that is strictly positive when $x$ is large on $\mathbb{R}$.

Big $O$ symbol: We write $f(x)=O(g(x))$ if there exist constants $M>0$ and $x_0>0$ such that⁸ $$|f(x)|\le M\cdot g(x)\text{ for all }x\ge x_0.$$ Using the limit superior notation, we know that $$f(x)=O(g(x))⟺\underset{x\to \mathrm{\infty }}{lim sup}\frac{|f(x)|}{g(x)}<\mathrm{\infty }.$$ Notice that $\underset{x\to \mathrm{\infty }}{lim sup}h(x)=\underset{x_0\to \mathrm{\infty }}{lim}[\underset{x\ge x_0}{sup}f(x)]$.

Little $o$ symbol: Similarly, we write $f(x)=o(g(x))$ if for any $ϵ>0$, there exists a constant $x_0>0$ such that $$|f(x)|\le ϵ\cdot g(x)\text{ for all }x\ge x_0.$$ Under the limit notation, we have that $$f(x)=o(g(x))⟺\underset{x\to \mathrm{\infty }}{lim}\frac{|f(x)|}{g(x)}=0.$$

Big $\mathrm{\Omega }$ symbol: Sometimes, depending on the context, we may encounter the big $\mathrm{\Omega }$ symbol in machine learning literature. In most cases, the definition of $f(x)=\mathrm{\Omega }(g(x))$ follows from ⁹, so we write $f(x)=\mathrm{\Omega }(g(x))$ if there exist constants $m>0$ and $x_0$ such that $$|f(x)|\ge m\cdot g(x)\text{ for all }x\ge x_0,$$ or equivalently, $$f(x)=\mathrm{\Omega }(g(x))⟺\underset{n\to \mathrm{\infty }}{lim inf}\frac{f(x)}{g(x)}>0.$$

Taking into account the randomness of input data, it may not be possible to bound a quantity or random variable in our algorithm through the above big $O$ and little $o$ symbols. We introduce the $O_P$ and $o_P$ symbols¹⁰ to handle the stochastic rate of convergence for a sequence of random variables $\{X_n{\}}_{n=1}^{\mathrm{\infty }}$.

Little $o_P$ symbol: We write $X_n=o_P(a_n)$ for a sequence of constants $\{a_n{\}}_{n=1}^{\mathrm{\infty }}$ if $\frac{X_n}{a_n}$ converges to 0 in probability as $n\to \mathrm{\infty }$. That is, for any $ϵ>0$, $$X_n=o_P(a_n)⟺\underset{n\to \mathrm{\infty }}{lim}P(\left|\frac{X_n}{a_n}\right|\ge ϵ)=0.$$

Big $O_P$ symbol: We write $X_n=O_P(a_n)$ for a sequence of constants $\{a_n{\}}_{n=1}^{\mathrm{\infty }}$ if $\frac{X_n}{a_n}$ is bounded in probability when $n$ is large. That is, for any $ϵ>0$, there exist a constant $M>0$ and an integer $N>0$ such that $$X_n=O_P(a_n)⟺P(\left|\frac{X_n}{a_n}\right|>M)<ϵ\text{ when }n>N.$$