Ανισότητες Μπονφερρόνι

Στην θεωρία πιθανοτήτων, οι ανισότητες Μπονφερρόνι (αναφέρονται και ως ανισότητες Bonferroni) είναι άνω και κάτω φράγματα για την πιθανότητα της ένωσης $n$ γεγονότων. Για παράδειγμα, για $n=3$, δίνουν τα εξής φράγματα για οποιαδήποτε γεγονότα $A_{1}$, $A_{2}$, $A_{3}$:

$\Pr(A_{1}\cup A_{2}\cup A_{3})\leq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})$

$\Pr(A_{1}\cup A_{2}\cup A_{3})\geq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})-\Pr(A_{1}\cap A_{2})-\Pr(A_{1}\cap A_{3})-\Pr(A_{2}\cap A_{3})$

${\begin{aligned}\Pr(A_{1}\cup A_{2}\cup A_{3})&\leq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})-\Pr(A_{1}\cap A_{2})-\Pr(A_{1}\cap A_{3})-\Pr(A_{2}\cap A_{3})\\&\qquad +\Pr(A_{1}\cap A_{2}\cap A_{3})\end{aligned}}$

Οι συνεισφορές κάθε περιοχής στο διάγραμμα Βεν στο δεξί μέλος των τριών ανισοτήτων Μπονφερρόνι για τρία γεγονότα $A_{1},A_{2},A_{3}$. Στην πρώτη ανισότητα όλες οι περιοχές καλύπτονται τουλάχιστον μία φορά επομένως είναι άνω φράγμα. Στην δεύτερη ανισότητα, όλες καλύπτονται μία φορά εκτός από από μία περιοχή που συνεισφέρει αρνητικά, επομένως είναι κάτω φράγμα. Η τρίτη ανισότητα ισχύει ως ισότητα.

Στην γενική περίπτωση για οποιαδήποτε $n$ γεγονότα $A_{1},\ldots ,A_{n}$, για κάθε μονό $k$ (με $1\leq k\leq n$), ισχύει ότι

$\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\leq \sum _{j=1}^{k}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j}}),$

και για κάθε ζυγό $k$ (με $1\leq k\leq n$),

$\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\geq \sum _{j=1}^{k}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j}}),$

όπου ο συμβολισμός ${\textstyle \sum _{i_{1}<\ldots <i_{j}}}$ σημαίνει το άθροισμα για όλες τις δυνατές ακολουθίες από $j$ διαφορετικούς δείκτες $i_{1},\ldots i_{j}$ με τιμές στο σύνολο $\{1,\ldots ,n\}$.

Για $k=1$, λαμβάνουμε την ανισότητα Μπουλ και για $k=n$ ισχύει ως ισότητα από την αρχή εγκλεισμού-αποκλεισμού.

Απόδειξη

Για οποιοδήποτε $n$ και $k=1$, η ανισότητα προκύπτει από την ανισότητα Μπουλ, καθώς

$\Pr(A_{1}\cup \ldots \cup A_{n})\leq \sum _{i=1}^{n}\Pr(A_{i})$.

Ας υποθέσουμε ότι ισχύει για $n$ και $k$ και κάθε $n'\leq n$ και $k'\leq k$. Τότε θα αποδείξουμε ότι ισχύει για $n$ και $k+1$. Ξεκινάμε με το δεξί μέλος και απομονώνουμε τις ακολουθίες με $A_{i_{k+1}}=A_{n}$, έτσι ώστε

${\begin{aligned}&\sum _{j=1}^{k+1}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j}})\\&=\sum _{j=1}^{k+1}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}<n}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j}})+\sum _{j=2}^{k+1}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j-1}<n}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j-1}}\cap A_{n})+\Pr(A_{n})\\&=\underbrace {\sum _{j=1}^{k+1}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}<n}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j}})} _{X}-\underbrace {\sum _{j=1}^{k}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}<n}\Pr((A_{i_{1}}\cap A_{n})\cap \ldots \cap (A_{i_{j}}\cap A_{n}))} _{Y}+\Pr(A_{n})\end{aligned}}$

(1)

Θα διαχωρίσουμε τις δύο περιπτώσεις για $k+1$ μονό και ζυγό (αλλά θα δούμε ότι είναι πολύ παρόμοιες).

(Μονό $k+1$) Για μονά $k+1$, το $X$ είναι το δεξί μέλος της ανισότητας Μπονφερρόνι για το μονό $k$ και για τα $n-1$ γεγονότα $A_{1},\ldots ,A_{n-1}$. Επομένως από την επαγωγική υπόθεση

$X\geq \Pr \left(\bigcup _{i=1}^{n-1}A_{i}\right)$.

Για το $Y$, πάλι από την επαγωγική υπόθεση για το ζυγό $k$ και για τα $n-1$ γεγονότα $A_{1}\cap A_{n},\ldots A_{n-1}\cap A_{n}$,ισχύει ότι

$Y\leq \Pr \left(\bigcup _{i=1}^{n-1}(A_{i}\cap A_{n})\right)=\Pr \left(A_{n}\cap \bigcup _{i=1}^{n-1}A_{i}\right)$

Επιστρέφοντας στην (1), έχουμε ότι

$\sum _{j=1}^{k+1}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j}})\geq \Pr \left(\bigcup _{i=1}^{n-1}A_{i}\right)-\Pr \left(A_{n}\cap \bigcup _{i=1}^{n-1}A_{i}\right)+\Pr(A_{n})=\Pr \left(\bigcup _{i=1}^{n}A_{i}\right),$

χρησιμοποιώντας ότι $\Pr(C\cup D)=\Pr(C)+\Pr(D)-\Pr(C\cup D)$ για $\textstyle C=\bigcup _{i=1}^{n-1}A_{i}$ και $D=A_{n}$.

