4
$\begingroup$

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?

$\endgroup$

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the nice reference, and for taking the time to write a complete proof. $\endgroup$
    – Balu
    Apr 16, 2012 at 14:36
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ $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). $\endgroup$ Mar 2, 2013 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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