Random Variables and Expectation

TL;DR

1. A random variable $X$ is a random number; its distribution says which values how likely. Discrete: $P(X=x)$. Continuous: a density $p(x)$ with $P(X\in A)={\int }_{A}p(x)dx$.
2. Expectation = probability-weighted average: $E(X)={\sum }_{x}xP(X=x)$ or $\int xp(x)dx$. It is linear: $E(aX+bY)=aE(X)+bE(Y)$, always.
3. Variance $\mathrm{Var}(X)=E(X-EX{)}^2=E(X^2)-(EX{)}^2$; $\mathrm{Var}(aX+b)=a^2\mathrm{Var}(X)$; for independent $X,Y$: $\mathrm{Var}(X+Y)=\mathrm{Var}X+\mathrm{Var}Y$.
4. Covariance $\mathrm{Cov}(X,Y)=E(XY)-EXEY$; correlation $\rho =\mathrm{Cov}/(\mathrm{std}X\mathrm{std}Y)\in [-1,1]$.
5. Average of $n$ i.i.d. copies: mean stays $\mu$, variance shrinks to ${\sigma }^2/n$, standard deviation to $\sigma /\sqrt{n}$. That $1/\sqrt{n}$ is behind almost every rate in the course.

Random variables and distributions

Random variable

A function $X:\Omega \to \mathbb{R}$ that turns an outcome into a number. It induces a distribution $P_X(A)=P(X\in A)$. Example: draw 3 balls from 5 red and 5 black, $X$ = number of red ones.

Distributions that occur in the course:

Distribution	$P(X=k)$ or density	Mean	Variance
Bernoulli($p$), values $\{0,1\}$	$P(X=1)=p$	$p$	$p(1-p)$
Binomial($n,p$), values $\mathrm{0..}n$	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}$	$np$	$np(1-p)$
Uniform on $[a,b]$	$\frac{1}{b-a}$	$\frac{a+b}{2}$	$\frac{(b-a{)}^2}{12}$
Normal $\mathcal{N}(\mu ,{\sigma }^2)$	$\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-(x-\mu {)}^2/(2{\sigma }^2)}$	$\mu$	${\sigma }^2$
Multivariate normal $\mathcal{N}(\mu ,\Sigma )$ on ${\mathbb{R}}^d$	$\propto e^{-\frac{1}{2}(x-\mu {)}^{\top }{\Sigma }^{-1}(x-\mu )}$	$\mu$	covariance matrix $\Sigma$

Where they appear: Bernoulli for labels and for the 0-1 loss of a fixed classifier; binomial for the number of errors on $n$ test points; uniform for toy data and bootstrap draws; normal for the noise $\epsilon$; multivariate normal for the Gaussian inputs in Lecture 8.

$\mathcal{N}(0,I_d)$ means: $d$ independent standard normal coordinates.

Densities

Density

$X$ has density $p$ if $P(X\in A)={\int }_{A}p(x)dx$ for all (measurable) sets $A$. A density is $\ge 0$ and integrates to 1; it may be larger than 1 and need not be continuous. Intuition: a “continuous histogram”. A single point has probability 0; only intervals get probability.

For the exam diagrams (Bayes decisions) you only need areas under straight lines:

Areas you need for density diagrams

• Rectangle (uniform density $h$ on an interval of length $\ell$): probability $h\cdot \ell$.
• Triangle or trapezoid under a linear density: ${\int }_a^b(cx+d)dx=\frac{c}{2}(b^2-a^2)+d(b-a)$; for a triangle simply $\frac{1}{2}\cdot \text{base}\cdot \text{height}$.
• Check: the total area under each class density must be 1. That fixes the height: a triangle on $[0,4]$ has peak $\frac{2}{4}=\frac{1}{2}$.

Example: $p(x)=x/8$ on $[0,4]$. $P(X\le 3)=\frac{1}{2}\cdot 3\cdot \frac{3}{8}=\frac{9}{16}$.

Memory aid

Probability = area. Every Bayes error in a diagram task is “the area under the lower of the two weighted curves”.

Expectation

Expectation

Discrete: $E(X)={\sum }_i{x}_{i}P(X=x_i)$. Continuous: $E(X)=\int xp(x)dx$. For a function: $E(g(X))={\sum }_{i}g(x_i)P(X=x_i)$ or $\int g(x)p(x)dx$.

Examples: a fair die has $E(X)=3.5$. For an indicator $1_A$ (1 if $A$ happens, else 0): $E(1_A)=P(A)$. That is why the risk under the 0-1 loss is a probability: $R(f)=E(1_{f(X)\ne Y})=P(f(X)\ne Y)$ (L1.1).

Rules

• Linearity (always): $E({\sum }_i{a}_i{X}_i)={\sum }_i{a}_{i}E(X_i)$, even for dependent $X_i$.
• Products (only if independent): $E(XY)=E(X)E(Y)$.
• Empirical risk is an average: $R_n(f)=\frac{1}{n}{\sum }_i\ell (X_i,Y_i,f(X_i))$ has expectation $R(f)$ for a fixed $f$ (linearity).

Conditional expectation

$E(Y\mid X=x)$ is the average of $Y$ among the outcomes with $X=x$. Example: two dice, $Z=X_1+X_2$: $E(Z\mid X_1=3)=3+3.5=6.5$. Without fixing the value, $E(Y\mid X)$ is itself a random variable (a function of $X$).

