2022¶

Αλυσίδες Markov¶

Διαβάστε από Ryan O'Donnell, Probability and Computing, Lec. 14, 15, 16.

Γρήγορη επανάληψη των βασικών για αλυσίδες Markov με πεπερασμένες καταστάσεις
Regular: αν $K^t$ δεν έχει μηδενικά για αρκετά μεγάλο $t$.
Βασικό Θεώρημα (χωρίς απόδειξη) Αν regular τότε $\lim_t K^t$ υπάρχει, με όλες τις γραμμές του ίσες και αυτή είναι η μοναδική στάσιμη κατανομή.
Αναμενόμενος χρόνος πρώτης επαναφοράς: $M_{uu} = 1/\pi_u$ (το αποδείξαμε πλήρως -- δείτε την απόδειξη από τις παραπάνω σημειώσεις).
Μιλήσαμε για τη μέθοδο Page Rank αξιολόγησης των ιστοσελίδων στο διαδίκτυο όπως αυτή φτιάχτξκς από την Google και το ποια είναι η σχέση της με τις αλυσίδες Markov.