Capped binomial random variables

Question

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?

Answer 1

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

Answer 2

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