Η αλυσίδα Μαρκόφ (Markov chain) είναι μία στοχαστική διαδικασία κατά την οποία η μετάβαση από τη μία κατάσταση στην επόμενη εξαρτάται μόνο από την τελεύταια και όχι από τις υπόλοιπες προηγούμενες.

Μαθηματικός ορισμός

Έστω \( X = (X_t)_{t \in T} \) μια στοχαστική διαδικασία στο χώρο πιθανοτήτων \( ( \Omega, \mathcal F, P )\) και τιμές στο σύνολο καταστάσεων \( S=\{s_1,s_2, \dots\}\) . Αν για \( 0<t_1<t_2< \ldots < t_{n+1}\) και \( s_{i_k} \in S, i,k \in \mathbb{N} \) ισχύει

\( P[X_{t_{n+1}}=s_{i_{n+1}}|X_{t_1}=s_{i_1}, X_{t_2}=s_{i_2}, \ldots, X_{t_n}=s_{i_n}] =\)
\( P[X_{t_{n+1}}=s_{i_{n+1}}|X_{t_{n}}=s_{i_n}], \)

τότε η (X_t) ονομάζεται αλυσίδα Μαρκόφ.

Ο χρόνος σε μια μαρκοβιανή αλυσίδα μπορεί να είναι διακριτός ή συνεχής. Αντιθέτως το σύνολο καταστάσεων είναι διακριτό. Όταν έχουμε συνεχές σύνολο καταστάσεων μιλαμε για μαρκοβιανή διαδικασία. Ένα παράδειγμα μαρκοβιανής διαδικασίας είναι η κίνηση Μπράουν.

Σε διακριτό χρόνο, \( t \in \mathbb{N} \) , οι πιθανότητες μετάβασης από την κατάσταση \( s_i\) στην κατάσταση \( s_j\) μπορούν να περιγραφούν ως εξής:

\( p_{ij}(t)=P(X_{t+1}=s_j \mid X_t=s_i).\)

Όταν επιπρόσθετα έχουμε πεπερασμένο σύνολο καταστάσεων \( S=\{s_1, \dots , s_m \}\) μπορούμε να ορίσουμε πίνακα μετάβασης. Αν οι πιθανότητες μετάβασης είναι ανεξάρτητες του χρόνου, \( p_{ij} = p_{ij}(t)\) για κάθε t, τότε η αλυσίδα ονομάζεται ομογενής. Σε αυτή την περίπτωση ο πίνακας μετάβασης ορίζεται ως εξής:

\( (p_{ij}) = \mathbf{M}= \begin{pmatrix} p_{11} & \dots & p_{1m} \\ \vdots & \ddots & \vdots \\ p_{m1} & \dots & p_{mm} \end{pmatrix}.\)

Η πιθανότητα μετάβασης από την κατάσταση s_i στην κατάσταση s_j σε n βήματα είναι

\( p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}= M^n(i,j). \)

Μαθηματική Εγκυκλοπαίδεια

Scientific Library