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\}$:


\begin{equation}
cn\leq \left\vert\left\{i:\langle z\_i,v \rangle>0 \right\} \right\vert 
\end{equation}



Almost evenly distributed spherical random vectors
$\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)$.


