**Conjecture:** There is a universal constant $c$ such that for any fixed nonzero real vector $q$ of any dimension $n$ and any random vector $p$ of the same dimension $n$ with independent components uniformly distributed in $[-1,1]$, we have 
$$(p^Tp)(q^Tq)\le cn(p^Tq)^2$$ with probability $\ge 1/2$.
Simulation suggests that the best constant is approximately $c\approx 16/7$.


I'd be interested in techniques for proving this and related statements. In particular, can one determine the best constant $c$?


An application of the inequality to numerical optimization is reported in the paper


M. Kimiaei and Arnold Neumaier,
Efficient global unconstrained black box optimization,
<http://www.optimization-online.org/DB_HTML/2018/08/6783.html>



A probabilistic angle inequality
$\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\varepsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\Si}{\Sigma}
\newcommand{\thh}{\theta}
\newcommand{\R}{\mathbb{R}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\E}{\operatorname{\mathsf E}} 
\newcommand{\PP}{\operatorname{\mathsf P}}
\newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}}$


Let us show more: For each real $\ep\in(0,1)$ there is some real $c>0$ such that for any nonzero $q=(q\_1,\dots,q\_n)\in\R^n$ we have 
\begin{equation\*}
 \PP((p^Tp)(q^Tq)\le cn(p^Tq)^2)\ge1-\ep, \tag{0}
