Useful Probability facts

An event $A$ is a subset of the sample space $\Omega$, the set of all possible outcomes. We assign probabilities $P(A) \in [0,1]$ to events.

A random variable $X : \Omega \to \mathbb{R}$ is a function that gives a number to each outcome. It is discrete when it takes values in a countable set $\mathcal{X}$, and continuous when it takes values in $\mathbb{R}^d$. For a die, $\Omega = \{1,2,3,4,5,6\}$ and $X(\omega) = 1$ if $\omega$ is even, $0$ otherwise, maps outcomes to $\{0,1\}$.

The distribution of $X$ is described by one of three objects:

• PMF (probability mass function), discrete: $\;p_X(x) = \Pr(X = x)$.
• PDF (probability density function), continuous: $\;p_X(x)$ such that $\Pr(X \in A) = \int_A p_X(x)\, dx$.
• CDF (cumulative distribution function), both: $\;F_X(x) = \Pr(X \le x)$.

Either way the mass has to sum to one,

$$\sum_x p(x) = 1 \quad \text{(discrete)}, \qquad \int_{-\infty}^{\infty} p(x)\, dx = 1 \quad \text{(continuous)}.$$

With two variables the joint distribution $p(x,y)$ holds everything. From it we recover one variable by summing (or integrating) out the other, which is the marginal,

$$p(x) = \sum_y p(x,y) \qquad \text{or} \qquad p(x) = \int p(x,y)\, dy,$$

and we condition on a known value with the conditional,

$$p(x \mid y) = \frac{p(x,y)}{p(y)}, \qquad p(y) > 0.$$

Rearranging the conditional gives the product rule $p(x,y) = p(x \mid y)\,p(y) = p(y \mid x)\,p(x)$, and equating the two factorings gives Bayes' rule, which flips the conditioning direction:

$$p(x \mid y) = \frac{p(y \mid x)\,p(x)}{p(y)}, \qquad p(y) = \sum_x p(y \mid x)\,p(x).$$

Two variables are independent, written $X \perp Y$, when the joint factors into the marginals, which is the same as saying conditioning on $Y$ tells us nothing about $X$:

$$p(x,y) = p(x)\,p(y) \quad\Longleftrightarrow\quad p(x \mid y) = p(x).$$

They are conditionally independent given $Z$, written $X \perp Y \mid Z$, when the same factoring holds once $Z$ is fixed:

$$p(x,y \mid z) = p(x \mid z)\,p(y \mid z) \quad\Longleftrightarrow\quad p(x \mid y, z) = p(x \mid z).$$

The expectation of $X$ is its probability-weighted average,

$$\mathbb{E}[X] = \sum_x x\, p(x) \qquad \text{or} \qquad \mathbb{E}[X] = \int x\, p(x)\, dx,$$

and for any function $f$ we average $f$ against the same distribution,

$$\mathbb{E}[f(X)] = \sum_x f(x)\, p(x).$$

A subscript on the expectation says which distribution we are averaging over, so $\mathbb{E}_{X \sim p}[\,\cdot\,]$ or just $\mathbb{E}_X[\,\cdot\,]$ when $p$ is clear. This matters once several distributions are floating around. Expectation is linear, for constants $a, b$,

$$\mathbb{E}[a X + b Y] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y],$$

and this holds whether or not $X$ and $Y$ are independent.

The variance measures how far $X$ spreads around its mean $\mu = \mathbb{E}[X]$, as an average squared deviation,

$$\operatorname{Var}(X) = \mathbb{E}\!\big[(X - \mu)^2\big].$$

Expanding the square and using linearity gives the form we actually compute with,

$$\operatorname{Var}(X) = \mathbb{E}[X^2 - 2\mu X + \mu^2] = \mathbb{E}[X^2] - 2\mu\,\mathbb{E}[X] + \mu^2 = \mathbb{E}[X^2] - \mathbb{E}[X]^2.$$

A constant shift moves the mean along with $X$ and leaves the spread alone, while a scale factor pulls out squared, so

$$\operatorname{Var}(aX + b) = a^2 \operatorname{Var}(X).$$

The covariance is the same idea for two variables, the average product of their deviations,

$$\operatorname{Cov}(X, Y) = \mathbb{E}\!\big[(X - \mathbb{E}[X])(Y - \mathbb{E}[Y])\big] = \mathbb{E}[XY] - \mathbb{E}[X]\,\mathbb{E}[Y],$$

so $\operatorname{Var}(X) = \operatorname{Cov}(X, X)$. Expanding $\mathbb{E}[((X - \mathbb{E}X) + (Y - \mathbb{E}Y))^2]$ the same way gives the variance of a sum,

$$\operatorname{Var}(X + Y) = \operatorname{Var}(X) + \operatorname{Var}(Y) + 2\operatorname{Cov}(X, Y).$$

