Αλυσίδα Μάρκοφ

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

Μια απλή μαρκοβιανή Αλυσίδα 2 καταστάσεων

Εισαγωγή

Ο Ρώσος μαθηματικός Αντρέι Μάρκοφ

Η μαρκοβιανή αλυσίδα είναι μια στοχαστική διαδικασία με τη μαρκοβιανή ιδιότητα για ένα πεπερασμένο ή μετρήσιμο χώρο καταστάσεων . Ο όρος "Μαρκοβιανή αλυσίδα" αναφέρεται στην αλληλουχία (ή αλυσίδα) των καταστάσεων μέσω των οποίων κινείται μια τέτοια διαδικασία. Συνήθως μια Μαρκοβιανή αλυσίδα ορίζεται για μια διακριτή συλλογή χρόνων (μαρκοβιανή αλυσίδα διακριτών χρόνων), παρόλο που μερικοί συγγραφείς χρησιμοποιούν την ίδια ορολογία για να αναφερθούν σε Μαρκοβιανή αλυσίδα συνεχούς χρόνου. Η χρήση του όρου στη μεθοδολογία μαρκοβιανής αλυσίδας Μόντε Κάρλο καλύπτει περιπτώσεις όπου η διαδικασία βρίσκεται σε διακριτό χρόνο (διακριτά αλγοριθμικά βήματα) με ένα συνεχή χώρο καταστάσεων. Οι πληροφορίες που ακολουθούν επικεντρώνονται στην περίπτωση διακριτού χρόνου και διακριτού χώρου καταστάσεων.

Μια τυχαία διαδικασία διακριτού χρόνου περιλαμβάνει ένα σύστημα που βρίσκεται σε μια συγκεκριμένη κατάσταση σε κάθε βήμα, με την κατάσταση να μεταβάλλεται τυχαία μεταξύ των βημάτων. Τα βήματα συχνά θεωρούνται ως στιγμές στο χρόνο αλλά μπορούν εξίσου να αναφέρονται σε φυσική απόσταση ή οποιαδήποτε άλλη διακριτή μέτρηση: τυπικά τα βήματα είναι οι ακέραιοι ή φυσικοί αριθμοί και η τυχαία διαδικασία είναι η χαρτογράφησή τους σε καταστάσεις. Η μαρκοβιανή ιδιότητα δηλώνει ότι η δεσμευμένη πιθανότητα κατανομής του συστήματος στο επόμενο βήμα (και κατά βάση, σε όλα τα μελλοντικά βήματα) εξαρτάται μόνο από την παρούσα κατάσταση του συστήματος και όχι αθροιστικά από την κατάσταση του συστήματος σε προηγούμενα βήματα.

Καθώς το σύστημα μεταβάλλεται τυχαία, είναι γενικά αδύνατο να προβλεφθεί με βεβαιότητα η κατάσταση μιας μαρκοβιανής αλυσίδας σε ένα δεδομένο μελλοντικό σημείο. Παρ' όλα αυτά, οι στατιστικές ιδιότητες του μέλλοντος του συστήματος μπορούν να προβλεφθούν. Σε πολλές εφαρμογές, είναι αυτές οι στατιστικές ιδιότητες που είναι σημαντικές.

Οι αλλαγές κατάστασης του συστήματος ονομάζονται μεταβάσεις και οι πιθανότητες που σχετίζονται με τις διάφορες μεταβάσεις μεταξύ καταστάσεων ονομάζονται πιθανότητες μετάβασης. Η διαδικασία χαρακτηρίζεται από ένα χώρο καταστάσεων, μια μήτρα μετάβασης που περιγράφει τις πιθανότητες μιας συγκεκριμένης μετάβασης και μια αρχική κατάσταση ή αρχική κατανομή στο χώρο καταστάσεων. Κατά συνθήκη, θεωρούμε ότι όλες οι δυνατές καταστάσεις και μεταβάσεις έχουν συμπεριληφθεί στον ορισμό των διαδικασιών, ώστε υπάρχει πάντα μια επόμενη κατάσταση και η διαδικασία συνεχίζεται για πάντα.

Μια γνωστή μαρκοβιανή αλυσίδα είναι ο λεγόμενος "τυχαίος περίπατος του μεθυσμένου ναύτη", μια τυχαία διαδρομή στην αριθμητική γραμμή όπου, σε κάθε βήμα, η θέση μπορεί να αλλάξει κατά +1 ή κατά -1 με ίση πιθανότητα. Από κάθε θέση υπάρχουν δύο δυνατές μεταβάσεις, στον επόμενο ή στον προηγούμενο ακέραιο. Οι πιθανότητες μετάβασης εξαρτώνται μόνο από την παρούσα θέση, όχι από τον τρόπο με τον οποίο η θέση επετεύχθη. Για παράδειγμα, οι πιθανότητες μετάβασης από το 5 στο 4 και από το 5 στο 6 είναι 0.5 και οι δύο, και όλες οι άλλες πιθανότητες μετάβασης από το 5 είναι 0. Αυτές οι πιθανότητες είναι ανεξάρτητες από το αν το σύστημα προηγουμένως βρισκόταν στο 4 ή στο 6.

Ένα άλλο παράδειγμα είναι οι διατροφικές συνήθειες ενός πλάσματος που τρώει μόνο σταφύλια, τυρί ή μαρούλι, οι οποίες ακολουθούν τους παρακάτω κανόνες:

• Τρώει ακριβώς μία φορά την ημέρα.
• Αν σήμερα έφαγε τυρί, αύριο θα φάει μαρούλι ή σταφύλια με ίσες πιθανότητες.
• Αν σήμερα έφαγε σταφύλια, αύριο θα φάει σταφύλια με πιθανότητα 1/10, τυρί με πιθανότητα 4/10 και μαρούλι με πιθανότητα 6/10.
• Αν σήμερα έφαγε μαρούλι, δε θα φάει μαρούλι αύριο αλλά θα φάει σταφύλια με πιθανότητα 4/10 ή τυρί με πιθανότητα 6/10.

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

Μια σειρά ανεξάρτητων γεγονότων (για παράδειγμα, μια σειρά από στριψίματα νομίσματος) ικανοποιεί τον επίσημο ορισμό της μαρκοβιανής αλυσίδας. Παρ' όλα αυτά, η θεωρία συνήθως εφαρμόζεται μόνο όταν η πιθανότητα κατανομής του επομένου βήματος εξαρτάται μη-αμελητέα από την παρούσα κατάσταση.

Υπάρχουν πολλά ακόμη παραδείγματα Μαρκοβιανών αλυσίδων.

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

