Sign up ×

Let $A_1,A_2,\dots,A_n$ be events on a probability space. For $0 \leq k \leq n$ let \begin{equation*} S_k=\sum_{1 \le {i_1}<{i_2}<\cdots<{i_k} \leq n} P(A_{i_1} \cap \cdots \cap A_{i_k}). \end{equation*} This is the $k$-th binomial moment of the number $m_n$ of those $A$s which occur.

Question: What bounds are known for $S_k$ in terms of $S_0,S_1,\dots,S_{k-1}$?

Note: Bonferroni-type inequalities give bounds for $P(m_n \geq t)$ in terms of linear combinations of the $S_i$ (for example Galambos, "Bonferroni Inequalities", Annals of Probability, Vol. 5 (1977), 577--581). It is possible to use these to give bounds for $S_k$ in terms of $S_0,S_1,\dots,S_{k-1}$ and $P(m_m \geq t)$ and use the fact that $0 \leq P(m_n \geq t) \leq 1$ to deduce bounds on $S_k$ in terms of $S_0,S_1,\dots,S_{k-1}$. It seems to me however that a lot is wasted that way. I am wondering if there are known ways of obtaining sharper bounds.

share|cite|improve this question

1 Answer 1

There are better methods using tree and graphs, for example, "Probability Bounds with Cherry Trees" in Math. of Oper. Research in 2001.

share|cite|improve this answer
Thanks! This paper looks interesting; I'll check it out. – Siksek Mar 3 '13 at 22:12

Your Answer


