Probability theory reference

• 05 July 2025
• probability theory

Probability theory quantifies uncertainty and makes predictions under conditions of incomplete information. The theory rests on several essential axioms.

Consider a random experiment with a set of all possible outcomes $\mathrm{\Omega }$, called the sample space. Events are subsets of $\mathrm{\Omega }$ and the collection of all events forms a $\sigma$-algebra $\mathcal{F}$.

A probability measure $P$ assigns each event $A$ in $\mathcal{F}$ a number $P(A)$ satisfying Kolmogorov's axioms.

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

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

$$P\left(\bigcup _{i=1}^{\mathrm{\infty }}{A}_i\right)=\sum _{i=1}^{\mathrm{\infty }}P(A_i)\text{ for disjoint events }{A}_i$$

The triple $(\mathrm{\Omega },\mathcal{F},P)$ forms a probability space which is the primary object of interest in probability theory.

The complement rule states the following.

$$P(A^c)=1-P(A)$$

For any event $A$ and its complement $A^c=\mathrm{\Omega }\setminus A$.

The union of two events follows the inclusion-exclusion principle.

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

This extends to multiple events.

$$P\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{i=1}^{n}P(A_i)-\sum _{i<j}P(A_i\cap A_j)+\sum _{i<j<k}P(A_i\cap A_j\cap A_k)$$

$$-\cdots +(-1{)}^{n-1}P(A_1\cap A_2\cap \cdots \cap A_n)$$

Conditional probability captures how the occurrence of one event affects the probability of another. The conditional probability of $A$ given $B$ is defined by the following relation.

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

The definition applies when $P(B)>0$.

Two events $A$ and $B$ are independent if and only if they satisfy the following.

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

This generalizes to multiple events. $A_1,A_2,\dots ,A_n$ are mutually independent if they satisfy the following.

$$P\left(\bigcap _{i\in S}{A}_i\right)=\prod _{i\in S}P(A_i)$$

For any subset $S$ of indices $1,2,\dots ,n$.

The law of total probability expresses the probability of an event as a weighted sum over a partition.

$$P(A)=\sum _{i=1}^{n}P(A|B_i)P(B_i)$$

For any partition $B_1,B_2,\dots ,B_n$ of the sample space.

Bayes' theorem relates conditional probabilities.

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

Using the law of total probability, we expand the denominator.

$$P(A|B)=\frac{P(B|A)P(A)}{\sum _{i}P(B|A_i)P(A_i)}$$

Random variables formalize the mapping from outcomes to numerical values. A random variable $X$ is a measurable function from $\mathrm{\Omega }$ to the real numbers.

The cumulative distribution function (CDF) of a random variable $X$ is defined by the following.

$$F_X(x)=P(X\le x)$$

CDF completely characterizes the distribution of $X$ and satisfies key properties. $F_X$ is non-decreasing. $\underset{x\to -\mathrm{\infty }}{lim}{F}_X(x)=0$ and $\underset{x\to \mathrm{\infty }}{lim}{F}_X(x)=1$. $F_X$ is right-continuous, implying that $\underset{y\downarrow x}{lim}{F}_X(y)=F_X(x)$.

Discrete random variables take countably many values. The probability mass function (PMF) is defined as follows.

$$p_X(x)=P(X=x)$$

PMF satisfies $p_X(x)\ge 0$ and $\sum _x{p}_X(x)=1$.

Continuous random variables have a probability density function (PDF) $f_X(x)$ that satisfies the following relation.

$$P(a\le X\le b)={\int }_a^b{f}_X(x)dx$$

PDF satisfies $f_X(x)\ge 0$ and ${\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}{f}_X(x)dx=1$.

The relationship between CDF and PDF is defined by these equations.

$$F_X(x)={\int }_{-\mathrm{\infty }}^x{f}_X(t)dt$$

$$f_X(x)=\frac{d}{dx}{F}_X(x)$$

The expected value (mean) of a random variable $X$ is calculated differently for discrete and continuous random variables.

