User balu - MathOverflow

Inequality on probability distributions

2010-12-02T07:36:38Z

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.

Capped binomial random variables

2012-04-15T01:19:40Z

Consider a random variable $X = \sum_{i=1}^{m} X_i$, where each $X_i$ is an indicator random variable that is $1$ with probability $k/m$ and $0$ otherwise. We are interested in the quantity $S_X(m) = E[\min(X,k)]$. The motivation is that we have a bin of capacity $k$. At each step, a ball is thrown into the bin with probability $k/m$. At the end of $m$ steps, we ask how many balls are in the bin. This quantity, in expectation, is precisely $S_X(m)$.

Now suppose we throw "fractional balls", i.e., instead of having ${0,1}$ random variables $X_i$s, we have random variables $Y_i$ that have support $[0,1]$. We retain the same expectation, i.e., $E[Y_i] = k/m = E[X_i]$ and the $Y_i$'s are iid. Let $S_Y(m) = E[\min(Y,k)]$, where $Y = \sum_{i=1}^{m} Y_i.$

The question I am interested in is whether $S_Y(m) \geq S_X(m)$?

I have an intuition for why this must be true: the variance of $X_i$ is at least as much as that of $Y_i$ --- this is because $E[X_i^2] = E[X_i]$, where as $E[Y_i^2] \le E[Y_i]$. Thus, one would expect a random variable with smaller variance (namely $Y = \sum_i Y_i$) to be more concentrated around the mean than a random variable with larger variance (namely $X = \sum_i X_i$), thus implying the result. Roughly speaking, one would expect the "wastage" of balls due to overflowing the capacity $k$ of the bin occurs lesser when we have fractional balls than integer balls. However this is not a definitive proof. Is there a simple proof for this?

Tail Conditional Expectation of a binomial random variable

2011-09-18T00:50:22Z

Let $X \sim B(n,c/n)$ be a binomially distributed random variable with parameter $p = c/n$, and hence mean $c$. Here $c$ is some function of $n$ such that

i) $c \geq n^{2/3}$

ii) The function $c$ grows slower than any linear function of $n$ (i.e., in big-O notation, $c = o(n)$, or equivalently $\lim_{n \to \infty} c/n = 0$).

For such a variable, I want a ball-park estimate of $E[X|X \geq c]$, i.e., tail conditional expectation (TCE), for large $n$. If the probability $c/n$ were a constant, then by central limit theorem the TCE is approximately $c + \sqrt{c}$. However, $c/n$ is not a constant here. I am most interested in finding whether the following statement is true:

For all $c$ in the said range, the TCE is of the form $c + f(c)$ where $f(c) = o(c^{r})$ for some constant $r < 1$.

The choice of lower-bound for $c$, namely $c \geq n^{2/3}$ has no significance. I would be happy with resolving the question for a much more restricted range of $c$ by placing a bigger lower bound on $c$.

I tried writing the explicit expression for the TCE but I have not been able to get anything useful out of it. Also I saw a paper on TCE for binomial rv's, but it just gives the obvious formula obtained by using linearity of expectation and nothing more.

Comment by Balu

2012-04-16T14:36:17Z

Thanks for the nice reference, and for taking the time to write a complete proof.

Comment by Balu

2011-09-18T04:17:21Z

Thanks Ori for the quick response.

Comment by Balu

2011-09-18T04:07:12Z

Thanks Brendan.

Comment by Balu

2011-01-02T11:37:31Z

Hahn, the answer to both of your questions is yes.

Comment by Balu

2011-01-02T11:36:03Z

Thanks Didier! Perfect.

Comment by Balu

2010-12-02T18:21:39Z

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.