Γεωμετρική κατανομή

Η γεωμετρική κατανομή είναι μια διακριτή συνάρτηση κατανομής τυχαίας μεταβλητής. Περιγράφει το πλήθος πειραμάτων με δυο πιθανά αποτελέσματα (επιτυχία - αποτυχία) και πιθανότητα επιτυχίας $p$, μέχρι να έχουμε μια επιτυχία.

Παραδείγματα γεωμετρικής κατανομής με $p=0.2,0.35,0.5$.

Παραδείγματα αθροιστικής κατανομής με $p=0.2,0.35,0.5$.

Γεωμετρική Κατανομή

Συμβολισμός	${\mathsf {Geom}}(p)$
Παράμετροι	$p\in [0,1]$
Φορέας	$x\in \{1,2,\ldots \}$
Συνάρτηση Μάζας Πιθανότητας	$p\cdot (1-p)^{x-1}$
Μέσος	$1/p$
Διάμεσος	$\left\lceil {\frac {-1}{\log _{2}(1-p)}}\right\rceil$
Διακύμανση	${\frac {1-p}{p^{2}}}$
Λοξότητα	${\frac {2-p}{\sqrt {1-p}}}$
Κύρτωση	$3+{\frac {p^{2}}{1-p}}$
Εντροπία	$-\log _{2}p-{\frac {1-p}{p}}\cdot \log _{2}(1-p)$
Ροπή	$\operatorname {E} [X^{k}]=p$
Πιθανογεννήτρια	${\frac {p\cdot t}{1-(1-p)\cdot t}}$ για $|t|<{\frac {1}{1-p}}$
Χαρακτηριστική	${\frac {p\cdot e^{t}}{1-(1-p)\cdot e^{t}}}$ για $e^{t}<{\frac {1}{1-p}}$

Θεωρούμε την τυχαία μεταβλητή $X$ που εκφράζει το πλήθος των πειραμάτων. Η πιθανότητα να χρειαστούμε $x\in \{1,2,\ldots \}$ πειράματα έως ότου να έχουμε μια επιτυχία με πιθανότητα επιτυχίας $p$ κάθε φορά είναι:

$\operatorname {P} (X=x)=p(1-p)^{x-1}$.

Παραδείγματα

• Το πλήθος των φορών $X$ που πρέπει να ρίξουμε ένα νόμισμα μέχρι να έρθει κορώνα ακολουθεί την κατανομή ${\mathsf {Geom}}(1/2)$.
• Το πλήθος των φορών $X$ που πρέπει να πάρει κανείς το λαχείο μέχρι να κερδίσει ακολουθεί την κατανομή ${\mathsf {Geom}}(1/1000)$, αν υποθέσουμε ότι συμμετέχουν $1000$ άτομα κάθε φορά.
• Αν ένας αλγόριθμος έχει πιθανότητα σφάλματος $\epsilon$, τότε το πλήθος των φορών που πρέπει να τον τρέξουμε έως ότου δώσει την σωστή απάντηση, ακολουθεί την κατανομή ${\mathsf {Geom}}(1/(1-\epsilon ))$.

Μέση τιμή

Απόδειξη 1η: Θα χρησιμοποιήσουμε την εξής φόρμουλα για τον υπολογισμό της μέσης τιμής:

$\operatorname {E} [X]=\sum _{x=1}^{\infty }\Pr(X\geq x).$

Η πιθανότητα να έρθει η πρώτη επιτυχία μετά το $x$-οστό πείραμα είναι ίση με την πιθανότητα τα πρώτα $x-1$ πειράματα να είναι αποτυχίες, δηλαδή

$\operatorname {P} (X\geq x)=(1-p)^{x-1}.$

επιστρέφοντας στον τύπο της μέσης τιμής, έχουμε ότι:

$\operatorname {E} [X]=\sum _{x=1}^{\infty }\Pr(X\geq x)=\sum _{x=1}^{\infty }(1-p)^{x-1}=\sum _{x=1}^{\infty }(1-p)^{x}={\frac {1}{1-(1-p)}}={\frac {1}{p}}.$

Απόδειξη 2η: Ένας εναλλακτικός τρόπος για την εύρεση την μέσης τιμής είναι ο εξής:

${\begin{aligned}\operatorname {E} [X]&=\sum _{x=0}^{\infty }x\cdot p\cdot (1-p)^{x-1}\\&=\sum _{x=0}^{\infty }p\cdot \left(x\cdot (1-p)^{x-1}\right)\\&=\sum _{x=0}^{\infty }p\cdot {\frac {d}{dp}}\left(-(1-p)^{x}\right)\\&=p\cdot {\frac {d}{dp}}\left(-\sum _{x=0}^{\infty }(1-p)^{x}\right)\\&=p\cdot {\frac {d}{dp}}\left(-{\frac {1}{p}}\right)\\&=p\cdot {\frac {1}{p^{2}}}\\&={\frac {1}{p}}.\end{aligned}}$

Διακύμανση

Ξεκινάμε υπολογίζοντας την τιμή:

