.
Η αλυσίδα Μαρκόφ (ή Μαρκοβιανή Αλυσιδα), που πήρε το όνομα της από τον Αντρέι Μαρκόφ, είναι ένα μαθηματικό σύστημα που μεταβάλλεται από μια κατάσταση σε μια άλλη, ανάμεσα σε ένα πεπερασμένο αριθμό καταστάσεων. Είναι μια τυχαία διαδικασία που δε διατηρεί μνήμη για τις προηγούμενες μεταβολές: Η επόμενη κατάσταση εξαρτάται μόνο από την τωρινή κατάσταση και σε καμιά περίπτωση από αυτές που προηγήθηκαν. Αυτό το συγκεκριμένο είδος "αμνησίας" ονομάζεται μαρκοβιανή ιδιότητα. Οι Μαρκοβιανές Αλυσίδες έχουν πολλές εφαρμογές ως στατιστικά μοντέλα καθημερινών διαδικασιών.
Εισαγωγή
ο Ρώσος μαθηματικός Andrey Markov
Η Μαρκοβιανή αλυσίδα είναι μια στοχαστική διαδικασία με τη μαρκοβιανή ιδιότητα για ένα πεπερασμένο ή μετρήσιμο χώρο καταστάσεων. Ο όρος "Μαρκοβιανή αλυσίδα" αναφέρεται στην αλληλουχία (ή αλυσίδα) των καταστάσεων μέσω των οποίων κινείται μια τέτοια διαδικασία. Συνήθως μια Μαρκοβιανή αλυσίδα ορίζεται για μια διακριτή συλλογή χρόνων (Μαρκοβιανή αλυσίδα διακριτών χρόνων), παρόλο που μερικοί συγγραφείς χρησιμοποιούν την ίδια ορολογία για να αναφερθούν σε Μαρκοβιανή αλυσίδα συνεχής χρόνου. Η χρήση του όρου στη μεθοδολογία Μαρκοβιανής αλυσίδας Μόντε Κάρλο καλύπτει περιπτώσεις όπου η διαδικασία βρίσκεται σε διακριτό χρόνο (διακριτά αλγοριθμικά βήματα) με ένα συνεχές χώρο καταστάσεων. Οι πληροφορίες που ακολουθούν επικεντρώνονται στην περίπτωση διακριτού χρόνου και διακριτού χώρου καταστάσεων.
Μια τυχαία διαδικασία διακριτού χρόνου περιλαμβάνει ένα σύστημα που βρίσκεται σε μια συγκεκριμένη κατάσταση σε κάθε βήμα, με την κατάσταση να μεταβάλλεται τυχαία μεταξύ των βημάτων. Τα βήματα συχνά θεωρούνται ως στιγμές στο χρόνο αλλά μπορούν εξίσου να αναφέρονται σε φυσική απόσταση ή οποιαδήποτε άλλη διακριτή μέτρηση: τυπικά τα βήματα είναι οι ακέραιοι ή φυσικοί αριθμοί και η τυχαία διαδικασία είναι η χαρτογράφησή τους σε καταστάσεις. Η Μαρκοβιανή ιδιότητα δηλώνει ότι η υποθετική πιθανότητα κατανομής του συστήματος στο επόμενο βήμα (και κατά βάση, σε όλα τα μελλοντικά βήματα) εξαρτάται μόνο από την παρούσα κατάσταση του συστήματος και όχι αθροιστικά από την κατάσταση του συστήματος σε προηγούμενα βήματα.
Καθώς το σύστημα μεταβάλλεται τυχαία, είναι γενικά αδύνατο να προβλεφθεί με βεβαιότητα η κατάσταση μιας Μαρκοβιανής αλυσίδας σε ένα δεδομένο μελλοντικό σημείο. Παρ' όλα αυτά, οι στατιστικές ιδιότητες του μέλλοντος του συστήματος μπορούν να προβλεφθούν. Σε πολλές εφαρμογές, είναι αυτές οι στατιστικές ιδιότητες που είναι σημαντικές.
Οι αλλαγές κατάστασης του συστήματος ονομάζονται μεταβάσεις και οι πιθανότητες που σχετίζονται με τις διάφορες μεταβατικές καταστάσεις ονομάζονται πιθανότητες μετάβασης. Η διαδικασία χαρακτηρίζεται από ένα χώρο καταστάσεων, μια μήτρα μετάβασης που περιγράφει τις πιθανότητες μιας συγκεκριμένης μετάβασης και μια αρχική κατάσταση ή αρχική κατανομή στο χώρο καταστάσεων. Κατά συνθήκη, θεωρούμε ότι όλες οι δυνατές καταστάσεις και μεταβάσεις έχουν συμπεριληφθεί στον ορισμό των διαδικασιών, ώστε υπάρχει πάντα μια επόμενη κατάσταση και η διαδικασία συνεχίζεται για πάντα.
Μια γνωστή Μαρκοβιανή αλυσίδα είναι ο λεγόμενος "περίπατος του μεθυσμένου", μια τυχαία διαδρομή στην αριθμητική γραμμή όπου, σε κάθε βήμα, η θέση μπορεί να αλλάξει κατά +1 ή κατά -1 με ίση πιθανότητα. Από κάθε θέση υπάρχουν δύο δυνατές μεταβάσεις, στον επόμενο ή στον προηγούμενο ακέραιο. Οι πιθανότητες μετάβασης εξαρτώνται μόνο από την παρούσα θέση, όχι από τον τρόπο με τον οποίο η θέση επετεύχθη. Για παράδειγμα, οι πιθανότητες μετάβασης από το 5 στο 4 και από το 5 στο 6 είναι 0.5 και οι δύο, και όλες οι άλλες πιθανότητες μετάβασης από το 5 είναι 0. Αυτές οι πιθανότητες είναι ανεξάρτητες από το αν το σύστημα προηγουμένως βρισκόταν στο 4 ή στο 6.
Ένα άλλο παράδειγμα είναι οι διατροφικές συνήθειες ενός πλάσματος που τρώει μόνο σταφύλια, τυρί ή μαρούλι, οι οποίες ακολουθούν τους παρακάτω κανόνες:
Τρώει ακριβώς μία φορά την ημέρα.
Αν σήμερα έφαγε τυρί, αύριο θα φάει μαρούλι ή σταφύλια με ίσες πιθανότητες.
Αν σήμερα έφαγε σταφύλια, αύριο θα φάει σταφύλια με πιθανότητα 1/10, τυρί με πιθανότητα 4/10 και μαρούλι με πιθανότητα 6/10.
Αν σήμερα έφαγε μαρούλι, δε θα φάει μαρούλι αύριο αλλά θα φάει σταφύλια με πιθανότητα 4/10 ή τυρί με πιθανότητα 6/10.
Οι διατροφικές συνήθειες αυτού του πλάσματος μπορούν να μοντελοποιηθούν με μία Μαρκοβιανή αλυσίδα καθώς η αυριανή επιλογή εξαρτάται αποκλειστικά από το τι έφαγε σήμερα, όχι τι έφαγε χθες ή παλαιότερα. Μια στατιστική ιδιότητα που θα μπορούσε να υπολογισθεί είναι το αναμενόμενο ποσοστό, κατά τη διάρκεια μιας μακράς περιόδου, των ημερών στις οποίες το πλάσμα θα φάει σταφύλια.
Μια σειρά ανεξάρτητων γεγονότων (για παράδειγμα, μια σειρά από στριψίματα νομίσματος) ικανοποιεί τον επίσημο ορισμό της Μαρκοβιανής αλυσίδας. Παρ' όλα αυτά, η θεωρία συνήθως εφαρμόζεται μόνο όταν η πιθανότητα κατανομής του επομένου βήματος εξαρτάται μη-αμελητέα από την παρούσα κατάσταση.
Υπάρχουν πολλά ακόμη παραδείγματα Μαρκοβιανών αλυσίδων.
Μαθηματικός ορισμός
Μια Μαρκοβιανή Αλυσίδα είναι μια ακολουθία τυχαίων μεταβλητών X1, X2, X3, … με τη Μαρκοβιανη Ιδιότητα, δηλαδη με δεδομενη την παρουσα κατασταση, οι παλαιοτερες και οι μελλοντικες καταστασεις είναι ανεξαρτητες. Ορίζουμε
\( \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).\, \)
Οι πιθανες τιμες των Xi σχηματιζουν ένα αριθμησιμο συνολο S που ονομαζουμε χωρο-καταστασεων της αλυσιδας
Οι Μαρκοβιανες Αλυσιδες συχνα περιγραφονται από ένα κατευθυνομενο γραφημα που οι ακρες του επιγραφουν τις πιθανοτητες μεταβασης από τη μια κατασταση στις αλλες
Παραλλαγες
Οι Μαρκοβιανες Αλυσιδες Συνεχους Χρονου εχουν ένα συνεχή δεικτη
'Μαρκοβιανες Αλυσιδες ομοιογενους χρονου (ή σταθερες Μαρκοβιανες Αλυσιδες) είναι διαδικασιες που
\( \Pr(X_{n+1}=x|X_n=y) = \Pr(X_n=x|X_{n-1}=y)\, \)
για όλα τα n. Η πιθανοτητα της μεταβασης είναι ανεξαρτητη από το n.
Μια Μαρκοβιανη Αλυσιδα ταξης m (ή Μαρκοβιανη Αλυσιδα με μνημη m), οπου το m είναι πεπερασμενο, είναι μια διαδικασια που ικανοποιει
\( \begin{align} {} &\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{align} \)
Με αλλα λογια η μελλοντικη κατασταση εξαρταται από τις προηγουμενες m καταστασεις. Είναι δυνατο να κατασκευασουμε μια αλυσιδα (Yn) απο (Xn) που να εχει την κλασικη Μαρκοβιανη Ιδιοτητα παιρνοντας ως χωρο καταστασεων το συνολο των m-πλειαδων του X, πχ. Yn = (Xn, Xn−1, ..., Xn−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) . \)
Παραδείγματα
Finance Markov chain example state
Ένα απλό παράδειγμα με χρήση κατευθυνόμενου γραφήματος για τις απεικονίσεις των μεταβάσεων μεταξύ των καταστάσεων φαίνεται στην εικόνα δεξιά. Οι καταστάσεις αντιπροσωπεύουν αν μια υποθετική χρηματιστηριακη αγορα παρουσιαζει ανοδικη ή πτωτικη πορεια ή αν παραμενει στασιμη κατά τη διαρκεια μια συγκεκριμενης βδομαδας. Με βάση την εικόνα μια ανοδική εβδομάδα ακολουθείται από μια ακόμα ανοδική εβδομάδα κατά 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(n)P. Άρα αν σε χρόνο n το σύστημα είναι στη 2η κατάσταση (πτωτική), τότε 3 περίοδους μετά για χρόνο n + 3 η κατανομή θα είναι ως εξής
\( \begin{align} 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{align} \)
Χρησιμοποιώντας τον πινάκα μετάβασης είναι δυνατόν να υπολογιστεί, για παράδειγμα, μακροπρόθεσμα, το ποσοστό των εβδομάδων που η αγορά μένει στάσιμη, ή ο μέσος αριθμός των εβδομάδων που θα χρειαστούν για να περάσει η αγορά από στάσιμη σε ανοδική κατάσταση. Χρησιμοποιώντας τις πιθανότητες μετάβασης, η σταθερή κατάσταση των πιθανοτήτων δείχνει ότι η αγορά θα βρίσκεται σε ανοδική φάση το 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(Xn = x) είναι το μοίρασμα των καταστάσεων σε χρόνο n. Η αρχική κατανομή είναι Pr(X0 = 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. Επισήμως θεωρούμε ότι η τυχαία μεταβλητή Ti είναι η πρώτη επιστροφή στην κατάσταση i :
\( T_i = \inf \{ n\ge1: 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 είναι ο αναμενόμενος χρόνος επιστροφής Mi:
\( M_i = E[T_i]=\sum_{n=1}^{\infty} n\cdot f_{ii}^{(n)}.\, \)
Η κατάσταση i είναι θετικά επαναληπτική αν το Mi είναι πεπερασμένο; αλλιώς, η κατάσταση 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\leq1. \)
\( \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 \rarr \infty} p_{ij}^{(n)} = \frac{C}{M_j}. \)
Προσέξτε ότι δεν υπάρχει καμία υπόθεση για την αρχική κατανομή; Η αλυσίδα συγκλίνει στον σταθερο κατανομεα ανεξάρτητα από το πώς ξεκίνησε. Ένα τέτοιο π λέγεται κατανομεας ισορροπίας της αλυσίδας.
Αν μια αλυσίδα έχει παραπάνω από μια κλειστές τάξεις, τότε ο σταθερός κατανομεας της δεν θα είναι μοναδικός. Όμως, αν η κατάσταση j είναι απεριοδική, τότε
\( \lim_{n \rarr \infty} p_{jj}^{(n)} = \frac{C}{M_j} \)
Και για κάθε άλλη κατάσταση i, έστω fij η πιθανότητα ότι η αλυσίδα φτάνει κάποια στιγμή στην κατάσταση j αν ξεκινησει από την κατάσταση i,
\( \lim_{n \rarr \infty} p_{ij}^{(n)} = C \frac{f_{ij}}{M_j}. \)
Αν η κατάσταση i είναι απεριοδική με περίοδο k > 1 τότε το όριο
\( \lim_{n \rarr \infty} p_{ii}^{(n)} \)
Δεν υπάρχει, αν και, το όριο
\lim_{n \rarr \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-οστη δύναμη του πινάκα μετάβασης, Pk.
Ο σταθερός κατανομεας π είναι ένα διάνυσμα γραμμής, του οποίου οι καταχωρήσεις είναι μη-αρνητικές και έχουν άθροισμα 1, που ικανοποιεί την εξίσωση
\( \pi = \pi\mathbf{P}.\, \)
Με αλλά λόγια, ο σταθερός κατανομεας π είναι ένα κανονικοποιημενο (δηλαδή όλες οι καταχωρήσεις του έχουν άθροισμα 1) αριστερό ιδιοδιανυσμα του πινάκα μετάβασης που σχετίζεται με την ιδιοτιμη 1
Διαφορετικά, το π μπορεί να θεωρηθεί ένα σταθερό σημείο του γραμμικού (και άρα συνεχούς) μετασχηματισμού της μονάδας που σχετίζεται με τον πινάκα μετάβασης P. Όπως κάθε συνεχής μετασχηματισμός της απλής μονάδας έχει ένα σταθερό σημείο, ένας σταθερός κατανομεας πάντα υπάρχει, αλλά δεν είναι δεδομένο ότι είναι μοναδικός. Όμως, αν η Μαρκοβιανη Αλυσίδα είναι αμείωτη και απεριοδική, τότε υπάρχει ένας μοναδικός σταθερός κατανομεας π. Επιπλέον σε αυτή την περίπτωση το Pk συγκλίνει σε ένα πρώτου βαθμού πινάκα που κάθε του σειρά είναι ο σταθερός κατανομεας π, δηλαδή,
\( \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} , \)
όπου In ο μοναδιαίος πινάκας μεγέθους n, και 0n,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(λ1,λ2,λ3,...,λn). Τότε, με φασματική αποσύνθεση
\( \mathbf{P} = \mathbf{U\Sigma U}^{-1} . \)
Έστω ότι τα ιδιοδιανυσματα αριθμούνται με τέτοιο τρόπο που 1=|λ1|>|λ2|≥|λ3|≥...≥|λn|. Αφού ο P κατά-σειρα στοχαστικός πινάκας, η μεγαλύτερη ιδιοτιμη του είναι 1. Αν υπάρχει ένας μοναδικός σταθερός κατανομεας, τότε η μεγαλύτερη ιδιοτιμη και το αντίστοιχο ιδιοδιανυσμα είναι επίσης μοναδικό (επειδή δεν υπάρχει άλλο π που να λύνει την εξίσωση του σταθερού κατανομεα). Έστω ui είναι η iστη στήλη του πινάκα U, π.χ. ui είναι το αριστερό ιδιοδιανυσμα του P που αντιστοιχεί στο λi. Επίσης έστω x είναι ένα αυθαίρετο μήκους-n διάνυσμα γραμμής στη διάρκεια των ιδιοδιανυσμάτων ui, δηλαδή
\( \mathbf{x}^T = \sum_{i=1}^n a_i \mathbf{u}_i \)
Για κάποιο ζεύγος ai∈ℝ. Αν αρχίσουμε να πολλαπλασιάζουμε τον P με x από αριστερά και συνεχίσουμε αυτή τη διαδικασία με τα αποτελέσματα, στο τέλος θα πάρουμε τον σταθερό κατανομεα π. Με αλλά λόγια π = ui ← xPPP...P = xPk όπου το 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\} . \)
Αφού π = u1, π(k) τείνει στο π όσο το k τείνει στο άπειρο με εκθετική ταχύτητα τάξης λ2/λ1. Αυτό ακολουθεί διότι |λ2|≥|λ3|≥...≥|λn|, άρα λ2/λ1 είναι ο κυρίαρχος Όρος.
Εφαρμογές
Η έρευνα έχει αναφέρει την εφαρμογή και χρησιμότητα των Μαρκοβιανών αλυσίδων σε ένα ευρύ φάσμα θεμάτων όπως φυσική, χημεία, ιατρική, μουσική, θεωρία παιγνίων και αθλήματα.
Φυσικη
Τα Μαρκοβιανά συστήματα εμφανίζονται εκτενώς στη θερμοδυναμική και στη στατική μηχανική, όποτε πιθανότητες χρησιμοποιούνται για να αναπαραστήσουν άγνωστες ή μη μοντελοποιημένες λεπτομέρειες του συστήματος, αν μπορεί να υποτεθεί ότι η δυναμική δεν μεταβάλλεται με το χρόνο και ότι καμία σχετική ιστορία που να μην περιλαμβάνεται ήδη στην περιγραφή κατάστασης δε χρειάζεται να θεωρηθεί.
Χημεια
Michaelis-Menten kinetics. Κινητική Michaelis-Menten. Το ένζυμο (Ε) προσδένεται στο υπόστρωμα (S) και παράγει ένα προϊόν (P). Κάθε αντίδραση είναι μια μετάβαση κατάστασης σε μια Μαρκοβιανή αλυσίδα.
Η χημεία είναι συχνά ένας τομέας όπου οι Μαρκοβιανές αλυσίδες και οι Μαρκοβιανές καταστάσεις συνεχούς χρόνου είναι ιδιαίτερα χρήσιμες επειδή αυτά τα απλά φυσικά συστήματα τείνουν να ικανοποιούν αρκετά καλά τη Μαρκοβιανή ιδιότητα. Το κλασικό μοντέλο της ενζυμικής δραστηριότητας, η κινητική Michaelis-Menten, μπορεί να θεωρηθεί ως μια Μαρκοβιανή αλυσίδα, όπου σε κάθε βήμα η αντίδραση προχωράει προς κάποια κατεύθυνση. Ενώ η κινητική Michaelis-Menten είναι αρκετά απλή, πολύ περισσότερο πολύπλοκα δίκτυα αντιδράσεων μπορούν επίσης να μοντελοποιηθούν με Μαρκοβιανές αλυσίδες Ένας αλγόριθμος που βασίζεται σε Μαρκοβιανή αλυσίδα χρησιμοποιήθηκε επίσης για να εστιάσει τη βασιζόμενη σε θραύσματα ανάπτυξη χημικών in silico προς μια επιθυμητή τάξη ενώσεων όπως φάρμακα ή φυσικά προϊόντα. Καθώς ένα στοιχείο αναπτύσσεται, ένα θραύσμα επιλέγεται από το εν τη γενέσει στοιχείο ως η "παρούσα" κατάσταση. Δεν έχει επίγνωση του παρελθόντος του (δε γνωρίζει τι βρίσκεται ήδη δεσμευμένο σε αυτό). Στη συνέχεια, μεταβαίνει στην επόμενη κατάσταση όταν ένα θραύσμα προσκολλάται σε αυτό. Οι πιθανότητες μετάβασης διευθύνονται από βάσεις δεδομένων αυθεντικών τάξεων ενώσεων.
Επίσης, η ανάπτυξη (και σύνθεση) συμπολυμερών μπορεί να μοντελοποιηθεί χρησιμοποιώντας Μαρκοβιανές αλυσίδες. Με βάση το κλάσμα αντίδρασης των μονομερών που αποτελούν την αναπτυσσόμενη πολυμερική αλυσίδα, η σύνθεση της αλυσίδας μπορεί να υπολογισθεί (πχ αν τα μονομερή τείνουν να προστίθεται με εναλασσόμενο τρόπο ή με μακριές σειρές του ίδιου μονομερούς).
Παρόμοια, έχει προταθεί ότι η κρυσταλλοποίηση και ανάπτυξη κάποιων επιταξιακών υπερπλεγμάτων οξειδίων μπορούν να περιγραφούν με ακρίβεια με Μαρκοβιανές αλυσίδες.
Δοκιμές
Πολλοί θεωρητικοί έχουν προτείνει την ιδέα της στατιστικής δοκιμής Μαρκοβιανής αλυσίδας (Marcov chain statistical test-MCST), μια μέθοδο σύνδεσης Μαρκοβιανών αλυσίδων προς σχηματισμό ενός "Μαρκοβιανού παπλώματος ", τοποθετώντας αυτές τις αλυσίδες σε διάφορα αναδρομικά στρώματα και παράγοντας πιο αποτελεσματικά σετ δοκιμών -δείγματα- ως αντικατάσταση των εξαντλητικών δοκιμών. Οι στατιστικές δοκιμές Μαρκοβιανής αλυσίδας έχουν επίσης εφαρμογές σε χρονικά δίκτυα που βασίζονται σε καταστάσεις: το άρθρο των Chilukuri και συνεργατών με τίτλο "Δίκτυα Συλλογισμού Χρονικής Αβεβαιότητας για Συγχώνευση Στοιχείων με Εφαρμογές στον Εντοπισμό και στην Παρακολούθηση Αντικειμένων" (ScienceDirect) δίνει ένα υπόβραθο και μια περίπτωση μελέτης για την εφαρμογή των MCST σε ευρύτερο φάσμα εφαρμογών.
Επιστημες Πληροφοριων
Οι Μαρκοβιανές αλυσίδες χρησιμοποιούνται ευρέως στην επεξεργασία πληροφοριών. Η διάσημη εργασία του Claude Shannon από το 1948 "Μια μαθηματική θεωρία επικοινωνίας", η οποία σε ένα βήμα δημιούργησε το πεδίο της θεωρίας πληροφοριών, ξεκινάει παρουσιάζοντας την έννοια της εντροπίας μέσω Μαρκοβιανής μοντελοποίησης της Αγγλικής γλώσσας. Τέτοια ιδανικά μοντέλα μπορούν να συλλάβουν πολλές από τις στατιστικές ανωμαλίες των συστημάτων. Ακόμη και χωρίς περιγραφή της πλήρης δομής του συστήματος, τέτοια μοντέλα σημάτων μπορούν να κάνουν δυνατή την πολύ αποτελεσματική συμπίεση δεδομένων μέσω τεχνικών κωδικοποίησης εντροπίας όπως η αριθμητική κωδικοποίηση. Επίσης επιτρέπουν αποτελεσματική εκτίμηση καταστάσεων και αναγνώριση προτύπων. Οι Μαρκοβιανές αλυσίδες παίζουν επίσης σημαντικό ρόλο στην ενισχυτική μάθηση.
Οι Μαρκοβιανές αλυσίδες είναι επιπλέον η βάση για Κρυμμένα Μαρκοβιανά μοντέλα, που αποτελούν σημαντικό εργαλείο σε ποικίλα πεδία όπως τηλεφωνικά δίκτυα (που χρησιμοποιούν τον αλγόριθμο Viterbi για διόρθωση σφαλμάτων), αναγνώριση λόγου και βιοπληροφορική.
Θεωρια Σειρων
Οι Μαρκοβιανές αλυσίδες είναι η βάση για την αναλυτική μεταχείριση σειρών (θεωρία σειρών). Ο Agner Krapup Erlang ξεκίνησε το θέμα το 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.
Μαρκοβιανά μοντέλα έχουν επίσης χρησιμοποιηθεί για την ανάλυση της συμπεριφοράς περιήγησης των χρηστών στο διαδίκτυο. Η μετάβαση διαδικτυακών συνδέσμων ενός χρήστη σε μια συγκεκριμένη ιστοσελίδα μπορεί να μοντελοποιηθεί χρησιμοποιώντας Μαρκοβιανά μοντέλα πρώτης ή δεύτερης τάξης και μπορεί να χρησιμοποιηθεί για να προβλέψει μελλοντική περιήγηση και να εξατομικεύσει την ιστοσελίδα για ένα συγκεκριμένο χρήστη.
Στατιστικη
Μέθοδοι Μαρκοβιανών αλυσίδων έχουν επίσης γίνει πολύ σημαντικές για την παραγωγή ακολουθιών τυχαίων αριθμών για να αποδώσουν με ακρίβεια πολύ περίπλοκες επιθυμητές κατανομές πιθανοτήτων, μέσω μιας διαδικασίας που λέγεται Μαρκοβιανή αλυσίδα Μόντε Κάρλο. Πρόσφατα, αυτό έχει οδηγήσει σε επανάσταση όσον αφορά στην πρακτικότητα μεθόδων Μπαγεσιανών συμπερασμάτων, επιτρέποντας ένα ευρύ φάσμα μεταγένεστερων κατανομών να προσομοιωθούν και οι παράμετροί τους να βρεθούν αριθμητικά.
Οικονομιά και Οικονομικά
Οι Μαρκοβιανές αλυσίδες χρησιμοποιούνται στα Χρηματοοικονομικά για να μοντελοποιήσουν μια ποικιλία διαφορετικών φαινομένων, συμπεριλαμβανομένων τιμών κεφαλαίων και πτώσεις αγορών. Το πρώτο χρηματοοικονομικό μοντέλο που χρησιμοποίησε Μαρκοβιανή αλυσίδα ήταν του Prasad και συνεργατών το 1974. Ένα άλλο ήταν το μοντέλο αλλαγής καθεστώτος του James D. Hamilton (1989), στο οποίο μια Μαρκοβιανή αλυσίδα χρησιμοποιείται για να μοντελοποιήσει αλλαγές μεταξύ περιόδων υψηλής μεταβλητότητας και χαμηλής μεταβλητότητας επιστροφής κεφαλαίων. Ένα πιο πρόσφατο παράδειγμα είναι το Πολυκλασματικό Μαρκοβιανό μοντέλο Αλλαγής τιμολόγησης κεφαλαίων, που βασίζεται στην ευκολία των προηγούμενων μοντέλων αλλαγής καθεστώτων. Χρησιμοποιεί μια τυχαία μακριά Μαρκοβιανή αλυσίδα για να οδηγήσει τα επίπεδα μεταβλητότητας επιστροφών κεφαλαίου. Η δυναμική μακροοικονομία ευρέως χρησιμοποιεί Μαρκοβιανές αλυσίδες. Ένα παράδειγμα είναι η χρήση τους για την εξωγενή μοντελοποίηση τιμών δικαιοσύνης (μετοχών) σε μια ρύθμιση γενικής ισορροπίας.
Κοινωνικες Επιστημες
Οι Μαρκοβιανές αλυσίδες χρησιμοποιούνται γενικά στην περιγραφή επιχειρημάτων που εξαρτώνται από τη διαδρομή, όπου οι παρούσες δομικές διαμορφώσεις διέπουν τα μελλοντικά αποτελέσματα. Ένα παράδειγμα είναι η αναδιατύπωση της ιδέας, αρχικά λόγω του "Κεφαλαίου" του Καρλ Μαρξ, συνδέοντας την οικονομική ανάπτυξη με την άνοδο του καπιταλισμού. Στην παρούσα έρευνα, είναι συνηθισμένη η χρήση Μαρκοβιανής αλυσίδας για να μοντελοποιήσει πώς όταν μια χώρα φτάσει ένα συγκεκριμένο επίπεδο οικονομικής ανάπτυξης, η διαμόρφωση δομικών παραγόντων, όπως το μέγεθος της εμπορικής αστικής τάξης, η αναλογία της αστικής προς την αγροτική κατοικία, ο ρυθμός πολιτικής κινητοποίησης κτλ θα οδηγήσει σε υψηλότερη πιθανότητα μετάβασης από απολυταρχικό σε δημοκρατικό καθεστώς.
Μαθηματικη Βιολογια
Οι Μαρκοβιανές αλυσίδες έχουν επίσης πολλές εφαρμογές σε βιολογικά μοντέλα, κυρίως πληθυσμικές διαδικασίες, με χρησιμότητα στη μοντελοποίηση διαδικασιών που είναι (τουλάχιστον) ανάλογες με βιολογικούς πληθυσμούς. Η μήτρα Leslie είναι ένα παράδειγμα, παρόλο που μερικές από τις καταχωρίσεις δεν είναι πιθανότητες (μπορεί να είναι μεγαλύτερες από 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. Ο Mark Pankin έδειξε ότι μοντέλα Μαρκοβιανών αλυσίδων μπορούν να χρησιμοποιηθούν για την εκτίμηση runs που δημιουργούνται και για τους δύο ανεξάρτητους παίκτες όπως και για την ομάδα. Επίσης συζητά διάφορα είδη στρατηγικών και όρων παιχνιδού: πώς τα μοντέλα Μαρκοβιανών αλυσίδων έχουν χρησιμοποιηθεί για την ανάλυση στατιστικών για καταστάσεις παιχνιδιού όπως bunting και base stealing και διαφορές παιχνιδιού επί χόρτου ή astroturf.
Μαρκοβιανη γεννήτρια κειμένου
Μαρκοβιανές διαδικασίες μπορούν επίσης να χρησιμοποιηθούν για την παραγωγή επιφανειακώς "αληθοφανούς" κειμένου με αφετηρία ένα δείγμα εγγράφου: χρησιμοποιούνται σε μια ποικιλία λογισμικού ψυχαγωγικών "γεννητριών παρωδίας" (βλέπε dissociated press, Jeff Harrison, Mark V Shaney). Αυτές οι διαδικασίες χρησιμοποιούνται επίσης από spammers για να εισάγουν αληθοφανείς, κρυμμένες παραγράφους σε ανεπιθύμητη ηλεκτρονική αλληλογραφία και να καταχωρήσουν σχόλια σε μια προσπάθεια να περάσουν αυτά τα μηνύματα από τα φίλτρα εντοπισμού spam.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
