REVISION AND PRACTICE

Formula summary and revision

On this page 2 headings

Learning goal: Choose the right tool and check its assumptions before substituting numbers.

Tool	Needs	Statement	Typical use
Markov	X ≥ 0, mean	$P (X \geq a) \leq \frac{E [ X ]}{a}$	Quick limit on large values
Chebyshev	mean, variance	$P (∣ X - μ ∣ \geq k σ) \leq \frac{1}{k ^{2}}$	Two-sided, uses spread
Hoeffding	independent, bounded in [a, b]	$P (X ˉ - E X ˉ \geq t) \leq e^{- 2 n t^{2} / (b - a)^{2}}$	Averages; how many samples?
Union bound	nothing	$P (\cup A_{i}) \leq \sum P (A_{i})$	"Any of many things fails"
A ⇒ B	A ⊆ B	$P (A) \leq P (B)$	Replace a hard event with an easier one
JL lemma	n points, ε ∈ (0,1)	$k = O (lo g n / ε^{2})$ keeps all $∥ x - y ∥^{2}$ within $1 \pm ε$	Shrink dimension, keep distances
Random projection	$r_{ij} \sim N (0, 1)$	$M = R / k$ , $E ∥ M u ∥^{2} = ∥ u ∥^{2}$ , $r_{i}^{⊤} u \sim N (0, ∥ u ∥^{2})$	The map that achieves JL
Key reduction	–	$P (∥ M u ∥^{2} \geq (1 + ε) ∥ u ∥^{2}) = P (∥ x ∥^{2} \geq k (1 + ε))$ , $x \sim N (0, I_{k})$	Removes d from the problem

The whole week in five sentences

Big data is expensive; randomness can make algorithms cheaper (Lesson 1).
Markov, Chebyshev and Hoeffding bound the chance that a random quantity is far from typical, using progressively more information (Lesson 2–Lesson 4).
The union bound and A ⇒ B let us combine and simplify bad events (Lesson 5).
JL: n points can be mapped to $O (lo g n / ε^{2})$ dimensions with all distances kept within 1 ± ε.
No fixed matrix keeps every length exactly (Lesson 6–Lesson 7).
A Gaussian matrix divided by √k keeps length on average, and the chance of a bad distortion reduces to a question about $∥ x ∥^{2}$ for a standard Gaussian vector in k dimensions (Lesson 8–Lesson 9).

YOUR STUDY PROGRESS

Finished this section? Save your progress.