# Lower-bound for $E[\min(X, k)]$ where $X$ is sum of Bernoulli random variables with $E[X]$ being a linear function of $k$

Given a real number $$\alpha \in [0.5, 1.5]$$, an integer number $$k>1$$, and a set of independent Bernoulli random variables $$x_1, \dots, x_n$$, I am interested to find a lower-bound for $$F(\alpha, k)= \frac{E[\min(X, k)]}{k}$$ subject to $$E[X] = \alpha k$$ where $$X=\sum_{i\in n} x_i$$.

My observation is that for $$k\rightarrow \infty$$ we have $$F(\alpha, k) = \min(\alpha, 1)$$. I can also find a tight lower-bound for k=2, which is $$1-\frac{(2+2\alpha)e^{-2\alpha}}{2}$$ when $$x_i$$'s are identical and $$n\rightarrow \infty$$.

My question is that, is it possible to show that for any $$k>2$$, the same bound holds? More precisely, I want to show that for any $$\alpha$$ and $$k$$, we have $$F(\alpha, k)\geq 1-\frac{(2+2\alpha)e^{-2\alpha}}{2}.$$

• Shouldn't that be $e^{-2\alpha}$? – Will Sawin Jan 3 at 22:02

Let $$x_1,\dots, x_n$$ be independent Bernoulli random variables with expectations $$p_1,\dots, p_n$$ summing to $$k\alpha$$. Let $$y_1,\dots, y_n$$ be independent random variables with expectations $$p_1 \frac{k-1}{k},\dots, p_n \frac{k-1}{k}$$, summing to $$(k-1)\alpha$$. I claim that $$\mathbb E \left[ \frac{ \min \left( \sum_{i=1}^n x_i, k \right)}{k} \right]\geq \mathbb E \left[ \frac{ \min \left( \sum_{i=1}^n y_i, k-1 \right)}{k-1} \right]$$

This implies that the optimal lower bound for a given $$k,\alpha$$ is an increasing function of $$k$$, so your $$k=2$$ lower bound works for all $$k$$.

To do this, we can couple $$x_i$$ with $$y_i$$ so that, whenever $$x_i=0$$, we also have $$y_i=0$$, and when $$x_i=1$$, $$y_i$$ has a $$\frac{k-1}{k}$$ conditional probability of being $$1$$. In other words the conditional expectation of $$y_i$$ on a given value of $$x_i$$ is equal to the $$\frac{k-1}{k} x_i$$. This implies that for $$F$$ any convex function, $$\mathbb E \left[ F \left( \frac{k-1}{k} x_1,\dots, \frac{k-1}{k} x_n \right) \right] \geq \mathbb E \left[ F \left( y_1,\dots,y_n \right) \right]$$ by (a conditional form of) Jensen's inequality.

Taking $$F(y_1,\dots,y_n) = \min ( \sum_{i=1}^n \frac{y_i}{k-1}, 1),$$ which is convex, gives our desired inequality.

In what also may be helpful, here is the sharp lower bound for fixed $$k>2$$:

Given a Bernoulli random variable $$x_i$$ with mean (probability of being $$1$$) $$p_i$$, we can find a Poisson random variable $$y_i$$ coupled with it, with the same mean, such that if $$x_i=0$$ then $$y_i=0$$. Indeed this is just saying that $$P(x_i=0) < P(y_i=0)$$ which follow from $$1-p< e^{-p}$$.

Thus we have the conditional probability $$\mathbb E[ y_i | x_i=x] =x$$. Thus, conditional on $$x_1,\dots, x_n$$ taking the values $$x_1',\dots, x_n'$$, the expected value of $$\sum_{i=1}^{n} y_i$$ is $$\sum_{i=1}^n x_i'$$, so the expectation of $$\min( \sum_{i=1}^{n} y_i,k)$$ is at most $$\min( \sum_{i=1}^n x_i', k)$$. Thus $$\mathbb E \left[ \min\left( \sum_{i=1}^{n} y_i, k\right)\right] \leq \mathbb E \left[ \min\left( \sum_{i=1}^{n} x_i, k\right)\right].$$

But $$\sum_{i=1}^{n} y_i$$ is a Poisson random variable with known distribution, so we get a lower bound of

$$\sum_{j=0}^{\infty} \frac{ \min(j,k)}{k} \frac{ (k\alpha)^j e^{-k \alpha} }{ j!}$$

When $$k=2$$ this is exactly your stated bound.

• Thanks for the answer. Could you please explain a little bit more about how you use Jensen's inequality? – Melika Jan 7 at 22:54
• @Melika For each possible value of the $x_i$, we apply Jensen's inequality to the expectation of $F(y_1,\dots,y_n)$ conditional on the $x_i$ having that value. This gives a lower bound of $F( \frac{k-1}{k} x_1,\dots, \frac{k-1}{k} x_n)$. Then we average over the possible values of the $x_i$. – Will Sawin Jan 7 at 23:19