Improved Bounds on the Probability of a Union and on the Number of Events that Occur
Ilan Adler, Richard M. Karp and Sheldon M. Ross · 2025
Read Improved Bounds on the Probability of a Union and on the Number of Events that Occur by Ilan Adler, Richard M. Karp and Sheldon M. Ross (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12243.txt.
Introduction
Ilan Adler, Richard Karp, and Sheldon Ross sharpen classic bounds on the chance that at least some of a set of events will occur, in a 2025 paper. The old bounds come from sums that add and cut terms in turn. They date back to work in the eighteen hundreds by Boole.
The trio pin down the exact flaw in each old sum. From that, they give a plain proof of the best bounds of one form. They also add new bounds that use more of the known joint odds. The new bounds are often tighter than the old ones, while they stay simple to state and use.
Catalog record
| CREATOR | Ilan Adler, Richard M. Karp and Sheldon M. Ross |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 14 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-12243
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved Bounds on the Probability of a Union and on the Number of Events that Occur Ilan Adler, Richard M. Karp and Sheldon M. Ross Abstract Let A 1 , A 2 , … , A n A_{1},A_{2},\ldots,A_{n} be events in a sample space. Given the probability of the intersection of each collection of up to k + 1 k+1 of these events, what can we say about the probability that at least r r of the events occur? This question dates back to Boole in the 19th century, and it is well known that the odd partial sums of the Inclusion- Exclusion formula provide upper bounds, while the even partial sums provide lower bounds. We give a combinatorial characterization of the error in these bounds and use it to derive a very simple proof of the strongest possible bounds of a certain form, as well as a couple of improved bounds. The new bounds use more information than the classical Bonferroni-type inequalities, and are often sharper. Keywords: Bonferroni-type inequalities 1 Introduction Let A_{1},A_{2},\ldots,A_{n} be events in a probability space and let X denote the number of these events that occur. We are interested in obtaining bounds on P(X\geq r) , for r=1,2,\ldots,n , based on knowledge of the probabilities of all s-way intersections of the events, for each s=1,2,\ldots,k+1, for some k<n . Let S_{j} be the sum of the probabilities of all j -way intersections, for 1\leq j\leq n. That is, S_{j}=\sum_{1\leq i_{1}<i_{2}<\cdots<i_{j}\leq n}P(A_{i_{1}}A_{i_{2}}\cdots A_{i_{j}}). The Principle of Inclusion and Exclusion states that P(X\geq r)=\sum_{j=r}^{n}(-1)^{r+j}{j-1\choose r-1}S_{j} It is also known that truncations of the preceding expression give upper and lower bounds on P(X\geq r) : if i is odd then \sum_{j=r}^{r+i}(-1)^{r+j}{j-1\choose r-1}S_{j}\leq P(X\geq r)\leq\sum_{j=r}^{r+i+1}(-1)^{r+j}{j-1\choose r-1}S_{j} (1) Many improvements of this bound have been given, and are generically called Bonferroni-type inequalities. In the next section we recall how the preceding inequalities can be derived from an algebraic identity. Our strategy in this note is to follow a similar line of reasoning, generalizing the algebraic identity to obtain some interesting expressions for P(X\geq r), and then derive bounds from those expressions that are stronger or more general than the bounds previously known. Whereas our strongest bounds are expressed in terms of the individual s -fold intersections of events, and hence exploit more information than the typical Bonferroni-type inequalities, which depend only on the coarser information given by the quantities S_{j},j=1,\ldots,k+1, we also give bounds just depending on the S_{j}. Other bounds based on the same information as ours are given in [ 1 ] and [ 3 ] as well as in the references therein. Notational Conventions. For integers s,t, we let {t\choose s}=0 if either \min(s,t)<0 or s>t. Otherwise {t\choose s}=\frac{t!}{s!(t-s)!}. Also, for any event B, we let I\{B\} be the indicator variable of the event B , equal to 1 if B ocurs and to 0 otherwise. 2 Basic Expressions for the Distribution of X Lemma 1 For all integers r>0,m\geq 0 I\{m\geq r\}=\sum_{j=r}^{m}(-1)^{r+j}{j-1\choose r-1}{m\choose j} (2) Proof: Note that both sides of Equation (\ref{eq:id1}) equal 0 when m<r. The proof when m\geq r is by induction on r . The result follows when r=1 since for m\geq 1 the identity \sum_{j=0}^{m}{m\choose j}(-1)^{j}=(1-1)^{m}=0 implies that 1=\sum_{j=1}^{m}{m\choose j}(-1)^{j+1}. Assuming the result for r , we have \displaystyle\sum_{j=r+1}^{m}(-1)^{r+j+1}{j-1\choose r}{m\choose j} \displaystyle= \displaystyle\sum_{j=r+1}^{m}(-1)^{r+j+1}[{j\choose r}-{j-1\choose r-1}]{m\choose j} (3) \displaystyle= \displaystyle\sum_{j=r+1}^{m}(-1)^{r+j+1}{j\choose r}{m\choose j}+\sum_{j=r+1}^{m}(-1)^{r+j}{j-1\choose r-1}{m\choose j} \displaystyle= \displaystyle\sum_{j=r+1}^{m}(-1)^{r+j+1}{m\choose r}{m-r\choose j-r}+1-{m\choose r} \displaystyle= \displaystyle{m\choose r}\sum_{k=1}^{m-r}(-1)^{k+1}{m-r\choose k}+1-{m\choose r} \displaystyle= \displaystyle{m\choose r}+1-{m\choose r}=1 where Equation ( 3 ) followed from the induction hypothesis. Theorem 1 With X being the number of the events A_{1},\ldots,A_{n} that occur, P(X\geq r)=\sum_{j=r}^{n}(-1)^{r+j}{j-1\choose r-1}S_{j} Proof: Because Lemma 1 holds for all m, it follows that, I\{X\geq r\}=\sum_{j=r}^{X}(-1)^{r+j}{j-1\choose r-1}{X\choose j}=\sum_{j=r}^{n}(-1)^{r+j}{j-1\choose r-1}{X\choose j} where the second equality follows because X\leq n and {X\choose j}=0 when j>X. Taking expectations, and using that E[{X\choose j}]=S_{j} yields the result. Lemma 2 For all nonnegative integers m,k,r such that k\geq r , \sum_{j=k+1}^{m}(-1)^{j}{j-1\choose r-1}{m\choose j}=(-1)^{k+1}\sum_{i=1}^{r}{k-i\choose r-i}{m-i\choose k-i+1} Proof: The result holds if m<k since both sides equal 0 in this case. Hence, we need to prove the result when m\geq k\geq r. The proof is by induction on m . As it is immediate for m=k assume it is true for m-1 . Then, with \;H(m,k,r)=\sum_{j=k+1}^{m}(-1)^{j}{j-1\choose r-1}{m\choose j}, \displaystyle H(m,k,r) \displaystyle= \displaystyle\sum_{j=k+1}^{m}(-1)^{j}{j-1\choose r-1}[{m-1\choose j-1}+{m-1\choose j}] \displaystyle= \displaystyle\sum_{j=k+1}^{m}(-1)^{j}{j-1\choose r-1}{m-1\choose j-1}+\sum_{j=k+1}^{m-1}(-1)^{j}{j-1\choose r-1}{m-1\choose j} \displaystyle= \displaystyle\sum_{j=k}^{m-1}(-1)^{j+1}{j\choose r-1}{m-1\choose j}-\sum_{j=k+1}^{m-1}(-1)^{j+1}{j-1\choose r-1}{m-1\choose j} \displaystyle= \displaystyle\sum_{j=k+1}^{m-1}(-1)^{j+1}[{j\choose r-1}-{j-1\choose r-1}]{m-1\choose j}\;+\;(-1)^{k+1}{k\choose r-1}{m-1\choose k} \displaystyle= \displaystyle\sum_{j=k+1}^{m-1}(-1)^{j+1}{j-1\choose r-2}{m-1\choose j}\;+\;(-1)^{k+1}{k\choose r-1}{m-1\choose k} \displaystyle= \displaystyle\sum_{j=k+1}^{m-1}(-1)^{j+1}{j-1\choose r-2}{m-1\choose j}\;+\;(-1)^{k+1}[{k-1\choose r-1}+{k-1\choose r-2}]{m-1\choose k} \displaystyle= \displaystyle\sum_{j=k}^{m-1}(-1)^{j+1}{j-1\choose r-2}{m-1\choose j}\;+\;(-1)^{k+1}{k-1\choose r-1}{m-1\choose k} \displaystyle= \displaystyle-H(m-1,k-1,r-1)\;+\;(-1)^{k+1}{k-1\choose r-1}{m-1\choose k} \displaystyle= \displaystyle(-1)^{k+1}\sum_{i=1}^{r-1}{k-1-i\choose r-1-i}{m-1-i\choose k-1-i+1}\;+\;(-1)^{k+1}{k-1\choose r-1}{m-1\choose k} \displaystyle= \displaystyle(-1)^{k+1}\sum_{j=2}^{r}{k-j\choose r-j}{m-j\choose k-j+1}\;+\;(-1)^{k+1}{k-1\choose r-1}{m-1\choose k} \displaystyle= \displaystyle(-1)^{k+1}\sum_{j=1}^{r}{k-j\choose r-j}{m-j\choose k-j+1} where the induction hypothesis was used to evaluate H(m-1,k-1,r-1).\quad\rule{5.69054pt}{5.69054pt} Theorem 2 For k\geq r, P(X\geq r)=\sum_{j=r}^{k}(-1)^{r+j}{j-1\choose r-1}S_{j}+(-1)^{r+k+1}\sum_{i=1}^{r}{k-i\choose r-i}E[{X-i\choose k-i+1}] Proof: It follows from Lemmas 1 and 2 that for k\geq r I\{X\geq r\}=\sum_{j=r}^{k}(-1)^{r+j}{j-1\choose r-1}{X\choose j}+(-1)^{r+k+1}\sum_{i=1}^{r}{k-i\choose r-i}{X-i\choose k-i+1} Taking expectations now yields the result. Remark: The classical Bonferroni type inequalities ( 1 ) follow from Theorem 2 upon observing that \,\sum_{i=1}^{r}{k-i\choose r-i}E[{X-i\choose k-i+1}]\geq 0. 3 Bounds on P(X\geq r) Lemma 3 \;E[{X-i\choose k+1-i}]\geq\frac{{k+1\choose i}}{{n\choose i}}S_{k+1} Proof: Because X\leq n and {j-i\choose k+1-i}/{j\choose k+1} is monotonically decreasing in j , it follows that {X-i\choose k+1-i}\geq{X\choose k+1}\frac{{n-i\choose k+1-i}}{{n\choose k+1}}={X\choose k+1}\frac{{k+1\choose i}}{{n\choose i}} Taking expectations yields the result. Theorem 3 P(X\geq r)\geq\sum_{j=r}^{k}(-1)^{r+j}{j-1\choose r-1}S_{j}+\sum_{i=1}^{r}{k-i\choose r-i}\frac{{k+1\choose i}}{{n\choose i}}S_{k+1},\quad r+k\;\mbox{ odd} P(X\geq r)\leq\sum_{j=r}^{k}(-1)^{r+j}{j-1\choose r-1}S_{j}-\sum_{i=1}^{r}{k-i\choose r-i}\frac{{k+1\choose i}}{{n\choose i}}S_{k+1},\quad r+k\;\mbox{ even} Proof: Immediate from Theorem 2 and Lemma 3 . Remarks: • Note (by considering the case P(X=n)=1 ) that \alpha=\sum_{i=1}^{r}{k-i\choose r-i}\frac{{k+1\choose i}}{{n\choose i}} is the most stringent among all the bounds of the type \sum_{j=r}^{k}(-1)^{r+j}{j-1\choose r-1}S_{j}+(-1)^{r+k+1}\alpha S_{k+1} • In his book, Galambos [ 1 ] presents a result (proved first in [ 2 ] ) that is similar to Theorem 3, except that \sum_{i=1}^{r}{k-i\choose r-i}\frac{{k+1\choose i}}{{n\choose i}} is replaced by \frac{(\sum_{j=0}^{k-r}(-1)^{j}{r+j-1\choose r-1}{n\choose r+j}-1)}{{n\choose k+1}} . However, these terms are actually identical, as can be easily shown via Lemmas 1 , 2 , and 3 . The proof presented here, though, is much simpler. Considering Theorem 2 , it is clear that obtaining a lower bound for E\left[\binom{X-i}{k+1-i}\right] can provide upper and lower bounds for P(X\geq r) . So far, we have derived bounds based solely on the coarse information provided by the quantities S_{j},j=1,\ldots,k+1, Next, we refine these bounds by expressing them in terms of the individual s-fold intersections of events, leading to stronger bounds. Let {\cal{S}}=\{A_{i_{1}},\ldots,A_{i_{x}}\},i_{1}<\ldots<i_{x}, be the set of events that occur, and note that for i\leq k\leq x-1 , {x-i\choose k+1-i} is the number of k+1-i sized subsets in . \{A_{i_{1}},\ldots,A_{i_{x}-i}\} . Now, for r_{1}<\ldots<r_{k+1-i} , \{A_{r_{1}},\ldots,A_{r_{k+1-i}}\} is such a subset if all of the events A_{r_{1}},\ldots,A_{r_{k+1-i}} occur as does at least i events A_{t_{1}},\ldots,A_{t_{i}} , where r_{k+1-i}<t_{j}\text{ for }j=1,\ldots,i . Hence, defining T(r_{1},\ldots,r_{k+1-i})=\{(t_{1},\ldots,t_{i}):r_{k+1-i}<t_{1}<\cdots<t_{i}\} we obtain the expectation bound \displaystyle E\left[\binom{X-i}{k+1-i}\right] \displaystyle=\sum_{\begin{subarray}{c}r_{1}<\cdots<r_{k+1-i}\end{subarray}}P\left(\bigcup_{(t_{1},\ldots,t_{i})\in T(r_{1},\ldots,r_{k+1-i})}A_{r_{1}}\cdots A_{r_{k+1-i}}A_{t_{1}}\cdots A_{t_{i}}\right) \displaystyle\geq\sum_{\begin{subarray}{c}r_{1}<\cdots<r_{k+1-i}\end{subarray}}\max_{(t_{1},\ldots,t_{i})\in T(r_{1},\ldots,r_{k+1-i})}P(A_{r_{1}}\cdots A_{r_{k+1-i}}A_{t_{1}}\cdots A_{t_{i}}). (4) The preceding yields Theorem 4 {P(X\geq r)\geq\sum_{j=r}^{k}(-1)^{r+j}{j-1\choose r-1}S_{j}+\sum_{i=1}^{r}{k-i\choose r-i}\sum_{r_{1}<\cdots<r_{k+1-i}}\max_{(t_{1}\ldots,t_{i})\in T(r_{1},\ldots,r_{k+1-i})}P(A_{r_{1}}\cdots A_{r_{k+1-i}}A_{t_{1}}\cdots A_{t_{i}})}\;r+k\mbox{ odd} {P(X\geq r)\leq\sum_{j=r}^{k}(-1)^{r+j}{j-1\choose r-1}S_{j}-\sum_{i=1}^{r}{k-i\choose r-i}\sum_{r_{1}<\cdots<r_{k+1-i}}\max_{(t_{1}\ldots,t_{i})\in T(r_{1},\ldots,r_{k+1-i})}P(A_{r_{1}}\cdots A_{r_{k+1-i}}A_{t_{1}}\cdots A_{t_{i}})}\;r+k\mbox{ even} Proof: Immediate fromTheorem 2 and ( 4 ) .\quad\rule{5.69054pt}{5.69054pt} 3.1 An Improved Bound of P(X\geq 1) The case of P(X\geq 1) is of particular interest, as there are applications in which the focus is on the probability of at