The Probabilistic Method

February 12, 2023

[ math probability ]

Mathematical truth is immutable; it lies outside physical reality... This is our belief; this is our core motivating force.

Joel Spencer, author of The Probabilistic Method

The following problem & proof, at least for me, outline the beauty of the probabilistic method. The first idea behind this problem is almost always induction. However, TPM gives way to an immediate result.

Problem 1. Let v₁, …v_n be unit vectors in ℝ^d. Prove that it is possible to assign weights ℰ_i ∈ { ± 1} such that the vector ∑_iℰ_iv_i has Euclidean norm less than or equal to √n.

Proof. Fix n to be a nonnegative integer. Then, fix a set of n unit vectors v₁, …v_n. Let W be the random set of size n such that each element is either 1 or − 1 with equal probability 1/2. Denote the ith value of W as ℰ_i. Then, let V be ∑_iℰ_iv_i, e.g. the weighted sum of all the vectors. Then,

E[|V|²] = E[(∑ℰ_iv_i)(∑ℰ_iv_i)] = ∑_i∑_jE[ℰ_iℰ_j]v_iv_j.

Note that E[ℰ_iℰ_j] = 0 if i ≠ j. If i = j, then E[ℰ_i²] = 1. So, ∑_i∑_jE[ℰ_iℰ_j]v_iv_j = ∑_iv_i ⋅ v_i = n.

This means that there is a set of weights such that |V|² ≤ n. So, for this set of weights, |V| ≤ √n. ◻