Δείκτρια τυχαία μεταβλητή

Στην θεωρία πιθανοτήτων, δείκτρια τυχαία μεταβλητή ενός γεγονότος $A\subseteq \mathrm{\Omega }$ του δειγματοχώρου $\mathrm{\Omega }$, είναι η τυχαία μεταβλητή ${\mathrm{𝟏}}_A:\mathrm{\Omega }\to ℝ$, η οποία ορίζεται ωςΠρότυπο:RpΠρότυπο:RpΠρότυπο:Rp

${\mathrm{𝟏}}_A(\omega )=\{\begin{array}{cc}1& \text{αν }\omega \in A,\\ 0& \text{διαφορετικά}.\end{array}$

Συμβολίζεται και ως 𝟙_A, $\mathrm{𝟏}(A)$.

Ιδιότητες

Οι δείκτριες τυχαίες μεταβλητές έχουν τις εξής ιδιότητες:Πρότυπο:R

• $\mathrm{E}({\mathrm{𝟏}}_A)=\mathrm{Pr}(A)$.

Πρότυπο:Collapse top Από τον ορισμό της αναμενόμενης τιμής, $\mathrm{E}({\mathrm{𝟏}}_A)=\mathrm{Pr}(A)\cdot 1+(1-\mathrm{Pr}(A))\cdot 0=\mathrm{Pr}(A)$. Πρότυπο:Collapse bottom

• Για κάθε $k\in ℝ$, $({\mathrm{𝟏}}_A{)}^k={\mathrm{𝟏}}_A$, καθώς η τυχαία μεταβλητή λαμβάνει μόνο τιμές $0$ και $1$.
• $\mathrm{Var}({\mathrm{𝟏}}_A)=\mathrm{Pr}(A)\cdot (1-\mathrm{Pr}(A))$.

Πρότυπο:Collapse top Από τον ορισμό της διακύμανσης,

$\mathrm{Var}({\mathrm{𝟏}}_A)=\mathrm{E}(X^2)-(\mathrm{E}(X){)}^2.$

Από την προηγούμενη ιδιότητα για $k=2$,

$\mathrm{Var}({\mathrm{𝟏}}_A)=\mathrm{E}({\mathrm{𝟏}}_A^2)-(\mathrm{E}({\mathrm{𝟏}}_A){)}^2=\mathrm{E}({\mathrm{𝟏}}_A)-(\mathrm{E}({\mathrm{𝟏}}_A){)}^2.$

Χρησιμοποιώντας την πρώτη ιδιότητα,

$\mathrm{Var}({\mathrm{𝟏}}_A)=\mathrm{Pr}(A)-(\mathrm{Pr}(A){)}^2=\mathrm{Pr}(A)\cdot (1-\mathrm{Pr}(A)).$

• ${\mathrm{𝟏}}_{A\cap B}={\mathrm{𝟏}}_A\cdot {\mathrm{𝟏}}_B=\min ({\mathrm{𝟏}}_A,{\mathrm{𝟏}}_B)$.
• ${\mathrm{𝟏}}_{\mathrm{\neg }A}=1-{\mathrm{𝟏}}_A$.
• ${\mathrm{𝟏}}_{A\cup B}={\mathrm{𝟏}}_A+{\mathrm{𝟏}}_B-{\mathrm{𝟏}}_{A\cap B}=\max ({\mathrm{𝟏}}_A,{\mathrm{𝟏}}_B)$.

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

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

Έχουμε ένα νόμισμα που με πιθανότητα $p$ είναι κορώνα και με πιθανότητα $1-p$ είναι γράμματα. Θα στρίψουμε το νόμισμα $n$ φορές και θέλουμε να βρούμε το αναμενόμενο πλήθος κορωνών.

Έστω $K_i$ το ενδεχόμενο να είναι το $i$-οστό στρίψιμο κορώνα και ${\mathrm{𝟏}}_{K_i}$ η δείκτρια τυχαία μεταβλητή αυτού του γεγονότος. Τότε, το συνολικό πλήθος κορωνών δίνεται από

$K={\mathrm{𝟏}}_{K_1}+\dots +{\mathrm{𝟏}}_{K_n}$.

Χρησιμοποιώντας την γραμμικότητα της αναμενόμενης τιμής και ότι $\mathrm{E}(K_i)=\mathrm{Pr}(K_i)=p$, έχουμε ότι

$\mathrm{E}(K)=\mathrm{E}\left(\sum _{i=1}^n{K}_i\right)=\sum _{i=1}^n\mathrm{E}(K_i)=\sum _{i=1}^n\mathrm{Pr}(K_i)=\sum _{i=1}^{n}p=n\cdot p,$

που είναι και το αναμενόμενο πλήθος κορωνών.

Πλήθος αντιστροφών σε μία τυχαία μετάθεση

Σε μία μετάθεση $\sigma :[n]\to [n]$, ένα ζευγάρι δεικτών $(i,j)$ με $i<j$ είναι αντιστροφή αν ισχύει ότι $\sigma (i)>\sigma (j)$. Θέλουμε να υπολογίσουμε το αναμενόμενο πλήθος αντιστροφών σε μία τυχαία μετάθεση.

Έστω ότι $A_{ij}$ είναι το γεγονός ότι η $(i,j)$ είναι αντιστροφή. Τότε, λόγω συμμετρίας στις μισές μεταθέσεις, η $(i,j)$ είναι αντιστροφή και στις μισές όχι, άρα

$\mathrm{Pr}(A_{ij})=\frac{1}{2}$.

Το συνολικό πλήθος των αντιστροφών δίνεται από

$A=\sum _{i=1}^n\sum _{j=i+1}^n{A}_{ij}.$

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

$\mathrm{E}(A)=\mathrm{E}\left(\sum _{i=1}^n\sum _{j=i+1}^n{A}_{ij}\right)=\sum _{i=1}^n\sum _{j=i+1}^n\mathrm{E}(A_{ij})=\sum _{i=1}^n\sum _{j=i+1}^n\frac{1}{2}=\frac{n\cdot (n-1)}{2}\cdot \frac{1}{2}=\frac{n\cdot (n-1)}{4}.$

Εφαρμογές

Οι δείκτριες τυχαίες μεταβλητές χρησιμοποιούνται σε αρκετά στην θεωρία πιθανοτήτων. Ενδεικτικά αναφέρουμε τις εξής εφαρμογές:

• Στην απόδειξη της ανισότητας Μαρκόφ.
• Στην απόδειξη της μεθόδου δεύτερης ροπής.
• Στην ανάλυση της χρονικής πολυπλοκότητας του αλγόριθμου γρήγορης ταξινόμησης.