I´m interested in the following problem:
Given a set of vectors $G = \{v_0, \ldots, v_n\}$, what is the probability $P$ that for any vector $u$, there is at least one vector $v_k \in G$ such that there is an acute angle between $u$ and $v_k$ (i.e. $u \cdot v_k > 0$)?
Notes: The vector $u$ has $d$ coordinates with $n \ll d$. Each coordinate of vector $u$ is sampled from a uniform distribution on $\mathbb{R}$ independently.
I'd appreciate it if someone could give me a pointer, and I'd be happy to just prove a loose upper bound on the probability (obviously tighter than $P > 0.5$) as well.
The probability depends on $G$, and you cannot improve the bounds $0.5 \leq p \leq 1$ unless further assumption is made on the set. Indeed, taking $G$ to be any single vector $\{v_0\}$ implies $p = 0.5$, while taking $G$ to be $\{v_0, -v_0\}$ for any $v_0$ implies $p=1$.
For the two-dimensional case $d=2$, I'm pretty sure (but still need to prove that) the probability can explicitly be given as $$ p = \min\left\{1, \frac{1}{2}+\frac{1}{2\pi}\max_i \{\theta(v_0, v_i)\}-\frac{1}{2\pi}\min_i \{\theta(v_0, v_i)\}\right\}$$ where $\theta(v_0,v_i) \in (-\pi, \pi]$ is the angle between $v_0$ and each other vector $v_i \in G$. I will try to add a proof shortly. The $d$-dimensional case seems less obvious, I need to think about it.