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

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

Διάγραμμα που αιτιολογεί την ανισότητα Μπουλ για τρία γεγονότα $A_{1},A_{2},A_{3}$. Κάθε τομή των γεγονότων μετριέται τουλάχιστον από μία φορά από το άθροισμα $\Pr(A_{1})+\Pr(A_{2})+\Pr(A_{3})$, επομένως είναι μεγαλύτερο από την πιθανότητα της ένωσης $\Pr(A_{1}\cup A_{2}\cup A_{3})$.

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

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

$\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\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},\ldots ,A_{k+1}$. Ξεκινάμε με το αριστερό μέλος,

$\Pr \left(\bigcup _{i=1}^{k+1}A_{i}\right)=\Pr \left(\bigcup _{i=1}^{k}A_{i}\cup A_{k+1}\right)\leq \Pr \left(\bigcup _{i=1}^{k}A_{i}\right)+\Pr(A_{k+1}),$

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

${\phantom {\Pr \left(\bigcup _{i=1}^{k+1}A_{i}\right)}}\leq \sum _{i=1}^{k}\Pr(A_{i})+\Pr(A_{k+1})$

${\phantom {\Pr \left(\bigcup _{i=1}^{k+1}A_{i}\right)}}=\sum _{i=1}^{k+1}\Pr(A_{i}).$

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

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

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

$B_{i}={\begin{cases}A_{1}&{\text{αν }}i=1\\A_{i}\setminus \bigcup _{j=1}^{i-1}A_{j}&{\text{διαφορετικά}},\end{cases}}$

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

$\Pr \left(\bigcup _{i=1}^{\infty }A_{i}\right)=\Pr \left(\bigcup _{i=1}^{\infty }B_{i}\right)=\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=2n\log n$ βήματα ο συλλέκτης θα έχει συλλέξει όλα τα κουπόνια.

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

$p=\Pr($ο συλλέκτης μάζεψε όλα τα κουπόνια στα $T$ πρώτα βήματα$)=\Pr \left(\neg \bigcup _{i=1}^{n}A_{i}\right)=1-\Pr \left(\bigcup _{i=1}^{n}A_{i}\right).$

(1)

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

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

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

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

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

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

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

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

Εφαρμογές

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

Κάτω φράγμα

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

$\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\geq \max _{j=1,\ldots ,n}\Pr(A_{j}),$

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

Ιστορία

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

Δείτε επίσης

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