12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @michael: Could you please indicate the argument for the normal (rather than uniform) case? Perhaps it can be generalized to other distributions. $\endgroup$ – Arnold Neumaier Apr 23 '18 at 14:34
  • 1
    $\begingroup$ The normals roatation invariance that means the wlog you can assume $ q = (1, 0,....,0) $ and then I think you are just looking at a couple of caps on the sphere, of which someone must know the area . Of course, the rotation invariance, and the fact that $\frac {\bar p } {||p||}$ is uniform on the sphere don't carry over. $\endgroup$ – user83457 Apr 23 '18 at 14:42
  • $\begingroup$ By the length of the vector, do you mean its dimension? $\endgroup$ – Iosif Pinelis Apr 23 '18 at 15:09
  • 2
    $\begingroup$ Try Berry-Essen Inequality (en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem). $\endgroup$ – Ron P Apr 23 '18 at 15:50
  • 1
    $\begingroup$ Perhaps computing expectations and using Markov's inequality? $\endgroup$ – usul Apr 23 '18 at 16:01
6
$\begingroup$

$\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.

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 or its arXiv version.

$\endgroup$
  • $\begingroup$ This answer is based on ideas different from the ones used in my previous answer. Here I co-opted the idea to use the Berry--Esseen inequality, suggested by Ron P. However, for the answer to be complete (as it now is), we needed to consider separately the cases depending on whether $\max_i|q_i|$ is relatively large or not. The result thus obtained is actually stronger than the one requested by the OP. $\endgroup$ – Iosif Pinelis Apr 24 '18 at 3:26
  • $\begingroup$ Can you extract from the proof how $c$ depends on $\varepsilon$? $\endgroup$ – Arnold Neumaier Apr 24 '18 at 8:43
  • 1
    $\begingroup$ I have now also provided an explicit expression for $c$ in terms of $\varepsilon$. $\endgroup$ – Iosif Pinelis Apr 24 '18 at 13:07
  • 1
    $\begingroup$ I have also added a lower bound on $c$. $\endgroup$ – Iosif Pinelis Apr 30 '18 at 15:30
  • $\begingroup$ ''One may try to improve the bounds on cc, but I believe that would be quite outside the usual scope for MathOverflow answers.'' - I want to use the bounds in a proper publication; so some version of the answer itself may deserve publication. $\endgroup$ – Arnold Neumaier Apr 30 '18 at 16:53
6
$\begingroup$

Normalize $q$ such that $q^Tq=1$ and $q_i\geq 0$, for all $i=1,\ldots,n$. Let $X_i=q_ip_i$, $i=1,\ldots,n$. We must find an absolute constant $c>0$ such that $$P\left(c\left(\sum_i X_i\right)^2\geq \frac{\sum_ip_i^2}{n}\right)\geq \frac 1 2.$$

By the weak law of large number $\frac{\sum_ip_i^2}{n} \to E[p_1^2]<1$ in probability. Therefore, it is sufficient to prove that $$P\left(\left\vert\sum_i X_i\right\vert< c^{-\frac 1 2} \right)< \frac 1 3,$$ for large enough constant $c>0$.

Assume wlog that $q_1=\max_i q_i$. Since $X_1$ is uniformly distributed in an interval of length $2q_1$ (independently of $\sum_{i>1}X_i$), $$P\left(\left\vert\sum_i X_i\right\vert< \frac {q_1} 4 \middle \vert \sum_{i>1}X_i\right)\leq \frac 1 4. $$ This concludes the proof in the case that $q_1$ is bounded away from 0. If $q_1$ is arbitrarily close to 0, then the distribution of $\sum_i X_i$ is arbitrarily close to the standard normal distribution, by Berry-Essen Inequality; therefore choosing $c=100$, say, will do.

$\endgroup$
  • $\begingroup$ This is an interesting approach. However, this way one cannot get $<1/3$ or even $<1/2$ in general, because the Berry--Esseen (BE) bound here can be as large as $CE|p_1|^3/(Ep_1^2)^{3/2}=C\times3\sqrt3/4>0.51>1/2$, where $C>0.4$ is the best possible constant factor in the BE bound (at this point, the best known value for $C$ in the non-iid case is $0.56$, which makes $CE|p_1|^3/(Ep_1^2)^{3/2}>0.72$). $\endgroup$ – Iosif Pinelis Apr 24 '18 at 0:19
  • $\begingroup$ I took Iosif Pinelis' idea to separate cases, $\max q_i$ bounded away from 0, and arbitrarily close to 0. $\endgroup$ – Ron P Apr 24 '18 at 5:45
  • $\begingroup$ You also need to assume wlog that $q_i\ge -q_1$. $\endgroup$ – Arnold Neumaier Apr 24 '18 at 8:42
  • $\begingroup$ I think quite a few details are missing in your answer. In particular, since you are using the law of large numbers (LLN), you need to take care of $n$ that are not large. On the other hand, of course you don't need to use an LLN at all, since $p^Tp\le n$. $\endgroup$ – Iosif Pinelis Apr 24 '18 at 13:14
  • $\begingroup$ AN, I'm assuming wlog that $q_i>0$. I'll add that, thanks! $\endgroup$ – Ron P Apr 24 '18 at 13:28
5
$\begingroup$

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

Note that $\E(p^Tq)^2=q^Tq/3$ and, by the Rosenthal inequality, $\E(p^Tq)^4\ll(q^Tq)^2$. So, by the Paley--Zygmund inequality, \begin{equation} \PP((p^Tq)^2\ge q^Tq/6)\gg\frac{(\E(p^Tq)^2)^2}{\E(p^Tq)^4}\ge a, \end{equation} where $a>0$ is a universal constant. Since $p^Tp\le n$, we have $$(p^Tp)(q^Tq)\le 6n(p^Tq)^2$$ with probability $\ge a$. ($a$ may be less than $1/2$, though.)

$\endgroup$
  • $\begingroup$ This kind of argument cannot reach probability 1/2. $\endgroup$ – Arnold Neumaier Apr 27 '18 at 8:23
  • $\begingroup$ @ArnoldNeumaier : It probably cannot. However, in my other answer, any probability $p\in(0,1)$ can be reached. Does that look acceptable to you? $\endgroup$ – Iosif Pinelis Apr 29 '18 at 16:01
  • $\begingroup$ I am still analyzing your other answer. Ideally, I want to find the optimal constant $c$! $\endgroup$ – Arnold Neumaier Apr 29 '18 at 16:59
  • $\begingroup$ @ArnoldNeumaier : That would be great, if you manage to find the optimal constant, and I would certainly like to hear about it if you find it! I believe that would require quite extraordinary ideas. $\endgroup$ – Iosif Pinelis Apr 29 '18 at 21:32
  • $\begingroup$ Do you have any idea for how to get a lower bound on $c$? $\endgroup$ – Arnold Neumaier Apr 30 '18 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.