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

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

Στην γενική περίπτωση για οποιαδήποτε $n$ γεγονότα $A_{1}, \dots, A_{n}$ , για κάθε μονό $k$ (με $1 \leq k \leq n$ ), ισχύει ότι^[1]Πρότυπο:Rp^[2]Πρότυπο:Rp

\Pr (⋃_{i = 1}^{n} A_{i}) \leq \sum_{j = 1}^{k} (- 1)^{j + 1} \sum_{i_{1} < \dots < i_{j}} \Pr (A_{i_{1}} \cap \dots \cap A_{i_{j}}),

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

\Pr (⋃_{i = 1}^{n} A_{i}) \geq \sum_{j = 1}^{k} (- 1)^{j + 1} \sum_{i_{1} < \dots < i_{j}} \Pr (A_{i_{1}} \cap \dots \cap A_{i_{j}}),

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

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

Απόδειξη

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

\Pr (A_{1} \cup \dots \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}$ , έτσι ώστε

Πρότυπο:NumBlk

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

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

X \geq \Pr (⋃_{i = 1}^{n - 1} A_{i})

.

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

Y \leq \Pr (⋃_{i = 1}^{n - 1} (A_{i} \cap A_{n})) = \Pr (A_{n} \cap ⋃_{i = 1}^{n - 1} A_{i})

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

\sum_{j = 1}^{k + 1} (- 1)^{j + 1} \sum_{i_{1} < \dots < i_{j}} \Pr (A_{i_{1}} \cap \dots \cap A_{i_{j}}) \geq \Pr (⋃_{i = 1}^{n - 1} A_{i}) - \Pr (A_{n} \cap ⋃_{i = 1}^{n - 1} A_{i}) + \Pr (A_{n}) = \Pr (⋃_{i = 1}^{n} A_{i}),

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

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

X \leq \Pr (⋃_{i = 1}^{n - 1} A_{i})

και

Y \geq \Pr (A_{n} \cap ⋃_{i = 1}^{n - 1} A_{i})

.

Επομένως, από την (Πρότυπο:EquationNote)

\sum_{j = 1}^{k + 1} (- 1)^{j + 1} \sum_{i_{1} < \dots < i_{j}} \Pr (A_{i_{1}} \cap \dots \cap A_{i_{j}}) \leq \Pr (⋃_{i = 1}^{n - 1} A_{i}) - \Pr (A_{n} \cap ⋃_{i = 1}^{n - 1} A_{i}) + \Pr (A_{n}) = \Pr (⋃_{i = 1}^{n} A_{i}) .

Επομένως η ανισότητα ισχύει και για $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{matrix} \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}) \\ - \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{matrix}

\begin{matrix} \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}) \\ - \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}) \\ + \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{matrix}

\begin{matrix} \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}) \\ - \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}) \\ + \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}) \\ - \Pr (A_{1} \cap A_{2} \cap A_{3} \cap A_{4}) . \end{matrix}

Αρχείο:Ανισότητα Μπονφερρόνι για 4 γεγονότα.svg

Οι συνεισφορές κάθε περιοχής στο διάγραμμα Βεν στο δεξί μέλος των τεσσάρων ανισοτήτων Μπονφερρόνι για τέσσερα γεγονότα

A_{1}, A_{2}, A_{3}, A_{4}

. Προκύπτει ότι η πρώτη και η τρίτη ανισότητα είναι άνω φράγματα, ενώ η δεύτερη και η τέταρτη είναι κάτω φράγματα.

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

\Pr (⋃_{i = 1}^{n} A_{i}) \leq \sum_{i = 1}^{n} \Pr (A_{i}) .

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

\Pr (⋃_{i = 1}^{n} A_{i}) \geq \sum_{i = 1}^{n} \Pr (A_{i}) - \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \Pr (A_{i} \cap A_{j}) .

Ιστορία

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

Δείτε επίσης

Παραπομπές

[1] Πρότυπο:Cite book

[2] Πρότυπο:Cite book

[3] Πρότυπο:Cite journal

[4] Πρότυπο:Cite journal

[1]

[2]

[3]

[4]

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

Περιεχόμενα

Απόδειξη

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

Ιστορία

Δείτε επίσης

Παραπομπές

Μενού πλοήγησης

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

Απόδειξη

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

Ιστορία

Δείτε επίσης

Παραπομπές

Μενού πλοήγησης

Αναζήτηση