Ημερολόγιο Τετάρτης 26/10/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.