Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I would like to know if the following inequality is satisfied by all probability distributions (or at least some class of probability distributions) for all integer $n \geq 2$.

$\int_0^{\infty} F(z)^{n-1}(1-\frac{F(z)}{n})\left[zF(z)^{n-2} - \int_0^z F(t)^{n-2}dt\right]f(z)dz$ $\leq \int_0^{\infty} F(z)^{n-1}\left[zF(z)^{n-1} - \int_0^z F(t)^{n-1}dt\right]f(z)dz $

Some comments follow:

1) F(z) is the cumulative distribution function of any probability distribution over positive real numbers. The outer integral runs over the entire support of the distribution, thus, in general, from zero to infinity. f(z) is the probability density function.

2) I will be happy even if this is proved for bounded support distributions, in which case, the outer integral runs from 0 to some upper limit H.

3) Note that both the LHS and the RHS are always non-negative. This is because of the special form of what is inside the square brackets. For both the LHS and the RHS, the second term in the square bracket (i.e. the negative integral from 0 to z), when replaced by its value at the upper limit throughout the region of integration from 0 to z, gives precisely the first term in the square bracket. Thus the term in the square bracket is always non-negative, for both the LHS and the RHS.

4) Also note the obvious similarity in the structure between the LHS and the RHS. The only differences are the difference in exponent for what is inside the square brackets, and the LHS having an extra factor of $1 - \frac{F(z)}{n}$.

5) Note that for $n=2$, this inequality is definitely true since the LHS evaluates to zero owing to the term in the square bracket in the LHS becoming zero, and the RHS is always non-negative, as mentioned in point 3 above.

6) It is easy to work out that for all $n \geq 2$, this inequality is true for uniform [0,1] distributions, i.e., the distribution with support [0,1] and $F(z) = z$.

7) I tried evaluating this integral for small values of $n$ (till 50) using Maple for exponential distribution, and the positive half of the normal distribution and found it to be true. I am guessing that this inequality is true for at least some large class of probability distributions if not all distributions.

8) For instance, would a monotone hazard rate condition help? Monotone hazard rate means that $\frac{f(z)}{1-F(z)}$ is non-decreasing.

share|improve this question
1  
Could you give some background of this inequality? –  zhoraster Dec 2 '10 at 11:21
    
This inequality pops up in my research in algorithmic game theory. The actual context itself yields little intuition, except for the fact that if the above inequality held, the result we get would be a natural one. Briefly, the problem has to do with comparing two kinds of auctions with each other and analyzing bidding strategies in the two auctions. One auction rewards the highest bidder more than the other, so we would expect the expected highest bid to be larger in the first auction. That is what this inequality would imply. –  Balu Dec 2 '10 at 18:21
    
Is $n$ the number of bidders and this inequality derived from expected order statistics? –  R Hahn Jan 1 '11 at 7:48
    
Hahn, the answer to both of your questions is yes. –  Balu Jan 2 '11 at 11:37
add comment

1 Answer

up vote 7 down vote accepted

The inequality holds for every $n\ge2$ (integer or not) and every probability distribution. Here is a proof. We begin with two easy facts.

Fact 1: For every $z\ge0$ and every $k\ge1$, $$ zF(z)^k-\int_0^zF(t)^k\mathrm{d}t=k\int_0^ztF(t)^{k-1}f(t)\mathrm{d}t. $$ Fact 2: For every $t$ and every $k\ge0$, $$ (k+1)\int_t^{+\infty}F(z)^kf(z)\mathrm{d}z=1-F(t)^{k+1}. $$ (Fact 1 is an integration by parts. Fact 2 is trivial.)

Now to the proof.

Replace the brackets on the LHS and on the RHS by integrals over $t$ in $(0,z)$ thanks to Fact 1. This yields expressions of the LHS and of the RHS as double integrals. Interchange the order of integration. The inner integrals over $z$ in $(t,+\infty)$ can both be evaluated thanks to Fact 2. One gets that the difference between the RHS and the LHS is $$ A_n=n^{-1}\int_0^{+\infty}tf(t)F(t)^{n-3}P_n(F(t))\mathrm{d}t, $$ where $$ P_n(x)=(n-1)x(1-x^n)-(n-2)(1-x^n)+(n-2)(1-x^{n+1})/(n+1). $$ Hence $$ A_n=n^{-1}\int_0^{+\infty}Q_n(F(t))\mathrm{d}t,\qquad\mbox{with}\quad Q_n(x)=\int_x^1u^{n-3}P_n(u)\mathrm{d}u. $$ The proof that $A_n\ge0$ for every probability distribution is complete if $Q_n\ge0$ over $(0,1)$. Some easy calculus of variation will do the job.

Namely, over $(0,1)$, the second derivative $P''_n$ is positive then negative, hence the first derivative $P'_n$ is increasing then decreasing. Since $P'_n(0)>0$ and $P'_n(1)<0$ (expressions omitted), $P'_n$ is positive then negative, hence $P_n$ is increasing then decreasing. Since $P_n(0)<0$ and $P_n(1)=0$, $P_n$ is negative then positive.

This shows that $Q_n$ is increasing then decreasing over $(0,1)$. Since $Q_n(1)=0$, it remains to prove that $Q_n(0)\ge0$. This last fact follows from the explicit computation of the integral over $(0,1)$ defining $Q_n(0)$, which yields, unless I am mistaken, that $Q_n(0)=(n-2)/(2(n-1)(2n-1))$. Since this quantity is nonnegative for every $n\ge2$, we are done.

share|improve this answer
    
Thanks Didier! Perfect. –  Balu Jan 2 '11 at 11:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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