A&W assignment 5

T5.1 Sum of Unit Vectors

a)

by linearity of expected value:

$$\mathbb{E}[X]=\mathbb{E}\left[\sum _{i=1}^n\sum _{j=1}^n{s}_i{s}_j\cdot (v_i\cdot v_j)\right]=\sum _{i=1}^n\sum _{j=1}^n\mathbb{E}[s_i{s}_j](v_i\cdot v_j)$$

case $i=j:$ then $s_i=s_j⟹s_i{s}_j=1⟹\mathbb{E}[s_i{s}_j]=1$ $v_i\cdot v_j=1⟹\mathbb{E}[s_i{s}_j](v_i\cdot v_j)=1$

case $i\ne j:$ since $s_i$ and $s_j$ are chosen independently $\mathbb{E}[s_i{s}_j]=\mathbb{E}[s_i]\cdot \mathbb{E}[s_j]=0⟹\mathbb{E}[s_i{s}_j](v_i\cdot v_j)=0$

Therefore:

$$\mathbb{E}[X]=\sum _{i=1}^{n}1=n$$

b)

Since $X=\Vert v{\Vert }^2$ and $\mathbb{E}[X]=n$ we know that there exists at least one $v$ such that $\Vert v{\Vert }^2\le n$ $⟹$ there exists at least one $v$ such that $v\le \sqrt{n}$ $⟹$ the minimal possible norm of $v$ $\le \sqrt{n}$

c)

let $Y$ be a random variable with $Y:=\sqrt{X}$ where $X$ is defined as above $\mathrm{Pr}[Y\ge 2\sqrt{n}]=\mathrm{Pr}[X\ge 4n]$ using Markov inequality: $\mathrm{Pr}[X\ge 4n]\le \frac{\mathbb{E}[X]}{4n}=\frac{n}{4n}=\frac{1}{4}$ Thus

$$\mathrm{Pr}[\Vert s_1{v}_1+\cdots +s_n{v}_n\Vert \ge 2\sqrt{n}]\le \frac{1}{4}$$

d)

Algorithm: We choose $s_1,\dots ,s_n$ randomly and independently from $\{-1,1\}$, then check if $\Vert s_1{v}_1+\cdots +s_n{v}_n\Vert \le 2\sqrt{n}$. We repeat this process until we find a valid answer

from c) we get $\mathrm{Pr}[\Vert v\Vert <2\sqrt{n}]\ge \frac{3}{4}$ ($v$ defined as in b) So each trial succeeds with probability at least $\frac{3}{4}$

The expected number of trials follows geometric distribution, so the expected number of trials is at most $\frac{1}{\frac{3}{4}}=\frac{4}{3}$

Each trial requires computing $s_1\cdot v_1+\cdots +s_n{v}_n$ which costs $O(n^2)$ time (assume each addition between vectors takes $O(n)$) Since the expected number of trials is in $O(1)$, the total expected running time is also $O(n^2)$