Given a set of independent Bernoulli random variables $\{x_1, \dots, x_n\}$, let $p = \sum_{0<i\leq n}\Pr[x_i = 1]$ and $X=\sum_{0<i\leq n} x_i$. We know that for any $i$, we have $\Pr[x_i = 1]\leq \frac{p}{2}$ and need to find a lower-bound for $\Pr[X>1]$ for any $p \in [0, 2]$. (The lower-bound should be a function of $p$.)
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
This turned out stranger than I expected.
A good lower bound is $$\min\left(\frac{p^2}{4}, 1-\frac{4+2p-p^2}{4e^{\,p/2}}, 1-\frac{1+p}{e^{\,p}} \right)$$ where the components apply in the regions [0,0.923], [0.923,1.547] and [1.547,2].
For $n=3$, I got an explicit solution from Mathematica with these minimizing probabilities and arguments: \begin{align} \frac{p^2}{4} \ \ \ \ \ &\text{ via }\{\frac{p}{2}, \frac{p}{2}, 0\} \text{ if } p \in [0,1]\\ \frac{p^2(5-p)}{16} &\text{ via }\{\frac{p}{2}, \frac{p}{4}, \frac{p}{4}\} \text{ if } p \in [1,\frac{9}{5}]\\ \frac{p^2(9-2p)}{27} &\text{ via }\{\frac{p}{3}, \frac{p}{3}, \frac{p}{3}\} \text{ if } p \in [\frac{9}{5},2]\\ \end{align}
FullSimplify[Minimize[{q r + q s + r s - 2 q r s, p == q + r + s,
0 <= q <= p/2, 0 <= r <= p/2, 0 <= s <= p/2}, {q, r, s}], Assumptions -> 0 < p < 2]
This and similar explicit results for $n=4$ suggest that for all $n$, the minimizing probabilities and arguments will be one of: \begin{align} \frac{p^2}{4} \ \ \ \ \ &\text{ via }\{\frac{p}{2}, \frac{p}{2}, 0, \ldots, 0\} \\ 1-\left(1+\frac{2p-p^2}{4-4q}\right) \left(1-q\right)^{n-1} &\text{ via }\{\frac{p}{2}, q, \ldots, q\} \\ 1-\left(1+p-\frac{p}{n}\right)\left(1-\frac{p}{n}\right)^{n-1} &\text{ via }\{\frac{p}{n}, \frac{p}{n}, \ldots, \frac{p}{n}\} \end{align} where $q=p/(2n-2)$. The formula at the top comes from taking the limit of this as $n$ goes to infinity.
The graph shows the blue line for $n=3$, the orange line for $n=4$, and the green line for the limit.
-
$\begingroup$ Thanks a lot. Do you have a proof for the mentioned lower-bound? I would very much appreciate if you could provide the proof since this is a very interesting bound and is exactly what I need. $\endgroup$– MelikaCommented Nov 2, 2018 at 8:24
-
$\begingroup$ I have ideas for a proof, but haven’t explored them in detail. Can you say more about your motivation or the context for the question? $\endgroup$– user44143Commented Nov 3, 2018 at 6:38
-
$\begingroup$ Can you clarify your statement that it's a lower bound? $\endgroup$ Commented Nov 3, 2018 at 13:14
-
$\begingroup$ I'm writing a computer science paper, and if I find a better lower-bound for this problem, it improves my result. I don't need a tight bound. What I have done by now is merely dividing them into two partitions $P_1$ and $P_2$ where $|\sum_{x\in P_1} \Pr[ x=1] - \sum_{x\in P2} \Pr[x=1]| \leq p/3$ and I've computed the probability that at least one of the variables in each partition is $1$. $\endgroup$– MelikaCommented Nov 3, 2018 at 19:10
-
1$\begingroup$ @TaroNGUYEN, it’s a lower bound for the exact results in the case n=3, a lower bound for all of the n=4 cases in which at least two probabilities agree (so at most three distinct probabilities), and a lower bound for all higher n if there are at most two distinct probabilities. I used the same formula for Fn as in your answer. $\endgroup$– user44143Commented Nov 5, 2018 at 18:02
$\begingroup$
$\endgroup$
As I see, for fixed $n$ and fixed $p$, the minimum of $P(X>1)$ can be expressed compactly as a recursive function of $n$ and $p$.
More precisely, let $G(n,p) = \text{min}( \mathbb{P}(X>1)$ under the given constraint and $$ F_n( y_1,y_2,y_3,...,y_n) = (1-y_1)(1-y_2)...(1-y_n)\left( 1+ \sum_{i=1}^n \frac{y_i}{1-y_i} \right) $$
As I observe, we can prove that :
Proposition 0 Forall $n>2$,
$G(n,p) = \text{min}\left( G(n-1,p) , 1- F_n\left( q,q,...,q, \frac{p}{2}\right) , 1- F_n \left(\frac{p}{n},...,\frac{p}{n} \right) \right) $ where $q = \frac{p}{2n-2}$
However, I don't think these results are so obvious that we can state them without verification as in the answer of Matt.
