Αλυσίδα Markov — Πίνακας Μετάβασης και Εφαρμογές

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

Αυτές οι πιθανότητες ενός βήματος συγκεντρώνονται σε έναν πίνακα μετάβασης. Αν η διαδικασία βρίσκεται τώρα στην κατάσταση $i$ και μεταβαίνει έπειτα στην κατάσταση $j$ με πιθανότητα $P_{ij}$, τότε

$$P = (P_{ij})$$

Για μια πεπερασμένη αλυσίδα Markov, κάθε γραμμή του $P$ αθροίζεται σε $1$ επειδή η διαδικασία πρέπει να μεταβεί σε μία από τις επιτρεπτές επόμενες καταστάσεις.

Τι Σημαίνει η Ιδιότητα Markov

Η τυπική ιδέα είναι

$$P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i)$$

Αυτό σημαίνει ότι μόλις γνωρίζεις την τρέχουσα κατάσταση $X_n = i$, το παλαιότερο ιστορικό δεν αλλάζει την πιθανότητα του επόμενου βήματος μέσα στο μοντέλο.

Αυτή η συνθήκη έχει σημασία. Ορισμένα πραγματικά συστήματα έχουν μνήμη, τάσεις ή καθυστερημένες επιδράσεις, οπότε μια αλυσίδα Markov είναι κατάλληλη μόνο όταν το «η τρέχουσα κατάσταση αρκεί» είναι μια λογική προσέγγιση.

Πώς Να Διαβάζεις Έναν Πίνακα Μετάβασης

Έστω ότι ένα απλό μοντέλο καιρού έχει δύο καταστάσεις:

• Ηλιοφάνεια
• Βροχή

Χρησιμοποίησε τον εξής πίνακα μετάβασης:

$$P = \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix}$$

Διάβασε κάθε γραμμή ως την τρέχουσα κατάσταση και κάθε στήλη ως την επόμενη κατάσταση.

Άρα, αν σήμερα έχει Ηλιοφάνεια, το μοντέλο λέει ότι αύριο θα έχει Ηλιοφάνεια με πιθανότητα $0.8$ και Βροχή με πιθανότητα $0.2$. Αν σήμερα έχει Βροχή, αύριο θα έχει Ηλιοφάνεια με πιθανότητα $0.4$ και Βροχή με πιθανότητα $0.6$.

Λυμένο Παράδειγμα: Ο Καιρός σε Δύο Ημέρες

Έστω ότι η σημερινή κατανομή είναι

$$\mathbf{v}_0 = \begin{bmatrix} 1 & 0 \end{bmatrix}$$

Αυτό σημαίνει ότι το μοντέλο ξεκινά από Ηλιοφάνεια με πιθανότητα $1$.

Η κατανομή για αύριο είναι

$$\mathbf{v}_1 = \mathbf{v}_0 P = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix}$$

Άρα μετά από ένα βήμα, το μοντέλο δίνει πιθανότητα $80\%$ για Ηλιοφάνεια και $20\%$ για Βροχή.

Μετά από ένα ακόμη βήμα,

$$\mathbf{v}_2 = \mathbf{v}_1 P = \begin{bmatrix} 0.8 & 0.2 \end{bmatrix} \begin{bmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.72 & 0.28 \end{bmatrix}$$

Τώρα η πιθανότητα για Ηλιοφάνεια είναι $0.72$ και η πιθανότητα για Βροχή είναι $0.28$.

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

Πού Χρησιμοποιούνται οι Αλυσίδες Markov

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

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

Συνηθισμένα Λάθη στις Αλυσίδες Markov

Να Θεωρείς Κάθε Τυχαία Διαδικασία ως Markov

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

Να Ξεχνάς Τι Σημαίνουν οι Γραμμές

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

Χρήση Μη Έγκυρων Πιθανοτήτων

Κάθε στοιχείο πρέπει να είναι μεταξύ $0$ και $1$, και κάθε γραμμή πρέπει να αθροίζεται σε $1$ για έναν τυπικό πίνακα μετάβασης μιας πεπερασμένης αλυσίδας Markov.

Να Υποθέτεις Ότι το Μοντέλο Προβλέπει Ένα Βέβαιο Μέλλον

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

Η Μακροχρόνια Συμπεριφορά Εξαρτάται Από την Αλυσίδα

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

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

Πότε Μια Αλυσίδα Markov Είναι Καλό Μοντέλο

Χρησιμοποίησε μια αλυσίδα Markov όταν όλα τα παρακάτω είναι περίπου αληθή:

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

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

Δοκίμασε τη Δική σου Εκδοχή

Φτιάξε ένα μοντέλο τριών καταστάσεων, όπως Χαμηλή, Μεσαία και Υψηλή ζήτηση. Διάλεξε πιθανότητες ανά γραμμή που αθροίζονται σε $1$, επίλεξε μια αρχική κατανομή και υπολόγισε το επόμενο βήμα με $\mathbf{v}_{n+1} = \mathbf{v}_n P$. Αν θέλεις να προχωρήσεις περισσότερο, δοκίμασε και μια δεύτερη ενημέρωση και δες αν η κατανομή αρχίζει να σταθεροποιείται σε κάποιο μοτίβο.