16

Let $n(x) := \frac{1}{\sqrt{2\pi}} e^{-\frac{x^2}{2}}$, and $N(x) := \int_{-\infty}^x n(t)dt$. I have plotted the curves of the both sides of the following inequality. The graph shows that the following inequality may be true. $$f(x):= (x^2+1)N + xn-(xN+n)^2 > N^2$$ where the dependency of $n$ and $N$ on $x$ are absorbed into the function symbols. However, I have not succeeded in providing a full proof except for $x$ above some positive number, with the help of various Mill's Ratio $\frac{m}{n}$ bounds.

I am asking for help in proving the above inequality or providing an $x$ that violates the above inequality. Judging from the aforementioned plot I am pretty confident the validity of the inequality, though.

The left hand side is actually the variance of a truncated normal distribution. I am trying to give it a lower bound. More explicitly, $$f(x):=\int_0^\infty t^2n(t+x)dt-\Big(\int_0^\infty t\,n(t+x)dt\Big)^2>\Big(\int_0^\infty n(t-x)dt\Big)^2.$$

The form of the inequality is probably more transparent if we set $m=1-N$ and the inequality is equivalent to $$g(x)\equiv m[(x^2+1)(1-m)+2xn]-n(x+n) > 0.$$

$N$ is the upper bound of $f$, i.e. $$(x^2+1)N + xn-(xN+n)^2 < N$$ or $$h(x)\equiv x^2 m(1-m)-n[x(1-2m)+n]<0$$

Proof: $h$ is an even function and $h(0)<0$, so we only need to consider $x>0$. From the integration by part of $m(x)$ and dropping a negative term, we have $$xm<n, \forall x>0.$$ The first term of $h(x)$ is then bounded and \begin{eqnarray} h(x)&<&x(1-m)n-n[x(1-2m)+n] \\ &=& n(xm-n) \\ &<& 0, \end{eqnarray} where last inequality is obtained by using $xm<n$ again.

The lower bound of $f(x)$ appears to be more difficult since it requires tighter approximation of $m$ without singularity at $x=0$. I can prove the lower bound for $x$ greater than some positive number. I know I need to stitch the small and large regions of positive $x$ together, but I have not carried the detailed computation out yet. Does anyone have more clever trick to accomplish this task?

$g(x)>0, \forall x\ge\sqrt{\frac{4}{3}}$

Proof: \begin{align} \frac{dg}{dx} &= 2n[xr(1-m)-2(0.5-m)] \\ &= 2n^2[(xr-1)n^{-1}+(2-xr)r] \end{align} where $r:=\frac{m}{n}$. In what follows we will use the first expression. The second expression is an alternative which I keep just for maybe future reference. Since $$r<\frac{1}{x}\Big(1-\frac{1}{x^2+3}\Big), \forall x>0,$$ \begin{align} \frac{dg}{dx} &< \frac{2n^2}{x^2+3}(-n^{-1}+(x^2+4)r) \\ &<\frac{2n^2}{x^2+3}\Big(-n^{-1}+x\Big(1+\frac{4}{x^2}\Big)\Big), \end{align} where on the last line we apply the $r$ bound again. Choose $x\ge x_0:=\sqrt{\frac{4}{3}}$, $$n^{-1}-x\Big(1+\frac{4}{x^2}\Big)>n^{-1}-4x.$$ It can be shown that $n^{-1}-4x$ is positive at $x=x_0$ and its derivative is always positive for $x\ge x_0$. We thus have $$\frac{dg}{dx}<0, \forall x\ge x_0.$$ It is easy to see that $g(x)>0$ for sufficiently large $x$. Therefore, $g(x)>0, \forall x\ge x_0$.

YCor
  • 60,149
