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

Στην θεωρία πιθανοτήτων, οι **ανισότητες Μπονφερρόνι** (αναφέρονται και ως **ανισότητες 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{align}\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{align}

Στην γενική περίπτωση για οποιαδήποτε 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 
και για κάθε ζυγό 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 
όπου ο συμβολισμός \sum_{i_1  σημαίνει το άθροισμα για όλες τις δυνατές ακολουθίες από 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, έτσι ώστε
: \cap A_n) + \Pr(A_n) \\
 & = \underbrace{\sum_{j = 1}^{k+1} (-1)^{j + 1} \sum_{i_1 |}}

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

(**Μονό <math>k+1</math>**) Για μονά 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)
Επιστρέφοντας στην (), έχουμε ότι
:
\sum_{j = 1}^{k+1} (-1)^{j + 1} \sum_{i_1 
χρησιμοποιώντας ότι \Pr(C \cup D) = \Pr(C) + \Pr(D) - \Pr(C \cup D) για \textstyle C = \bigcup_{i = 1}^{n-1} A_i και D = A_n.

(**Ζυγό <math>k+1</math>**) Αντίστοιχα, για ζυγά 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). 
Επομένως, από την ()
:
\sum_{j = 1}^{k+1} (-1)^{j + 1} \sum_{i_1 
Επομένως η ανισότητα ισχύει και για 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{align}
\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{align}
:\begin{align}
\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{align}
:\begin{align}
\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{align}

Για γενικό 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 σε μία εφαρμογή για ασφάλειες ζωής.

## Δείτε επίσης
* Ανισότητα Μπουλ
* Ανισότητα Τσουνγκ-Έρντος

## Παραπομπές


Κατηγορία:Ανισότητες
Κατηγορία:Θεωρία πιθανοτήτων