Where it appears: the regression function $\eta (x)=E(Y\mid X=x)$ is the best predictor under the squared loss (L1.1); for $Y\in \{0,1\}$ it equals $P(Y=1\mid X=x)$. Tower rule: $E(E(Y\mid X))=E(Y)$.

Variance, covariance, correlation

Variance

$$\mathrm{Var}(X)=E(X-E(X){)}^2=E(X^2)-(E(X){)}^2,$$ $$\mathrm{std}(X)=\sqrt{\mathrm{Var}(X)}.$$

$\mathrm{Var}(X)\ge 0$; $\mathrm{Var}(aX+b)=a^2\mathrm{Var}(X)$ (shifting does not change the spread, scaling squares it).

Covariance and correlation

$$\mathrm{Cov}(X,Y)=E((X-EX)(Y-EY))=E(XY)-E(X)E(Y),$$ $$\rho (X,Y)=\frac{\mathrm{Cov}(X,Y)}{\mathrm{std}(X)\mathrm{std}(Y)}.$$

$\mathrm{Var}(X+Y)=\mathrm{Var}X+\mathrm{Var}Y+2\mathrm{Cov}(X,Y)$. Independent ⇒ uncorrelated ($\mathrm{Cov}=0$), not the other way round. $\rho =\pm 1$ iff $Y=aX+b$ exactly; correlation only measures linear dependence.

Worked example: the variance of an average

$Z_1,\dots ,Z_B$ with variance ${\sigma }^2$ each, pairwise correlation $\rho$ (so $\mathrm{Cov}(Z_i,Z_j)=\rho {\sigma }^2$). Then

$$\mathrm{Var}\left(\frac{1}{B}\sum _i{Z}_i\right)=\frac{1}{B^2}(B{\sigma }^2+B(B-1)\rho {\sigma }^2)=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2.$$

• Independent ($\rho =0$): ${\sigma }^2/B$, the classic “averaging reduces variance”.
• Correlated: the part $\rho {\sigma }^2$ never goes away. This is the bagging formula (L6); random forests decorrelate the trees to make $\rho$ small.

Memory aid

Averaging kills only the independent part of the noise. With ${\sigma }^2=4$, $\rho =0.25$, $B=50$: $1+0.06=1.06$, and more trees cannot go below $1$.

i.i.d. samples and empirical estimates

i.i.d.

$X_1,\dots ,X_n$ are independent and identically distributed: each has the same distribution, and they do not influence each other. All training sets in the course are assumed i.i.d. from $P$ (L1.2).

The sample mean

For i.i.d. $X_i$ with mean $\mu$ and variance ${\sigma }^2$:

$$E({\bar{X}}_n)=\mu ,\mathrm{Var}({\bar{X}}_n)=\frac{{\sigma }^2}{n},\mathrm{std}({\bar{X}}_n)=\frac{\sigma }{\sqrt{n}}.$$

Memory aid

Error of an average $\sim 1/\sqrt{n}$. Four times the data halves the error. Hoeffding (Inequalities and Convergence) gives the same $1/\sqrt{n}$ with a probability guarantee, and so do all the generalization bounds of Lecture 3.

Empirical (sample) estimates from data $x_1,\dots ,x_n$: $\bar{x}=\frac{1}{n}{\sum }_i{x}_i$, $\widehat{\mathrm{Var}}=\frac{1}{n}{\sum }_i(x_i-\bar{x}{)}^2$, $\widehat{\mathrm{Cov}}=\frac{1}{n}{\sum }_i(x_i-\bar{x})(y_i-\bar{y})$ (sometimes with $\frac{1}{n-1}$ for an unbiased estimate).

Random vectors and the covariance matrix

Covariance matrix

For $X=(X^{(1)},\dots ,X^{(d)})\in {\mathbb{R}}^d$: $E(X)$ is the vector of coordinate means, and ${\Sigma }_{kl}=\mathrm{Cov}(X^{(k)},X^{(l)})$. $\Sigma$ is symmetric and positive semi-definite. For centered data in the rows of $X\in {\mathbb{R}}^{n\times d}$, the empirical covariance is $\hat{\Sigma }=\frac{1}{n}{X}^{\top }X$.

Where it appears: $\hat{\Sigma }=\frac{1}{n}{X}^{\top }X$ in least squares (L5); the eigenvalues ${\lambda }_i$ of $\Sigma$ decide whether overfitting is benign (L8). Eigenvalues are explained in Linear Algebra.

Self-check

Question cards (4)

$X$ takes the values 0 and 10 with probability 0.9 and 0.1. Compute $E(X)$ and $\mathrm{Var}(X)$.

Answer

$E(X)=1$, $E(X^2)=10$, $\mathrm{Var}(X)=10-1=9$.

Why is the risk under the 0-1 loss a probability?

Answer

The loss is the indicator $1_{f(X)\ne Y}$, and the expectation of an indicator is the probability of the event: $R(f)=P(f(X)\ne Y)$.

100 i.i.d. measurements with standard deviation 5. What is the standard deviation of their mean?

Answer

$5/\sqrt{100}=0.5$.

Two estimators with variance 1 and correlation 0.5 are averaged. Variance of the average?

Answer

$\rho {\sigma }^2+(1-\rho ){\sigma }^2/2=0.5+0.25=0.75$, not $0.5$.

Related

• Math overview · Probability Basics · Inequalities and Convergence