Μια μαρκοβιανή αλυσίδα είναι μια ακολουθία τυχαίων μεταβλητών X₁, X₂, X₃, … με τη μαρκοβιανή ιδιότητα, δηλαδή με δεδομένη την παρούσα κατάσταση, οι παλαιότερες και οι μελλοντικές καταστάσεις είναι ανεξάρτητες. Ορίζουμε

$\Pr(X_{n+1}=x|X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x|X_{n}=x_{n}).\,$

Οι πιθανές τιμές των X_i σχηματίζουν ένα αριθμήσιμο σύνολο S που ονομάζουμε χώρο καταστάσεων της αλυσίδας.

Οι μαρκοβιανές αλυσίδες συχνά περιγράφονται από έναν κατευθυνόμενο γράφο με βάρη, όπου οι κορυφές του είναι οι καταστάσεις και τα βάρη των ακμών του δίνουν τις πιθανότητες μετάβασης από τη μια κατάσταση στην άλλη.

Παραλλαγές

• Οι μαρκοβιανές αλυσίδες συνεχούς χρόνου έχουν ένα συνεχή δείκτη.
• Μαρκοβιανές αλυσίδες ομοιογενούς χρόνου (ή σταθερές μαρκοβιανές αλυσίδες) είναι διαδικασίες που ικανοποιούν

$\Pr(X_{n+1}=x|X_{n}=y)=\Pr(X_{n}=x|X_{n-1}=y)\,$

για όλα τα n. Η πιθανότητα της μετάβασης είναι ανεξάρτητη από το n.

• Μια μαρκοβιανή αλυσίδα τάξης m (ή μαρκοβιανή αλυσίδα με μνήμη m), όπου το m είναι πεπερασμένο, είναι μια διαδικασία που ικανοποιεί

${\begin{aligned}{}&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}$

Με άλλα λόγια η μελλοντική κατάσταση εξαρτάται από τις προηγούμενες m καταστάσεις. Είναι δυνατό να κατασκευάσουμε μια αλυσίδα (Y_n) από (X_n) που να έχει την κλασική μαρκοβιανή ιδιότητα παίρνοντας ως χώρο καταστάσεων το σύνολο των m-πλειαδων του X, π.χ. Y_n = (X_n, X_n−1, ..., X_n−m+1).

• Μια προσθετική μαρκοβιανή αλυσίδα τάξης m καθορίζεται από μια προσθετική πιθανότητα,

$\Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m})=\sum _{r=1}^{m}f(x_{n},x_{n-r},r).$

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

Ένα απλό παράδειγμα με χρήση κατευθυνόμενου γραφήματος για τις απεικονίσεις των μεταβάσεων μεταξύ των καταστάσεων φαίνεται στην εικόνα δεξιά. Οι καταστάσεις αντιπροσωπεύουν αν μια υποθετική χρηματιστηριακή αγορά παρουσιάζει ανοδική ή πτωτική πορεία ή αν παραμένει στάσιμη κατά τη διάρκεια μια συγκεκριμένης εβδομάδας. Με βάση την εικόνα μια ανοδική εβδομάδα ακολουθείται από μια ακόμα ανοδική εβδομάδα κατά 90%, από μια πτωτική εβδομάδα κατά 7,5% και από μια στάσιμη βδομάδα κατά 2,5%. Επισημαίνουμε τον χώρο καταστάσεων (1=ανοδική εβδομάδα, 2=πτωτική εβδομάδα, 3=στατική εβδομάδα) και ο πίνακας μετάβασης των καταστάσεων είναι ο εξής:

$P={\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}.$

Η κατανομή πάνω στις καταστάσεις μπορεί να γραφτεί ως ένα στοχαστικό διάνυσμα x με σχέση x^(n + 1) = x⁽ⁿ⁾P. Άρα αν σε χρόνο n το σύστημα είναι στη 2η κατάσταση (πτωτική), τότε 3 περίοδους μετά για χρόνο n + 3 η κατανομή θα είναι ως εξής

${\begin{aligned}x^{(n+3)}&=x^{(n+2)}P=\left(x^{(n+1)}P\right)P\\\\&=x^{(n+1)}P^{2}=\left(x^{(n)}P^{2}\right)P\\&=x^{(n)}P^{3}\\&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}^{3}\\&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.7745&0.17875&0.04675\\0.3575&0.56825&0.07425\\0.4675&0.37125&0.16125\\\end{bmatrix}}\\&={\begin{bmatrix}0.3575&0.56825&0.07425\end{bmatrix}}.\end{aligned}}$

Χρησιμοποιώντας τον πίνακα μετάβασης είναι δυνατόν να υπολογιστεί, για παράδειγμα, μακροπρόθεσμα, το ποσοστό των εβδομάδων που η αγορά μένει στάσιμη, ή ο μέσος αριθμός των εβδομάδων που θα χρειαστούν για να περάσει η αγορά από στάσιμη σε ανοδική κατάσταση. Χρησιμοποιώντας τις πιθανότητες μετάβασης, η σταθερή κατάσταση των πιθανοτήτων δείχνει ότι η αγορά θα βρίσκεται σε ανοδική φάση το 62.5% του χρόνου, 31.25% σε πτωτική φάση και 6.25 θα παραμένει σταθερή αφού:

$\lim _{N\to \infty }\,P^{N}={\begin{bmatrix}0.625&0.3125&0.0625\\0.625&0.3125&0.0625\\0.625&0.3125&0.0625\\\end{bmatrix}}$

Μια μηχανή πεπερασμένων καταστάσεων μπορεί να χρησιμοποιηθεί ως αναπαράσταση της μαρκοβιανής αλυσίδας. Θεωρώντας μια ακολουθία από ανεξάρτητα και ταυτόσημα κατανεμημένα σήματα εισόδου, αν η μηχανή είναι στην κατάσταση y για χρόνο n, τότε η πιθανότητα να κινηθεί στην κατάσταση x για χρόνο n + 1 εξαρτάται μόνο από την τωρινή κατάσταση

Μαρκοβιανές αλυσίδες

Η πιθανότητα να πάει από την κατάσταση i στην κατάσταση j σε n χρονικά βήματα είναι:

$p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,$

Και το απλό βήμα μετάβασης:

$p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,$

Για μια ομογενή-χρονικά μαρκοβιανή αλυσίδα:

$p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)\,$

και

$p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i).\,$

Οι πιθανότητες του n-βήματος μετάβασης ικανοποιούν το Θεώρημα Chapman–Kolmogorov ότι για οποιοδήποτε k που να ισχύει 0 < k < n,

$p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}$

όπου S ο χώρος καταστάσεων της μαρκοβιανής αλυσίδας