$$E[X]=\{\begin{array}{ll}\sum _{x}x\cdot p_X(x)& \text{for discrete X}\\ {\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}x\cdot f_X(x)dx& \text{for continuous X}\end{array}$$

The variance measures the spread around the mean and is calculated using this formula.

$$\text{Var}(X)=E[(X-E[X]{)}^2]=E[X^2]-(E[X]{)}^2$$

The moment generating function (MGF) encapsulates all moments of X.

$$M_X(t)=E[e^{tX}]$$

When it exists, MGF uniquely determines the distribution. The $k$-th moment can be extracted using differentiation.

$$E[X^k]={\frac{d^k}{d{t}^k}{M}_X(t)|}_{t=0}$$

The characteristic function always exists and is defined by this formula.

$${\phi }_X(t)=E[e^{itX}]$$

Bernoulli distribution models binary outcomes with parameter $p\in [0,1]$. Its PMF is given by:

$$P(X=1)=p,P(X=0)=1-p$$

Its mean is $E[X]=p$ and variance is $\text{Var}(X)=p(1-p)$.

The binomial distribution $\text{Bin}(n,p)$ counts successes in $n$ independent Bernoulli trials. Its PMF is given by:

$$P(X=k)=(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k}$$

The mean is $E[X]=np$ and the variance is $\text{Var}(X)=np(1-p)$.

The geometric distribution models the number of trials until the first success. Its PMF is given by:

$$P(X=k)=(1-p{)}^{k-1}p$$

The mean is $E[X]=\frac{1}{p}$ and the variance is $\text{Var}(X)=\frac{1-p}{p^2}$.

The Poisson distribution $\text{Pois}(\lambda )$ models the number of events in a fixed interval. Its PMF is given by:

$$P(X=k)=\frac{{\lambda }^k{e}^{-\lambda }}{k!}$$

Both its mean and variance equal $\lambda$.

The uniform distribution $\text{Unif}(a,b)$ has constant density on an interval. Its PMF is given by:

$$f_X(x)=\{\begin{array}{lll}\frac{1}{b-a}& \text{if }a\le x\le b0& \text{otherwise}\end{array}$$

The mean is $E[X]=\frac{a+b}{2}$ and the variance is $\text{Var}(X)=\frac{(b-a{)}^2}{12}$.

The normal distribution $N(\mu ,{\sigma }^2)$ has the following probability density function.

$$f_X(x)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-\frac{(x-\mu {)}^2}{2{\sigma }^2}}$$

The mean is $\mu$ and the variance is ${\sigma }^2$.

The standard normal distribution $N(0,1)$ has a special CDF denoted $\mathrm{\Phi }(x)$ and defined by this integral.

$$\mathrm{\Phi }(x)=\frac{1}{\sqrt{2\pi }}{\int }_{-\mathrm{\infty }}^x{e}^{-\frac{t^2}{2}}dt$$

For any normal random variable $X\sim N(\mu ,{\sigma }^2)$, the standardization $Z=\frac{X-\mu }{\sigma }\sim N(0,1)$.

The exponential distribution $\text{Exp}(\lambda )$ models the time between events in a Poisson process. Its PMF is given by:

$$f_X(x)=\lambda e^{-\lambda x}\text{ for }x\ge 0$$

The mean is $E[X]=\frac{1}{\lambda }$ and the variance is $\text{Var}(X)=\frac{1}{{\lambda }^2}$.

The gamma distribution $\text{Gamma}(\alpha ,\beta )$ generalizes the exponential. The probability density function is given by this relation.

$$f_X(x)=\frac{{\beta }^{\alpha }}{\mathrm{\Gamma }(\alpha )}{x}^{\alpha -1}{e}^{-\beta x}\text{ for }x>0$$

The mean is $E[X]=\frac{\alpha }{\beta }$ and the variance is $\text{Var}(X)=\frac{\alpha }{{\beta }^2}$.

Joint distributions describe the behavior of multiple random variables. For discrete random variables $X$ and $Y$, the joint PMF is defined as follows.

$$p_{X,Y}(x,y)=P(X=x,Y=y)$$

For continuous random variables, the joint PDF $f_{X,Y}(x,y)$ satisfies:

$$P((X,Y)\in A)=\int {\int }_A{f}_{X,Y}(x,y)dxdy$$

Marginal distributions are obtained by summing or integrating out variables.

$$p_X(x)=\sum _y{p}_{X,Y}(x,y)$$

$$f_X(x)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}{f}_{X,Y}(x,y)dy$$