Hans
  • 2,169
  • When you say "prove the following inequality" - do you mean that you already know the inequality is true? If so, what is your source? If not, then what evidence do you have for why the inequality might be true? – Yemon Choi Jul 03 '13 at 04:10
  • @YemonChoi: You are correct in that I have not prove the inequality. I am however pretty confident of its validity judging from the plot I made of the two sides of the inequality. I have edited the post to reflect this discussion. Thank you. – Hans Jul 03 '13 at 05:01
  • 2
    @WillJagy et al: I have edited my original post to describe the problem with accuracy, provide reason for my speculation of its validity, and give more context. This is not an easy problem. There is a subject called normal approximation with Stein's Method. Besides, browsing through the forum, I have seen several other more trivial looking but legitimate posts. I would like to ask for the reason for deeming this question "off topic" and a review of the classification. – Hans Jul 03 '13 at 13:22
  • 1
    I am inclined to believe this may not be easy, as you say, but if you have a write-up of the results you've obtained so far that you can link to, you might have more success in convincing others that the problem is definitely non-trivial. (This is too far from my areas of research for me to weigh in with any authority, so I won't vote to reopen. I suspect however it might be MO-worthy.) – Todd Trimble Jul 03 '13 at 14:57
  • 2
    Posted this http://meta.mathoverflow.net/questions/223/requests-for-reopen-votes/357#357 on meta – Yemon Choi Jul 03 '13 at 16:55
  • @ToddTrimble et al: I have added the easier upper bound proof and pointed out the difficulty in carrying out the lower bound proof. – Hans Jul 04 '13 at 23:59
  • 1
    @Hans: Note that the argument for the upper bound, as given, isn't quite correct since $x^2 m (1-m) < n x (1-m)$ holds only for nonnegative $x$. You are saved by the fact that $h(x)$ happens to be an even function, so it suffices to consider only nonnegative $x$. Also, $g$ is even. Could you please edit to specify precisely what truncation of a normal you are considering. Perhaps a somewhat more indirect approach might yield something if we know a little more about the problem you are considering. Cheers. – cardinal Jul 05 '13 at 14:19
  • @cardinal: You are absolutely right. I had the positive axis of $x$ in mind when proving the upper bound but neglected to write it down. Like you, I am also thinking of looking at the original integral and to see if I can resolve it more elegantly through the original integral itself. I will write the original formulation shortly. – Hans Jul 06 '13 at 01:31
  • @cardinal: I have written out the explicit integral form of $f(x)$. See if you can see any openings. – Hans Jul 07 '13 at 04:46
  • @Hans: Yesterday, I was trying to reverse-engineer your problem and found several other representations. Let $U$ be a standard normal random variable. Two equivalent formulations are below (assuming I've done the algebra correctly). First, $\mathbb(E(U - x)\mid U > x) \mathbb E(x-U \mid U < x) \leq 1$. Second, $\left(\int_{-\infty}^x N(u),\mathrm d u\right)\left(\int_x^\infty (1-N(u)) ,\mathrm du\right) \leq N(x)(1-N(x))$. – cardinal Jul 07 '13 at 14:33

6 Answers6

12

Yes, the conjectured lower bound is true and can be proved using fairly simple, if somewhat tedious, analysis of derivatives.

First define $$ b := f - N^2 = x(xN + n) - (xN + n)^2 + N(1-N)\>. $$ The plan is to show that $b$ is a decreasing function bounded below by zero.

Let $u := x N + n$, so that $b = (x-u)u + (1-N)N = (x-u)u + (1-u')u'$. Since $u(-x) = -(x-u(x))$ and $N(-x) = 1-N(x)$, $b$ is an even function and so we restrict ourselves to the case $x \geq 0$.

Observe that $u' = N$, $u'' = n$, and $b(0) = (1/4) - (1/2\pi) > 0$.

By using the classical inequalities, valid for $x > 0$, $$ \frac{xn}{x^2+1} \leq 1-N \leq \frac{n}{x} \>, $$ on $(x-u)u$, it is straightforward to verify that $\lim_{x\to\infty} b(x) = 0$.

Now, using the fact $u = x u' + u''$, $$ b' = 2u(1-u') - 2 u' u'' = 2 u' u''\left(\frac{(1-u')u}{u'u''} - 1\right) \>. $$ So, if we can show that $\frac{(1-u')u}{u'u''} \leq 1$, we will be done. Plugging in the definitions yields $\frac{(1-u')u}{u'u''} = \frac{1-N}{n}(x+n/N)$.

Lemma 1. For $x \geq 0$, $n/N \leq a e^{-a x}$ where $a = \sqrt{2/\pi}$.

Proof. Define $g := a^{-1} e^{ax} n - N$. Then $g(0) = 0$ and $$ g' = (1-x/a - e^{-ax})e^{ax} n < 0 \>. $$

In particular, we have, $x+n/N \leq x + a e^{-a x}$ for any $x \geq 0$.

Lemma 2. For $x \geq 0$, $(1-N)/n \leq (x+a e^{-ax})^{-1}$.

Proof. Set $g := (x+ae^{-ax})^{-1} n - (1-N)$. Then, $g(0) = 0$ and $$ g' = (a+ae^{-ax} + x - a^{-1} e^{ax}) \frac{a e^{-ax} n}{(x+a e^{-ax})^2}\>. $$ The fraction on the right is positive, so we concentrate on the first term on the right. Let $z := a + a e^{-ax} + x - a^{-1} e^{ax}$. Then $z(0) = 2a - 1/a > 0$ and $\lim_{x\to\infty} z(x) = -\infty$. Furthermore, $$ z' = - a^2 e^{-ax} + 1 - e^{ax} < 0 \>. $$ Hence, $g'$ is positive for small $x$ and negative for large $x$. Since $\lim_{x\to\infty} g(x) = 0$, we conclude that $g \geq 0$.

This allows us to complete the proof, since by applying Lemma 1 and then Lemma 2, we have $$ \frac{1-N}{n} (x + n/N) \leq \frac{1-N}{n} (x+a e^{-ax}) \leq 1 \>. $$

Hence, $b' < 0$, so $b > 0$ as desired.

cardinal
  • 1,136
  • 1
  • 9
  • 14
  • Beautiful proof! I think the introduction of $u:=\int_{-\infty}^x n(t)dt$ is the key. Lemma 1 and Lemma 2 are useful result in their own rights. They connect the behavior of $N$ or $1-N$ near $0$ and $\infty$ smoothly. I will wait a while for others to check the computation, before I will check it as THE accepted answer, even though it is too pretty to be wrong. Meanwhile, could you please describe your motivation in coming up with the function $a e^{ax}$? – Hans Jul 08 '13 at 02:36
  • It is unfortunate that there is only 1 point up vote allow for each person per answer. Otherwise, I would have put in ticked more. :-) – Hans Jul 08 '13 at 02:40
  • Dear @Hans: Regarding motivation: Note that $n/N$ is decreasing and so I first tried the crudest thing possible, i.e, $x + n/N \leq x + n(0)/N(0) = x + a$. However, this doesn't work since it turns out by a similar argument to Lemma 2 that $(1-N)/n \geq (x+a)^{-1}$. So, I needed a function that decreased but stayed above $n/N$, while also decreasing fast enough that I'd still get an upper bound on $(1-N)/n$. Note that, actually, the same basic analysis as Lemma 2 will yield $(1-N)/n \leq (x+a e^{-bx})^{-1}$ where $b = \sqrt{\pi/2}-\sqrt{2/\pi}$, which is a little sharper, but unneeded here. – cardinal Jul 08 '13 at 03:08
  • @Hans: (Also, just a minor typo in your first comment: $u := \int_{-\infty}^x N(u),\mathrm du$. Cheers.) – cardinal Jul 08 '13 at 03:09
  • I see your rationale, but can you describe what makes you think of the particular form of the exponential function $e^{-ax}$? Just a first lucky choice? And thanks for pointing out my typo. – Hans Jul 08 '13 at 04:46
  • @Hans: $n$ is obviously exponentially bounded and so I was most concerned with matching the behavior near zero. Note that $n/N$ and $a e^{-ax}$ share the same derivative at zero as do their respective logs. – cardinal Jul 08 '13 at 13:00
