SECTION 01 / 10

Prerequisite toolkit

On this page 16 headings

Learning goal: Learn the notation needed for probability bounds and random projections.

Review these foundations before starting the main lessons.
Each idea includes an explanation and a small example.

0.1 Random variable, sample space, probability

The ideaA random variable is a number whose value you only learn after an experiment.
Roll a die: before rolling you don't know the number, after rolling you do.
That number is a random variable, usually called X.

Sample space: all the values X can take.
For a die: {1, 2, 3, 4, 5, 6}.
Event: any set of outcomes you might ask about, such as "the roll is 5 or more" = {5, 6}.
The collection of all events you can ask about is the event space.
For a die it is every subset of {1,…,6}, called the power set (there are 2⁶ = 64 of them).
Probability: a number between 0 and 1 for each event.
For a fair die each face has probability 1/6, so $P (X \geq 5) = P (X \in {5, 6}) = \frac{1}{6} + \frac{1}{6} = \frac{1}{3}$ .
Non-negative random variable: one that can never be below 0, such as a distance, a count or a waiting time.

0.2 Expectation (the average) and linearity

The ideaThe expected value E[X] is the average you would get if you repeated the experiment a huge number of times and averaged the results.

Multiply each value by its probability and add up:

E [X] = values x \sum x \cdot P (X = x) .

Worked example

Fair die: $E [X] = 1 \cdot \frac{1}{6} + 2 \cdot \frac{1}{6} + \dots + 6 \cdot \frac{1}{6} = \frac{21}{6} = 3.5$ .
You can never roll 3.5, but over many rolls the average approaches 3.5.

Linearity of expectation is used again and again in Lesson 8 and Lesson 9.
For any random variables (independent or not) and fixed numbers $a, b$ :

E [a X + bY] = a E [X] + b E [Y], E [i \sum c_{i} X_{i}] = i \sum c_{i} E [X_{i}] .

In words: you can pull fixed numbers out of an expectation and split a sum into separate expectations.

0.3 Variance and standard deviation

The ideaThe average alone does not tell the whole story.
The class averages 50 % whether everyone scores 50 or half the class scores 0 and half scores 100.
Variance measures how spread out the values are around the average.

Var (X) = E [(X - E [X])^{2}] = E [X^{2}] - (E [X])^{2}, σ = Var (X) .

σ (sigma) is the standard deviation, a "typical distance from the average" measured in the same units as X.

Worked example

Fair die: $E [X^{2}] = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6} \approx 15.17$ .
So $Var (X) = 15.17 - 3. 5^{2} = 15.17 - 12.25 = 2.92$ , and $σ = 2.92 \approx 1.71$ .

Two facts used in Lesson 8:

If $E [X] = 0$ , then $Var (X) = E [X^{2}]$ , because the second term vanishes.
$Var (c X) = c^{2} Var (X)$ , and for independent X, Y: $Var (X + Y) = Var (X) + Var (Y)$ .

0.4 Independence

Two random variables are independent if knowing one tells you nothing about the other, like two separate coin tosses.
The key consequence used in Lesson 8 and Lesson 9 is that the expectation of a product splits:

X, Y independent ⟹ E [X Y] = E [X] E [Y] .

"i.i.d." means independent and identically distributed: separate draws from the same distribution.

0.5 The normal (Gaussian) distribution

The ideaThe famous bell curve.
Heights, measurement errors and many sums of small random effects follow it: most values sit near the middle, and values far away are rare.

$X \sim N (μ, σ^{2})$ means "X is normal with mean μ and variance σ²".
The standard normal is $N (0, 1)$ : mean 0, variance 1.
Facts we need:

About 68 % of values lie within 1σ of the mean, 95.4 % within 2σ, and 99.7 % within 3σ.
If $Z \sim N (0, 1)$ then $E [Z] = 0$ , $E [Z^{2}] = Var (Z) = 1$ .
Sums of independent normals are normal. If $Z_{1}, \dots, Z_{d}$ are independent $N (0, 1)$ and $c_{1}, \dots, c_{d}$ are fixed numbers, then $\sum_{i} c_{i} Z_{i} \sim N (0, \sum_{i} c_{i}^{2})$ .
This is the engine of Lesson 8.

0.6 Vectors, dot product and length

The ideaA data point with d features is a list of d numbers, which is a vector in $R^{d}$ .
A house with (area, rooms, age) is a vector in $R^{3}$ .
A word embedding with 10,000 numbers is a vector in $R^{10000}$ .

Dot product: $r^{⊤} u = r_{1} u_{1} + r_{2} u_{2} + \dots + r_{d} u_{d}$ .
The result is a single number.
The notation $r^{⊤} u$ ("r transpose u") means exactly this.
Length (norm): $∥ u ∥ = u_{1}^{2} + \dots + u_{d}^{2}$ .
This is Pythagoras in d dimensions.
The squared length is $∥ u ∥^{2} = u^{⊤} u = \sum_{i} u_{i}^{2}$ .
The small 2 under the bars in $∥ u ∥_{2}$ just says "ordinary (Euclidean) length".
Distance between two points x and y is the length of their difference: $∥ x - y ∥$ .
Two vectors are orthogonal (perpendicular) when their dot product is 0.
A set of vectors is orthonormal when every pair is orthogonal and each has length 1.

