Στοχαστικός πίνακας

Στα μαθηματικά, στοχαστικός πίνακας (επίσης λέγεται πίνακας μετάβασης, πίνακας αντικατάστασης ή Μαρκοβιανός πίνακας) είναι ένας πίνακας $P$ με μη-αρνητικά πραγματικά στοιχεία, ο οποίος ικανοποιεί μία από τις παρακάτω συνθήκες:

Κάθε γραμμή έχει άθροισμα $1$, δηλαδή $P\cdot \mathbf {1} =\mathbf {1}$. (Δεξιά στοχαστικός πίνακας)

Κάθε στήλη έχει άθροισμα $1$, δηλαδή $\mathbf {1} ^{T}\cdot P=\mathbf {1} ^{T}$. (Αριστερά στοχαστικός πίνακας)

όπου $\mathbf {1}$ το διάνυσμα από μονάδες διαστάσεων $n\times 1$. Ο πίνακας λέγεται διπλά στοχαστικός αν είναι και δεξιά και αριστερά στοχαστικός πίνακας.

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

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

Οι παρακάτω πίνακες είναι δεξιά στοχαστικοί, καθώς το άθροισμα των στοιχείων των γραμμών είναι $1$:

${\begin{bmatrix}0.7&0.3\\0.6&0.4\end{bmatrix}},\quad {\begin{bmatrix}0.7&0.2&0.1\\0.4&0.3&0.3\\0.2&0.5&0.3\end{bmatrix}}.$

Οι παρακάτω πίνακες είναι αριστεροί στοχαστικοί, καθώς το άθροισμα των στοιχείων των στηλών είναι $1$:

${\begin{bmatrix}0.7&0.6\\0.3&0.4\end{bmatrix}},\quad {\begin{bmatrix}0.7&0.4&0.2\\0.2&0.3&0.5\\0.1&0.3&0.3\end{bmatrix}}.$

Οι παρακάτω πίνακες είναι διπλά στοχαστικοί:

${\begin{bmatrix}0.7&0.3\\0.3&0.7\end{bmatrix}},\quad {\begin{bmatrix}0.7&0.2&0.1\\0.15&0.6&0.25\\0.15&0.2&0.65\end{bmatrix}}.$

Ιδιότητες

• Κάθε δεξιός στοχαστικός πίνακας έχει ιδιοδιάνυσμα $\mathbf {1}$ με ιδιοτιμή $1$ καθώς εξ'ορισμού $P\cdot \mathbf {1} =\mathbf {1}$.
• Από αυτό προκύπτει ότι κάθε μαρκοβιανή αλυσίδα με πίνακα μετάβασης που είναι διπλά στοχαστικός έχει σταθερή κατανομή την ομοιόμορφη κατανομή.
• Το γινόμενο δύο στοχαστικών πινάκων είναι στοχαστικός.
• Οι ιδιοτιμές ενός δεξιά στοχαστικού πίνακα είναι μη-αρνητικές και $\lambda \leq 1$.

Απόδειξη  

Έστω $\lambda$ μία ιδιοτιμή του πίνακα $P$ και $x$ ένα ιδιοδιάνυσμά του. Τότε,

$Px=\lambda x$.

Κοιτώντας το $i$-οστό στοιχείο του γινομένου έχουμε ότι

$\lambda x_{i}=\sum _{k=1}^{n}P_{ik}x_{ki}\leq \sum _{k=1}^{n}P_{ik}x_{\max }=x_{\max }\cdot \sum _{k=1}^{n}P_{ik}=x_{\max }.$

Επομένως $\lambda \leq {\tfrac {x_{\max }}{x_{i}}}\leq 1$.