Independence of random variables $X$ and $Y$ is characterized by the following.

$$f_{X,Y}(x,y)=f_X(x)\cdot f_Y(y)$$

The covariance measures the linear relationship between random variables. It is calculated using this formula.

$$\text{Cov}(X,Y)=E[(X-E[X])(Y-E[Y])]=E[XY]-E[X]E[Y]$$

The correlation coefficient normalizes the covariance with the following.

$${\rho }_{X,Y}=\frac{\text{Cov}(X,Y)}{\sqrt{\text{Var}(X)\text{Var}(Y)}}$$

Values range from $-1$ to $1$, implying perfect negative correlation, independence or perfect positive correlation.

Transformations of random variables follow specific rules. For a function $g$ and a random variable $X$, the expected value is:

$$E[g(X)]=\{\begin{array}{ll}\sum _{x}g(x)\cdot p_X(x)& \text{for discrete X}\\ {\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}g(x)\cdot f_X(x)dx& \text{for continuous X}\end{array}$$

For linear transformations $Y=aX+b$, the mean and variance transform according to these equations.

$$E[Y]=aE[X]+b$$

$$\text{Var}(Y)=a^2\text{Var}(X)$$

For a strictly monotonic function $g$ with inverse $g^{-1}$, the PDF of $Y=g(X)$ is given by:

$$f_Y(y)=f_X(g^{-1}(y))|\frac{d}{dy}{g}^{-1}(y)|$$

This generalizes to multivariate transformations through the Jacobian.

Sums of independent random variables exhibit special properties. If $X$ and $Y$ are independent, their means and variances add.

$$E[X+Y]=E[X]+E[Y]$$

$$\text{Var}(X+Y)=\text{Var}(X)+\text{Var}(Y)$$

The MGF of their sum is the product of the individual MGFs.

$$M_{X+Y}(t)=M_X(t)\cdot M_Y(t)$$

The convolution relation gives the PDF of $Z=X+Y$ through this integral.

$$f_Z(z)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}{f}_X(z-y)f_Y(y)dy$$

Central limit theorem (CLT) is one of the most important results in probability theory. Let $X_1,X_2,\dots ,X_n$ be independent and identically distributed random variables with mean $\mu$ and variance ${\sigma }^2<\mathrm{\infty }$. CLT states the following convergence.

$$\frac{\sum _{i=1}^n{X}_i-n\mu }{\sigma \sqrt{n}}\stackrel{d}{\to }N(0,1)$$

The symbol $\stackrel{d}{\to }$ denotes convergence in distribution as $n\to \mathrm{\infty }$.

CLT explains the ubiquity of the normal distribution in natural phenomena that result from many small, independent effects.

The law of large numbers (LLN) comes in two forms. The weak LLN states this convergence.

$$\frac{1}{n}\sum _{i=1}^n{X}_i\stackrel{p}{\to }\mu$$

The strong LLN makes a stronger statement.

$$P(\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\sum _{i=1}^n{X}_i=\mu )=1$$

All of these laws formalize the intuition that the sample mean converges to the expected value as sample size increases.

Conditional expectations extend the concept of conditional probability to random variables. For discrete random variables $X$ and $Y$, the conditional expectation is defined as follows.

$$E[X|Y=y]=\sum _{x}x\cdot p_{X|Y}(x|y)$$

For continuous random variables, the definition is an integral.

$$E[X|Y=y]={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}x\cdot f_{X|Y}(x|y)dx$$

The law of total expectation states the following.

$$E[X]=E[E[X|Y]]$$

The conditional variance formula decomposes the variance.

$$\text{Var}(X)=E[\text{Var}(X|Y)]+\text{Var}(E[X|Y])$$

Markov chains model stochastic processes with the Markov property:

The future depends on the past only through the present state.

A discrete-time Markov chain has transition probabilities defined by:

