Μετάβαση στο περιεχόμενο

Μέθοδος δεύτερης ροπής

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Στην θεωρία πιθανοτήτων, η μέθοδος της δεύτερης ροπής αναφέρεται σε τεχνική απόδειξης ότι μία τυχαία μεταβλητή X είναι μη-μηδενική με θετική πιθανότητα, δηλαδή Pr⁡(X≠0)>0, με την χρήση της ροπής δεύτερης τάξης, δηλαδή την E⁡(X2) ή διακύμανση Var⁡(X). Συνήθως αναφέρεται στην χρήση της εξής ανισότητας για κάθε ακέραια τυχαία μεταβλητή X με E⁡(X)≠0,[1]:47[2]:143[3]

Pr⁡(X=0)≤Var⁡(X)(E⁡(X))2.

Για μη-αρνητική τυχαία μεταβλητή X, εμφανίζεται και με την μορφή

Pr⁡(X>0)≥(E⁡(X))2E⁡(X2).

Για την τυχαία μεταβλητή X με διακύμανση Var⁡(X)<∞, η ανισότητα Τσεμπισιόφ δίνει για a=E⁡(X)

Pr⁡(|X−E⁡(X)|≥E⁡(X))≤Var⁡(X)(E⁡(X))2.

Όταν X=0 έπεται ότι |X−E⁡(X)|≥E⁡(X). Συνεπώς,

Pr⁡(X=0)≤Pr⁡(|X−E⁡(X)|≥E⁡(X))≤Var⁡(X)(E⁡(X))2.

Η ανισότητα Κωσύ-Σβαρτς δίνει ότι για δύο τυχαίες μεταβλητές A και B, ισχύει ότι

(E⁡(AB))2≤E⁡(A2)E⁡(B2).

Για την ζητούμενη ανισότητα, θεωρούμε την δείκτρια τυχαία μεταβλητή Z=𝟏X>0, για την οποία ισχύει ότι E⁡(Z)=Pr⁡(X>0) και Z2=Z από τις ιδιότητες των δείκτριων τυχαίων μεταβλητών. Επίσης, ισχύει ότι

Z⋅X=X,

καθώς η X είναι μη-αρνητική και αν X=0 τότε και Z=0 (άρα 0=ZX=X), ενώ διαφορετικά Z=1 (άρα ZX=X). Συνεπώς χρησιμοποιώντας την ανισότητα Κωσύ-Σβαρτς,

(E⁡(X))2=(E⁡(ZX))2≤E⁡(Z2)⋅E⁡(X2)=E⁡(Z)⋅E⁡(X2)=Pr⁡(X>0)⋅E⁡(X2).

Αναδιατάσσοντας τα δύο μέλη της ανισότητας, προκύπτει το ζητούμενο

Pr⁡(X>0)≥(E⁡(X))2E⁡(X2).
  1. ↑ Νικολετσεας, Σωτήρης Ε.· Σπυράκης, Παύλος Γ. (2003). Στοιχεία της πιθανοτικής μεθόδου (PDF). Gutenberg.
  2. ↑ Mitzenmacher, Michael. Probability and computing : randomization and probabilistic techniques in algorithms and data analysis (2η έκδοση). Cambridge, United Kingdom: Cambridge University Press. ISBN 978-1107154889.
  3. ↑ Janson, Svante (1996). «The Second Moment Method, Conditioning and Approximation». Random Discrete Structures: 175–183. doi:https://doi.org/10.1007/978-1-4612-0719-1_11.