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

Αρχείο:Geometric distribution examples.svg

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

Αρχείο:Cdf geometric distribution examples.svg

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

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

Συμβολισμός	$𝖦𝖾𝗈𝗆(p)$
Παράμετροι	$p\in [0,1]$
Φορέας	$x\in \{1,2,\dots \}$
Συνάρτηση Μάζας Πιθανότητας	$p\cdot (1-p{)}^{x-1}$
Μέσος	$1/p$
Διάμεσος	$\lceil \frac{-1}{{\log }_2(1-p)}\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)$
Ροπή	$\mathrm{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}$

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

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

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

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

• Το πλήθος των φορών $X$ που πρέπει να ρίξουμε ένα νόμισμα μέχρι να έρθει κορώνα ακολουθεί την κατανομή $𝖦𝖾𝗈𝗆(1/2)$.
• Το πλήθος των φορών $X$ που πρέπει να πάρει κανείς το λαχείο μέχρι να κερδίσει ακολουθεί την κατανομή $𝖦𝖾𝗈𝗆(1/1000)$, αν υποθέσουμε ότι συμμετέχουν $1000$ άτομα κάθε φορά.
• Αν ένας αλγόριθμος έχει πιθανότητα σφάλματος $ϵ$, τότε το πλήθος των φορών που πρέπει να τον τρέξουμε έως ότου δώσει την σωστή απάντηση, ακολουθεί την κατανομή $𝖦𝖾𝗈𝗆(1/(1-ϵ))$.

Μέση τιμή

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

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

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

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

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

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

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

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

Διακύμανση

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

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

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

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

Διάμεσος

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

$\mathrm{P}(X\ge x)=(1-p{)}^x\le \frac{1}{2}.$

Ισοδύναμα,

$x{\log }_2(1-p)\le -1.$

Δηλαδή,

$x=\lceil \frac{-1}{{\log }_2(1-p)}\rceil .$

Εντροπία

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

$\begin{array}{cc}\mathrm{E}[-{\log }_{2}X]& =-\sum _{x=0}^{\mathrm{\infty }}p\cdot (1-p{)}^{x-1}\cdot {\log }_2(p\cdot (1-p{)}^{x-1})\\ & =-\sum _{x=0}^{\mathrm{\infty }}p\cdot (1-p{)}^{x-1}\cdot {\log }_{2}p-\sum _{x=0}^{\mathrm{\infty }}p\cdot (1-p{)}^x\cdot (x-1)\cdot {\log }_2(1-p)\\ & =-({\log }_{2}p)\cdot \sum _{x=0}^{\mathrm{\infty }}p\cdot (1-p{)}^{x-1}-({\log }_2(1-p))\cdot \sum _{x=2}^{\mathrm{\infty }}p\cdot (1-p{)}^{x-2}\cdot (x-1)\\ & =-{\log }_{2}p-({\log }_2(1-p))\mathrm{E}[X-1]\\ & =-{\log }_{2}p-\frac{1-p}{p}\cdot {\log }_2(1-p).\end{array}$

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

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

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

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

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

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

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

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

Ιδιότητες

• (Έλλειψη μνήμης) Έστω $X\sim 𝖦𝖾𝗈𝗆(p)$, τότε για κάθε $m,n\ge 0$, ισχύει ότι:

$\mathrm{P}(X\ge m+n\mid X\ge m)=\mathrm{P}(X\ge n).$

$\mathrm{P}(X\ge m+n\mid X\ge m)=\frac{\mathrm{P}(X\ge m+n,X\ge m)}{\mathrm{P}(X\ge m)}=\frac{\mathrm{P}(X\ge m+n)}{\mathrm{P}(X\ge m)}=\frac{(1-p{)}^{m+n}}{(1-p{)}^m}=(1-p{)}^n=\mathrm{P}(X\ge n).$

• Το ελάχιστο $Z=\min \{X_1,X_2\}$ δύο ανεξάρτητων γεωμετρικών κατανομών $X_1\sim 𝖦𝖾𝗈𝗆(p_1)$ και $X_2\sim 𝖦𝖾𝗈𝗆(p_2)$, ακολουθεί επίσης γεωμετρική κατανομή $Z\sim 𝖦𝖾𝗈𝗆(p_1+p_2-p_1{p}_2)$.

Πρότυπο:Collapse top Το γεγονός $Z\ge x$ συμβαίνει όταν $X_1\ge x$ και $X_2\ge x$. Επομένως, για κάθε $x\ge 0$, έχουμε ότι

$\begin{array}{cc}\mathrm{P}(Z\ge x)& =\mathrm{P}(X_1\ge x,X_2\ge x)\\ & =\mathrm{P}(X_1\ge x)\cdot \mathrm{P}(X_2\ge x)\\ & =(1-p_1{)}^x\cdot (1-p_2{)}^x\\ & ={((1-p_1)\cdot (1-p_2))}^x\\ & ={(1-(p_1+p_2-p_1{p}_2))}^x.\end{array}$

Συνεπώς η $Z$ είναι γεωμετρική κατανομή με παράμετρο $p=p_1+p_2-p_1{p}_2$. Πρότυπο:Collapse bottom

Δείτε επίσης

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