Let us suppose that we are in the setting of Janson's inequality for Poisson-type deviations of increasing events. Specifically, we have independent Bernoulli variables $X_1, \dots, X_n$, and events $A_1, \dots, A_m$, each of which is an increasing function of some subset $S_i$ of the $X$ variables. For the purposes of this question, we can in fact assume that each event $A_i$ has the form $A_i = \bigwedge_{k \in S_i} X_k$.

We write $i \sim j$ if $i \neq j$ and $S_i \cap S_j \neq \emptyset$. Define $\mu = \sum_i \Pr(A_i)$ and $\Delta = \sum_{i,j: i \sim j} \Pr(A_i \cap A_j)$.

Let us define the event $$ B = \bigvee_{i=1}^m \Bigl( A_i \cap \bigwedge_{j: j \sim i} \overline A_j \Bigr), $$ i.e. that some event $A_i$ holds, but none of its neighbors $A_j$ do. I would like to show a lower bound on $\Pr(B)$, assuming that $\mu \gg \Delta$.

We can count the expected number of indices $i$ with this property; by the union bound, it is at least $\sum_{i=1}^m \Pr(A_i) \Bigl(1 - \sum_{j: j \sim i} \Pr(A_i \cap A_j) \Bigr) = \mu - \Delta$. My question is whether a Janson-type bound holds in this setting. For example, I might conjecture that $$ \Pr(B) \geq 1 - e^{-\mu + \Delta} $$

Is such a bound possible to show?


1 Answer 1


According to your definition, the set $B$ is always empty if $S_i\ne\emptyset$ for all $i$, because then $A_i\sim A_i$ for all $i$. Hence, $P(B)=0$ -- so that no strictly positive lower bound on $P(B)$ is possible.

Even if you amend your definition of $B$ as follows: $$ B := \bigvee_{i=1}^m \Bigl( A_i \cap \bigwedge_{j\colon\, j\ne i, A_j \sim A_i} \overline A_j \Bigr), $$ you will still get $B=\emptyset$ and hence $P(B)=0$ if (say) the set $S_i$ is nonempty and does not depend on $i$.

The definition of $B$ has now been amended, but the desired result will still fail to hold in general. (It seems that you tacitly identify events with their indicators, and let us follow this convention, albeit not tacitly anymore.)

Indeed, suppose that for all $i=1,\dots,n$ we have $S_i=\{i\}$, so that $A_i=X_i$, $P(B)\le\sum_{i=1}^n P(A_i)=\mu$, and $\Delta=0$. Then nothing like the inequality $$ P(B)\ge e^{-\mu+\Delta} $$ can hold if $\mu$ is small.

  • $\begingroup$ I adjusted the definition like you suggested. If $S_i$ is non-empty and does not depend on $i$, it would seem that $\Delta$ would be large. As I mentioned, I am interested in the case where $\mu \gg \Delta$. $\endgroup$ Sep 5, 2021 at 15:45
  • $\begingroup$ @DavidHarris : I have now considered the adjusted definition of $B$ as well. Unfortunately, the answer is still negative. $\endgroup$ Sep 5, 2021 at 19:56
  • $\begingroup$ I realized that actually the bound should have the form $1 - e^{-\mu + \Delta}$. In your example, you would have $\Pr(B) = 1- \prod (1-p_i) \geq 1 - e^{-\mu}$, as desired. I apologize that I botched the original formula. $\endgroup$ Sep 5, 2021 at 21:09
  • 1
    $\begingroup$ @DavidHarris : Well, now, after the two edits, the question is quite different from the original one, is it not? $\endgroup$ Sep 6, 2021 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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