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

Στην θεωρία πιθανοτήτων, η ανισότητα Μπουλ (ή αλλιώς ανισότητα της υποπροσθετικότητας) λέει ότι για ένα σύνολο από γεγονότα, η πιθανότητα να συμβεί τουλάχιστον ένα από αυτά είναι το πολύ όσο το άθροισμα της πιθανότητας να συμβεί το κάθε γεγονός ξεχωριστά. Πιο συγκεκριμένα, για κάθε  γεγονότα , ισχύει ότι

Πιο γενικά, για κάθε αριθμήσιμο σύνολο γεγονότων  ισχύει ότι

Αποδείξεις

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

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

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

Επειδή, η πιθανότητα , ισχύει ότι

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

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

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

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

Βασική περίπτωση: Για , η ανισότητα ισχύει ως ισότητα για κάθε γεγονός , δηλαδή .

Επαγωγικό βήμα: Θεωρούμε ότι ισχύει για  γεγονότα. Θα αποδείξουμε ότι ισχύει για  γεγονότα . Ξεκινάμε με το αριστερό μέλος,

από την παραπάνω περίπτωση για . Χρησιμοποιώντας την επαγωγική υπόθεση για τα γεγονότα  έχουμε ότι

Επομένως, ισχύει και για  και συνεπώς για κάθε .

Για κάθε αριθμήσιμο πλήθος
Η παραπάνω απόδειξη ισχύει για πεπερασμένο πλήθος γεγονότων. Τώρα θα αποδείξουμε την ανισότητα για κάθε αριθμήσιμο πλήθος γεγονότων .  Ορίζουμε τα γεγονότα  ως εξής:

έτσι ώστε να είναι ανεξάρτητα  για  και . Συνεπώς, από το αξίωμα για την πιθανότητα ανεξάρτητων γεγονότων

χρησιμοποιώντας ότι  καθώς . Επομένως, έπεται η ανισότητα.

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

Απλό παράδειγμα
Έστω ότι η πιθανότητα να βρέξει αύριο στην Αθήνα είναι  και η πιθανότητα να βρέξει αύριο στην Θεσσαλονίκη είναι . Τότε η ανισότητα Μπουλ δίνει ότι η πιθανότητα να βρέξει σε μία από τις δύο πόλεις είναι το πολύ .

Παρατηρήστε ότι δεν κάναμε καμία υπόθεση ότι τα γεγονότα είναι ανεξάρτητα. Αλλά αν οι πιθανότητες ήταν μεγαλύτερες, για παράδειγμα  και , τότε η ανισότητα Μπουλ θα μας έδινε ότι η πιθανότητα να βρέξει σε κάποιο από τα δύο μέρη είναι το πολύ , που δεν είναι χρήσιμο καθώς γνωρίζουμε ήδη ότι κάθε πιθανότητα είναι το πολύ .

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

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

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

και επομένως μένει να φράξουμε την πιθανότητα . Για να μην συλλέξουμε το κανένα κουπόνι είδους  σημαίνει ότι σε κάθε ένα από τα  βήματα διαλέξαμε κάποιο άλλο από τα  κουπόνια. Επομένως, αφού οι επιλογές στα βήματα είναι ανεξάρτητες 

όπου χρησιμοποιήσαμε ότι  για κάθε  και ότι  για κάθε .

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

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

Εφαρμογές

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

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

χρησιμοποιώντας ότι αφού , έχουμε ότι  για κάθε , άρα και για το γεγονός με την μέγιστη πιθανότητα.

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

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

Παραπομπές

Ανισότητες