6

Here is a complete solution. The idea is to kill the entries of $N$ in two steps, by applying two appropriately constructed first-order differential operators, which will result in a simple elementary expression:

Let $b:=f-N^2$. As noted by cardinal, $b$ is an even function. So, it is enough to show that $b>0$ on $[0,\infty)$. Let $$ b_0(x):=\frac{b(x)}{x^2+1} $$ and $$ b_1(x)=\pi\, \left(x^2+1\right)^2 e^{x^2/2}\, b_0'(x). $$ Then $b_1'(x)=-e^{-\frac{x^2}{2}} \left(x^2+1\right)<0$, so that $b_1$ is decreasing. Also, $b_1(0)=0$. Hence, $b_1(x)<0$ for $x>0$, and so, $b_0$ is decreasing on $[0,\infty)$. Moreover, $b_0(x)\to0$ as $x\to\infty$. So, $b_0>0$ and hence $b>0$.

Iosif Pinelis
  • 116,648
  • 1
    I will verify the algebra later but it looks like an ingenious proof! Would you be so kind as to share your insight and motivation that leads you to the definition of $b_0$ and subsequent $b_1$? – Hans Jun 04 '15 at 19:49
  • 3
    Thank you for your comment Hans. The "worst" in the expression of $b(x)$ are the "like terms" containing $N(x)^2$, which can be combined, with the total coefficient $x^2+1$ (maybe times some constant). So, the division by $x^2+1$ leaves only a constant coeff. at $N(x)^2$, and the derivative of $N^2$ is $2Nn$, which is "simpler" than $N^2$. So, $b_0'$ is "simpler" than $b$. Similarly proceeding further, till I get something really simple. – Iosif Pinelis Jun 04 '15 at 20:32
  • I am revisiting this problem. I see your motivation clearly now after having finally checked out the algebra, which is correct. It is, as you said, to keep reducing the integration and its powers of $n$ while the derivatives of $n$ is itself multiplied by polynomials. Again, ingenious. +1 I do not now what the etiquette is here, but if it is not frowned upon and not seen as diminishing the excellency of cardinal's proof, I would accept your answer. – Hans Jan 10 '18 at 09:18
