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



Lower-bound for $E[\min(X, k)]$ where $X$ is sum of Bernoulli random variables with $E[X]$ being a linear function of $k$
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.