${\begin{aligned}\operatorname {E} [X\cdot (X-1)]&=\sum _{x=0}^{\infty }p\cdot (1-p)^{x-1}\cdot x\cdot (x-1)\\&=p\cdot (1-p)\cdot \sum _{x=2}^{\infty }(1-p)^{x-2}\cdot x\cdot (x-1)\\&=p\cdot (1-p)\cdot \sum _{x=2}^{\infty }{\frac {d}{dp^{2}}}\left((1-p)^{x}\right)\\&=p\cdot (1-p)\cdot {\frac {d^{2}}{dp^{2}}}\sum _{x=2}^{\infty }(1-p)^{x}\\&=p\cdot (1-p)\cdot {\frac {d^{2}}{dp^{2}}}{\frac {(1-p)^{2}}{p}}\\&=p\cdot (1-p)\cdot {\frac {d}{dp}}\left(1-{\frac {1}{p^{2}}}\right)\\&=p\cdot (1-p)\cdot {\frac {2}{p^{3}}}\\&=2\cdot {\frac {1-p}{p^{2}}}.\end{aligned}}$

Η διακύμανση τότε δίνεται από τον τύπο:

${\begin{aligned}\operatorname {V} [X]&=\operatorname {E} [X\cdot (X-1)]+\operatorname {E} [X]-(\operatorname {E} [X])^{2}\\&=2\cdot {\frac {1-p}{p^{2}}}+{\frac {1}{p}}-{\frac {1}{p^{2}}}\\&={\frac {1-p}{p^{2}}}.\end{aligned}}$

Διάμεσος

Θέλουμε να βρούμε την μικρότερη τιμή του $x$ ώστε:

$\operatorname {P} (X\geq x)=(1-p)^{x}\leq {\frac {1}{2}}.$

Ισοδύναμα,

$x\log _{2}(1-p)\leq -1.$

Δηλαδή,

$x=\left\lceil {\frac {-1}{\log _{2}(1-p)}}\right\rceil .$

Εντροπία

Από τον ορισμό της εντροπίας, έχουμε ότι:

${\begin{aligned}\operatorname {E} [-\log _{2}X]&=-\sum _{x=0}^{\infty }p\cdot (1-p)^{x-1}\cdot \log _{2}\left(p\cdot (1-p)^{x-1}\right)\\&=-\sum _{x=0}^{\infty }p\cdot (1-p)^{x-1}\cdot \log _{2}p-\sum _{x=0}^{\infty }p\cdot (1-p)^{x}\cdot (x-1)\cdot \log _{2}(1-p)\\&=-(\log _{2}p)\cdot \sum _{x=0}^{\infty }p\cdot (1-p)^{x-1}-(\log _{2}(1-p))\cdot \sum _{x=2}^{\infty }p\cdot (1-p)^{x-2}\cdot (x-1)\\&=-\log _{2}p-(\log _{2}(1-p))\operatorname {E} [X-1]\\&=-\log _{2}p-{\frac {1-p}{p}}\cdot \log _{2}(1-p).\end{aligned}}$

Πιθανογεννήτρια συνάρτηση

Από τον ορισμό της πιθανογεννήτριας συνάρτησης, έχουμε ότι:

${\begin{aligned}\operatorname {E} [t^{X}]&=\sum _{x=0}^{\infty }p\cdot (1-p)^{x-1}\cdot t^{x}\\&=p\cdot t\cdot \sum _{x=0}^{\infty }((1-p)\cdot t)^{x-1}\\&=p\cdot t\cdot {\frac {1}{1-(1-p)\cdot t}},\end{aligned}}$

χρησιμοποιώντας ότι $|t|<{\frac {1}{1-p}}$.

Χαρακτηριστική συνάρτηση

Από τον ορισμό της χαρακτηριστικής συνάρτησης, έχουμε ότι:

${\begin{aligned}\operatorname {E} [e^{tX}]&=\sum _{x=0}^{\infty }p\cdot (1-p)^{x-1}\cdot e^{tx}\\&=p\cdot e^{t}\cdot \sum _{x=0}^{\infty }((1-p)\cdot e^{t})^{x-1}\\&=p\cdot e^{t}\cdot {\frac {1}{1-(1-p)\cdot e^{t}}},\end{aligned}}$

χρησιμοποιώντας ότι $e^{t}<{\frac {1}{1-p}}$.

Ιδιότητες

• (Έλλειψη μνήμης) Έστω $X\sim {\mathsf {Geom}}(p)$, τότε για κάθε $m,n\geq 0$, ισχύει ότι:

$\operatorname {P} (X\geq m+n\mid X\geq m)=\operatorname {P} (X\geq n).$

• Το ελάχιστο $Z=\min\{X_{1},X_{2}\}$ δύο ανεξάρτητων γεωμετρικών κατανομών $X_{1}\sim {\mathsf {Geom}}(p_{1})$ και $X_{2}\sim {\mathsf {Geom}}(p_{2})$, ακολουθεί επίσης γεωμετρική κατανομή $Z\sim {\mathsf {Geom}}(p_{1}+p_{2}-p_{1}p_{2})$.

Δείτε επίσης

• Γεωμετρική πρόοδος
• Αρνητική διωνυμική κατανομή