Worked example

$u = (1, 2, 2, 4)$ : $∥ u ∥^{2} = 1 + 4 + 4 + 16 = 25$ , so $∥ u ∥ = 5$ .
With $x = (1, 1)$ and $y = (4, 5)$ : $x - y = (- 3, - 4)$ , so $∥ x - y ∥^{2} = 9 + 16 = 25$ and the distance is 5.

0.7 Matrices, matrix × vector, transpose, identity

A k × d matrix R has k rows and d columns.
Multiplying it by a vector $u \in R^{d}$ gives a vector in $R^{k}$ .
Entry i of the result is the dot product of row i with u:

R u = r_{1}^{⊤} u r_{2}^{⊤} u ⋮ r_{k}^{⊤} u \in R^{k} .

So a k × d matrix is a machine that turns d-dimensional vectors into k-dimensional vectors.
If k < d, it reduces dimension.
This matrix operation is called a linear transformation.

Transpose $R^{⊤}$ : flip rows and columns, so a k × d matrix becomes d × k.
Identity matrix I: 1s on the diagonal, 0s elsewhere.
It leaves vectors unchanged: $I u = u$ .
Useful identity: $∥ R u ∥^{2} = (R u)^{⊤} (R u) = u^{⊤} (R^{⊤} R) u$ .

Worked example

$R = [1001 2 - 1]$ (2 × 3), $u = (3, 1, 1)$ .
Row 1 · u $= 3 + 0 + 2 = 5$ ; row 2 · u $= 0 + 1 - 1 = 0$ .
So $R u = (5, 0)$ : three numbers went in, two came out.

0.8 Random vectors and the covariance matrix

A random vector $x = (x_{1}, \dots, x_{k})$ is a list of random variables.
Its mean is the vector of means, and its spread is described by the covariance matrix, a k × k table:

Cov (x)_{ii} = Var (x_{i}), Cov (x)_{ij} = E [(x_{i} - E x_{i}) (x_{j} - E x_{j})] (i \neq = j) .

When the mean is zero, these become simply $E [x_{i}^{2}]$ on the diagonal and $E [x_{i} x_{j}]$ off it.
If the covariance matrix is the identity, every coordinate has variance 1 and no two coordinates move together.

$x \sim N (0, I_{k})$ , the standard multivariate normal, means the k coordinates are independent standard normals.
Its squared length $∥ x ∥^{2} = x_{1}^{2} + \dots + x_{k}^{2}$ has average k.
This quantity is the hero of Lesson 9.

0.9 Estimators and maximum likelihood

The ideaAn estimator is a recipe that turns observed data into a guess for an unknown number.
It is unbiased if, averaged over many repetitions, the guess equals the true value exactly.

The maximum likelihood estimate (MLE) is the guess that makes the observed data most probable.
The case we need: you observe $y_{1}, \dots, y_{k}$ from $N (0, σ^{2})$ , where the mean 0 is known but σ² is unknown.
The MLE is

σ^^{2} = \frac{1}{k} i = 1 \sum k (y_{i} - 0)^{2} = \frac{y _{1}^{2} + \dots + y _{k}^{2}}{k} .

It is unbiased: $E [σ^^{2}] = \frac{1}{k} \sum E [y_{i}^{2}] = \frac{1}{k} \cdot k σ^{2} = σ^{2}$ .

Worked example

Observations 3, −5, 4, −2 from $N (0, σ^{2})$ : $σ^^{2} = \frac{9 + 25 + 16 + 4}{4} = \frac{54}{4} = 13.5$ .

For the curious: why this is the MLE

The log-likelihood is $ℓ (σ^{2}) = - \frac{k}{2} ln (2 π σ^{2}) - \frac{1}{2 σ ^{2}} \sum y_{i}^{2}$ .
Setting the derivative with respect to σ² to zero gives $- \frac{k}{2 σ ^{2}} + \frac{1}{2 σ ^{4}} \sum y_{i}^{2} = 0$ , so $σ^{2} = \frac{1}{k} \sum y_{i}^{2}$ .

0.10 Logs, e−x and big-O

$lo g n$ grows very slowly.
$ln (1 0^{6}) \approx 13.8$ and $lo g_{2} (1 0^{6}) \approx 19.9$ .
Doubling n adds only a constant to log n.
$e^{- x}$ shrinks very fast: $e^{- 2} \approx 0.135$ , $e^{- 5} \approx 0.0067$ , $e^{- 20} \approx 2 \times 1 0^{- 9}$ .
Big-O: $k = O (\frac{l o g n}{ε ^{2}})$ means "k is at most a fixed constant times $\frac{l o g n}{ε ^{2}}$ ".
The constant is hidden, and the base of the log does not matter (it only changes that constant).
So big-O tells you how k grows, not its exact value.
ε (epsilon) is a small positive number used for "allowed error", for example 0.1 = 10 %.

Key points to remember

Expectation is an average; variance measures spread.
Keep original dimension d, target dimension k, and number of points n distinct.
Mean zero and identity covariance do not establish normality unless Gaussianity is also known.

YOUR STUDY PROGRESS

Finished this section? Save your progress.