When $X$ and $Y$ are independent the cross term $\mathbb{E}[XY] = \mathbb{E}[X]\,\mathbb{E}[Y]$ cancels, so $\operatorname{Cov}(X, Y) = 0$ and variances simply add. The converse is not true, zero covariance does not imply independence. Dividing the covariance by the two standard deviations rescales it into the correlation $\rho = \operatorname{Cov}(X,Y) / (\sigma_X \sigma_Y) \in [-1, 1]$.

For a convex function $\phi$ and any random variable $X$, the average of the function is at least the function of the average,

$$\phi\big(\mathbb{E}[X]\big) \;\le\; \mathbb{E}\big[\phi(X)\big].$$

If $\phi$ is concave the inequality goes the other way. It is an equality when $\phi$ is linear over the range of $X$, or when $X$ is constant.

Here is why it holds. A convex function lies above each of its tangent lines, so at any point $m$ there is a slope $g$ (a subgradient, the ordinary derivative $\phi'(m)$ when it exists) with

$$\phi(x) \;\ge\; \phi(m) + g\,(x - m) \qquad \text{for all } x.$$

Take $m = \mathbb{E}[X]$ and put $x = X$, so the bound holds for the random variable itself,

$$\phi(X) \;\ge\; \phi\big(\mathbb{E}[X]\big) + g\,\big(X - \mathbb{E}[X]\big).$$

Now take expectations of both sides. The right-hand side is linear in $X$, and $\mathbb{E}\big[X - \mathbb{E}[X]\big] = 0$, so the slope term vanishes and what remains is

$$\mathbb{E}\big[\phi(X)\big] \;\ge\; \phi\big(\mathbb{E}[X]\big).$$

Suppose $\hat{\theta}$ is an estimate of some fixed quantity $\theta$, computed from random data so $\hat{\theta}$ is itself random. Two things can make it wrong. It can be off on average, and it can be noisy. The bias is the average error $\operatorname{Bias}(\hat{\theta}) = \mathbb{E}[\hat{\theta}] - \theta$, and the variance is the noise around that average.

Write the mean $m = \mathbb{E}[\hat{\theta}]$ and split the error into a noise part $\hat{\theta} - m$ and a bias part $m - \theta$:

$$\hat{\theta} - \theta = (\hat{\theta} - m) + (m - \theta).$$

Squaring gives three terms,

$$(\hat{\theta} - \theta)^2 = (\hat{\theta} - m)^2 + 2(\hat{\theta} - m)(m - \theta) + (m - \theta)^2.$$

Let's take the expectation of each. The first term is $\operatorname{Var}(\hat{\theta})$ by definition. In the middle term $m - \theta$ is a constant, so we can pull it out by linearity, leaving $2(m - \theta)\,\mathbb{E}[\hat{\theta} - m]$. That last factor is zero, since $\mathbb{E}[\hat{\theta} - m] = \mathbb{E}[\hat{\theta}] - m = m - m = 0$, so the cross term vanishes. The last term is already constant. What is left is

$$\mathbb{E}\!\big[(\hat{\theta} - \theta)^2\big] = \underbrace{\operatorname{Var}(\hat{\theta})}_{\text{noise}} + \underbrace{\big(\mathbb{E}[\hat{\theta}] - \theta\big)^2}_{\text{bias}^2}.$$

So the expected squared error is variance plus bias squared, which is a natural tradeoff. It works a bit like a waterbed: pushing one down tends to push the other up. You can think of it as a small Pareto problem, where whoever designs the estimator has to decide how much bias and how much variance they can tolerate.

This is used pretty much everywhere and follows directly from the definition of expectation. Start from the average of $f$ over the joint distribution, and split the joint with the product rule $p(x,y) = p(x \mid y)\,p(y)$:

$$\mathbb{E}_{X,Y}\!\big[f(X,Y)\big] = \sum_{x,y} f(x,y)\, p(x,y) = \sum_{y} p(y) \sum_{x} f(x,y)\, p(x \mid y).$$

The inner sum $\sum_x f(x,y)\, p(x \mid y)$ is by definition the conditional expectation $\mathbb{E}_{X \mid Y}[f(X,y) \mid Y = y]$, a function of $y$ alone. The outer sum then averages that over $p(y)$, which is an expectation over $Y$. Reassembled,

$$\mathbb{E}_{X,Y}\!\big[f(X,Y)\big] = \mathbb{E}_{Y}\!\left[\, \mathbb{E}_{X \mid Y}\!\big[\, f(X,Y) \mid Y\,\big] \,\right].$$

Reading the result inside-out:

• The inner expectation $\mathbb{E}_{X \mid Y}[\,\cdot \mid Y]$ averages over the conditional distribution of $X$ given $Y$, producing a function of $Y$ alone.
• The outer expectation $\mathbb{E}_{Y}[\,\cdot\,]$ averages that result over the marginal distribution of $Y$.

Written out, the outer average is just a sum (or integral) over $y$ weighted by how likely each $y$ is:

$$\mathbb{E}_{X,Y}\!\big[f(X,Y)\big] = \sum_y \mathbb{E}_{X \mid Y}\!\big[f(X,y) \mid Y = y\big]\, P_Y(Y = y),$$ $$\mathbb{E}_{X,Y}\!\big[f(X,Y)\big] = \int_{-\infty}^{\infty} \mathbb{E}_{X \mid Y}\!\big[f(X,y) \mid Y = y\big]\, p_Y(y)\, dy.$$

If we fit a predictor by minimizing squared error, the best predictor at each input is the conditional mean of the target. Suppose we want a function $f$ that predicts $Y$ from $X$, scored by the squared-error risk

$$\mathcal{R}(f) = \mathbb{E}_{X,Y}\!\big[\, (Y - f(X))^2 \,\big].$$

Fix a single input $X = x$ and call the predicted value $c = f(x)$. Write $\mu = \mathbb{E}[Y \mid x]$ for the conditional mean we are after, and split the error around it, the same move as in the bias-variance argument above:

$$(Y - c)^2 = (Y - \mu)^2 + 2(Y - \mu)(\mu - c) + (\mu - c)^2.$$

Take the conditional expectation given $x$. The cross term drops, since $\mu - c$ is constant and $\mathbb{E}[Y - \mu \mid x] = 0$, leaving

$$\mathbb{E}\!\big[(Y - c)^2 \mid x\big] = \mathbb{E}\!\big[(Y - \mu)^2 \mid x\big] + (\mu - c)^2.$$

The first term does not depend on $c$, and the second is a square, smallest when it is zero. So the best prediction at $x$ is $c = \mu = \mathbb{E}[Y \mid X = x]$. By the law of total expectation, the full risk is the average of these inner risks over $x$,

$$\mathcal{R}(f) = \mathbb{E}_X\!\Big[\, \mathbb{E}\!\big[(Y - f(X))^2 \mid X\big] \,\Big],$$

and since each inner term is minimized on its own by $f(x) = \mathbb{E}[Y \mid X = x]$, the same choice minimizes the whole thing. The minimizer is the regression function

$$f^\star(x) = \mathbb{E}[Y \mid X = x].$$

We often need the gradient of an expectation whose distribution itself depends on the parameter,

$$\nabla_\theta\, \mathbb{E}_{x \sim p_\theta}\big[\, g(x) \,\big].$$

We cannot push the gradient inside, because the distribution $p_\theta$ we average over moves with $\theta$. Writing the expectation as an integral and differentiating, only $p_\theta$ depends on $\theta$:

$$\nabla_\theta\, \mathbb{E}_{x \sim p_\theta}\big[g(x)\big] = \nabla_\theta \int p_\theta(x)\, g(x)\, dx = \int \nabla_\theta p_\theta(x)\, g(x)\, dx.$$

The log-derivative trick $\nabla_\theta \log p_\theta(x) = \nabla_\theta p_\theta(x) / p_\theta(x)$ lets us put a $p_\theta(x)$ back in front, which turns the integral into an expectation again:

$$\nabla_\theta p_\theta(x) = p_\theta(x)\, \nabla_\theta \log p_\theta(x),$$ $$\nabla_\theta\, \mathbb{E}_{x \sim p_\theta}\big[g(x)\big] = \int p_\theta(x)\, \nabla_\theta \log p_\theta(x)\, g(x)\, dx = \mathbb{E}_{x \sim p_\theta}\big[\, g(x)\, \nabla_\theta \log p_\theta(x) \,\big].$$

This is the score function estimator, also called the likelihood-ratio estimator, and $\nabla_\theta \log p_\theta(x)$ is the score. It only needs to sample $x$ and to differentiate $\log p_\theta$, so it works even when $g$ is not differentiable in $x$, discrete $x$ included. The price is variance: it sees the value of $g$ at sampled points and the score, not the shape of $g$.

The score function above works for any $p_\theta$ we can sample from. When a sample can instead be written as a deterministic function of $\theta$ plus a fixed noise source, there is a lower-variance alternative. For a Gaussian $p_\theta = \mathcal{N}(\mu_\theta, \sigma_\theta^2)$, write

$$x = \mu_\theta + \sigma_\theta\, \epsilon, \qquad \epsilon \sim \mathcal{N}(0, I).$$

Sampling $x \sim p_\theta$ is now the same as sampling $\epsilon$ from a fixed distribution and pushing it through a deterministic function of $\theta$. The distribution we average over is $\epsilon$'s, which does not depend on $\theta$, so the gradient passes straight through the expectation:

$$\nabla_\theta\, \mathbb{E}_{x \sim p_\theta}\big[\, g(x) \,\big] = \mathbb{E}_{\epsilon \sim \mathcal{N}(0, I)}\big[\, \nabla_\theta\, g(\mu_\theta + \sigma_\theta\, \epsilon) \,\big].$$

With one noise sample per term this is a plain average of gradients. By the chain rule each term is $\nabla_x g \cdot \nabla_\theta(\mu_\theta + \sigma_\theta\, \epsilon)$, so it uses the slope of $g$ in $x$. That is usually why it has lower variance than the score function, which only sees $\log p_\theta$ and not the shape of $g$. The catch is that $g$ has to be differentiable in $x$, so this is for continuous variables, not discrete ones.