$$P(X_{n+1}=j|X_n=i)=p_{ij}$$

The transition matrix $P=(p_{ij})$ completely describes the chain's dynamics.

The $n$-step transition probabilities are given by the $n$-th power of $P$.

$$P(X_m=j|X_0=i)=(P^m{)}_{ij}$$

For an irreducible and aperiodic Markov chain, a unique stationary distribution $\pi$ exists. It satisfies these equations.

$$\pi =\pi P$$

$$\sum _i{\pi }_i=1$$

The chain converges to this distribution regardless of the initial state.

Order statistics examine the distributions of ranked random variables. Given i.i.d. random variables $X_1,X_2,\dots ,X_n$ with CDF $F_X$, the $k$-th order statistic $X_{(k)}$ has the following CDF.

$$F_{X_{(k)}}(x)=\sum _{j=k}^n(\genfrac{}{}{0ex}{}{n}{j})[F_X(x){]}^j[1-F_X(x){]}^{n-j}$$

The minimum $X_{(1)}$ and maximum $X_{(n)}$ have special forms.

$$F_{X_{(1)}}(x)=1-[1-F_X(x){]}^n$$

$$F_{X_{(n)}}(x)=[F_X(x){]}^n$$

Bayesian statistics treats unknown parameters as random variables with prior distributions. Given data $X$ and parameter $\theta$, Bayes' theorem gives the posterior distribution.

$$f_{\mathrm{\Theta }|X}(\theta |x)=\frac{f_{X|\mathrm{\Theta }}(x|\theta )f_{\mathrm{\Theta }}(\theta )}{f_X(x)}$$

The posterior distribution $f_{\mathrm{\Theta }|X}(\theta |x)$ updates our belief about $\theta$ after observing data x.

A conjugate prior yields a posterior in the same family, simplifying computation. E.g. the Beta distribution is conjugate to the Bernoulli and Binomial likelihoods.

Sufficiency reduces data without losing information about parameters. A statistic $T(X)$ is sufficient for parameter $\theta$ if the conditional distribution of $X$ given $T(X)$ does not depend on $\theta$.

The Fisher-Neyman factorization theorem provides a way to identify sufficient statistics. $T(X)$ is sufficient for $\theta$ if and only if the likelihood can be factored as follows.

$$f_X(x|\theta )=g(T(x),\theta )\cdot h(x)$$

The functions $g$ and $h$ may depend on $x$ and $\theta$ as indicated.

Maximum likelihood estimation (MLE) finds the parameter value $\theta$ that maximizes the likelihood function. The likelihood is defined by the following.

$$L(\theta |x)=f_X(x|\theta )$$

Often, we maximize the log-likelihood instead.

$$\ell (\theta |x)=\log L(\theta |x)$$

For i.i.d. observations, the log-likelihood has this form.

$$\ell (\theta |x_1,\dots ,x_n)=\sum _{i=1}^n\log f_X(x_i|\theta )$$

The method of moments estimates parameters by equating sample moments to theoretical moments.

$$\frac{1}{n}\sum _{i=1}^n{X}_i^k=E[X^k]$$

Hypothesis testing evaluates evidence against a null hypothesis $H_0$ in favor of an alternative $H_1$. The p-value is the probability of observing a test statistic at least as extreme as the one observed, assuming $H_0$ is true.

Type I error occurs when rejecting a true $H_0$. Type II error occurs when failing to reject a false $H_0$. The power of a hypothesis test is the probability of correctly rejecting a false $H_0$.

The likelihood ratio test compares the maximized likelihoods under $H_0$ and $H_1$. The test statistic is defined as follows.

$$\mathrm{\Lambda }(x)=\frac{\underset{\theta \in {\mathrm{\Theta }}_0}{sup}L(\theta |x)}{\underset{\theta \in \mathrm{\Theta }}{sup}L(\theta |x)}$$

Under certain regularity conditions, $-2\log \mathrm{\Lambda }(X)$ converges to a chi-squared distribution as sample size increases.

• ← Previous
  Linux syscalls
• Next →
  Writing an AVX2 DGEMM kernel