So far, we use the cosine function to measure the similarity between two vectors. Next, you are asked to do theoretical study of its reasonableness.
Your task is to prove the following theorem.
Theorem:
- Let \mathbf{x}, \mathbf{y} \in \Bbb R^d be two independent d-dim vectors that follow the same multi-variate standard normal distribution N \left( \mathbf{0}_d , \mathbf{I}_{d \times d} \right).
Then for any \epsilon > 0, when d is large,
\Bbb P \left( \frac{\mathbf{x}^\top \mathbf{y}}{|| \mathbf{x} ||_2 || \mathbf{y}||_2 } > \epsilon \right)
\leq \frac{1}{\epsilon^2 d} .
We prove this in multiple steps.
Part 17 (5 points, non-coding task)
First, you are asked to prove the following lemma.
Lemma 1:
- If \mathbf{x} \sim N \left( \mathbf{0}_d , \mathbf{I}_{d \times d} \right), then for any unit vector \mathbf{\hat e} \in \Bbb R^d,
\mathbf{\hat e}^\top \mathbf{x} \sim N \left( 0 , 1 \right) .
That is, the projection of \mathbf{x} onto \mathbf{\hat e} is a standard normal random variable.
Hint: You can directly use the result that \mathbf{\hat e}^\top \mathbf{x} is normal. Therefore, you only need to prove that \mathbf{\hat e}^\top \mathbf{x} has mean 0 and variance 1.