1

We may see that the inequality is true for every $|x|<0.597$ in the following way:

For a given value of $x$ consider the values of $N$ and $n$. The inequality will be true for this $x$ if the quadratic polynomial in $y$ $$(y^2+1)N+y\, n-(y N+n)^2-N^2$$ is always positive. In other words the inequality is true for this $x$ as soon as the discriminant $\Delta$ of this quadratic is negative (the coefficient of $y^2$ being positive).

The discriminant is $\Delta =n^2-4N^2(1-N)^2$. Since $n^2<1/(2\pi)$, the inequality will be true for every $x$ such that $4N^2(1-N)^2>1/(2\pi)$.

Thus the inequality is true for every $x$ such that $0.275214<N<0.724786$. This corresponds to the condition $|x|<0.597$.

Did
  • 5,701
juan
  • 6,976
  • @ juan : You wrote "Since the derivative of your function is easily bounded". Could you explain that place in detail? The expression for $f'(x)$ (which can be downloaded from http://rapidshare.com/files/3032281090/derivative.pdf ) is not so simple. – user64494 Jul 07 '13 at 05:11
  • @user64494 To apply the maximal slope principle you only need a rough bound of the derivative. For example substitute all exp(-x^2/2) by 1 and all N(x) by 1, all x by 0.597. All in absolute value and this bound will suffice. – juan Jul 07 '13 at 08:11
  • @ juan: You don't answer my request concerning the estimate of the derivative. So called slope principle is the next step in your answer. – user64494 Jul 07 '13 at 08:17
  • @user64494 My answer proof completely the inequality for $x<-0.597$ or $x>0.597$. For this you have no need of a bound of the derivative. Now to show $f(x)>0$ (my $f$ is different from yours) on the interval $|x|<0.597$ you may apply the maximal slope principle. This need a bound of the derivative on $|x|<0.597$ (a rough bound suffice). This is very easy to get. And you finish without difficulty the proof with a little computation (see the paper cited in my answer). – juan Jul 07 '13 at 08:18
  • @ juan: If this is very easy to get, please give it. – user64494 Jul 07 '13 at 09:10
  • @Hans It is realy easy. But now I am a little confused about who is interested. – juan Jul 07 '13 at 09:24
  • @Hans I had edited my answer because at the start I said $|x|<0.597$ instead of the intended $|x|>0.597$. – juan Jul 07 '13 at 11:20
  • 1
    I am not sure to follow: the good regime $4N^2(1-N)^2\gt1/2\pi$ is when $|x|\lt x_$ for some $x_$, not the other way round (as an aside, note that the inequality one is interested in holds at $x=0$ hence also in a neighborhood of $x=0$). – Did Jul 07 '13 at 11:52
  • @Did yes I was wrong. This proves the inequality for $|x|<0.597. And the rest is not so easy, because now the intervals are infinite. I changed my solution correspondingly. – juan Jul 07 '13 at 15:51
  • @juan: I have noticed your error in reversing the inequality some time ago, but I was busy with other things and I knew you'd notice it yourself anyway.:-) It seems there is still some work to actually prove the desired inequality holds in $|x|<0.597$. One way to do it is through bounding the integral $N$. It seems your previously suggested method of maximal slope gives a valid region much smaller than $|x|<0.597$. Maybe my derivative bound is not tight enough. Could you show your work in detail? – Hans Jul 07 '13 at 16:39
  • @juan: I like your discriminant trick. – Hans Jul 07 '13 at 18:16
  • For $x>0$ in the case of discriminant positive, the inequality will be true if $x>$ the greater of the two roots. I think this is also promising. – juan Jul 07 '13 at 19:37
  • @juan: Also, numerical computation shows the discriminant $\Delta<0$ for $0<x<1.3$. If we can show this, together with my result for $x>1.16$, the proof will be complete. – Hans Jul 07 '13 at 19:54
  • @juan: Could you show your work for getting $|x|<0.597$ from the bound on $N$ in detail, or at least with some sketch? It is not enough coming from numerical computation. The proof is not completely obvious. – Hans Jul 07 '13 at 19:57
  • @Hans can you send me a mail. To send you this privately. They want to pass the discussion to chat. I prefer mail. My address is easy to get. – juan Jul 07 '13 at 20:07
  • @juan: I don't know why you repeat your discriminant inequality in your last comment. I know perfectly that from this inequality you can get the range for $N$. However, what I am saying is that you need to convert the value from $N(x)$ to $x$. That needs some work. You can not just quote whatever comes out of the numerical quadrature result. You need to give it tight error bounds. Do you see what I am getting at? – Hans Jul 07 '13 at 20:14
  • @juan: OK. Just emailed you. – Hans Jul 07 '13 at 20:19