Η οριακή κατανομή Pr(X_n = x) είναι το μοίρασμα των καταστάσεων σε χρόνο n. Η αρχική κατανομή είναι Pr(X₀ = x). Η εξέλιξη της διαδικασίας για ένα χρονικό βήμα περιγράφεται από τη σχέση:

$\Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r).$

Σημείωση: Το σύμβολο (n) είναι δείκτης και όχι εκθέτης.

Κατηγοριοποίηση των καταστάσεων μίας μαρκοβιανής αλυσίδας

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

Μια κατάσταση i καλείται προσβάσιμη από την κατάσταση j (συμβολίζεται με i → j) εάν για κάποιο ακέραιο n ≥ 0 ισχύει : $\ p_{ij}^{(n)}>0.\,$. Επιτρέποντας το n να μπορεί να πάρει την τιμή του μηδενός σημαίνει ότι κάθε κατάσταση είναι προσβάσιμη από τον εαυτό της.

Μια κατάσταση i λέμε ότι επικοινωνεί με την κατάσταση j (συμβολίζεται με i ↔ j) αν ισχύει ότι i → j και j → i.

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

Μια κλάση επικοινωνίας είναι κλειστή αν η πιθανότητα να φύγουμε από την κλάση είναι μηδέν, δηλαδή αν για i που βρίσκεται στη C και για j που δε βρίσκεται στη C, η j δεν είναι προσβάσιμη από την i. Διαφορετικά η κλάση λέγεται ανοιχτή.

Μια κατάσταση i τη λέμε βασική ή τελική αν για κάθε j που ισχύει i → j ισχύει και j → i. Μια κατάσταση i που δεν είναι βασική τη λέμε μη βασική

Τέλος, μια μαρκοβιανή αλυσίδα λέμε ότι είναι μη υποβιβάσιμη αν ο χώρος καταστάσεων είναι μια μοναδική κλάση, δηλαδή είναι δυνατόν να πάμε από κάθε κατάσταση σε κάθε άλλη κατάσταση.

Περιοδικότητα

Μια κατάσταση i έχει περίοδο k αν κάθε επιστροφή στην κατάσταση i μπορεί να συμβεί μόνο σε πολλαπλάσια του k χρονικά βήματα. Επισήμως η περίοδος μιας κατάστασης ορίζεται ως

$k=\operatorname {gcd} \{n:\Pr(X_{n}=i|X_{0}=i)>0\}$

