# Bounds on the probability of k-of-n events in terms of bounds on single and pairwise probabilities

Let $A_1,\dotsc,A_n$ be events in a probability space, and let $N = \sum_{i=1}^n \mathbf{1}_{A_i}$ be the random number of events that occur. For a fixed value $k \in \{1,\dotsc,n\}$, what can be said about the quantity $$p_k = \mathbb{P}[ N \ge k ]$$ if all that is known is the number $n$ and upper bounds on the single probabilities $\mathbb{P}[A_i]$ and pairwise probabilities $\mathbb{P}[A_i \cap A_j]$?

A simple approach is Chebyshev's inequality, since the first two moments of $N$ can be expressed in terms of these probabilities. Focusing for simplicity on the symmetric case ($\mathbb{P}[A_i]$ is the same for all $i$, $\mathbb{P}[A_i \cap A_j]$ is the same for all $i\ne j$), a simple calculation gives $$\mathbb{E}[N] = n \mathbb{P}[A_1]$$ $$\mathbb{E}[N^2] = n \mathbb{P}[A_1] + (n^2 - n) \mathbb{P}[A_1 \cap A_2].$$ However, we then have $\mathrm{Var}[N] = \mathbb{E}[N^2] - \mathbb{E}[N]^2$, so it appears that getting an upper bound on $p_k$ via this approach requires an upper bound on $\mathbb{E}[N^2]$ and both upper and lower bounds on $\mathbb{E}[N]$, the latter being used to upper bound the variance (the trivial upper bound of $\mathbb{E}[N^2]$ does not suffices for my purposes).

What if we only have have access to upper bounds? In particular, can we obtain a good upper bound on $p_k$ if we only know that $\mathbb{P}[A_i] \le \alpha$ and $\mathbb{P}[A_i \cap A_j] \le \alpha^2$ for some $\alpha > 0$?

In the case that $k=1$, $p_k$ is simply the probability of a union of events, so we may use tools such as the union bound, the inclusion-exclusion principle, and de Caen's bound (http://dl.acm.org/citation.cfm?id=253949) to get useful upper and lower bounds. It is unclear whether these have analogs for higher values of $k$.

• It sounds like you could really use something akin to positive/negative association such as $P(A_i\cap A_j)\leq \geq P(A_i)P(A_j)$. Do you happen to know if these hold on some large subset of index pairs? Jun 23, 2015 at 19:15
• I expect that I should have P[A_i and A_j] > P(A_i)P(A_j) in my setting - though it might not be easy to prove. Jun 24, 2015 at 15:09

It seems we can give a simple bound given upper bounds in the finite case. You can probably extend it. (The computation is trivial, but it seems to give an intuition that this is close to tight.. edit: well, if $\alpha$ is reasonably small. See the bottom of the post..)
Denote by d the maximum size of an intersection $A_i \cap A_j$. (Note $\alpha^{2}=\frac{d}{\Omega}$).
We can write a matrix $(a_{i,j})$ s.t. $a_{i,j}=\left|\{x\in \Omega \mid x\in A_i \cap A_j\}\right|$, i.e. the entries outside the diagonal are all at most d.
Now suppose there is some $x\in\Omega$ in the intersection of some k of the $A_i$. This x is already a $k\times k$ submatrix of ones "spoken for" - it is an element in each of ${k \choose 2}$ intersections of the events, and it consists of $2{k \choose 2}$ off-diagonal ones out of $2d{n \choose 2}$ we can fill. So we can have at most $\frac{dn(n-1)}{k(k-1)}$ such elements of $\Omega$, i.e. $\frac{n(n-1)}{k(k-1)}\alpha^2$ is an upper bound on the probability of k events occuring together.
(later addition: as $d$ and $|\Omega|$ grow, the upper bound becomes easier to attain by, for example, adding an appropriately-sized part of $\Omega$ to all k-subsets of the $A_i$. This is where a relation between $\alpha$,$n$,$k$ becomes relevant - if $\alpha\le\frac{k-1}{n-k+1}$ no diagonal element of the aforementioned matrix will receive too high a value in this way.. if these are not entirely insufficient bounds I can post the envelope calculations.)