0 Review of Probability
In this chapter, we will review some concepts from probability theory and linear algebra that will be useful in the rest of the course.
This review is not comprehensive. You can refer to the course webpage for more resources.
0.1 What is probability?
Intuitively, probability is a way of systematically studying events whose outcomes are uncertain (e.g., the probability of rolling a 6 is 1/6, or the probability of rain at 10 am tomorrow is 20%). It enables us to quantify information and uncertainty and provides ways to transfer our knowledge about one random quantity to another. Mathematically, probability deals with sets, and functions that assign real values to those sets, in a way that certain axioms are satisfied; like geometry or number theory, it can be used to model the real world, but it can also be studied as an abstract subject.
0.1.1 Definitions
Assuming an experiment with different possible outcomes, consider the following definitions.1
\(\Omega\): the sample space, the set of all possibilities (outcomes)
\(E\subseteq\Omega\): an event, i.e., a set of outcomes
\({\Pr}:\) A function from subsets of \(\Omega\) to \(\mathbb{R}\). \({\Pr}\left(E\right)\) is the probability of the event \(E\).
0.1.2 Axioms
\({\Pr}\left(E\right)\ge0\) for all \(E\subseteq\Omega\).
\({\Pr}\left(\Omega\right)=1\)
\({\Pr}\left(E_{1}\cup E_{2}\right)={\Pr}\left(E_{1}\right)+{\Pr}\left(E_{2}\right)\) if \(E_{1}\cap E_{2}=\varnothing\).
Based on these axioms, many theorems and other results can be proven. For \(A,B\subseteq \Omega\):
If \(A\subseteq B\), then \({\Pr}(A)\le {\Pr}(B)\).
\({\Pr}(A\cup B)={\Pr}(A)+{\Pr}(B)-{\Pr}(A\cap B)\).
\({\Pr}(A^c)=1-{\Pr}(A)\), where \(A^c\) is the complement of \(A\), i.e., the event that \(A\) does not occur.
\({\Pr}(A)\le 1\), which is the first result with \(B=\Omega\).
What these theorems and definitions ‘mean’ depends on what we think probability means.
0.1.3 Interpretations of probability
“Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.”
Bertrand Russell
How do we assign probability to events? What does it mean, for example, to say that \({\Pr}(E)=1/3\)?
Classical If there are \(K\) possible outcomes and no reason for some to be more likely than others, each outcome gets probability \(1/K\): rolling a 3 has probability \(1/6\).
Frequentist In \(N\) repetitions of a “random” experiment, with \(N\) very large, \(E\) occurs approximately \(N{\Pr}(E)\) times: a coin with \({\Pr}(H)=1/3\) tossed \(3000\) times shows heads around \(1000\) times.
Bayesian Probability is a degree of belief, consistent with the axioms; this covers events that are, strictly speaking, not random, such as the stock market hitting a threshold this year, a nuclear war this century, or a defendant being guilty.
Each interpretation can be criticized: the classical for circularity (a coin is fair if the outcomes are equally likely, which is what we set out to define); the frequentist for vagueness (how large is “large”?); and the Bayesian for subjectivity and for assigning probabilities to one-time events. From a purely mathematical perspective, none of this matters: we only need to assign probabilities in a way that satisfies the axioms. But the interpretation shapes how problems are approached and can lead to different real-world decisions.
0.2 Sets and their sizes
Finding the probability of an event is easiest when all outcomes are equally likely. In such cases, if we can measure the size of the set \(A\) of desirable outcomes, dividing it by the size of the sample space yields the probability, \[{\Pr}(A)=\frac{|A|}{|\Omega|},\] where \(|A|\) denotes the size of the set \(A\).
Definition 0.1 Finite, countable, uncountable
A set \(A\) is finite if there is a natural number \(n\) such that the number of elements in \(A\) is less than \(n\). Otherwise, it is infinite. If the elements of \(A\) can be counted, i.e., there is a one-to-one function from \(A\) to natural numbers, then \(A\) is countable. Otherwise, it is uncountable. A countable set may be finite (e.g., \(\{1,5,6\}\)) or infinite (e.g., integers, prime numbers, rational numbers).
If \(A\) is finite, we define its size (aka, cardinality) as the number of elements. Counting the elements of a finite set usually rests on the product principle: if each element is specified by a sequence of \(n\) choices, with \(k_1\) options for the first choice, \(k_2\) for the second, and so on, then the set has \(k_1k_2\dotsm k_n\) elements. In particular, there are \(k^n\) strings of length \(n\) over an alphabet of \(k\) symbols, since each of the \(n\) positions can be filled in \(k\) ways. The same count applied to membership shows that a set of \(n\) elements has \(2^n\) subsets, since each element is either in or out; in particular, a sample space with \(n\) outcomes has \(2^n\) events. As an example with unequal \(k_i\), arranging \(n\) objects in a row means choosing which object comes first (\(n\) options), then which of the rest comes second (\(n-1\) options), and so on, so the number of arrangements is \[n!=n\times(n-1)\times\dotsm\times2\times1.\]
Example 0.2 Bits for a die roll
A die is rolled, showing \(X\). How many bits are needed to represent the value of \(X\)?
Solution
A string of \(m\) bits takes \(2^m\) values, so it can represent \(X\) only if \(2^m\ge6\), i.e., \(m\ge\log_26\simeq2.58\). As \(m\) is an integer, \(m=3\) bits are needed. In general, a quantity with \(k\) possible values needs \(\lceil\log_2k\rceil\) bits.
The number of ways to choose \(k\) objects from a set of \(n\) objects, when the order of the choice does not matter, is \[\binom{n}{k}=\frac{n!}{k!(n-k)!}.\]
Exercise 0.3 Bytes with three ones
How many 8-bit bytes are there? How many of these have exactly 3 ones? If we pick a random byte, what is the probability that it has exactly 3 ones (binomial distribution)?
If the sample space has an infinite, even uncountable, number of outcomes, we may still be able to think of the outcomes as equally likely. For example, if we pick a random number between 0 and 1, we may assume all outcomes are equally likely. In such cases, the size of the set can be measured via length, area, volume, etc.
Exercise 0.4 Point in a square
A random point is chosen in a square of unit side. What is the probability that it is inside the circle of diameter one inscribed in the square? What is the probability that it is on the circle?
0.3 Random variables and distributions
A random variable (RV) is a function that assigns real values to outcomes in \(\Omega\). In most cases, there is a very natural mapping. For example, let \(X\) denote the number showing on a die. Now \(X\) is a random variable, mapping each outcome of the form “the die shows \(i\)” to the real number \(i\). For this reason, the fact that random variables are really functions is often overlooked. Information about the probabilities of different outcomes is given by the distribution of the random variable.
A random variable is discrete if there are a countable number of possibilities (could be infinite but countable, like natural numbers). It can also be continuous (uncountable number of outcomes, defined over the real line or a subset of a Euclidean space).
For example, a random variable that is 1 if heads shows when a given coin is flipped and is 0 otherwise is discrete and finite; the number of phone calls made in a given hour is discrete and infinite; the arrival time of a plane from midnight is continuous.
0.3.1 Discrete distributions
The distribution of a discrete random variable \(X\) is given by its probability mass function (pmf) denoted by \(p_X(x)\), where \[p_X(x) = {\Pr}(X=x).\] Clearly, \(p_X(x)\ge 0\) for all \(x\) and \[\begin{equation} \sum_x p_X(x) = 1. \end{equation}\tag{0.1}\]
If clear from the context, we drop the \(X\) in the subscript.
Example 0.5 Poisson distribution
An RV \(X\) has the Poisson distribution with parameter \({\lambda}\) if \[p(x) = \frac{{\lambda}^xe^{-\lambda}}{x!}, \quad x\in \{0,1,\dotsc\}.\] The number of times an event, e.g., phone calls or car accidents, occurs in a given interval of time is often assumed to have a Poisson distribution (with good reason).
Exercise 0.6 Red die, blue die
A red die and a blue die are rolled. Let \(X\) denote the number showing on the red die and \(Y\) denote the sum of the two dice. Find the pmf of \(X\) and the pmf of \(Y\).
Exercise 0.7 Drawing aces
Two cards are drawn at random from a standard deck of 52 cards and let \(Z\) denote the number of Aces drawn. Find the pmf of \(Z\).
0.3.2 Continuous distributions
The distribution of a continuous random variable \(X\) is given by its probability density function (pdf) \(p_X(x)\), also sometimes denoted \(f_X(x)\). Roughly speaking, \[{\Pr}\left(x-\frac{dx}{2}\le X \le x+\frac{dx}{2}\right)=p_X(x) dx.\] For two real numbers \(a,b\), \[{\Pr}(a\le X\le b) = \int_{a}^b p_X(x) dx.\] For any pdf, we have \(p_X(x)\ge 0\) and \[\int_{-\infty}^{\infty} p_X(x) dx=1.\] A pdf is a probability per unit length rather than a probability, so unlike a pmf it may exceed 1; the exponential density below equals \({\lambda}\) at \(x=0\). What it assigns to a single point is zero: for a continuous RV, \({\Pr}(X=x)=0\) for every \(x\), and only intervals carry probability.
Example 0.8 Exponential distribution
An exponential random variable \(X\) with parameter \({\lambda}\) has distribution \[f(x) = {\lambda}e^{-\lambda x}, \quad x\ge0.\] For \({\lambda}=1\), approximate the probability that \(X\) is between 1 and 1.1.
Solution
Over a short interval, the probability is approximately the density times the length of the interval: \(f(1)\times 0.1=e^{-1}\times0.1=0.37\times 0.1=0.037\). In the figure below, the area colored red represents this probability.
0.3.3 Cumulative distribution functions
Cumulative distribution functions (CDFs) are defined for both discrete and continuous RVs as \(F_X(x)={\Pr}(X\le x)\) and can be found via summation or integration: \[\begin{align*} F_X(x) &= \sum_{k\le x} p_X(k)\\ F_X(x) &= \int_{-\infty}^x p_X(t)dt \end{align*}\] Each relation can also be run backwards, recovering the distribution from the CDF: for an integer-valued RV, \(p_X(k)=F_X(k)-F_X(k-1)\), the height of the jump the staircase makes at \(k\); for a continuous RV, the density is the derivative of the CDF, \(p_X(x)=\frac{d}{dx}F_X(x)\).
Example 0.9 Exponential CDF
Find the CDF of the exponential RV in Example 0.8.
Solution
For \(x\ge0\), \[F_X(x) = \int_{0}^x {\lambda}e^{-\lambda t}dt=1-e^{-\lambda x},\] shown below for \({\lambda}=2\), along with the pdf.
0.3.4 Expected value
The expected value or the mean \(\mathop{\mathrm{{\mathbb{E}}}}[X]\) of a random variable \(X\) with distribution \(p(x)\) is given by \[\begin{align*} \mathop{\mathrm{{\mathbb{E}}}}[X] &=\sum_x x p(x),\\ \mathop{\mathrm{{\mathbb{E}}}}[X] &= \int_{-\infty}^{\infty} xp(x)dx. \end{align*}\] One way to think about the expected value is as the average of a large number of experiments. For example, if a game pays out \(\$X\) each time you play with probability distribution \(p(x)\), if you play the game many times, on average you will win \(\$\mathop{\mathrm{{\mathbb{E}}}}[X]\) per game. That is, if you play \(n\) times, winning \(\$x_i\) in game \(i\), and \(n\) is large, then \[\frac{1}{n}(x_1+x_2+\dotsb+x_n)\simeq \mathop{\mathrm{{\mathbb{E}}}}[X].\]
Exercise 0.10 Means from earlier examples
Find the expected value of the discrete and continuous RVs in the examples above.
Exercise 0.11 Expectation of a constant
Find \(\mathop{\mathrm{{\mathbb{E}}}}[1]\).
0.3.4.1 Indicator random variables
For an event \(A\), the indicator random variable \(𝟙(A)\) equals 1 if \(A\) occurs and 0 otherwise. Its expectation is the probability of the event, \[\mathop{\mathrm{{\mathbb{E}}}}[𝟙(A)] = 1\cdot{\Pr}(A)+0\cdot{\Pr}(A^c) = {\Pr}(A),\] which lets us move between probabilities and expectations.
Example 0.12 Indicator of a die roll
A die is rolled, showing \(X\). What is \(\mathop{\mathrm{{\mathbb{E}}}}[𝟙(X\ge5)]\)?
Solution
\(\mathop{\mathrm{{\mathbb{E}}}}[𝟙(X\ge5)]={\Pr}(X\ge 5)=1/3\).
0.3.4.2 Expectation of functions of random variables
For an RV \(X\) and a function \(f(x)\) it follows from the definition that \[\begin{equation} \begin{split} \mathop{\mathrm{{\mathbb{E}}}}[f(X)] &=\sum_x f(x) p(x),\\ \mathop{\mathrm{{\mathbb{E}}}}[f(X)] &= \int_{-\infty}^{\infty} f(x)p(x)dx. \end{split} \end{equation}\tag{0.2}\]
Exercise 0.13 A four-value pmf
A random variable \(X\) has distribution \[p_X(-1) = 0.1,\ p_X(0)=0.2,\ p_X(1) = 0.3,\ p_X(2) = 0.4.\] Find \(\mathop{\mathrm{{\mathbb{E}}}}X\). Let \(Y=X^2\). Find \(\mathop{\mathrm{{\mathbb{E}}}}Y\), both by finding the distribution of \(Y\) and by using (0.2).
0.3.4.3 Linearity of expectation
For a RV \(X\), functions \(f(x)\) and \(g(x)\), and real numbers \(a\) and \(b\), \[\mathop{\mathrm{{\mathbb{E}}}}[af(X)+bg(X)] = a\mathop{\mathrm{{\mathbb{E}}}}[f(X)]+b\mathop{\mathrm{{\mathbb{E}}}}[g(X)],\] which can be proven easily from the definition of expectation.
Example 0.14 Expanding a square
For an RV \(X\) and a constant \(a\), express \(\mathop{\mathrm{{\mathbb{E}}}}[(X-a)^2]\) in terms of \(\mathop{\mathrm{{\mathbb{E}}}}[X^2]\) and \(\mathop{\mathrm{{\mathbb{E}}}}X\).
Solution
\(\mathop{\mathrm{{\mathbb{E}}}}[(X-a)^2] = \mathop{\mathrm{{\mathbb{E}}}}[X^2-2aX+a^2] = \mathop{\mathrm{{\mathbb{E}}}}[X^2]-2a\mathop{\mathrm{{\mathbb{E}}}}X +a^2.\)
Consider a collection of random variables \(X_1,X_2,\dotsc,X_n\). By the linearity of expectation \[\begin{equation} \mathop{\mathrm{{\mathbb{E}}}}\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n \mathop{\mathrm{{\mathbb{E}}}}X_i. \end{equation}\] If all variables are identically distributed, then \[\begin{equation} \mathop{\mathrm{{\mathbb{E}}}}\left[\sum_{i=1}^n X_i\right] = n \mathop{\mathrm{{\mathbb{E}}}}X_1. \end{equation}\]
Example 0.15 Shared birthdays
In a class of \(n\) students, what is the expected number of pairs of students who have the same birthday?
Solution
For two students \(i\) and \(j\), let \(X_{ij}\) be equal to 1 if they share a birthday and 0 otherwise (the indicator of that event) and let \(X=\sum_{i=1}^{n-1}\sum_{j=i+1}^nX_{ij}\). Now, \[\begin{equation} \mathop{\mathrm{{\mathbb{E}}}}X=\binom{n}{2}\mathop{\mathrm{{\mathbb{E}}}}X_{12}=\binom{n}{2}{\Pr}(X_{12}=1)=\binom{n}{2}\frac1{365}\simeq\frac{n^2}{730}. \end{equation}\] In particular, having \(n=\sqrt{730}\simeq 27\) students in a class is enough to have on average one pair with the same birthday. With \(n=60\) and \(n=85\) students, there should be around 5 and 10 such pairs, respectively.
Example 0.16 The forgetful waiter
In a restaurant, \(n\) diners each order a different dish, and the forgetful waiter places the dishes in front of the diners at random. How many diners do we expect to receive the dish they ordered?
Image: ChatGPT
Solution
For any given diner, the probability of receiving the correct dish is \(\frac1n\). Letting \(X_i\) be the indicator of diner \(i\) being served correctly, the number of correctly served diners is \(X=\sum_{i=1}^n X_i\), so \[\mathop{\mathrm{{\mathbb{E}}}}X = \sum_{i=1}^n \mathop{\mathrm{{\mathbb{E}}}}X_i = n\cdot\frac1n = 1,\] regardless of \(n\). Note that the \(X_i\) are far from independent. For example, if \(n-1\) diners got the right dish, so did the remaining one. Linearity of expectation, however, does not require independence.
Exercise 0.17 Heads as indicators
A coin with probability of heads \(p\) is tossed \(n\) times and \(X\) is the number of heads. Write \(X\) as a sum of \(n\) indicator random variables and use linearity to show that \(\mathop{\mathrm{{\mathbb{E}}}}X=np\).
0.3.4.4 Variance
Suppose someone offers you a game in which your expected winning is $100. Will you accept? Which game would you play?
Sure thing You always win exactly $100.
Coin flip You win $0 with probability \(\nicefrac12\) and $200 with probability \(\nicefrac{1}{2}\).
High stakes You win $1200 with probability \(\nicefrac{1}{2}\) and lose $1000 with probability \(\nicefrac{1}{2}\).
All three have the same mean. So what’s different between them?
The mean helps us represent a distribution with one value, which describes the average behavior of the RV. But as this example shows, the behavior around the mean is also important. Denoting the mean of \(X\) by \(\mu_X\), the variability around the mean is captured to a degree by the variance \(\mathop{\mathrm{Var}}[X]\), \[\begin{equation*} \mathop{\mathrm{Var}}[X]=\mathop{\mathrm{{\mathbb{E}}}}[(X-\mu_X)^2]. \end{equation*}\] The variance gives a sense of how far \(X\) is from its mean \(\mu_X\), on average. The standard deviation, \({\sigma}_X\), is defined as \[{\sigma}_X=\sqrt{\mathop{\mathrm{Var}}[X]},\] and the variance is usually denoted as \({\sigma}_X^2\).
Exercise 0.18 Variance identity
Prove that \[\mathop{\mathrm{Var}}[X] = \mathop{\mathrm{{\mathbb{E}}}}X^2 - (\mathop{\mathrm{{\mathbb{E}}}}X)^2.\]
Exercise 0.19 Scaling and shifting
Find the mean and variance of each of the following RVs [1]:
\(X+c\)
\(aX\)
\(aX+c\)
\(\frac{X-\mu_X}{\sigma_X}\) (called the standardized version of \(X\))
0.3.4.5 Mode and median
Two other single-value summaries of a distribution are used alongside the mean. The mode is a value at which the pmf or pdf is maximized, and a median is a value \(m\) such that \({\Pr}(X\le m)\ge 1/2\) and \({\Pr}(X\ge m)\ge 1/2\) (for a continuous RV, a solution of \(F(m)=1/2\)). The three generally differ; as we will see when discussing Bayesian point estimates, each is the best single-value summary under a different measure of error. The median is less sensitive to outliers than the mean: if a billionaire walks into a bar, the mean income of the patrons jumps by millions while the median hardly moves.
Example 0.20 Summaries of the exponential
Find the mode, the median, and the mean of the exponential RV of Example 0.8 with parameter \({\lambda}\).
Solution
The pdf \({\lambda}e^{-\lambda x}\) is maximized at \(x=0\), the mode. The median solves \(1-e^{-\lambda m}=1/2\), giving \(m=(\ln 2)/{\lambda}\simeq 0.69/{\lambda}\). The mean is \(1/{\lambda}\).
Exercise 0.21 Discrete mode and median
Find the mode and the median of the RV of Exercise 0.13.
0.3.5 Common distributions
We denote \(X\) having distribution ‘\(\mathrm{Dist}\)’ by \(X\sim \mathrm{Dist}(a,b,\dotsc)\), where \(a,b,\dotsc\), are the parameters of the distribution.
0.3.5.1 Discrete distributions
\(X\sim\mathop{\mathrm{\mathrm{Ber}}}(p):\quad {\Pr}(X=1) = p,\ {\Pr}(X=0)=1-p,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = p,\quad \mathop{\mathrm{Var}}[X] = p(1-p).\)
\(X\sim\mathop{\mathrm{\mathrm{Cat}}}(\theta_1,\dotsc,\theta_k):\quad {\Pr}(X=i) = \theta_i,\ 1\le i\le k,\quad \sum_{i=1}^k\theta_i=1.\) The categorical distribution describes a single trial with \(k\) possible outcomes; \(\mathop{\mathrm{\mathrm{Ber}}}(p)\) is the special case \(k=2\). The vector of counts of the \(k\) outcomes in \(n\) independent trials has the multinomial distribution, which we will meet in a later chapter.
\(X\sim\mathop{\mathrm{\mathrm{Bin}}}(n,p)\):2 \(p(x) = \binom{n}{x}p^x(1-p)^{n-x},\ 0\le x\le n,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = np,\quad \mathop{\mathrm{Var}}[X] = np(1-p).\)
\(X\sim\mathop{\mathrm{\mathrm{Geo}}}(p):\quad p(x) = (1-p)^{x-1}p,\ x\ge 1,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = 1/p,\quad \mathop{\mathrm{Var}}[X] = \frac{1-p}{p^2}.\)
\(X\sim\mathop{\mathrm{\mathrm{Poi}}}({\lambda}):\quad p(x) = \frac{\lambda^x e^{-\lambda}}{x!},\ x\ge 0,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = {\lambda},\quad \mathop{\mathrm{Var}}[X] = {\lambda}.\)
\(X\sim\mathop{\mathrm{\mathrm{Uni}}}[a,b]:\quad p(x) = \frac{1}{b-a+1},\ x\in{\mathbb{Z}},a\le x\le b,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = \frac{a+b}{2},\quad \mathop{\mathrm{Var}}[X] = \frac{(b-a+1)^2-1}{12}.\)
Example 0.22 A character-level language model
A simple model of English text treats the next character as a categorical random variable: with an alphabet consisting of the letters a–z and the space character, we have \(k=27\), and \(\theta_1,\dotsc,\theta_{27}\) can be set to the letter frequencies of English. Generating text then amounts to repeatedly sampling from this distribution (Section 0.3.6 shows how). Modern language models produce text the same way: at each step, the next token is drawn from a categorical distribution over a large vocabulary, whose parameters are computed from the text so far.
0.3.5.2 Continuous distributions
\(X\sim\mathop{\mathrm{\mathrm{Uni}}}(a,b):\quad p(x) = \frac{1}{b-a},\ x\in(a,b),\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = \frac{a+b}{2},\quad \mathop{\mathrm{Var}}[X] = \frac{(b-a)^2}{12}.\)
\(X\sim\mathop{\mathrm{{\mathcal{N}}}}(\mu,\sigma^2):\quad p(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp(-\frac{(x-\mu)^2}{2\sigma^2}),\ x\in{\mathbb{R}},\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = {\mu},\quad \mathop{\mathrm{Var}}[X] = {\sigma}^2.\)
\(X\sim\mathop{\mathrm{\mathrm{Exp}}}(\lambda):\quad p(x) = {\lambda}e^{-\lambda x},\ x\ge 0,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = {1/{\lambda}},\quad \mathop{\mathrm{Var}}[X] = {1/{\lambda}}^2.\)
A useful property of the normal distribution is closure under linear transformations: if \(X\sim\mathop{\mathrm{{\mathcal{N}}}}(\mu,{\sigma}^2)\), then \(aX+b\sim\mathop{\mathrm{{\mathcal{N}}}}(a\mu+b,a^2{\sigma}^2)\), and a sum of independent normal RVs is again normal. We will study the multivariate version of this fact in a later chapter.
Sometimes, we drop the normalization constant, that is, the constant by which we divide to ensure that the distribution integrates to 1. This could be because the constant is not important (e.g., in Bayesian inference) or because it is hard to determine. In such cases, we use \(\propto\) to show proportionality rather than equality. We should be careful which of the entities appearing is the variable. For example, viewed as a function of \(x\), we have \(f(x)=\frac{\lambda^x e^{-\lambda}}{x!}\propto \frac{\lambda^x} {x!}\) and as a function of \({\lambda}\), we have \(g({\lambda})=\frac{\lambda^x e^{-\lambda}}{x!}\propto{\lambda^x e^{-\lambda}}\).
\(X\sim\mathop{\mathrm{\mathrm{Beta}}}(\alpha,\beta):\quad p(x) \propto x^{\alpha-1}(1-x)^{\beta-1},\ 0\le x\le 1,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = \frac{\alpha}{\alpha+\beta},\quad \mathop{\mathrm{Var}}[X] = \frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}.\)
\(X\sim\mathop{\mathrm{\mathrm{Gamma}}}(\alpha,\beta):\quad p(x) \propto x^{\alpha-1}e^{-\beta x},\ x>0,\quad \mathop{\mathrm{{\mathbb{E}}}}[X] = \frac{\alpha}{\beta},\quad \mathop{\mathrm{Var}}[X] = \frac{\alpha}{\beta^2}.\)
Example 0.23 Swapping variable and parameter
For the distributions given in this section, try changing what the variable is and what the parameters are and check whether another distribution from the list can be obtained with appropriate normalization.
Solution
For example, \(\mathop{\mathrm{\mathrm{Bin}}}(n,p)\) viewed as a distribution in \(p\) turns into \(\mathop{\mathrm{\mathrm{Beta}}}(x+1,n-x+1)\).
0.3.6 Functions of a random variable and sampling
If \(X\) is a random variable and \(g\) a function, then \(Y=g(X)\) is also a random variable, whose distribution is determined by that of \(X\). For a discrete \(X\), \[p_Y(y) = \sum_{x:\,g(x)=y} p_X(x).\]
Example 0.24 Distribution of \(|X|\)
Let \(X\) be uniform on \(\{-2,-1,0,1,2\}\) and \(Y=|X|\). Find the pmf of \(Y\).
Solution
\(p_Y(0)=1/5\) and \(p_Y(1)=p_Y(2)=2/5\).
For a continuous \(X\) and a strictly increasing \(g\), the CDF of \(Y=g(X)\) is \[F_Y(y) = {\Pr}(g(X)\le y) = {\Pr}\left(X\le g^{-1}(y)\right) = F_X\left(g^{-1}(y)\right),\] and differentiating gives the change-of-variables formula \[p_Y(y) = p_X\left(g^{-1}(y)\right)\frac{dg^{-1}(y)}{dy},\] where for a strictly decreasing \(g\) the derivative is replaced by its absolute value.
Example 0.25 From uniform to exponential
Let \(X\sim\mathop{\mathrm{\mathrm{Uni}}}(0,1)\) and \(Y=-\ln X\). Find the distribution of \(Y\).
Solution
For \(y\ge 0\), \[F_Y(y) = {\Pr}(-\ln X\le y) = {\Pr}\left(X\ge e^{-y}\right) = 1-e^{-y},\] so \(Y\sim\mathop{\mathrm{\mathrm{Exp}}}(1)\): transforming a uniform random variable has produced an exponential one.
0.3.6.1 Sampling and the inverse-CDF transform
Computers readily produce pseudo-random samples from \(\mathop{\mathrm{\mathrm{Uni}}}(0,1)\). Samples from other distributions, needed whenever we simulate a model or generate data from it, are obtained by transforming such uniform samples, as in Example 0.25. The general recipe inverts the CDF:
Definition 0.26 Generalized inverse CDF
For a CDF \(F\) and \(0<u<1\), the generalized inverse of \(F\), also called its quantile function, is \[F^{-1}(u) = \min\{x: F(x)\ge u\},\] the smallest value at which the CDF has reached \(u\).3
This definition applies to any random variable, discrete or continuous. If \(F\) is continuous and strictly increasing, \(F^{-1}(u)\) is the ordinary inverse, the unique \(x\) with \(F(x)=u\). If \(X\) is discrete, \(F\) is a staircase and \(F^{-1}(u)\) is the first value of \(X\) whose cumulative probability reaches \(u\).
Theorem 0.27 Inverse-CDF transform
Let \(F\) be a CDF and \(U\sim\mathop{\mathrm{\mathrm{Uni}}}(0,1)\). Then \(X=F^{-1}(U)\) has CDF \(F\).
Proof
For any \(c\), we have \(F^{-1}(u)\le c\) if and only if \(u\le F(c)\). If \(u\le F(c)\), then \(c\) belongs to the set \(\{x:F(x)\ge u\}\), so the minimum of that set is at most \(c\). Conversely, if \(F^{-1}(u)\le c\), then \(F(c)\ge F(F^{-1}(u))\ge u\) because \(F\) is non-decreasing. Hence \({\Pr}(X\le c) = {\Pr}\left(F^{-1}(U)\le c\right) = {\Pr}\left(U\le F(c)\right) = F(c)\).
Fig. 1 shows a CDF and its inverse side by side, drawn to the same scales, so that the inverse is the CDF reflected with its two axes exchanged. Two intervals of the same width are shaded on the \(F^{-1}\) axis. Reading each across to the curve and down gives the values of \(u\) that are mapped into it, and those two sets of \(u\) have very different lengths: \(-1\le X\le 0\) has probability \(0.23\) and \(2\le X\le 3\) has probability \(0.07\), so a uniform \(U\) produces a value in the first interval more than three times as often. An interval of \(u\)-values of length \(\ell\) is always mapped to a set of values of probability \(\ell\).
Example 0.28 Sampling an exponential
Find a function \(G:(0,1)\to \mathbb R\) such that \(G(U)\) is exponentially distributed with parameter \({\lambda}\), where \(U\sim\mathop{\mathrm{\mathrm{Uni}}}(0,1)\).
Solution
We have \(F(x) = 1-e^{-\lambda x}\). Set \(G(u) = F^{-1}(u) = -\ln(1-u)/{\lambda}\). So \(-\ln(1-U)/{\lambda}\), with \(U\sim\mathop{\mathrm{\mathrm{Uni}}}(0,1)\), is a sample from \(\mathop{\mathrm{\mathrm{Exp}}}({\lambda})\). This is consistent with Example 0.25, since \(1-U\) is also uniform on \((0,1)\).
For a discrete distribution, the CDF is a staircase and so is its inverse: the jump of size \(\theta_i\) that the CDF makes at \(i\) becomes an interval of \(u\) of length \(\theta_i\) on which \(F^{-1}\) equals \(i\) (Fig. 2). Sampling therefore amounts to partitioning \([0,1)\) into consecutive intervals of lengths \(\theta_1,\theta_2,\dotsc\) and outputting \(i\) if \(U\) falls in the \(i\)th interval, which happens with probability \(\theta_i\), as required.
Sampling general 1-D random variables
To sample from a distribution, take \(U\sim\mathop{\mathrm{\mathrm{Uni}}}(0,1)\) and apply to it the inverse CDF.
Example 0.29 Sampling a categorical
How can we sample from \(\mathop{\mathrm{\mathrm{Cat}}}(0.5,0.3,0.2)\)?
Solution
Draw \(U\sim\mathop{\mathrm{\mathrm{Uni}}}(0,1)\); output 1 if \(U<0.5\), output 2 if \(0.5\le U<0.8\), and output 3 otherwise. Repeating this with the letter frequencies of English generates (zero-order) random text.
Exercise 0.30 Sampling a geometric
Give an algorithm that turns a \(\mathop{\mathrm{\mathrm{Uni}}}(0,1)\) sample into a sample from \(\mathop{\mathrm{\mathrm{Geo}}}(p)\).
0.4 Joint probability distributions
Joint probability distributions allow us to encode information about relationships between quantities.
For random variables \(X\) and \(Y\), the CDF and the pmf/pdf give their joint distribution, depending on their type, \[\begin{align*} F_{X,Y}(x,y) &= {\Pr}(X\le x,Y\le y), &\text{CDF for continuous and discrete}\\ p_{X,Y}(x,y) &= {\Pr}(X=x,Y=y), &\text{pmf for discrete}\\ p_{X,Y}(x,y)dx dy &\simeq {\Pr}\left(x-\frac{dx}{2}\le X\le x+\frac{dx}{2},y-\frac{dy}{2}\le Y\le y+\frac{dy}{2}\right) ,&\text{pdf for continuous}\\ \end{align*}\] We can find the distribution for each random variable (in this context these are called the marginals) by integration/summation, \[\begin{align*} p_X(x) &= \sum_y p_{X,Y}(x,y),& p_X(x) &= \int_{-\infty}^{\infty}p_{X,Y}(x,y)dy. \end{align*}\]
Example 0.31 A joint pmf table
A fair coin is flipped twice. Let \(X\) be 1 if the first flip is heads and 0 otherwise, and let \(Y\) be the total number of heads. Find the joint pmf of \(X\) and \(Y\) and the two marginals.
Solution
Each of the four outcomes has probability \(\nicefrac14\), giving the joint pmf below. The pmfs of \(X\) and \(Y\) are obtained by summing each row and column, and are written, as is customary, in the margins of the table, which is where the name marginal comes from.
| \(p_{X,Y}(x,y)\) | \(y=0\) | \(y=1\) | \(y=2\) | \(p_X(x)\) |
|---|---|---|---|---|
| \(x=0\) | \(\nicefrac14\) | \(\nicefrac14\) | \(0\) | \(\nicefrac12\) |
| \(x=1\) | \(0\) | \(\nicefrac14\) | \(\nicefrac14\) | \(\nicefrac12\) |
| \(p_Y(y)\) | \(\nicefrac14\) | \(\nicefrac12\) | \(\nicefrac14\) |
For instance, \(p_Y(1) = p_{X,Y}(0,1)+p_{X,Y}(1,1)=\nicefrac14+\nicefrac14=\nicefrac12\).
0.4.1 Expectation, correlation, and covariance
Given two or more RVs, we may be interested in finding the expected value of a function of these RVs, e.g., \(\mathop{\mathrm{{\mathbb{E}}}}[XY]\). In such cases, similar to (0.2), we have \[\begin{equation} \begin{split} \mathop{\mathrm{{\mathbb{E}}}}[f(X,Y)] &= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(x,y)p(x,y)dxdy, \end{split} \end{equation}\tag{0.6}\] and similarly for discrete variables.
The correlation between \(X\) and \(Y\) is \(\mathop{\mathrm{{\mathbb{E}}}}[XY] = \int\int xy p(x,y)dxdy.\) The covariance \(\mathop{\mathrm{Cov}}(X,Y)\) and the correlation coefficient \(\rho_{X,Y}\) are defined as \[\begin{align*} \mathop{\mathrm{Cov}}(X,Y) &= \mathop{\mathrm{{\mathbb{E}}}}[(X-\mu_X)(Y-\mu_Y)]\\ \rho_{X,Y} &= \frac{\mathop{\mathrm{Cov}}(X,Y)}{{\sigma}_X{\sigma}_Y}. \end{align*}\] It can be shown that \(-1\le \rho_{X,Y}\le 1\). If \(\rho=0\), then the random variables are uncorrelated.
What does the correlation coefficient mean? Let \(X\) and \(Y\) be random variables, for example, weight and height of a person chosen at random. Suppose that we want to predict the value of \(Y\) given \(X\) but we are restricted to linear functions of \(X\). Then, in a certain sense,4 the best predictor \(\hat Y\) of \(Y\) is \[\hat Y = \mathop{\mathrm{{\mathbb{E}}}}Y+ \rho \frac{\sigma_Y}{\sigma_X} (X-\mathop{\mathrm{{\mathbb{E}}}}X),\] with the “error” being \[\sigma_{Y}^{2}\left(1-\rho^{2}\right).\] In particular, if \(X\) and \(Y\) are standardized, \(\hat Y = \rho X\) with error \(1-\rho^2\).
Exercise 0.32 Strong correlation
If \(|\rho|\) is close to 1, the RVs are said to be strongly correlated. Why?
Exercise 0.33 Covariance identity
Show that \(\mathop{\mathrm{Cov}}(X,Y) = \mathop{\mathrm{{\mathbb{E}}}}[XY]-\mathop{\mathrm{{\mathbb{E}}}}X\mathop{\mathrm{{\mathbb{E}}}}Y\).
Example 0.34 Bivariate normal
The bivariate jointly Gaussian distribution for \(X\),\(Y\) with means \(\mu_X\) and \(\mu_Y\), standard deviations \({\sigma}_X\) and \({\sigma}_Y\), and correlation coefficient \(\rho\) is given as \[\begin{equation*} p(x,y) = \frac{1}{2\pi{\sigma}_X{\sigma}_Y\sqrt{1-\rho^2}}e^{-\frac{1}{2(1-\rho^2)}\left[ \frac{(x-\mu_X)^2}{\sigma_X^2} + \frac{(y-\mu_Y)^2}{\sigma_Y^2} - \frac{2\rho(x-\mu_X)(y-\mu_Y)}{\sigma_X \sigma_Y} \right]}. \end{equation*}\] Examples of this pdf are given in Figure 3.
Exercise 0.35 Covariance properties
For random variables \(X,Y,Z\) and constants \(a,b,c,d,e\), prove that
\(\mathop{\mathrm{Var}}(X)=\mathop{\mathrm{Cov}}(X,X)\)
\(\mathop{\mathrm{Cov}}(X+Y,Z) = \mathop{\mathrm{Cov}}(X,Z)+\mathop{\mathrm{Cov}}(Y,Z)\)
\(\mathop{\mathrm{Cov}}(aX,Y)=a\mathop{\mathrm{Cov}}(X,Y)\)
\(\mathop{\mathrm{Cov}}(X,b) = 0\)
\(\mathop{\mathrm{Cov}}(aX+bY+c,dZ+e)=ad\mathop{\mathrm{Cov}}(X,Z)+bd\mathop{\mathrm{Cov}}(Y,Z)\)
\(\mathop{\mathrm{Var}}(X+Y)=\mathop{\mathrm{Var}}(X)+\mathop{\mathrm{Var}}(Y)+2\mathop{\mathrm{Cov}}(X,Y)\)
Exercise 0.36 Dice covariance
Find the expected values and variances of \(X\) and \(Y\) from Exercise 0.6. Find \(\mathop{\mathrm{Cov}}(X,Y)\).
0.4.2 Independence
Recall that two events \(A\) and \(B\) are independent, denoted \(A{\mathrel{\perp\mkern-10mu\perp}}B\), iff (if and only if) \({\Pr}(A\cap B)={\Pr}(A){\Pr}(B)\). Two random variables \(X\) and \(Y\) are independent if \(\{X\in S_1\}\) and \(\{Y\in S_2\}\) are independent for all sets \(S_1\) and \(S_2\). This implies that \[\begin{equation} p(x,y) = p(x)p(y). \end{equation}\tag{0.7}\]
Example 0.37 Hearts and aces
A card is drawn at random from a standard 52-card deck. Determine whether the following pairs of events are independent: ‘heart’ and ‘ace’; ‘red’ and ‘heart’; ‘black’ and ‘heart’.
Solution
The events ‘heart’ and ‘ace’ are independent: \[{\Pr}(\text{heart})=\frac14,\quad {\Pr}(\text{ace})=\frac1{13},\quad {\Pr}(\text{heart and ace})=\frac1{52}=\frac14\cdot\frac1{13}.\] The events ‘red’ and ‘heart’ are not independent: \({\Pr}(\text{red and heart})=\frac14\ne\frac12\cdot\frac14\). Neither are ‘black’ and ‘heart’, which are disjoint: \({\Pr}(\text{black and heart})=0\ne\frac12\cdot\frac14\). In fact, disjoint events with nonzero probabilities are never independent: each rules the other out, which is as far from ‘no information’ as possible.
For two independent random variables, we have \[\begin{equation} \mathop{\mathrm{{\mathbb{E}}}}[XY]=\mathop{\mathrm{{\mathbb{E}}}}[X]\mathop{\mathrm{{\mathbb{E}}}}[Y] \end{equation}\tag{0.8}\] and \(\mathop{\mathrm{Cov}}(X,Y)=0\).
Exercise 0.39 Independent sums
For two independent RVs \(X\) and \(Y\), find \(\mathop{\mathrm{Var}}[X+Y]\) and \(\mathop{\mathrm{{\mathbb{E}}}}[(X-Y)^2+3XY+5]\) in terms of means and variances of \(X\) and \(Y\).
A collection \(X_1,\dotsc,X_n\) of random variables that are independent from each other but have the same distribution are called independent and identically distributed (iid). We have \[\begin{equation} p(x_1,\dotsc,x_n)= \prod_{i=1}^n p(x_i). \end{equation}\]
Exercise 0.40 Variance of a sum
For iid RVs \(X_1,\dotsc,X_n\), let \(S_n = \sum_{i=1}^n X_i\). Show that \[\begin{align} \mathop{\mathrm{Var}}(S_n) = \sum_{i=1}^n \mathop{\mathrm{Var}}(X_i). \end{align}\]
Exercise 0.41 The sample mean
For iid RVs \(X_1,\dotsc,X_n\), suppose \(\mathop{\mathrm{{\mathbb{E}}}}[X_i]=\mu\) and \(\mathop{\mathrm{Var}}[X_i]=\sigma^2\), and let \(\bar X\) be their average. Show that \[\begin{align} \mathop{\mathrm{{\mathbb{E}}}}[\bar X]&=\mu,&\mathop{\mathrm{Var}}[\bar X]&=\frac{\sigma^2}{n}. \end{align}\]
0.4.3 Conditional probability and conditional distributions
For events \(A\) and \(B\) with \({\Pr}(B)\neq0\), the conditional probability of \(A\) given \(B\) is defined as \[{\Pr}(A|B)=\frac{{\Pr}(A\cap B)}{{\Pr}(B)}.\] For two discrete variables \(X\) and \(Y\), the conditional probability distribution of \(Y\) given \(X\) is given by \[\begin{align*} p_{Y|X}(y|x) = {\Pr}(Y=y|X=x) = \frac{{\Pr}(Y=y,X=x)}{{\Pr}(X=x)}=\frac{p_{X,Y}(x,y)}{p_X(x)}. \end{align*}\] For continuous RVs, we also have \(p_{Y|X}(y|x) =\frac{p_{X,Y}(x,y)}{p_X(x)}.\) In this case, however, we interpret the conditional density as \[p_{Y|X}(y|x) \simeq \frac{{\Pr}\left(y-\epsilon/2\le Y\le y+\epsilon/2|x-\epsilon/2\le X\le x+\epsilon/2\right)}{\epsilon},\] for small positive \(\epsilon\). This essentially says to find \(p_{Y|X}(y|x)\), we first assume that \(X\) is in a narrow strip around \(x\) and then find the density for \(Y\) given this assumption.
Law of total probability. Let \(A_1,A_2,\dotsc,A_n\) be a partition of the sample space. That is, \(\cup_{i=1}^n A_i=\Omega\) and for all \(i\neq j\), we have \(A_i\cap A_j=\varnothing\). For an event \(B\), we have \[{\Pr}(B) = \sum_{i=1}^n {\Pr}(B\cap A_i) = \sum_{i=1}^n {\Pr}(B|A_i){\Pr}(A_i).\] In particular, if \(X\) can take on \(\{1,2,\dotsc,n\}\), then for another RV Y, \[p_Y(y) = \sum_{x=1}^n p_{Y|X}(y|x)p_X(x).\]
Exercise 0.42 Monty Hall
On a game show, a prize is hidden behind one of three doors. You pick a door; the host, who knows where the prize is, opens one of the other two doors, revealing no prize, and offers you the chance to switch to the remaining unopened door. Using the law of total probability (conditioning on which door hides the prize), show that switching wins with probability \(\frac23\), while staying with your original choice wins with probability \(\frac13\).5
Chain rule of probability. For events \(A_1,\dotsc,A_n\), we have \[{\Pr}(A_1\cap A_2\cap \dotsm \cap A_n) = {\Pr}(A_1){\Pr}(A_2|A_1){\Pr}(A_3|A_1,A_2)\dotsm {\Pr}(A_n|A_1,\dotsc,A_{n-1}),\] which can be easily proven by induction. A similar rule holds for random variables \(X_1,\dotsc,X_n\): \[p(x_1,\dotsc,x_n) = p(x_1)p(x_2|x_1)p(x_3|x_1,x_2)\dotsc p(x_n|x_1,\dotsc,x_{n-1}).\]
0.4.3.1 Conditional independence
Two events \(A\) and \(B\) are conditionally independent given an event \(C\) with \({\Pr}(C)>0\) if \[{\Pr}(A\cap B|C) = {\Pr}(A|C){\Pr}(B|C).\] Similarly, random variables \(X\) and \(Z\) are conditionally independent given \(Y\), denoted \(X{\mathrel{\perp\mkern-10mu\perp}}Z\mid Y\), if \[p(x,z|y) = p(x|y)\,p(z|y)\qquad \text{for all } x,y,z,\] or, equivalently, \(p(z|x,y) = p(z|y)\): once \(Y\) is known, also learning \(X\) provides no further information about \(Z\).
Conditional independence neither implies nor is implied by (unconditional) independence, as the following two examples show.
Example 0.43 Alice, Bob, and traffic
Alice and Bob take the same route to work. Let \(T\) indicate whether traffic is heavy, with \({\Pr}(T=1)=1/2\), and let \(X\) and \(Z\) indicate whether Alice and Bob are late, respectively. Given the state of traffic, they are late independently: conditioned on \(T=1\), \(X\) and \(Z\) are independent \(\mathop{\mathrm{\mathrm{Ber}}}(0.8)\) RVs, and conditioned on \(T=0\), they are independent \(\mathop{\mathrm{\mathrm{Ber}}}(0.2)\) RVs. So \(X{\mathrel{\perp\mkern-10mu\perp}}Z\mid T\) by construction. Are \(X\) and \(Z\) independent?
Solution
They are not: \[{\Pr}(X=1) = {\Pr}(Z=1) = \frac12(0.8)+\frac12(0.2) = 0.5,\] while \[{\Pr}(X=1,Z=1) = \frac12(0.8)^2+\frac12(0.2)^2 = 0.34 \ne 0.25 = {\Pr}(X=1){\Pr}(Z=1).\] Intuitively, learning that Alice is late makes heavy traffic more likely, which in turn makes it more likely that Bob is late.
Example 0.44 Agreement of two coins
Two fair coins are flipped independently, giving \(X\) and \(Z\) (each 1 for heads), and let \(Y = 𝟙(X=Z)\) indicate whether they agree. Then \(X\) and \(Z\) are independent. Are they conditionally independent given \(Y\)?
Solution
No. Given \(Y=1\), knowing \(X\) determines \(Z\) exactly: \(p(z|x,Y=1)\) equals 1 for \(z=x\) and 0 otherwise, while \(p(z|Y=1)=1/2\). So \(X\mathrel{\rlap{\mkern5.5mu/}{\perp\mkern-10mu\perp}}Z\mid Y\).
Exercise 0.45 Learning from Alice
In Example 0.43, find \({\Pr}(Z=1|X=1)\) and compare it with \({\Pr}(Z=1)\).
Conditional expectations are defined based on conditional distributions, e.g., \[\begin{equation*} \mathop{\mathrm{{\mathbb{E}}}}[X|Y=y] = \sum_{x} x p_{X|Y}(x|y). \end{equation*}\]
Exercise 0.46 A conditional pmf table
Suppose the joint pmf is given as
| \(p_{X,Y}(x,y)\) | \(x=0\) | \(x=1\) |
|---|---|---|
| \(y=0\) | 0.25 | 0 |
| \(y=1\) | 0.5 | 0.25 |
Find \(p(y|x)\), \(p(x|y)\), \(\mathop{\mathrm{{\mathbb{E}}}}[Y|X=0]\), \(\mathop{\mathrm{{\mathbb{E}}}}[Y|X=1]\), \(\mathop{\mathrm{{\mathbb{E}}}}[X|Y=0]\), \(\mathop{\mathrm{{\mathbb{E}}}}[X|Y=1]\).
Exercise 0.47 Point in a triangle
A point is chosen uniformly at random in a triangle with vertices on \((0,0),(1,0),(1,1)\). Let \(X\) and \(Y\) determine the \(x\) and \(y\) coordinates of the chosen point. Find \(p(x|y)\), \(p(y|x)\), \(\mathop{\mathrm{{\mathbb{E}}}}[X|Y=y]\), \(\mathop{\mathrm{{\mathbb{E}}}}[Y|X=x]\).
0.4.3.2 Law of iterated expectations
Consider a random variable \(X\) and a function \(g(x)\). We can now obtain \(g(X)\) by replacing the deterministic value for \(x\) with a random one. Note that \(g(X)\) is a random variable. For example, if \(X\sim\mathop{\mathrm{\mathrm{Uni}}}(-1,1)\) and \(g(x)=|x|\), then \(g(X)\) is a random variable with distribution \(\mathop{\mathrm{\mathrm{Uni}}}(0,1)\).
Now let \(g(x)=\mathop{\mathrm{{\mathbb{E}}}}[Y|X=x]\). This is, of course, a well-defined function. We define \(\mathop{\mathrm{{\mathbb{E}}}}[Y|X]=g(X)\), which is as discussed a random variable. Now that we have a random variable, we can compute its expectation, i.e., \(\mathop{\mathrm{{\mathbb{E}}}}[\mathop{\mathrm{{\mathbb{E}}}}[Y|X]]\).
Exercise 0.48 Die then coins
A die is rolled, showing \(X\). A coin is then flipped \(X\) times resulting in \(Y\) heads. Find the conditional pmf \(p_{Y|X}(y|3)\), \(\mathop{\mathrm{{\mathbb{E}}}}[Y]\), \(\mathop{\mathrm{{\mathbb{E}}}}[Y|X=x]\), the pmf of \(\mathop{\mathrm{{\mathbb{E}}}}[Y|X]\), and \(\mathop{\mathrm{{\mathbb{E}}}}[\mathop{\mathrm{{\mathbb{E}}}}[Y|X]]\).
It can be shown that \[\begin{align} \mathop{\mathrm{{\mathbb{E}}}}[\mathop{\mathrm{{\mathbb{E}}}}[Y|X]]&=\mathop{\mathrm{{\mathbb{E}}}}[Y],& \mathop{\mathrm{{\mathbb{E}}}}[\mathop{\mathrm{{\mathbb{E}}}}[Y|X,Z]|Z] &= \mathop{\mathrm{{\mathbb{E}}}}[Y|Z]. \end{align}\]
0.4.4 Bayes’ rule
In Exercise 0.48, the conditional distribution \(p(y|x)\) is readily available as \[\begin{equation*} p(y|x) = \binom{x}{y}2^{-x}. \end{equation*}\] But what if we are interested in \(p(x|y)\)? Since \(p(x|y) = \frac{p(x,y)}{p(y)}\) and \(p(x,y)=p(y|x)p(x)\), we have \[\begin{align*} p(x|y) &= \frac{p(y|x)p(x)}{p(y)}= \frac{p(y|x)p(x)}{\sum_{x'} p(y|x')p(x')}, \end{align*}\] which is called Bayes’ rule.
Example 0.49 Inferring the die roll
In Exercise 0.48, find \(p(x|y)\). What are the likeliest values for \(X\) if \(Y=2\)?
Solution
By Bayes’ rule, \[\begin{align*} p(x|y) &= \frac{\binom{x}{y}2^{-x}(1/6)}{\sum_{x'=y}^6 \binom{x'}{y}2^{-x'}(1/6)}= \frac{\binom{x}{y}2^{-x}}{\sum_{x'=y}^6 \binom{x'}{y}2^{-x'}}. \end{align*}\] The plot below shows \(p_{X|Y}(x|2)\), the conditional distribution of \(X\) given \(Y=2\). We can see that the likeliest values for \(X\) are \(3,4\).
Bayes’ rule is used in evidential reasoning, examples of which we will see in the next chapter. In this setting, the goal is to find the probabilities of different causes based on the evidence.
Bayesian inference takes its name from Bayes’ rule. In this setting, it is often the case that we know the distribution of data given the parameters. But what we actually have is data and need to find the distribution of the parameters. Bayes’ rule allows us to find this conditional distribution, a topic we will discuss in detail later.
0.5 Limit theorems
Limits in probability provide a way to understand what happens when the number of experiments grows or many random effects accumulate. Limit theorems are beneficial given that we often deal with large volumes of data. The following limit theorems will be helpful to us later in the course.
0.5.1 Law of large numbers
Let \(X_1,\dots,X_n\) be random variables with mean \(\mu\) and variance \(\le{\sigma}^2\) and suppose that for each \(i\neq j\), \(X_i\) and \(X_j\) are uncorrelated (as is the case, in particular, if they are independent). Also, let \(\bar{X}_n=\frac{1}{n}\sum_{i=1}^nX_i\). Then, for any \(\epsilon>0\), \[\begin{equation} {\Pr}\left(|\bar X_n-\mu|\ge \epsilon\right)\le \frac{{\sigma}^2}{n\epsilon^2}. \end{equation}\tag{0.13}\] As \(n\) becomes large the right side becomes smaller and smaller. So for large \(n\) the probability of \(\bar X_n\) being too far from the mean is very small. This is referred to as the Law of Large Numbers (LLN). In other words, if we take \(n\) independent samples from a random variable \(X\), then the average of those samples will be close to the mean \(\mathop{\mathrm{{\mathbb{E}}}}X\), \[\frac{1}{n}(x_1+x_2+\dotsb+x_n)\simeq \mathop{\mathrm{{\mathbb{E}}}}[X],\] which is what we used to motivate expected value. This mode of convergence, \({\Pr}(|\bar X_n-\mu|\ge\epsilon)\to0\) for every \(\epsilon>0\), is called convergence in probability: \(\bar X_n\) converges in probability to \(\mu\). We will encounter it again when defining what it means for an estimator to be consistent.
Exercise 0.50 Proving the LLN
Use the Chebyshev inequality (Section 0.7) to prove LLN when random variables are independent and all have the same variance \({\sigma}^2\).
Example 0.51 LLN in simulation
Suppose \(X_i\sim \mathop{\mathrm{\mathrm{Poi}}}(2)\), \(1\le i\le 500,\) and let \(\bar X_n\) be the average of the first \(n\) \(X_i\)s. Fig. 4 shows the plot for \(\bar X_n\) for a realization of \(X_i\)s obtained via computer simulation. It is observed that for large values of \(n\), \(\bar X_n\) is close to \(2\), the mean of the Poisson distribution.
0.5.2 Central limit theorem
Let \(X_1,X_2,\dotsc\) be iid random variables with mean \(\mu\) and variance \({\sigma}^2\) and let \(\bar X_n=\frac{1}{n}\sum_{i=1}^nX_i\). The Central Limit Theorem (CLT) states that, as \(n\to\infty\), \[\begin{equation} \text{distribution of }\sqrt{n}(\bar X_n-\mu) \quad\to\quad\mathop{\mathrm{{\mathcal{N}}}}(0,{\sigma}^2). \end{equation}\tag{0.14}\] That is, the distribution of \(\sqrt{n}(\bar X_n-\mu)\) approaches the distribution of a normal random variable with mean 0 and variance \({\sigma^2}\). This mode of convergence, in which the CDF of a sequence of random variables approaches the CDF of a limiting distribution, is called convergence in distribution.
Loosely speaking, the CLT also means \(S_n=\sum_{i=1}^n X_i\) has distribution \(\mathop{\mathrm{{\mathcal{N}}}}(n\mu,n{\sigma}^2)\).
Long-term averages approach the mean, deviating normally
The average of many independent samples concentrates around \(\mathop{\mathrm{{\mathbb{E}}}}X\), and by the CLT its fluctuations around the mean are approximately normal.
Example 0.52 CLT in simulation
Let \(X_i\sim\mathop{\mathrm{\mathrm{Uni}}}(0,1), 1\le i\le n=10\). We produce \(50,000\) samples of \(\bar X_n\) (and \(S_n\)), and plot the normalized histograms for \(\sqrt{n}(\bar X_n-\mu)\) and the pdf of \(\mathop{\mathrm{{\mathcal{N}}}}(0,{\sigma}^2)\) and the normalized histogram for \(S_n\) and the pdf of \(\mathop{\mathrm{{\mathcal{N}}}}(n\mu,n{\sigma}^2)\) in Fig. 5.
0.6 Random vectors
A random vector is a vector of random variables.6 Consider the random vectors \({{\boldsymbol{X}}}\) and \({{\boldsymbol{Y}}}\) \[\begin{equation} {{\boldsymbol{X}}}= \begin{pmatrix}X_1\\\vdots\\X_m\end{pmatrix},\quad {{\boldsymbol{Y}}}= \begin{pmatrix}Y_1\\\vdots\\Y_n\end{pmatrix}. \end{equation}\] The expected value of \({{\boldsymbol{X}}}\) is \[\begin{equation} \mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{X}}}= \begin{pmatrix}\mathop{\mathrm{{\mathbb{E}}}}X_1\\\vdots\\\mathop{\mathrm{{\mathbb{E}}}}X_m\end{pmatrix}. \end{equation}\] The correlation matrix of \({{\boldsymbol{X}}}\) and \({{\boldsymbol{Y}}}\) is the \(m\times n\) matrix \(\mathop{\mathrm{{\mathbb{E}}}}[{{\boldsymbol{X}}}{{\boldsymbol{Y}}}^T]\), whose \(i,j\)th element is \(\mathop{\mathrm{{\mathbb{E}}}}[X_iY_j]\). The cross-covariance matrix \(\mathop{\mathrm{Cov}}({{\boldsymbol{X}}},{{\boldsymbol{Y}}})\) of \({{\boldsymbol{X}}}\) and \({{\boldsymbol{Y}}}\) is the matrix \(\mathop{\mathrm{{\mathbb{E}}}}[({{\boldsymbol{X}}}-\mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{X}}})({{\boldsymbol{Y}}}-\mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{Y}}})^T]\), whose \(i,j\)th element is \(\mathop{\mathrm{Cov}}(X_i,Y_j)\). The covariance of a vector \({{\boldsymbol{X}}}\) is \(\mathop{\mathrm{Cov}}({{\boldsymbol{X}}})=\mathop{\mathrm{Cov}}({{\boldsymbol{X}}},{{\boldsymbol{X}}})\). The conditional expectation \(\mathop{\mathrm{{\mathbb{E}}}}[{{\boldsymbol{X}}}|{{\boldsymbol{Y}}}]\) of \({{\boldsymbol{X}}}\) given \({{\boldsymbol{Y}}}\) is a vector whose \(i\)th element is \(\mathop{\mathrm{{\mathbb{E}}}}[X_i|{{\boldsymbol{Y}}}]\).
If the elements of \({{\boldsymbol{X}}}\) are uncorrelated, then \(\mathop{\mathrm{Cov}}(X_i,X_j)=0\) for \(i\neq j\) and the covariance matrix becomes diagonal. If, in addition, \(\mathop{\mathrm{Cov}}(X_i,X_i) = \mathop{\mathrm{Var}}(X_i) = \sigma^2\), i.e., all elements of \({{\boldsymbol{X}}}\) have the same variance \(\sigma^2\), then \(\mathop{\mathrm{Cov}}({{\boldsymbol{X}}}) = \sigma^2 I\).
0.6.1 Properties of expectation and covariance
For deterministic matrices \({\mathsf{A}},{\mathsf{B}}\), deterministic vectors \({{\boldsymbol{a}}},{{\boldsymbol{b}}}\), and random vectors \({{\boldsymbol{X}}},{{\boldsymbol{Y}}},{{\boldsymbol{W}}},{{\boldsymbol{Z}}}\), we have [1]
\(\mathop{\mathrm{{\mathbb{E}}}}[{\mathsf{A}}{{\boldsymbol{X}}}+{{\boldsymbol{a}}}]={\mathsf{A}}\mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{X}}}+{{\boldsymbol{a}}}\)
\(\mathop{\mathrm{Cov}}({{\boldsymbol{X}}},{{\boldsymbol{Y}}}) = \mathop{\mathrm{{\mathbb{E}}}}[{{\boldsymbol{X}}}({{\boldsymbol{Y}}}-\mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{Y}}})^T] = \mathop{\mathrm{{\mathbb{E}}}}[({{\boldsymbol{X}}}-\mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{X}}}){{\boldsymbol{Y}}}^T] = \mathop{\mathrm{{\mathbb{E}}}}[{{\boldsymbol{X}}}{{\boldsymbol{Y}}}^T]-\mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{X}}}\mathop{\mathrm{{\mathbb{E}}}}{{\boldsymbol{Y}}}^T\)
\(\mathop{\mathrm{{\mathbb{E}}}}[({\mathsf{A}}{{\boldsymbol{X}}})({\mathsf{B}}{{\boldsymbol{Y}}})^T]={\mathsf{A}}\mathop{\mathrm{{\mathbb{E}}}}[{{\boldsymbol{X}}}{{\boldsymbol{Y}}}^T]{\mathsf{B}}^T\)
\(\mathop{\mathrm{Cov}}({\mathsf{A}}{{\boldsymbol{X}}}+{{\boldsymbol{a}}},{\mathsf{B}}{{\boldsymbol{Y}}}+{{\boldsymbol{b}}})={\mathsf{A}}\mathop{\mathrm{Cov}}({{\boldsymbol{X}}},{{\boldsymbol{Y}}}){\mathsf{B}}^T\)
\(\mathop{\mathrm{Cov}}({\mathsf{A}}{{\boldsymbol{X}}}+{{\boldsymbol{a}}})={\mathsf{A}}\mathop{\mathrm{Cov}}({{\boldsymbol{X}}}){\mathsf{A}}^T\)
\(\mathop{\mathrm{Cov}}({{\boldsymbol{W}}}+{{\boldsymbol{X}}},{{\boldsymbol{Y}}}+{{\boldsymbol{Z}}})=\mathop{\mathrm{Cov}}({{\boldsymbol{W}}},{{\boldsymbol{Y}}})+\mathop{\mathrm{Cov}}({{\boldsymbol{W}}},{{\boldsymbol{Z}}})+\mathop{\mathrm{Cov}}({{\boldsymbol{X}}},{{\boldsymbol{Y}}})+\mathop{\mathrm{Cov}}({{\boldsymbol{X}}},{{\boldsymbol{Z}}})\)
Example 0.53 Covariance under scaling
For a random vector \({{\boldsymbol{X}}}\) and constants \(a,{{\boldsymbol{b}}}\), property 5 gives \(\mathop{\mathrm{Cov}}(a{{\boldsymbol{X}}}+{{\boldsymbol{b}}}) = a^2\mathop{\mathrm{Cov}}({{\boldsymbol{X}}})\). Prove this using the other properties.
Solution
The relevant properties are given in each step. \[\begin{align} \mathop{\mathrm{Cov}}(a{{\boldsymbol{X}}}+{{\boldsymbol{b}}}) &= \mathop{\mathrm{Cov}}(a{{\boldsymbol{X}}}+{{\boldsymbol{b}}},a{{\boldsymbol{X}}}+{{\boldsymbol{b}}}) \\ &\stackrel{6}{=} \mathop{\mathrm{Cov}}(a{{\boldsymbol{X}}},a{{\boldsymbol{X}}}) + \mathop{\mathrm{Cov}}(a{{\boldsymbol{X}}},{{\boldsymbol{b}}}) + \mathop{\mathrm{Cov}}({{\boldsymbol{b}}},a{{\boldsymbol{X}}})+ \mathop{\mathrm{Cov}}({{\boldsymbol{b}}},{{\boldsymbol{b}}})\\ &\stackrel{4}{=} a^2\mathop{\mathrm{Cov}}({{\boldsymbol{X}}},{{\boldsymbol{X}}}) + 0 + 0+ 0 \end{align}\]
0.7 Concentration inequalities
The following inequalities bound the probability that a random variable is far from its mean, using only the mean, or the mean and the variance. Chebyshev’s inequality is the tool behind the proof of the law of large numbers.
0.7.1 Markov inequality
Suppose the average length of a blue whale is 22 meters and we do not know anything else about the distribution of the lengths of blue whales. Can we say anything about the probability that the length of a randomly chosen blue whale is at least 30 meters? For example, is it possible that this probability is \(0.8\) or larger? No, since in that case, the average would be at least \(0.8\times 30=24\) meters. So only knowing the mean enables us to say something about the extremes of the probability distribution.
This observation is formalized via the Markov inequality. For a non-negative random variable \(X\), we have \[\begin{equation*} {\Pr}(X\ge a) \le \frac{\mathop{\mathrm{{\mathbb{E}}}}X}{a}. \end{equation*}\]
Exercise 0.54 Proving Markov’s inequality
Prove the Markov inequality.
A special case of this occurs when \(X\) counts something, i.e., it only takes non-negative integer values. Then, \[\begin{align*} \Pr(X\ge 1)=\Pr(X>0)&\le \mathop{\mathrm{{\mathbb{E}}}}X,&\Pr(X=0)&\ge 1-\mathop{\mathrm{{\mathbb{E}}}}X. \end{align*}\] In particular, if the mean \(\mathop{\mathrm{{\mathbb{E}}}}X\) is small, then there is a large probability that \(X=0\).
0.7.2 Chebyshev inequality
If in addition to the mean, we also have the variance, we can use the Chebyshev bound. For a random variable \(X\) with mean \(\mu\) and variance \({\sigma}^2\), \[\begin{equation*} \Pr\left(\left|\frac{X-\mu}{{\sigma}}\right|\ge a\right)\le \frac{1}{a^2}. \end{equation*}\] That is, being \(a\) standard deviations away from the mean has probability at most \(1/a^2\); for example, being 10 standard deviations away from the mean has probability at most \(1\%\).
Exercise 0.55 Proving Chebyshev’s inequality
Prove the Chebyshev bound using the Markov bound.
References
[1] B. Hajek, Random Processes for Engineers, 2014. http://hajek.ece.illinois.edu/Papers/randomprocJuly14.pdf
These definitions and the following axioms are simplified. We cannot always assign probability to all subsets of \(\Omega\). Also, for the third axiom, for any countable sequence of mutually exclusive events \(E_1,E_2,\dotsc\), we require that \({\Pr}(\bigcup_{i=1}^\infty E_i)=\sum_{i=1}^{\infty}{\Pr}(E_i)\).↩︎
Note that sometimes \(p\) is used both as a parameter and as the distribution. The meaning should be clear from the context.↩︎
The minimum is attained for every CDF, since \(F\) is non-decreasing and right-continuous.↩︎
Minimizing the Mean Square Error↩︎
You can play the Monty Hall game at https://fhfarnoud.github.io/moi/conditional.html.↩︎
We use lowercase bold letters to denote deterministic vectors, uppercase bold letters to denote random vectors, and uppercase sans serif letters, such as \({\mathsf{A}}\), to denote matrices.↩︎