(όπου "gcd" είναι ο μέγιστος κοινός διαιρέτης. Σημειώστε ότι μπορεί μια κατάσταση να έχει περίοδο k, αλλά να μην είναι δυνατό να επιστρέψουμε σε αυτήν σε k βήματα. Για παράδειγμα, ας θεωρήσουμε ότι είναι δυνατόν να επιστρέψουμε στην κατάσταση σε {6, 8, 10, 12, ...} χρονικά βήματα; Η περίοδος k θα είναι 2, αν και το 2 δεν εμφανίζεται σε αυτή τη λίστα.

Αν k = 1, τότε η κατάσταση λέμε ότι είναι απεριοδική: επιστροφές στην κατάσταση μπορούν να συμβούν σε ακανόνιστους χρόνους. Με αλλά λόγια, μια κατάσταση i είναι απεριοδική αν υπάρχει κάποιο n τέτοιο ώστε για όλα τα n' ≥ n να ισχύει

$\Pr(X_{n'}=i|X_{0}=i)>0.$

Διαφορετικά (k > 1), η κατάσταση λέμε ότι είναι περιοδική με περίοδο k. Μια μαρκοβιανή αλυσίδα είναι απεριοδική αν κάθε κατάσταση της είναι απεριοδική. Μια μη υποβιβάσιμη μαρκοβιανή Αλυσίδα χρειάζεται μόνο μια απεριοδική κατάσταση ώστε να πούμε ότι όλες οι καταστάσεις είναι απεριοδικές.

Κάθε κατάσταση ενός διήμερου γραφήματος έχει για περίοδο έναν ζυγό αριθμό.

Επαναληπτικότητα

Μια κατάσταση i λέμε ότι είναι παροδική όταν, αν ξεκινήσουμε από την κατάσταση i, υπάρχει μια μη-μηδενική πιθανότητα να μη γυρίσουμε ποτέ στην κατάσταση i. Επισήμως θεωρούμε ότι η τυχαία μεταβλητή T_i είναι η πρώτη επιστροφή στην κατάσταση i :

$T_{i}=\inf\{n\geq 1:X_{n}=i|X_{0}=i\}.$

Ο αριθμός

$f_{ii}^{(n)}=\Pr(T_{i}=n)$

Είναι η πιθανότητα να γυρίσουμε στην κατάσταση i για πρώτη φορά μετά από n βήματα. Άρα, η κατάσταση i είναι παροδική όταν

$\Pr(T_{i}<{\infty })=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1.$

Η κατάσταση i λέμε ότι είναι επαναληπτική αν δεν είναι παροδική. Οι επαναληπτικές καταστάσεις έχουν πάντα πεπερασμένο χρόνο πρώτης επιστροφής.

Μέσος Χρόνος Επανάληψης

Ακόμα και αν ο πρώτος χρόνος επιστροφής είναι πάντα πεπερασμένος , δεν είναι απαραίτητο ότι θα έχει αριθμό πεπερασμένης άξιας. Ο Μέσος Χρόνος Επανάληψης για την κατάσταση i είναι ο αναμενόμενος χρόνος επιστροφής M_i:

$M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.\,$

Η κατάσταση i είναι θετικά επαναληπτική αν το M_i είναι πεπερασμένο; αλλιώς, η κατάσταση i είναι μηδενικά επαναληπτική.

Αναμενόμενος Αριθμός Επισκέψεων

Έχει αποδειχτεί ότι μια κατάσταση i είναι επαναληπτική όταν και μόνο όταν ο αναμενόμενος αριθμός επισκέψεων σε αυτή την κατάσταση είναι μη πεπερασμένος, π.χ.

$\sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .$

Καταστάσεις Απορρόφησης

Μια κατάσταση i ονομάζεται απορροφητική αν είναι αδύνατο να φύγουμε από αυτή την κατάσταση. Άρα, η κατάσταση i είναι απορροφητική όταν και μόνο όταν

$p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.$

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

Εργοδικότητα

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

Έχει αποδειχτεί ότι μια πεπερασμένη μη υποβιβάσιμη μαρκοβιανή αλυσίδα είναι εργοδική αν έχει μια απεριοδική κατάσταση. Ένα μαρκοβιανό μοντέλο έχει την εργοδική ιδιότητα αν υπάρχει ένας πεπερασμένος αριθμός N τέτοιος ώστε κάθε κατάσταση μπορεί να φτάσει σε κάθε άλλη κατάσταση σε ακριβώς N βήματα. Σε περίπτωση που έχουμε ένα πλήρως συνδεδεμένο πίνακα μετάβασης όπου όλες οι μεταβάσεις έχουν μη-μηδενική πιθανότητα, αυτή η προϋπόθεση ικανοποιείται για N=1. Ένα μοντέλο με παραπάνω από μια καταστάσεις και με μόνο μια πιθανή μετάβαση σε κάθε κατάσταση δε μπορεί να είναι εργοδικό.

Ανάλυση σταθερών καταστάσεων και περιορισμού διανομών

Αν έχουμε μια ομογενής μαρκοβιανή αλυσίδα, που η διαδικασία της περιγράφεται από έναν ενιαίο και ανεξάρτητο από το χρόνο πίνακα $p_{ij}$, τότε το διάνυσμα ${\boldsymbol {\pi }}$ ονομάζεται στάσιμη ή αναλλοίωτη κατανομή αν $\forall j\in S$ ισχύει ότι

$0\leq \pi _{j}\leq 1.$

$\sum _{j\in S}\pi _{j}=1.$

$\pi _{j}=\sum _{i\in S}\pi _{i}p_{ij}.$

Μια μη υποβιβάσιμη αλυσίδα έχει μία σταθερή κατανομή αν και μόνο αν όλες οι καταστάσεις της είναι θετικά επαναληπτικές. Σε αυτή την κατάσταση, το π είναι μοναδικό και εξαρτάται από τον αναμενόμενο χρόνο επιστροφής:

$\pi _{j}={\frac {C}{M_{j}}}\,,$

Όπου το $C$ είναι μια ομαλοποιητική σταθερά. Επιπλέον, αν η Αλυσίδα είναι και μη υποβιβάσιμη και απεριοδική, τότε για κάθε i και j, ισχύει ότι

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {C}{M_{j}}}.$

Προσέξτε ότι δεν υπάρχει καμία υπόθεση για την αρχική κατανομή; Η αλυσίδα συγκλίνει στην στάσιμη κατανομή ανεξάρτητα από το πώς ξεκίνησε. Ένα τέτοιο διάνυσμα π λέγεται στάσιμη κατανομή της αλυσίδας.

Αν μια αλυσίδα έχει παραπάνω από μια κλειστές κλάσεις, τότε η σταθερή κατανομή της δεν θα είναι μοναδική. Όμως, αν η κατάσταση j είναι απεριοδική, τότε

$\lim _{n\rightarrow \infty }p_{jj}^{(n)}={\frac {C}{M_{j}}}$

Και για κάθε άλλη κατάσταση i, έστω f_ij η πιθανότητα ότι η αλυσίδα φτάνει κάποια στιγμή στην κατάσταση j αν ξεκινήσει από την κατάσταση i,

$\lim _{n\rightarrow \infty }p_{ij}^{(n)}=C{\frac {f_{ij}}{M_{j}}}.$

Αν η κατάσταση i είναι απεριοδική με περίοδο k > 1 τότε το όριο

$\lim _{n\rightarrow \infty }p_{ii}^{(n)}$

Δεν υπάρχει, αν και, το όριο

$\lim _{n\rightarrow \infty }p_{ii}^{(kn+r)}$

Υπάρχει για κάθε ακέραιο  r.

Ανάλυση σταθερών καταστάσεων και οι μη-ομογενείς μαρκοβιανες αλυσίδες

Μια μαρκοβιανη αλυσίδα δεν είναι απαραίτητο να είναι χρονικά ομογενής ώστε να έχει έναν στάσιμη κατανομή. Αν υπάρχει μια πιθανότητα κατανομής πάνω στις καταστάσεις ${\boldsymbol {\pi }}$ τέτοια ώστε

$\pi _{j}=\sum _{i\in S}\pi _{i}\,\Pr(X_{n+1}=j\mid X_{n}=i)$

Για κάθε κατάσταση j και κάθε χρόνο n τότε ${\boldsymbol {\pi }}$ είναι μία στάσιμη κατανομή της μαρκοβιανής αλυσίδας. Κάτι τέτοιο μπορεί να συμβεί στις μεθοδολογίες της μαρκοβιανής αλυσίδας Μόντε Κάρλο σε περιπτώσεις όπου χρησιμοποιούνται πολλοί διαφορετικοί πίνακες μετάβασης.

Πεπερασμένοι Χώροι Καταστάσεων

Αν ο χώρος καταστάσεων είναι πεπερασμένος, οι πιθανότητες μετάβασης μπορούν να αναπαρασταθούν από έναν πίνακα που λέγεται πίνακας μετάβασης, με το (i, j)στο στοιχείο του P ίσο με

$p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i).\,$

Αφού κάθε σειρά του P έχει άθροισμα 1 και όλες οι καταστάσεις είναι μη-μηδενικές τότε ο P είναι ένας σωστός στοχαστικός πινάκας.

Χρονικά ομοιογενείς μαρκοβιανές αλυσίδες με πεπερασμένο χώρο καταστάσεων

Αν μια μαρκοβιανή αλυσίδα είναι χρονικά-ομοιογενής, τότε ο πίνακας μετάβασης P παραμένει ίδιος μετά από κάθε βήμα, όποτε οι πιθανότητες του k-βήματος μετάβασης μπορούν να υπολογιστούν σαν την k-οστή δύναμη του πίνακα μετάβασης, P^k.

Η σταθερή κατανομή π είναι ένα διάνυσμα γραμμής, του οποίου οι καταχωρήσεις είναι μη-αρνητικές και έχουν άθροισμα 1 (δηλαδή είναι ένα διάνυσμα πιθανότητας, που ικανοποιεί την εξίσωση

$\pi =\pi \mathbf {P} .$

Με αλλά λόγια, η σταθερή κατανομή π είναι ένα κανονικοποιημένο (δηλαδή όλες οι καταχωρήσεις του έχουν άθροισμα 1) αριστερό ιδιοδιάνυσμα του πίνακα μετάβασης που σχετίζεται με την ιδιοτιμή 1.

Διαφορετικά, το π μπορεί να θεωρηθεί ένα σταθερό σημείο του γραμμικού (και άρα συνεχούς) μετασχηματισμού της μονάδας που σχετίζεται με τον πίνακα μετάβασης P. Όπως κάθε συνεχής μετασχηματισμός της απλής μονάδας έχει ένα σταθερό σημείο, μία στάσιμη κατανομή πάντα υπάρχει, αλλά δεν είναι δεδομένο ότι είναι μοναδική. Όμως, αν η μαρκοβιανή αλυσίδα είναι μη υποβιβάσιμη και απεριοδική, τότε υπάρχει ένας μοναδική στάσιμη κατανομή π. Επιπλέον σε αυτή την περίπτωση το P^k συγκλίνει σε ένα πρώτου βαθμού πίνακα που κάθε του σειρά είναι η στάσιμη κατανομή π, δηλαδή,

$\lim _{k\rightarrow \infty }\mathbf {P} ^{k}=\mathbf {1} \pi$

όπου 1 είναι το διάνυσμα στήλης με όλες τις καταχωρήσεις ίσες με 1. Αυτό το ξέρουμε από το Θεώρημα Perron-Frobenius. Αν, κάτω από οποιεσδήποτε συνθήκες, βρεθεί το $\scriptstyle \lim _{k\to \infty }\mathbf {P} ^{k}$ τότε η στάσιμη κατανομή της μαρκοβιανής αλυσίδας μπορεί εύκολα να οριστεί από κάθε εναρκτήρια κατανομή, όπως θα εξηγηθεί παρακάτω.

Για κάποιους στοχαστικούς πίνακες P, το όριο $\scriptstyle \lim \limits _{k\to \infty }\mathbf {P} ^{k}$ δεν υπάρχει, όπως φαίνεται από το παρακάτω παράδειγμα:

${\begin{pmatrix}0&1\\1&0\end{pmatrix}}.$

Επειδή υπάρχουν αρκετές διαφορετικές ειδικές περιπτώσεις να εξεταστούν, η διαδικασία της εύρεσης αυτού του ορίου (αν υπάρχει) είναι αρκετά χρονοβόρα. Όμως υπάρχουν αρκετές τεχνικές που μπορούν να μας βοηθήσουν στην εύρεση αυτού του ορίου. Έστω P είναι ένας n×n πίνακας, και ορίζουμε $\scriptstyle \mathbf {Q} =\lim _{k\to \infty }\mathbf {P} ^{k}.$

Ισχύει πάντα ότι:

$\mathbf {QP} =\mathbf {Q} .$

Αφαιρώντας Q και από τις δύο πλευρές και αναλύοντας σε παράγοντες στη συνέχεια παίρνουμε

$\mathbf {Q} (\mathbf {P} -\mathbf {I} _{n})=\mathbf {0} _{n,n},$

όπου I_n ο μοναδιαίος πίνακας μεγέθους n, και 0_n,n ο μηδενικός πίνακας μεγέθους n×n. Όταν πολλαπλασιάζουμε στοχαστικούς πίνακες πάντα το αποτέλεσμα μας δίνει έναν καινούργιο στοχαστικό πίνακα, άρα ο Q είναι ένας στοχαστικός πίνακας. Αρκετές φορές είναι αρκετό να χρησιμοποιήσουμε αυτή την εξίσωση πινάκων και το στοιχειό ότι ο Q είναι ένας στοχαστικός πίνακας για να λύσουμε ως προς Q. Συμπεριλαμβανόμενου του δεδομένου ότι το άθροισμα κάθε σειράς του P είναι 1, υπάρχουν n+1 εξισώσεις για να βρούμε n αγνώστους, όποτε είναι πιο εύκολο υπολογιστικά αν από τη μια πλευρά επιλέξουμε μία σειρά του Q και αντικαταστήσουμε κάθε ένα από τα στοιχειά του με 1, και από την άλλη αντικαταστήσουμε το αντίστοιχο στοιχείο στο μηδενικό διάνυσμα 0, και μετά πολλαπλασιάσουμε από αριστερά το τελικό διάνυσμα με το αντίστροφο του αρχικού πίνακα ώστε να βρούμε το Q.

Ταχύτητα σύγκλισης προς την στάσιμη κατανομή

Όπως αναφέρθηκε προηγουμένως, από την εξίσωση $\mathbf {\pi } =\mathbf {\pi P}$, (αν υπάρχει) η σταθερή κατανομή π είναι ένα αριστερό ιδιοδιάνυσμα του στοχαστικού πίνακα P. Έτσι, υποθέτοντας ότι ο P διαγωνιοποιείται ή ισοδύναμα ότι ο P έχει n γραμμικά ανεξάρτητα ιδιοδιανύσματα, η ταχύτητα της σύγκλισης ορίζεται ως εξής. Για πίνακες που δεν διαγωνιοποιούνται, μπορούμε να ξεκινήσουμε με την κανονική μορφή του Jordan (σχεδόν διαγώνια μορφή) του P και να προχωρήσουμε με μια λίγο πιο περίπλοκη σειρά επιχειρημάτων αλλά με παρόμοιο τρόπο. Έστω U είναι ο πίνακας των ιδιοδιανυσμάτων όπου κάθε στήλη είναι ένα αριστερό ιδιοδιάνυσμα του P και έστω ότι Σ είναι ο διαγώνιος πίνακας των αριστερών ιδιοδιανυσμάτων του P, π.χ. Σ = diag(λ₁,λ₂,λ₃,...,λ_n). Τότε, με φασματική αποσύνθεση

$\mathbf {P} =\mathbf {U\Sigma U} ^{-1}.$

Έστω ότι τα ιδιοδιανύσματα αριθμούνται με τέτοιο τρόπο που 1=|λ₁|>|λ₂|≥|λ₃|≥...≥|λ_n|. Αφού ο P κατά-σειρά στοχαστικός πίνακας, η μεγαλύτερη ιδιοτιμή του είναι 1. Αν υπάρχει μία στάσιμη κατανομή, τότε η μεγαλύτερη ιδιοτιμή και το αντίστοιχο ιδιοδιάνυσμα είναι επίσης μοναδικό (επειδή δεν υπάρχει άλλο π που να λύνει την εξίσωση της στάσιμης κατανομής). Έστω u_i είναι η iστη στήλη του πίνακα U, π.χ. u_i είναι το αριστερό ιδιοδιάνυσμα του P που αντιστοιχεί στο λ_i. Επίσης έστω x είναι ένα αυθαίρετο μήκους-n διάνυσμα γραμμής στη διάρκεια των ιδιοδιανυσμάτων u_i, δηλαδή

$\mathbf {x} ^{T}=\sum _{i=1}^{n}a_{i}\mathbf {u} _{i}$

Για κάποιο ζεύγος a_i∈ℝ. Αν αρχίσουμε να πολλαπλασιάζουμε τον P με x από αριστερά και συνεχίσουμε αυτή τη διαδικασία με τα αποτελέσματα, στο τέλος θα πάρουμε μία στάσιμη κατανομή π. Με αλλά λόγια π = u_i ← xPPP...P = xP^k όπου το k τείνει στο άπειρο. Αυτό σημαίνει ότι

$\mathbf {\pi } ^{(k)}=\mathbf {x} (\mathbf {U\Sigma U} ^{-1})(\mathbf {U\Sigma U} ^{-1})...(\mathbf {U\Sigma U} ^{-1})$

$=\mathbf {xU\Sigma } ^{k}\mathbf {U} ^{-1}$

αφού UU^-1 = I ο μοναδιαίος πίνακας και η δύναμη ενός διαγώνιου πίνακα είναι επίσης ένας διαγώνιος πίνακας, όπου κάθε στοιχειό του φτάνει σε αυτή τη δύναμη.

$=(a_{1}\mathbf {u} _{1}^{T}+a_{2}\mathbf {u} _{2}^{T}+...+a_{n}\mathbf {u} _{n}^{T})\mathbf {U\Sigma } ^{k}\mathbf {U} ^{-1},$

$=a_{1}\lambda _{1}^{k}\mathbf {u} _{1}+a_{2}\lambda _{2}^{k}\mathbf {u} _{2}+...+a_{n}\lambda _{n}^{k}\mathbf {u} _{n},$

Αφού τα ιδιοδιανύσματα είναι ορθοκανονικά. Στη συνεχεία: $=\lambda _{1}^{k}\left\{a_{1}\mathbf {u} _{1}+a_{2}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{2}+a_{3}\left({\frac {\lambda _{3}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{3}+...+a_{n}\left({\frac {\lambda _{n}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{n}\right\}.$

Αφού π = u₁, π^(k) τείνει στο π όσο το k τείνει στο άπειρο με εκθετική ταχύτητα τάξης λ₂/λ₁. Αυτό ακολουθεί διότι |λ₂|≥|λ₃|≥...≥|λ_n|, άρα λ₂/λ₁ είναι ο κυρίαρχος Όρος.

Εφαρμογές

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

Φυσική

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

Χημεία

Michaelis-Menten kinetics. Κινητική Michaelis-Menten. Το ένζυμο (Ε) προσδένεται στο υπόστρωμα (S) και παράγει ένα προϊόν (P). Κάθε αντίδραση είναι μια μετάβαση κατάστασης σε μια μαρκοβιανή αλυσίδα.

Η χημεία είναι συχνά ένας τομέας όπου οι μαρκοβιανές αλυσίδες και οι μαρκοβιανές καταστάσεις συνεχούς χρόνου είναι ιδιαίτερα χρήσιμες επειδή αυτά τα απλά φυσικά συστήματα τείνουν να ικανοποιούν αρκετά καλά τη μαρκοβιανή ιδιότητα. Το κλασικό μοντέλο της ενζυμικής δραστηριότητας, η κινητική Michaelis-Menten, μπορεί να θεωρηθεί ως μια μαρκοβιανή αλυσίδα, όπου σε κάθε βήμα η αντίδραση προχωράει προς κάποια κατεύθυνση. Ενώ η κινητική Michaelis-Menten είναι αρκετά απλή, πολύ περισσότερο πολύπλοκα δίκτυα αντιδράσεων μπορούν επίσης να μοντελοποιηθούν με μαρκοβιανές αλυσίδες. Ένας αλγόριθμος που βασίζεται σε μαρκοβιανή αλυσίδα χρησιμοποιήθηκε επίσης για να εστιάσει τη βασιζόμενη σε θραύσματα ανάπτυξη χημικών in silico προς μια επιθυμητή τάξη ενώσεων όπως φάρμακα ή φυσικά προϊόντα. Καθώς ένα στοιχείο αναπτύσσεται, ένα θραύσμα επιλέγεται από το εν τη γενέσει στοιχείο ως η "παρούσα" κατάσταση. Δεν έχει επίγνωση του παρελθόντος του (δε γνωρίζει τι βρίσκεται ήδη δεσμευμένο σε αυτό). Στη συνέχεια, μεταβαίνει στην επόμενη κατάσταση όταν ένα θραύσμα προσκολλάται σε αυτό. Οι πιθανότητες μετάβασης διευθύνονται από βάσεις δεδομένων αυθεντικών τάξεων ενώσεων.

Επίσης, η ανάπτυξη (και σύνθεση) συμπολυμερών μπορεί να μοντελοποιηθεί χρησιμοποιώντας μαρκοβιανές αλυσίδες. Με βάση το κλάσμα αντίδρασης των μονομερών που αποτελούν την αναπτυσσόμενη πολυμερική αλυσίδα, η σύνθεση της αλυσίδας μπορεί να υπολογισθεί (π.χ. αν τα μονομερή τείνουν να προστίθεται με εναλλασσόμενο τρόπο ή με μακριές σειρές του ίδιου μονομερούς).

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

Δοκιμές

Πολλοί θεωρητικοί έχουν προτείνει την ιδέα της στατιστικής δοκιμής μαρκοβιανής αλυσίδας (Marcov chain statistical test-MCST), μια μέθοδο σύνδεσης μαρκοβιανών αλυσίδων προς σχηματισμό ενός "μαρκοβιανού παπλώματος", τοποθετώντας αυτές τις αλυσίδες σε διάφορα αναδρομικά στρώματα και παράγοντας πιο αποτελεσματικά σετ δοκιμών -δείγματα- ως αντικατάσταση των εξαντλητικών δοκιμών. Οι στατιστικές δοκιμές μαρκοβιανής αλυσίδας έχουν επίσης εφαρμογές σε χρονικά δίκτυα που βασίζονται σε καταστάσεις: το άρθρο των Chilukuri και συνεργατών με τίτλο "Δίκτυα Συλλογισμού Χρονικής Αβεβαιότητας για Συγχώνευση Στοιχείων με Εφαρμογές στον Εντοπισμό και στην Παρακολούθηση Αντικειμένων" (ScienceDirect) δίνει ένα υπόβαθρο και μια περίπτωση μελέτης για την εφαρμογή των MCST σε ευρύτερο φάσμα εφαρμογών.

Επιστήμες Πληροφοριών

Οι μαρκοβιανές αλυσίδες χρησιμοποιούνται ευρέως στην επεξεργασία πληροφοριών. Η διάσημη εργασία του Κλοντ Σάνον από το 1948 "Μια μαθηματική θεωρία επικοινωνίας", η οποία σε ένα βήμα δημιούργησε το πεδίο της θεωρίας πληροφοριών, ξεκινάει παρουσιάζοντας την έννοια της εντροπίας μέσω μαρκοβιανής μοντελοποίησης της Αγγλικής γλώσσας. Τέτοια ιδανικά μοντέλα μπορούν να συλλάβουν πολλές από τις στατιστικές ανωμαλίες των συστημάτων. Ακόμη και χωρίς περιγραφή της πλήρης δομής του συστήματος, τέτοια μοντέλα σημάτων μπορούν να κάνουν δυνατή την πολύ αποτελεσματική συμπίεση δεδομένων μέσω τεχνικών κωδικοποίησης εντροπίας όπως η αριθμητική κωδικοποίηση. Επίσης επιτρέπουν αποτελεσματική εκτίμηση καταστάσεων και αναγνώριση προτύπων. Οι μαρκοβιανές αλυσίδες παίζουν επίσης σημαντικό ρόλο στην ενισχυτική μάθηση.

Οι μαρκοβιανές αλυσίδες είναι επιπλέον η βάση για τα κρυμμένα μαρκοβιανά μοντέλα, που αποτελούν σημαντικό εργαλείο σε ποικίλα πεδία όπως τηλεφωνικά δίκτυα (που χρησιμοποιούν τον αλγόριθμο Βίτερμπι για διόρθωση σφαλμάτων), αναγνώριση λόγου και βιοπληροφορική.

Θεωρία Σειρών

Οι μαρκοβιανές αλυσίδες είναι η βάση για την αναλυτική μεταχείριση σειρών (θεωρία σειρών). Ο Άγκνερ Κράρουπ Έρλανγκ ξεκίνησε το θέμα το 1917. Αυτό τις κάνει σημαντικές για τη βελτιστοποίηση της απόδοσης τηλεπικοινωνιακών δικτύων, όπου τα μηνύματα συχνά ανταγωνίζονται για περιορισμένους πόρους (όπως εύρος ζώνης).

Εφαρμογές του Διαδικτύου

Πώς οι μαρκοβιανές αλυσίδες μπορούν να χρησιμοποιηθούν για τον υπολογισμό του PageRank

Η κατάταξη μιας ιστοσελίδας με βάση τον αλγόριθμο PageRank, όπως χρησιμοποιείται από τη Google, ορίζεται από μια Μαρκοβιανή αλυσίδα. Είναι η πιθανότητα να βρίσκεσαι στη σελίδα $i$ στη στατική κατανομή της ακόλουθης μαρκοβιανής αλυσίδας για όλες τις (γνωστές) ιστοσελίδες. Αν $N$ είναι ο αριθμός των γνωστών ιστοσελίδων και μια σελίδα $i$ εχει $k_{i}$ συνδέσμους σε αυτή, τότε έχει πιθανότητα μετάβασης ${\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}$ για όλες της σελίδες που συνδέονται με αυτήν και ${\frac {1-\alpha }{N}}$ for για όλες τις σελίδες που δε συνδέονται με αυτήν. Η παράμετρος $\alpha$ θεωρείται περίπου 0,85.

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

Στατιστική

Μέθοδοι μαρκοβιανών αλυσίδων έχουν επίσης γίνει πολύ σημαντικές για την παραγωγή ακολουθιών τυχαίων αριθμών για να αποδώσουν με ακρίβεια πολύ περίπλοκες επιθυμητές κατανομές πιθανοτήτων, μέσω μιας διαδικασίας που λέγεται μαρκοβιανή αλυσίδα Μόντε Κάρλο. Πρόσφατα, αυτό έχει οδηγήσει σε επανάσταση όσον αφορά στην πρακτικότητα μεθόδων Μπεϋσιανών συμπερασμάτων, επιτρέποντας ένα ευρύ φάσμα μεταγενέστερων κατανομών να προσομοιωθούν και οι παράμετροί τους να βρεθούν αριθμητικά.

Οικονομία και Οικονομικά

Οι Μαρκοβιανές αλυσίδες χρησιμοποιούνται στα Χρηματοοικονομικά για να μοντελοποιήσουν μια ποικιλία διαφορετικών φαινομένων, συμπεριλαμβανομένων τιμών κεφαλαίων και πτώσεις αγορών. Το πρώτο χρηματοοικονομικό μοντέλο που χρησιμοποίησε μαρκοβιανή αλυσίδα ήταν του Πρασάντ και συνεργατών το 1974. Ένα άλλο ήταν το μοντέλο αλλαγής καθεστώτος του Τζέιμς Ντ. Χάμιλτον (1989), στο οποίο μια μαρκοβιανή αλυσίδα χρησιμοποιείται για να μοντελοποιήσει αλλαγές μεταξύ περιόδων υψηλής μεταβλητότητας και χαμηλής μεταβλητότητας επιστροφής κεφαλαίων. Ένα πιο πρόσφατο παράδειγμα είναι το πολυκλασματικό μαρκοβιανό μοντέλο αλλαγής τιμολόγησης κεφαλαίων, που βασίζεται στην ευκολία των προηγούμενων μοντέλων αλλαγής καθεστώτων. Χρησιμοποιεί μια τυχαία μακριά μαρκοβιανή αλυσίδα για να οδηγήσει τα επίπεδα μεταβλητότητας επιστροφών κεφαλαίου. Η δυναμική μακροοικονομία ευρέως χρησιμοποιεί μαρκοβιανές αλυσίδες. Ένα παράδειγμα είναι η χρήση τους για την εξωγενή μοντελοποίηση τιμών δικαιοσύνης (μετοχών) σε μια ρύθμιση γενικής ισορροπίας.

Κοινωνικές Επιστήμες

Οι μαρκοβιανές αλυσίδες χρησιμοποιούνται γενικά στην περιγραφή επιχειρημάτων που εξαρτώνται από τη διαδρομή, όπου οι παρούσες δομικές διαμορφώσεις διέπουν τα μελλοντικά αποτελέσματα. Ένα παράδειγμα είναι η αναδιατύπωση της ιδέας, αρχικά λόγω του "Κεφαλαίου" του Καρλ Μαρξ, συνδέοντας την οικονομική ανάπτυξη με την άνοδο του καπιταλισμού. Στην παρούσα έρευνα, είναι συνηθισμένη η χρήση μαρκοβιανής αλυσίδας για να μοντελοποιήσει πώς όταν μια χώρα φτάσει ένα συγκεκριμένο επίπεδο οικονομικής ανάπτυξης, η διαμόρφωση δομικών παραγόντων, όπως το μέγεθος της εμπορικής αστικής τάξης, η αναλογία της αστικής προς την αγροτική κατοικία, ο ρυθμός πολιτικής κινητοποίησης κτλ. θα οδηγήσει σε υψηλότερη πιθανότητα μετάβασης από απολυταρχικό σε δημοκρατικό καθεστώς.

Μαθηματική Βιολογία

Οι μαρκοβιανές αλυσίδες έχουν επίσης πολλές εφαρμογές σε βιολογικά μοντέλα, κυρίως πληθυσμιακές διαδικασίες, με χρησιμότητα στη μοντελοποίηση διαδικασιών που είναι (τουλάχιστον) ανάλογες με βιολογικούς πληθυσμούς. Η μήτρα Λέσλι είναι ένα παράδειγμα, παρόλο που μερικές από τις καταχωρίσεις δεν είναι πιθανότητες (μπορεί να είναι μεγαλύτερες από 1). Ένα άλλο παράδειγμα είναι η μοντελοποίηση του κυτταρικού σχήματος σε διαιρούμενα φύλλα επιθηλιακών κυττάρων. Ένα ακόμη παράδειγμα είναι η κατάσταση ιοντικών καναλιών στις κυτταρικές μεμβράνες.

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

Γενετική

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

Παιχνίδια

Οι μαρκοβιανές αλυσίδες μπορούν να χρησιμοποιηθούν για να μοντελοποιήσουν πολλά τυχερά παιχνίδια. Τα παιδικά παιχνίδια "Φιδάκι" και "Γκρινιάρης", για παράδειγμα, αντιπροσωπεύονται με ακρίβεια από μαρκοβιανές αλυσίδες. Σε κάθε γύρο, ο παίκτης ξεκινά σε μια δεδομένη κατάσταση (σε ένα δεδομένο τετράγωνο) και από εκεί έχει καθορισμένες πιθανότητες να μετακινηθεί σε συγκεκριμένες άλλες καταστάσεις (τετράγωνα).

Μουσική

Μαρκοβιανές αλυσίδες χρησιμοποιούνται στην αλγοριθμική σύνθεση μουσικής, ιδιαίτερα σε προγράμματα λογισμικού όπως CSound, Max ή SuperCollider. Σε μια πρώτης τάξης αλυσίδα, οι καταστάσεις του συστήματος γίνονται νότες ή τιμές τόνου και κατασκευάζεται ένα διάνυσμα πιθανότητας για κάθε νότα, συμπληρώνοντας μια μήτρα πιθανοτήτων μετάβασης (βλέπε παρακάτω). Ένας αλγόριθμος κατασκευάζεται για την παραγωγή και απόδοση τιμών νοτών βασιζόμενος σε στάθμιση της μήτρας μετάβασης, που θα μπορούσε να είναι τιμές νοτών MIDI, συχνότητα (Hz) ή οποιαδήποτε άλλη επιθυμητή μέτρηση.

Πίνακας 1ης Τάξης

Νότα	A	C♯	E♭
A	0.1	0.6	0.3
C♯	0.25	0.05	0.7
E♭	0.7	0.3	0

Πίνακας 2ης Τάξης

Νότα	A	D	G
AA	0.18	0.6	0.22
AD	0.5	0.5	0
AG	0.15	0.75	0.1
DD	0	0	1
DA	0.25	0	0.75
DG	0.9	0.1	0
GG	0.4	0.4	0.2
GA	0.5	0.25	0.25
GD	1	0	0

Μια δεύτερης τάξης μαρκοβιανής αλυσίδα μπορεί να εισαχθεί θεωρώντας την παρούσα κατάσταση και επίσης την προηγούμενη κατάσταση, όπως φαίνεται στο δεύτερο πίνακα. Ψηλότερες, νιοστής τάξης αλυσίδες τείνουν να ομαδοποιούν συγκεκριμένες νότες μαζί ενώ περιστασιακά break off σε άλλα πρότυπα και αλληλουχίες. Αυτές οι αλυσίδες ψηλότερης τάξης τείνουν να παράγουν αποτέλεσμα με μια αίσθηση φραστικής δομής αντί για την "άσκοπη περιπλάνηση" που παράγεται από ένα σύστημα πρώτης τάξης.

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

Συνήθως τα μουσικά συστήματα χρειάζεται να επιβάλλουν συγκεκριμένα όρια ελέγχου στις πεπερασμένου μήκους αλληλουχίες που παράγουν αλλά τα όρια ελέγχου δεν είναι συμβατά με μαρκοβιανά μοντέλα, καθώς προκαλούν εξαρτήσεις μεγάλης εμβέλειας που παραβιάζουν τη μαρκοβιανή υπόθεση περιορισμένης μνήμης. Για να ξεπεραστεί αυτός ο περιορισμός, μια νέα προσέγγιση έχει προταθεί.

Μπέιζμπολ

Μοντέλα μαρκοβιανών αλυσίδων έχουν χρησιμοποιηθεί σε προηγμένες αναλύσεις baseball από το 1960, παρόλο που η χρήση τους είναι ακόμη σπάνια. Κάθε half-inning ενός παιχνιδιού μπέιζμπολ αντιστοιχεί στην κατάσταση μαρκοβιανής αλυσίδας όταν ληφθούν υπόψη ο αριθμός των runners και outs. Κατά τη διάρκεια οποιουδήποτε at-bat, υπάρχουν 24 πιθανοί συνδυασμοί αριθμών outs και θέσης των runners. Ο Μαρκ Πάνκιν έδειξε ότι μοντέλα μαρκοβιανών αλυσίδων μπορούν να χρησιμοποιηθούν για την εκτίμηση runs που δημιουργούνται και για τους δύο ανεξάρτητους παίκτες όπως και για την ομάδα. Επίσης συζητά διάφορα είδη στρατηγικών και όρων παιχνιδιού: πώς τα μοντέλα μαρκοβιανών αλυσίδων έχουν χρησιμοποιηθεί για την ανάλυση στατιστικών για καταστάσεις παιχνιδιού όπως bunting και base stealing και διαφορές παιχνιδιού επί χόρτου ή astroturf.

Μαρκοβιανή γεννήτρια κειμένου

Μαρκοβιανές διαδικασίες μπορούν επίσης να χρησιμοποιηθούν για την παραγωγή επιφανειακώς "αληθοφανούς" κειμένου με αφετηρία ένα δείγμα εγγράφου: χρησιμοποιούνται σε μια ποικιλία λογισμικού ψυχαγωγικών "γεννητριών παρωδίας" (βλέπε dissociated press, Jeff Harrison, Mark V Shaney). Αυτές οι διαδικασίες χρησιμοποιούνται επίσης από spammers για να εισάγουν αληθοφανείς, κρυμμένες παραγράφους σε ανεπιθύμητη ηλεκτρονική αλληλογραφία και να καταχωρήσουν σχόλια σε μια προσπάθεια να περάσουν αυτά τα μηνύματα από τα φίλτρα εντοπισμού spam.