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

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

Μια κατάσταση  i καλείται προσιτή από την κατάσταση j (συμβολίζεται με i → j) εάν για κάποιο ακέραιο 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 λέμε ότι είναι εργοδική αν είναι απεριοδική και θετικά επαναλαμβανόμενη. Με αλλά λόγια, μια κατάσταση i είναι εργοδική αν είναι επαναληπτική, έχει περίοδο ίση με 1 και έχει πεπερασμένο μέσο χρόνο επανάληψης. Αν όλες οι καταστάσεις σε μια αμείωτη Μαρκοβιανή Αλυσίδα είναι εργοδικές τότε λέμε ότι η Αλυσίδα είναι Εργοδική.
Έχει αποδειχτεί ότι μια πεπερασμένη αμείωτη Μαρκοβιανή Αλυσίδα είναι εργοδική αν έχει μια απεριοδική κατάσταση.  Ένα Μαρκοβιανό μοντέλο έχει την εργοδική ιδιότητα αν υπάρχει ένας πεπερασμένος αριθμός N τέτοιος ώστε κάθε κατάσταση μπορεί να φτάσει σε κάθε άλλη κατάσταση σε ακριβώς N βήματα. Σε περίπτωση που έχουμε ένα πλήρως συνδεδεμένο πινάκα μετάβασης όπου όλες οι μεταβάσεις έχουν μη-μηδενική πιθανότητα, αυτή η προϋπόθεση ικανοποιείται για N=1. Ένα μοντέλο με παραπάνω από μια καταστάσεις και με μόνο μια πιθανή μετάβαση σε κάθε κατάσταση δε μπορεί να είναι εργοδικό.

Εφαρμογές

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

Φυσικη

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

Χημεια

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

Δοκιμές

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

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

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

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

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

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

Η κατάταξη μιας ιστοσελίδας με βάση τον αλγόριθμο PageRank, όπως χρησιμοποιείται από τη Google, ορίζεται από μια Μαρκοβιανή αλυσίδα. Είναι η πιθανότητα να βρίσκεσαι στη σελίδα   στη στατική κατανομή της ακόλουθης Μαρκοβιανής αλυσίδας για όλες τις (γνωστές) ιστοσελίδες. Αν  είναι ο αριθμός των γνωστών ιστοσελίδων και μια σελίδα   εχει  συνδέσμους σε αυτή, τότε έχει πιθανότητα μετάβασης   για όλες της σελίδες που συνδέονται με αυτήν και  for για όλες τις σελίδες που δε συνδέονται με αυτήν. Η παράμετρος  θεωρείται περίπου 0,85.
Μαρκοβιανά μοντέλα έχουν επίσης χρησιμοποιηθεί για την ανάλυση της συμπεριφοράς περιήγησης των χρηστών στο διαδίκτυο. Η μετάβαση διαδικτυακών συνδέσμων ενός χρήστη σε μια συγκεκριμένη ιστοσελίδα μπορεί να μοντελοποιηθεί χρησιμοποιώντας Μαρκοβιανά μοντέλα πρώτης ή δεύτερης τάξης και μπορεί να χρησιμοποιηθεί για να προβλέψει μελλοντική περιήγηση και να εξατομικεύσει την ιστοσελίδα για ένα συγκεκριμένο χρήστη.

Στατιστικη

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

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

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

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

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

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

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

Γενετική

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

Παιχνιδια

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

Μπέιζμπολ

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