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

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

\Pr (⋃_{i = 1}^{n} A_{i}) \geq \frac{{(\sum_{i = 1}^{n} \Pr (A_{i}))}^{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 {(\Pr (⋃_{i = 1}^{n} A_{i}))}^{- 1} \cdot {(\sum_{i = 1}^{n} \Pr (A_{i}))}^{2} - \sum_{i = 1}^{n} \Pr (A_{i}) .

Απόδειξη

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

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

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

\sum_{i = 1}^{n} \Pr (A_{i}) = \sum_{i = 1}^{n} E (𝟏_{A_{i}}) = E (\sum_{i = 1}^{n} 𝟏_{A_{i}}),

και

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} E (𝟏_{A_{i}} 𝟏_{A_{j}}) = E (2 \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} 𝟏_{A_{i}} 𝟏_{A_{j}}) .

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

Πρότυπο:NumBlk

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

Πρότυπο:NumBlk

Επομένως συνδυάζοντας τις (Πρότυπο:EquationNote) και (Πρότυπο:EquationNote) η αρχική ανισότητα γράφεται ως εξής

\Pr (\sum_{i = 1}^{n} 𝟏_{A_{i}} > 0) \cdot E ({(\sum_{i = 1}^{n} 𝟏_{A_{i}})}^{2}) \geq {(E (\sum_{i = 1}^{n} 𝟏_{A_{i}}))}^{2}

Θέτοντας $X = \sum_{i = 1}^{n} 𝟏_{A_{i}}$ , η ανισότητα παίρνει την μορφή

\Pr (X > 0) \cdot E (X^{2}) \geq (E (X))^{2},

η οποία προκύπτει από αναδιάταξη της ανισότητα της μεθόδου της δεύτερης ροπής.

Δείτε επίσης

Παραπομπές

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

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

[1]

[2]

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

Απόδειξη

Δείτε επίσης

Παραπομπές

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

Αναζήτηση