# Probabilistic method proof

Let $v_1, v_2,...,v_n \in \mathbb{R}^n$ be unit vectors. Use probabilistic method to show that there exist constants $a_1, a_2,..., a_n \in \{-1,1\}$ such that $||a_1 v_1 + a_2 v_2 + ... + a_n v_n ||_2 \leq \sqrt{n}$.

I think I should make a n random variable $X_i$ that take values in $\{-1,1\}$ each with probability ½, and somehow show that the probability that the squared $2-$norm of the linear combination with coefficients $X_i$ is greater than n, is less than 1. But I am not sure how I should go about that. Any hint would be appreciated.

• Should $\mathbb{R}$ be replaced with $\mathbb{R}^d$? – angryavian Jan 21 '16 at 7:57
• @angryavian you're absolutely right. – user90593 Jan 21 '16 at 7:58
• Start by squaring both sides. – AJY Jan 21 '16 at 8:06

You shouldn't look for the probability that the norm squared is greater than $n$. You should look for it's expectation value. We have
$$\left|\sum a_jv_j\right|^2 = \sum\sum a_j a_k v_j\cdot v_k = \sum a_j^2|v_j|^2 + \sum_{j\ne k} a_j a_k v_j\cdot v_k = n + \sum a_ja_kv_jv_k$$
Assume that $a_j$ are mutually independent variables with $P(a_j=\pm1) = 1/2$
Now the expectation value of $a_ja_k = 0$ so the expectation value of the norm squared is $n$. This can only happen if it's probable that it's less than or equal to $n$ - therefore there must exist $a_j$s that make it less than or equal to $n$.
• Do you mean $v_j v_k$ the dot product of the two vectors? Also I think $\sum a_j^2 v_j^2 = n$, if by $v_j^2$ you meant $|v_j|_2^2$. – user90593 Jan 21 '16 at 9:02