\end{equation\*}
where $p:=(U\_1,\dots,U\_n)$ and $U\_1,\dots,U\_n$ are iid random variables (r.v.'s) uniformly distributed in $[-1,1]$. Here, instead of $1/2$ in the OP's question, we have $1-\ep$. 


By rescaling, without loss of generality (wlog) $q^Tq=1$. Also, $p^Tp\le n$, so that the inequality $(p^Tp)(q^Tq)\le cn(p^Tq)^2$ is implied by $(p^Tq)^2\ge1/c$. 


So, letting 
$$\de=2/\sqrt c,$$ 
we see that it is enough to show that $\forall\ep>0$ $\exists\de>0$ $\forall q\in\Si\_{n-1}$ $\PP(|S\_q|\le\de/2)\le\ep$, where $\Si\_{n-1}$ is the unit sphere in $\R^n$ and 
\begin{equation\*}
 S\_q:=p^Tq=\sum\_1^n q\_i U\_i. 
\end{equation\*}


In turn, it is enough to show that 
\begin{equation\*}
 Q\_{S\_q}(\de)\underset{\de\downarrow0}\longrightarrow0 \tag{1}
\end{equation\*}
uniformly in $q\in\Si\_{n-1}$, where 
\begin{equation\*}
 Q\_X(\de):=\sup\_{x\in\R}\PP(|X-x|\le\de/2), 
\end{equation\*}
so that $Q\_X$ is the so-called concentration function of a r.v. $X$. 


Let us now prove (1). Because the r.v.'s $U\_1,\dots,U\_n$ are iid and symmetrically distributed, wlog 
\begin{equation\*}
 q\_1\ge\cdots\ge q\_n\ge0. 
\end{equation\*}
Take any $q\_\*\in(0,1)$. 
One of the following cases must occur. 


*Case 1: $q\_1\ge q\_\*$.* Then 
\begin{equation\*}
 Q\_{S\_q}(\de)\le Q\_{q\_1 U\_1}(\de)\le\frac12\frac\de{q\_1}\le\frac\de{2q\_\*}; \tag{1.5}
\end{equation\*}
the first inequality in the above display is due to the fact that for any independent r.v.'s $X$ and $Y$ 
\begin{align\*}
 Q\_{X+Y}(\de)&=\sup\_{x\in\R}\PP(|X+Y-x|\le\de/2) \\ 
 &=\sup\_{x\in\R}\int\_\R \PP(Y\in dy)\PP(|X+y-x|\le\de/2) \\
 &\le\int\_\R \PP(Y\in dy)\sup\_{x\in\R}\PP(|X+y-x|\le\de/2)
 =Q\_X(\de). 
\end{align\*}


*Case 2: $q\_1\le q\_\*$.* Then, by the Berry--Esseen (BE) inequality, 
\begin{align\*}
 Q\_{S\_q}(\de)&\le Q\_Z(\de)+2A\frac{\sum\_1^n \E|q\_iU\_i|^3}{(\sum\_1^n \E(q\_iU\_i)^2)^{3/2}} \\ 
 &\le\frac\de{\sqrt{2\pi}}+2A\sum\_1^n q\_i^3\,\frac{3\sqrt3}4 
 \le \frac\de{\sqrt{2\pi}}+2Aq\_\*\,\frac{3\sqrt3}4, 
\end{align\*}
where $Z\sim N(0,1)$ and $A$ is the universal positive real constant factor in the BE bound for non-iid independent r.v.'s; the best currently known value for $A$ is $0.56$ (I. G. Shevtsova. Refinement of estimates for the rate of convergence in Lyapunov's theorem.
Dokl. Akad. Nauk, 435(1):26--28, 2010); a slightly worse value, $0.5606$, was a bit earlier established by [Tyurin](https://arxiv.org/abs/0912.0726). 


Thus, for all $q\in\Si\_{n-1}$ 
\begin{equation\*}
 Q\_{S\_q}(\de)\le\max\Big(\frac\de{2q\_\*},\frac\de{\sqrt{2\pi}}+2Aq\_\*\,\frac{3\sqrt3}4\Big). \tag{2}
\end{equation\*}
So (1) follows by choosing $q\_\*=\sqrt\de$, say. 




---


The OP later requested an explicit expression for $c$ providing for (0). Let us get this as well. 
The $\max$ in (2) is minimized in $q\_\*\in(0,1)$ when the two arguments of the $\max$ are equal to each other, that is, when 
\begin{equation\*}
 q\_\*=q\_\*(\de):=\frac{\sqrt{6 \sqrt{3} \pi A \de +\de ^2}-\de}{3 \sqrt{6 \pi } A}. 
\end{equation\*}
Equating now $\frac\de{2q\_\*(\de)}$ (which equals the $\max$ minimized in $q\_\*$) with $\ep$ and solving for $\de$, we get 
\begin{equation\*}
 \de=\de(\ep):=\frac{4 \sqrt{2 \pi } \ep ^2}{3 \sqrt{6 \pi } A+4 \ep }, 
\end{equation\*}
whence 
\begin{equation\*}
 c=c(\ep):=\frac4{\de(\ep)^2}=\frac{\left(3 \sqrt{6 \pi } A+4 \ep\right)^2}{8 \pi \ep^4} \tag{3}
\end{equation\*}
is enough for condition (0). 
In particular, using the mentioned best known value $0.56$ for $A$, we get $c(1/2)=54.98\dots$. 




---


The OP has now also requested a lower bound $c$ providing for (0). Let us get this as well. 
Suppose that for some real $\ep\in(0,1)$, some real $c>0$, all natural $n$, and all nonzero $q=(q\_1,\dots,q\_n)\in\R^n$ we have (0), where, as before, $p=(U\_1,\dots,U\_n)$ and $U\_1,\dots,U\_n$ are iid r.v.'s uniformly distributed in $[-1,1]$. 
Then, choosing $q=(1,\dots,1)/\sqrt n$, we have 
\begin{equation}
 \PP(|T\_n|\ge1/\sqrt c)\ge1-\ep,
\end{equation}
where 
\begin{equation}
 T\_n:=\frac{\sum\_1^n U\_i}{\sqrt{\sum\_1^n U\_i^2}}. 
\end{equation}
By the central limit theorem and the law of large numbers, $\sum\_1^n U\_i/\sqrt n\to Z\sim N(0,1)$ in distribution and $\sum\_1^n U\_i^2/n\to\E U\_1^2=1/3$ in probability (say), so that $T\_n\to Z\sqrt3\sim N(0,3)$ in distribution; the convergence here is for $n\to\infty$. So, 
\begin{equation}
 2(1-\Phi(1/\sqrt{3c}))\ge1-\ep,
\end{equation}
where $\Phi$ is the standard normal cumulative distribution function; that is, 
\begin{equation}
 c\ge c\_\ep:=\tfrac13\,/\Phi^{-1}(\tfrac12+\tfrac\ep2)^2\sim\tfrac2{3\pi\ep^2}
\end{equation}
as $\ep\downarrow0$, because $\Phi(x)-1/2\sim x/\sqrt{2\pi}$ as $x\to0$ and hence $\Phi^{-1}(\tfrac12+u)\sim u\sqrt{2\pi}$ as $\to0$. 


This lower bound, $c\_\ep$, on $c$ in (0) is quite a bit lower than the upper bound $c(\ep)$ in (3), especially for small $\ep$. For $\ep=1/2$, we have the lower bound $c\_{1/2}=0.7327\dots$ on $c$ vs. the mentioned upper bound $c(1/2)=54.98\dots$. The gap is pretty large. 


One can follow the lines of the above proof to see the causes of this gap. One such cause is the first inequality in (1.5). The other one is due to the use of the Berry--Esseen (BE) bound -- which is true for all distributions (with the worst case being discrete distributions, whereas the distributions of $q\_i U\_i$ are absolutely continuous with bounded densities) and uniformly for all deviations from the mean. One may try to improve the bounds on $c$, but I believe that would be quite outside the usual scope for MathOverflow answers. Here one may also note that in the possibly simpler case of the so-called nonuniform BE bounds, the gap between the constant factors in the best known upper bound ($25.80$) and in the best known lower bound ($1.0135$) is similarly very large; see e.g. the paper [On the Nonuniform Berry--Esseen Bound](https://www.sciencedirect.com/science/article/pii/B9780128098189000045) or its [arXiv version](https://arxiv.org/abs/1301.2828). 


