Ανισότητα Μπουλ

Στην θεωρία πιθανοτήτων, η ανισότητα Μπουλ ή ιδιότητα της υποπροσθετικότητας (αναφέρεται και ως ανισότητα Boole) λέει ότι για ένα σύνολο από γεγονότα, η πιθανότητα να συμβεί τουλάχιστον ένα από αυτά είναι το πολύ όσο το άθροισμα της πιθανότητας να συμβεί το κάθε γεγονός ξεχωριστά. Πιο συγκεκριμένα, για κάθε $n$ γεγονότα $A_{1}, \dots, A_{n}$ , ισχύει ότι^[1]Πρότυπο:Rp^[2]Πρότυπο:Rp^[3]Πρότυπο:Rp^[4]^[5]Πρότυπο:Rp

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

Πιο γενικά, για κάθε αριθμήσιμο σύνολο γεγονότων $A_{1}, A_{2}, \dots$ ισχύει ότι

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

Αποδείξεις

Περίπτωση n=2

Για την περίπτωση $n = 2$ γεγονότων, θέλουμε να δείξουμε ότι

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

Από την ταυτότητα για την ένωση δύο γεγονότων έχουμε ότι

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

Επειδή, η πιθανότητα $\Pr (A_{1} \cap A_{2}) \geq 0$ , ισχύει ότι

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

που συνεπάγεται ότι

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

το οποίο είναι και το ζητούμενο.

Για κάθε n (μαθηματική επαγωγή)

Θα αποδείξουμε με την χρήση της μαθηματικής επαγωγής ότι ισχύει για οποιαδήποτε $n \geq 1$ στο πλήθος γεγονότα.

Βασική περίπτωση: Για $n = 1$ , η ανισότητα ισχύει ως ισότητα για κάθε γεγονός $A_{1}$ , δηλαδή $\Pr (A_{1}) \leq \Pr (A_{1})$ .

Επαγωγικό βήμα: Θεωρούμε ότι ισχύει για $n = k$ γεγονότα. Θα αποδείξουμε ότι ισχύει για $n = k + 1$ γεγονότα $A_{1}, \dots, A_{k + 1}$ . Ξεκινάμε με το αριστερό μέλος,

\Pr (⋃_{i = 1}^{k + 1} A_{i}) = \Pr (⋃_{i = 1}^{k} A_{i} \cup A_{k + 1}) \leq \Pr (⋃_{i = 1}^{k} A_{i}) + \Pr (A_{k + 1}),

από την παραπάνω περίπτωση για $n = 2$ . Χρησιμοποιώντας την επαγωγική υπόθεση για τα γεγονότα $A_{1}, \dots, A_{k}$ έχουμε ότι

\leq \sum_{i = 1}^{k} \Pr (A_{i}) + \Pr (A_{k + 1})

= \sum_{i = 1}^{k + 1} \Pr (A_{i}) .

Επομένως, ισχύει και για $n = k + 1$ και συνεπώς για κάθε $n \in ℕ_{+}$ .

Για κάθε αριθμήσιμο πλήθος

Η παραπάνω απόδειξη ισχύει για πεπερασμένο πλήθος γεγονότων. Τώρα θα αποδείξουμε την ανισότητα για κάθε αριθμήσιμο πλήθος γεγονότων $A_{1}, A_{2}, \dots$ . Ορίζουμε τα γεγονότα $B_{1}, B_{2}, \dots$ ως εξής:

