# Almost evenly distributed spherical random vectors

Consider $$n$$ i.i.d spherically distributed random vectors $$z_1 ,\cdots , z_n \sim \text{Unif}(\mathbb{S}^{d-1})$$. What is the best lower bound on $$n$$ for which whp there exists a constant $$c>0$$ such that the following bound holds for all $$v\in \mathbb{R}^d\backslash \{0\}$$:

$$$$cn\leq \left\vert\left\{i:\langle z_i,v \rangle>0 \right\} \right\vert$$$$

• Note that $n \ge d$ since otherwise, you can always find a $v$ that is orthogonal to all of the $z_i$'s so the set is empty. Jul 28 '21 at 2:04
• "whp"? Is that, with high probability? Nov 25 '21 at 1:24
• Sorry for the late response. Yes, whp means with high probability. Dec 8 '21 at 21:53

## 1 Answer

$$\newcommand\PP{\mathbb P}$$ Surely $$n_\min \lesssim d$$, because it works for $$c = 1/4$$ and $$n=160d$$.

We use that the number of "distinct" $$v$$ with respect to the classifiers $$\textrm{sgn}\langle \cdot, z_i \rangle$$ is $$\sum_{i=0}^{d-1} \binom{n-1}{i} \le \left( \frac{ne}{d} \right)^d$$

The proof can be found in [Bürgisser and Cucker (2013), Lemma 13.7]. (Anyone has a better reference?)

Let $$X = \lvert \left\{ i ~:~ \langle z_i, e_1 \rangle \right\} \rvert$$ for a basis vector $$e_1$$. Then, by the union bound $$\PP \left[ ~\exists v ~~ \lvert \left\{ i ~:~ \langle z_i, v \rangle > 0 \right\}\rvert < cn \right] \\ \le \left( \frac{ne}{d} \right)^d \PP \left[ X < cn \right] \\ \le \exp(d\log(n) - \frac{n}{16} + d - d \log{d}) \\ = \exp(\log(160)d - 9d) \xrightarrow{d \to \infty} 0$$

where we used the Chernoff bound on $$\PP[X < cn]$$, in the form $$\PP\left[X \le (1 - \delta) \mathbb E[X] \right] \le \exp(-\frac12 \delta^2 \mathbb E[X]).$$

As noted in the comment by Sandeep Silwal, $$n_{\text{min}} \ge d$$ due to the strict inequality sign in the question. So the answer to the original question is $$n_{\text{min}} = \Theta(d)$$.

• you meant $<cn, \exists v$ in the first line of the chain of inequalities? Jul 13 '21 at 19:21
• Thank you for the fix! I will check again, but it seems correct now. Jul 13 '21 at 19:38