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.

  • $\begingroup$ Should $\mathbb{R}$ be replaced with $\mathbb{R}^d$? $\endgroup$ – angryavian Jan 21 '16 at 7:57
  • $\begingroup$ @angryavian you're absolutely right. $\endgroup$ – user90593 Jan 21 '16 at 7:58
  • $\begingroup$ Start by squaring both sides. $\endgroup$ – 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$.

  • $\begingroup$ 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$. $\endgroup$ – user90593 Jan 21 '16 at 9:02
  • 1
    $\begingroup$ @user90593 Yes. I've updated the answer to clarify and correct for that. $\endgroup$ – skyking Jan 21 '16 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.