Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Στην θεωρία πιθανοτήτων , η ανισότητα Τσουνγκ-Έρντος δίνει ένα κάτω φράγμα στην ένωση γεγονότων . Πιο συγκεκριμένα, για οποιαδήποτε
n
{\displaystyle n}
γεγονότα
A
1
,
…
,
A
n
{\displaystyle A_{1},\ldots ,A_{n}}
με
Pr
(
A
1
∪
…
∪
A
n
)
>
0
{\displaystyle \Pr(A_{1}\cup \ldots \cup A_{n})>0}
, ισχύει ότι[ 1] [ 2]
Pr
(
⋃
i
=
1
n
A
i
)
≥
(
∑
i
=
1
n
Pr
(
A
i
)
)
2
∑
i
=
1
n
∑
j
=
1
n
Pr
(
A
i
∩
A
j
)
.
{\displaystyle \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
∑
i
=
1
n
∑
j
=
i
+
1
n
Pr
(
A
i
∩
A
j
)
≥
(
Pr
(
⋃
i
=
1
n
A
i
)
)
−
1
⋅
(
∑
i
=
1
n
Pr
(
A
i
)
)
2
−
∑
i
=
1
n
Pr
(
A
i
)
.
{\displaystyle 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
{\displaystyle X}
,
Pr
(
X
>
0
)
≥
(
E
(
X
)
)
2
E
(
X
2
)
.
{\displaystyle \Pr(X>0)\geq {\frac {(\operatorname {E} (X))^{2}}{\operatorname {E} (X^{2})}}.}
Θα χρησιμοποιήσουμε τις δείκτριες τυχαίες μεταβλητές
1
A
i
{\displaystyle \mathbf {1} _{A_{i}}}
για τα γεγονότα
A
i
{\displaystyle A_{i}}
. Από τις ιδιότητες των δείκτριων τυχαίων μεταβλητών έχουμε ότι
∑
i
=
1
n
Pr
(
A
i
)
=
∑
i
=
1
n
E
(
1
A
i
)
=
E
(
∑
i
=
1
n
1
A
i
)
,
{\displaystyle \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
∑
i
=
1
n
∑
j
=
i
+
1
n
Pr
(
A
i
∩
A
j
)
=
2
∑
i
=
1
n
∑
j
=
i
+
1
n
E
(
1
A
i
1
A
j
)
=
E
(
2
∑
i
=
1
n
∑
j
=
i
+
1
n
1
A
i
1
A
j
)
.
{\displaystyle 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).}
Συνδυάζοντας αυτές τις δύο σχέσεις έχουμε ότι,
∑
i
=
1
n
Pr
(
A
i
)
+
2
∑
i
=
1
n
∑
j
=
i
+
1
n
Pr
(
A
i
∩
A
j
)
=
∑
i
=
1
n
∑
j
=
1
n
Pr
(
A
i
∩
A
j
)
=
E
(
(
∑
i
=
1
n
1
A
i
)
2
)
.
{\displaystyle \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
{\displaystyle n}
γεγονότα
A
1
,
…
,
A
n
{\displaystyle A_{1},\ldots ,A_{n}}
είναι ισοδύναμη με την πιθανότητα το άθροισμα των δεικτών να είναι μεγαλύτερο του μηδενός. Επομένως,
Pr
(
⋃
i
=
1
n
A
i
)
=
Pr
(
∑
i
=
1
n
X
i
>
0
)
.
{\displaystyle \Pr \left(\bigcup _{i=1}^{n}A_{i}\right)=\Pr \left(\sum _{i=1}^{n}X_{i}>0\right).}
(2 )
Επομένως συνδυάζοντας τις (1 ) και (2 ) η αρχική ανισότητα γράφεται ως εξής
Pr
(
∑
i
=
1
n
1
A
i
>
0
)
⋅
E
(
(
∑
i
=
1
n
1
A
i
)
2
)
≥
(
E
(
∑
i
=
1
n
1
A
i
)
)
2
{\displaystyle \Pr \left(\sum _{i=1}^{n}\mathbf {1} _{A_{i}}>0\right)\cdot \operatorname {E} \left(\left(\sum _{i=1}^{n}\mathbf {1} _{A_{i}}\right)^{2}\right)\geq \left(\operatorname {E} \left(\sum _{i=1}^{n}\mathbf {1} _{A_{i}}\right)\right)^{2}}
Θέτοντας
X
=
∑
i
=
1
n
1
A
i
{\displaystyle \textstyle X=\sum _{i=1}^{n}\mathbf {1} _{A_{i}}}
, η ανισότητα παίρνει την μορφή
Pr
(
X
>
0
)
⋅
E
(
X
2
)
≥
(
E
(
X
)
)
2
,
{\displaystyle \Pr \left(X>0\right)\cdot \operatorname {E} (X^{2})\geq (\operatorname {E} (X))^{2},}
η οποία προκύπτει από αναδιάταξη της ανισότητα της μεθόδου της δεύτερης ροπής.