2
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer. Could you please explain a little bit more about how you use Jensen's inequality? $\endgroup$ – Melika Jan 7 at 22:54
  • $\begingroup$ @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$. $\endgroup$ – Will Sawin Jan 7 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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