(Ζυγό $k+1$) Αντίστοιχα, για ζυγά $k+1$, οι ανισότητες για τα $X$ και $Y$ είναι αντεστραμμένες, δηλαδή

$X\leq \Pr \left(\bigcup _{i=1}^{n-1}A_{i}\right)$ και $Y\geq \Pr \left(A_{n}\cap \bigcup _{i=1}^{n-1}A_{i}\right)$.

Επομένως, από την (1)

$\sum _{j=1}^{k+1}(-1)^{j+1}\sum _{i_{1}<\ldots <i_{j}}\Pr(A_{i_{1}}\cap \ldots \cap A_{i_{j}})\leq \Pr \left(\bigcup _{i=1}^{n-1}A_{i}\right)-\Pr \left(A_{n}\cap \bigcup _{i=1}^{n-1}A_{i}\right)+\Pr(A_{n})=\Pr \left(\bigcup _{i=1}^{n}A_{i}\right).$

Επομένως η ανισότητα ισχύει και για $n$ και $k+1$, άρα για όλα τα $n,k$ από την μέθοδο της μαθηματικής επαγωγής.

Ειδικές περιπτώσεις

Για $n=2$,

$\Pr(A_{1}\cup A_{2})\leq \Pr(A_{1})+\Pr(A_{2})$,

$\Pr(A_{1}\cup A_{2})\geq \Pr(A_{1})+\Pr(A_{2})-\Pr(A_{1}\cap A_{2})$.

Για $n=3$,

$\Pr(A_{1}\cup A_{2}\cup A_{3})\leq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})$,

$\Pr(A_{1}\cup A_{2}\cup A_{3})\geq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})-\Pr(A_{1}\cap A_{2})-\Pr(A_{1}\cap A_{3})-\Pr(A_{2}\cap A_{3})$,

$\Pr(A_{1}\cup A_{2}\cup A_{3})\leq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})-\Pr(A_{1}\cap A_{2})-\Pr(A_{1}\cap A_{3})-\Pr(A_{2}\cap A_{3})+\Pr(A_{1}\cap A_{2}\cap A_{3})$.

Για $n=4$,

$\Pr(A_{1}\cup A_{2}\cup A_{3}\cup A_{4})\leq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})+\Pr(A_{4})$,

${\begin{aligned}\Pr(A_{1}\cup A_{2}\cup A_{3}\cup A_{4})&\geq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})+\Pr(A_{4})\\&\qquad -\Pr(A_{1}\cap A_{2})-\Pr(A_{1}\cap A_{3})-\Pr(A_{1}\cap A_{4})-\Pr(A_{2}\cap A_{3})-\Pr(A_{2}\cap A_{4})-\Pr(A_{3}\cap A_{4}),\\\end{aligned}}$

${\begin{aligned}\Pr(A_{1}\cup A_{2}\cup A_{3}\cup A_{4})&\leq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})+\Pr(A_{4})\\&\qquad -\Pr(A_{1}\cap A_{2})-\Pr(A_{1}\cap A_{3})-\Pr(A_{1}\cap A_{4})-\Pr(A_{2}\cap A_{3})-\Pr(A_{2}\cap A_{4})-\Pr(A_{3}\cap A_{4})\\&\qquad +\Pr(A_{1}\cap A_{2}\cap A_{3})+\Pr(A_{1}\cap A_{2}\cap A_{4})+\Pr(A_{1}\cap A_{3}\cap A_{4})+\Pr(A_{2}\cap A_{3}\cap A_{4}),\end{aligned}}$

${\begin{aligned}\Pr(A_{1}\cup A_{2}\cup A_{3}\cup A_{4})&\geq \Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})+\Pr(A_{4})\\&\qquad -\Pr(A_{1}\cap A_{2})-\Pr(A_{1}\cap A_{3})-\Pr(A_{1}\cap A_{4})-\Pr(A_{2}\cap A_{3})-\Pr(A_{2}\cap A_{4})-\Pr(A_{3}\cap A_{4})\\&\qquad +\Pr(A_{1}\cap A_{2}\cap A_{3})+\Pr(A_{1}\cap A_{2}\cap A_{4})+\Pr(A_{1}\cap A_{3}\cap A_{4})+\Pr(A_{2}\cap A_{3}\cap A_{4})\\&\qquad -\Pr(A_{1}\cap A_{2}\cap A_{3}\cap A_{4}).\end{aligned}}$

Οι συνεισφορές κάθε περιοχής στο διάγραμμα Βεν στο δεξί μέλος των τεσσάρων ανισοτήτων Μπονφερρόνι για τέσσερα γεγονότα $A_{1},A_{2},A_{3},A_{4}$. Προκύπτει ότι η πρώτη και η τρίτη ανισότητα είναι άνω φράγματα, ενώ η δεύτερη και η τέταρτη είναι κάτω φράγματα.

Για γενικό $n$ και $k=2$, έχουμε την ανισότητα Μπουλ,

$\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\leq \sum _{i=1}^{n}\Pr(A_{i}).$

Για γενικό $n$ και $k=2$, έχουμε

$\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\geq \sum _{i=1}^{n}\Pr(A_{i})-\sum _{i=1}^{n}\sum _{j=i+1}^{n}\Pr(A_{i}\cap A_{j}).$

Ιστορία

Οι ανισότητες αυτές αναφέρονται στην εργασία του Κάρολου Μπονφερρόνι το 1936 ως γενίκευση της ανισότητας Μπουλ, ενώ της είχε χρησιμοποιήσει νωρίτερα το 1935 σε μία εφαρμογή για ασφάλειες ζωής.

Δείτε επίσης

• Ανισότητα Μπουλ
• Ανισότητα Τσουνγκ-Έρντος