0

This is just to make explicit the functions in Iosif Pinelis' ingenious answer for posterity.

$$b_0(x):=\frac{b(x)}{x^2+1}=-N^2+\Big(1-\frac{2xn}{x^2+1}\Big)N+\frac{x-n}{x^2+1}n,$$ and $$b_0'(x)=\frac{2n}{(x^2+1)^2}\,(-2N+1+xn).$$ $$b_1(x):=\frac{(x^2+1)^2}{2n}b_0'(x),$$ implying $$b_1'(x)=-(1+x^2)n>0.$$

Hans
  • 2,169
-1

The Maple command $$asympt((x^2+1)*N(x)+x*n(x)-(x*N(x)+n(x))^2-N(x)^2, x, 8)$$ produces $$ \left( {\frac {\sqrt {2}}{\sqrt {\pi }{x}^{3}}}-6\,{\frac {\sqrt {2}} {\sqrt {\pi }{x}^{5}}}+O \left( {x}^{-7} \right) \right) {\frac {1}{ \sqrt {{{\rm e}^{{x}^{2}}}}}}. $$ Thus the inequality is true for big positive $x$. I leave the investigation of it on the finite interval on your own. The above asymptotics can be obtained by hand too.

user64494
  • 3,309
  • 1
    You did not say which finite interval. – Did Jul 06 '13 at 08:33
  • @ Did: A positive result is obtained by me. What can you do? – user64494 Jul 06 '13 at 08:43
  • Sorry but I do not understand your comment. You might want to explain (or to delete the comment). – Did Jul 06 '13 at 08:48
  • @ Did: Indeed, I did not say it. What can you suggest to this end? – user64494 Jul 06 '13 at 09:17
  • BTW, compare this answer with the answer by David Speyer in http://mathoverflow.net/questions/133028/the-following-inequality-is-truebut-i-cant-prove-it – user64494 Jul 06 '13 at 13:33
  • 4
    @user64494: Did you read the last few sentences of my original post? "I can prove the lower bound for x greater than some positive number. I know I need to stitch the small and large regions of positive x together, but I have not carried the detailed computation out yet. Does anyone have more clever trick to accomplish this task?" The lower bound can be easily verified for very small $x$ too. The difficulty lies in specifying what you call "finite interval" show that the valid finite interval overlaps with the large $x$ interval. – Hans Jul 06 '13 at 16:15
  • @ Hans: Can your present your proof of the lower bound for $x$ greater than some positive number? – user64494 Jul 06 '13 at 17:33
  • @user64494: Thank you for the reference to link. The solution is very intriguing. However, how does it help in this case? – Hans Jul 07 '13 at 16:46
  • @user64494: I have put in the proof for the lower bond for $x\ge\sqrt{\frac{4}{3}}$. – Hans Jul 07 '13 at 18:15
-1

In view of $$f(x):= (x^2+1)N(x)+xn(x)-(x+N(x))^2-N(x)^2=$$ $$\left( {x}^{2}+1 \right) \left( 1/2+1/2\, {{\rm erf}\left(1/2\,\sqrt {2}x\right)} \right) +1/2\,{\frac {{{\rm e} ^{-1/2\,{x}^{2}}}\sqrt {2}x}{\sqrt {\pi }}}- $$ $$\left( x+1/2+1/2\, {{\rm erf}\left(1/2\,\sqrt {2}x\right)} \right) ^{2}- \left( 1/2+1/2\, {{\rm erf}\left(1/2\,\sqrt {2}x\right)} \right) ^{2} $$ and its taylor expansion at $x=0$ $$f(x)=-x+ \left( -1/2\,{\pi }^{-1}+{\frac {1}{2}}- \left( 1+1/2\,{\frac { \sqrt {2}}{\sqrt {\pi }}} \right) ^{2} \right) {x}^{2}+O \left( {x}^{3 } \right) $$ the inequality under consideration seems to fail for small positive values of $x$.

user64494
  • 3,309