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

Στην θεωρία πιθανοτήτων, η **ανισότητα Μπουλ** ή **ιδιότητα της υποπροσθετικότητας** (αναφέρεται και ως **ανισότητα Boole**) λέει ότι για ένα σύνολο από γεγονότα, η πιθανότητα να συμβεί τουλάχιστον ένα από αυτά είναι το πολύ όσο το άθροισμα της πιθανότητας να συμβεί το κάθε γεγονός ξεχωριστά. Πιο συγκεκριμένα, για κάθε n γεγονότα A_1, \ldots, A_n, ισχύει ότι
:
\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 \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 \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 \R και ότι e^{x \log n} = n^x  για κάθε x \in \R.

Επομένως, επιστρέφοντας στην () έχουμε ότι
: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, άρα και για το γεγονός με την μέγιστη πιθανότητα.

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

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

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


Κατηγορία:Ανισότητες