Ανισότητα Τσουνγκ-Έρντος

Στην θεωρία πιθανοτήτων, η ανισότητα Τσουνγκ-Έρντος δίνει ένα κάτω φράγμα στην ένωση γεγονότων. Πιο συγκεκριμένα, για οποιαδήποτε $n$ γεγονότα $A_{1},\ldots ,A_{n}$ με $\Pr(A_{1}\cup \ldots \cup A_{n})>0$ , ισχύει ότι^[1]^[2]

\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\geq {\frac {\left(\sum _{i=1}^{n}\Pr(A_{i})\right)^{2}}{\sum _{i=1}^{n}\sum _{j=1}^{n}\Pr(A_{i}\cap A_{j})}}.

Στην εργασία των Τσουνγκ και Έρντος η ανισότητα εμφανίζεται με την ισοδύναμη μορφή,

2\sum _{i=1}^{n}\sum _{j=i+1}^{n}\Pr(A_{i}\cap A_{j})\geq \left(\Pr \left(\bigcup _{i=1}^{n}A_{i}\right)\right)^{-1}\cdot \left(\sum _{i=1}^{n}\Pr(A_{i})\right)^{2}-\sum _{i=1}^{n}\Pr(A_{i}).

Απόδειξη[Επεξεργασία | επεξεργασία κώδικα]

Η απόδειξη στηρίζεται στην εξής ανισότητα της μεθόδου της δεύτερης ροπής, όπου για κάθε μη-αρνητική τυχαία μεταβλητή $X$ ,

\Pr(X>0)\geq {\frac {(\operatorname {E} (X))^{2}}{\operatorname {E} (X^{2})}}.

Θα χρησιμοποιήσουμε τις δείκτριες τυχαίες μεταβλητές $\mathbf {1} _{A_{i}}$ για τα γεγονότα $A_{i}$ . Από τις ιδιότητες των δείκτριων τυχαίων μεταβλητών έχουμε ότι

\sum _{i=1}^{n}\Pr(A_{i})=\sum _{i=1}^{n}\operatorname {E} (\mathbf {1} _{A_{i}})=\operatorname {E} \left(\sum _{i=1}^{n}\mathbf {1} _{A_{i}}\right),

και

2\sum _{i=1}^{n}\sum _{j=i+1}^{n}\Pr(A_{i}\cap A_{j})=2\sum _{i=1}^{n}\sum _{j=i+1}^{n}\operatorname {E} (\mathbf {1} _{A_{i}}\mathbf {1} _{A_{j}})=\operatorname {E} \left(2\sum _{i=1}^{n}\sum _{j=i+1}^{n}\mathbf {1} _{A_{i}}\mathbf {1} _{A_{j}}\right).

Συνδυάζοντας αυτές τις δύο σχέσεις έχουμε ότι,

$\sum _{i=1}^{n}\Pr(A_{i})+2\sum _{i=1}^{n}\sum _{j=i+1}^{n}\Pr(A_{i}\cap A_{j})=\sum _{i=1}^{n}\sum _{j=1}^{n}\Pr(A_{i}\cap A_{j})=\operatorname {E} \left(\left(\sum _{i=1}^{n}\mathbf {1} _{A_{i}}\right)^{2}\right).$

(1)

Επίσης, η πιθανότητα να γίνει οποιοδήποτε από τα $n$ γεγονότα $A_{1},\ldots ,A_{n}$ είναι ισοδύναμη με την πιθανότητα το άθροισμα των δεικτών να είναι μεγαλύτερο του μηδενός. Επομένως,