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

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

The answer to your question is positive and, for example, follows immediately from Corollary 4 of

C. A. León and F. Perron (2003), Extremal properties of sums of Bernoulli random variables, Statistics and Probability Letters, vol. 62, 345–354.

A slight specialization of the corollary states:

Let $\newcommand{\E}{\mathbb E} Y = Y_1 + \cdots + Y_n$ be a sum of iid random variables taking values in $[0,1]$ with mean $\E Y_i = \mu$ and let $X \sim \mathrm{Bin}(n,\mu)$. For any convex function $g : [0,n] \to \mathbb R$, $$ \E g(Y) \leq \E g(X) \ . $$

Your result follows by noting that $g(x,a) = -\min(x,a)$ is convex in $x$ for any $a \in \mathbb R$.

The paper appeals to other references, but an easy and direct proof can be constructed, so we may as well give a version of it here as several short lemmas.

In what follows below, we assume $(Y_i)$ are iid on $[0,1]$ with distribution function $F$ and mean $\mu$ and that $(X_i)$ are iid Bernoulli random variables also with mean $\mu$. The function $g$ is assumed to be an arbitrary convex function defined on the appropriate domain.

Lemma 1: If $Y \sim F$ and $X \sim \mathrm{Ber}(\mu)$, then $\E g(Y) \leq \E g(X)$.

Proof: $Y = 1 \cdot Y + 0 \cdot (1-Y)$, so, by convexity, $\E g(Y) \leq g(1) \E Y + g(0) \E (1-Y) = \E g(X)$.

Lemma 2: $\E g(Y_1 + Y_2) \leq \E g(X_1 + X_2)$.

Proof: Assume wlog that $(Y_1,Y_2)$ is independent of $(X_1,X_2)$. If $g$ is convex, then so is $g(y+\cdot)$, hence $$\E g(Y_1 + Y_2) = \int_0^1 \E g(y + Y_2) \ \mathrm dF \leq \int_0^1 \E g(y + X_2) \ \mathrm dF = \E g(Y_1 + X_2) \leq \E g(X_1 + X_2) \ . $$

Corollary: Let $Y = Y_1 + \cdots + Y_n$ and $X = X_1 + \cdots X_n$, where $X \sim \mathrm{Bin}(n,\mu)$ as in the problem. Then, $\E g(Y) \leq \E g(X)$.

Proof: Extend the previous lemma by induction.

The desired result now follows by taking the aforementioned choice for $g$ with $a = n \mu$.

share|improve this answer
    
Thanks for the nice reference, and for taking the time to write a complete proof. –  Balu Apr 16 '12 at 14:36

You might look into convex orders. I think (maybe) Y is larger than X in that ordering, and it's preserved under convolution.

share|improve this answer
    
$Y$ is smaller than $X$ in the convex order, by bounding from above any convex function on $[0,1]$ by the secant line passing through the points $(0,g(0))$ and $(1,g(1))$; this is Lemma 1 in cardinal's answer. And yes, convex order inequalities between between laws on the line (or a measurable vector space over the reals) "can be multiplied" with respect to convolution; this is Lemma 2 from above formulated in its natural generality. Books treating such things include \textit{Stochastic Orders} by Shaked and Shantikhumar (2007) and \texit{Comparison Methods ...} by Müller and Stoyan (2002). –  Lutz Mattner Mar 2 '13 at 15:36

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.