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

Στην θεωρία πιθανοτήτων, δείκτρια τυχαία μεταβλητή ενός γεγονότος $A\subseteq \Omega$ του δειγματοχώρου $\Omega$, είναι η τυχαία μεταβλητή $\mathbf {1} _{A}\colon \Omega \to \mathbb {R}$, η οποία ορίζεται ως

$\mathbf {1} _{A}(\omega )={\begin{cases}1&{\text{αν }}\omega \in A,\\0&{\text{διαφορετικά}}.\end{cases}}$

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

Ιδιότητες

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

• $\operatorname {E} (\mathbf {1} _{A})=\Pr(A)$.

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

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

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

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

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

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

$K=\mathbf {1} _{K_{1}}+\ldots +\mathbf {1} _{K_{n}}$.

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

$\operatorname {E} (K)=\operatorname {E} \left(\sum _{i=1}^{n}K_{i}\right)=\sum _{i=1}^{n}\operatorname {E} (K_{i})=\sum _{i=1}^{n}\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)$ είναι αντιστροφή και στις μισές όχι, άρα

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

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

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

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

$\operatorname {E} (A)=\operatorname {E} \left(\sum _{i=1}^{n}\sum _{j=i+1}^{n}A_{ij}\right)=\sum _{i=1}^{n}\sum _{j=i+1}^{n}\operatorname {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}}.$

Εφαρμογές

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

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