B_{i} = {\begin{matrix} A_{1} & αν i = 1 \\ A_{i} ∖ ⋃_{j = 1}^{i - 1} A_{j} & διαφορετικά, \end{matrix}

έτσι ώστε να είναι ανεξάρτητα $B_{i} \cap B_{j} = \emptyset$ για $i \neq j$ και $B_{i} \subseteq A_{i}$ . Συνεπώς, από το αξίωμα για την πιθανότητα ανεξάρτητων γεγονότων

\Pr (⋃_{i = 1}^{\infty} A_{i}) = \Pr (⋃_{i = 1}^{\infty} B_{i}) = \sum_{i = 1}^{\infty} \Pr (B_{i}) \leq \sum_{i = 1}^{\infty} \Pr (A_{i}),

χρησιμοποιώντας ότι $\Pr (B_{i}) \leq \Pr (A_{i})$ καθώς $B_{i} \subseteq A_{i}$ . Επομένως, έπεται η ανισότητα.

Παραδείγματα

Απλό παράδειγμα

Έστω ότι η πιθανότητα να βρέξει αύριο στην Αθήνα είναι $p_{1} = 0.1$ και η πιθανότητα να βρέξει αύριο στην Θεσσαλονίκη είναι $p_{2} = 0.2$ . Τότε η ανισότητα Μπουλ δίνει ότι η πιθανότητα να βρέξει σε μία από τις δύο πόλεις είναι το πολύ $p_{1} + p_{2} = 0.1 + 0.2 = 0.3$ .

Παρατηρήστε ότι δεν κάναμε καμία υπόθεση ότι τα γεγονότα είναι ανεξάρτητα. Αλλά αν οι πιθανότητες ήταν μεγαλύτερες, για παράδειγμα $p_{1} = 0.6$ και $p_{2} = 0.8$ , τότε η ανισότητα Μπουλ θα μας έδινε ότι η πιθανότητα να βρέξει σε κάποιο από τα δύο μέρη είναι το πολύ $p_{1} + p_{2} = 0.6 + 0.8 = 1.4$ , που δεν είναι χρήσιμο καθώς γνωρίζουμε ήδη ότι κάθε πιθανότητα είναι το πολύ $1$ .

Πρόβλημα συλλέκτη κουπονιών

Στο πρόβλημα του συλλέκτη κουπονιών, υπάρχουν $n$ είδη από κουπόνια και σε κάθε στιγμή ο συλλέκτης λαμβάνει ένα καινούργιο κουπόνι τυχαία από τα $n$ διαθέσιμα είδη. Χρησιμοποιώντας την ανισότητα Μπουλ, μπορούμε να δείξουμε ότι με μεγάλη πιθανότητα μετά από $T = 2 n \log n$ βήματα ο συλλέκτης θα έχει συλλέξει όλα τα κουπόνια.

Έστω $A_{i}$ το γεγονός ότι το $i$ -οστό τύπου κουπόνι δεν έχει συλλεχθεί στα πρώτα $T$ βήματα. Τότε

Πρότυπο:NumBlk

Χρησιμοποιώντας την ανισότητα του Μπουλ έχουμε ότι

p \geq 1 - \sum_{i = 1}^{n} \Pr (A_{i}),

και επομένως μένει να φράξουμε την πιθανότητα $\Pr (A_{i})$ . Για να μην συλλέξουμε το κανένα κουπόνι είδους $i$ σημαίνει ότι σε κάθε ένα από τα $T = 2 n \log n$ βήματα διαλέξαμε κάποιο άλλο από τα $n - 1$ κουπόνια. Επομένως, αφού οι επιλογές στα βήματα είναι ανεξάρτητες

\Pr (A_{i}) = {(\frac{n - 1}{n})}^{T} = {(1 - \frac{1}{n})}^{2 n \log n} \leq {(e^{- 1 / n})}^{- 2 n \log n} = e^{2 \log n} = n^{- 2} = \frac{1}{n^{2}},

όπου χρησιμοποιήσαμε ότι $1 + x \leq e^{x}$ για κάθε $x \in ℝ$ και ότι $e^{x \log n} = n^{x}$ για κάθε $x \in ℝ$ .

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

p \geq 1 - \sum_{i = 1}^{n} \Pr (A_{i}) \geq 1 - n \cdot \frac{1}{n^{2}} = 1 - \frac{1}{n},

που ολοκληρώνει την απόδειξη ότι με "μεγάλη πιθανότητα" ο συλλέκτης θα έχει μαζέψει όλων των ειδών τα κουπόνια στα πρώτα $T$ βήματα. Συγκεκριμένα όσο μεγαλώνει το $n$ τόσο μεγαλώνει και η πιθανότητα.

Εφαρμογές

Στην θεωρητική πληροφορική και συγκεκριμένα στην ανάλυση πιθανοτικών αλγορίθμων, η ανισότητα Μπουλ χρησιμοποιείται συχνά για να φράξει την πιθανότητα ένας αλγόριθμος να αποτύχει ή να χρειάζεται πολύ χρόνο να καταλήξει στην σωστή απάντηση.^[6]^[7]

Κάτω φράγμα

Στην ίδια εργασία του Τζορτζ Μπουλ παρουσιάζεται και το εξής κάτω φράγμα για την πιθανότητα της ένωσης γεγονότων:Πρότυπο:R^[8]

\Pr (⋃_{i = 1}^{n} A_{i}) \geq \max_{j = 1, \dots, n} \Pr (A_{j}),

χρησιμοποιώντας ότι αφού $A_{j} \subseteq ⋃_{i = 1}^{n} A_{i}$ , έχουμε ότι $\Pr (A_{j}) \subseteq \Pr (⋃_{i = 1}^{n} A_{i})$ για κάθε $j = 1, \dots, n$ , άρα και για το γεγονός με την μέγιστη πιθανότητα.

Ιστορία

Η ανισότητα καλείται και ως ανισότητα Μπουλ από τον Τζορτζ Μπουλ.Πρότυπο:R

Δείτε επίσης

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

Παραπομπές

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Ανισότητα Μπουλ

Περιεχόμενα

Αποδείξεις

Περίπτωση n=2

Για κάθε n (μαθηματική επαγωγή)

Για κάθε αριθμήσιμο πλήθος

Παραδείγματα

Απλό παράδειγμα

Πρόβλημα συλλέκτη κουπονιών

Εφαρμογές

Κάτω φράγμα

Ιστορία

Δείτε επίσης

Παραπομπές

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

Ανισότητα Μπουλ

Αποδείξεις

Περίπτωση n=2

Για κάθε n (μαθηματική επαγωγή)

Για κάθε αριθμήσιμο πλήθος

Παραδείγματα

Απλό παράδειγμα

Πρόβλημα συλλέκτη κουπονιών

Εφαρμογές

Κάτω φράγμα

Ιστορία

Δείτε επίσης

Παραπομπές

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

Αναζήτηση