Στοχαστικές Ανελίξεις (Σ.Ε.Μ.Φ.Ε. Εαρινό 2014)

Ώρες διδασκαλίας: Δευτέρα 10:45-10:30, Τρίτη 8:45-10:30, (Γεν. Έδρες, Αμφ. 2)

Ώρες γραφείου: Τρίτη 10:30-12:30 ή μετά από συνεννόηση.

ανακοινώσεις

Σάββατο 31/5: Τις Τετάρτες 4,11,18 και 25 Ιουνίου 10:30-12:30 στο Αμφιθέατρο 1 των ΓΕ θα γίνουν οι αναπληρώσεις των ωρών που χάθηκαν και δύο επιπλέον δίωρα με ασκήσεις.

Πέμπτη 28/8: Τα θέματα και τα αποτελέσματα της εξ’ αναβολής εξέτασης του εαρινού εξαμήνου είναι διαθέσιμα. Αν επιθυμείτε να δείτε το γραπτό σας, παρακαλώ περάστε την Δευτέρα 1/9 1μμ-3μμ.

Κυριακή 5/10: Τα θέματα και τα αποτελέσματα της επαναληπτικής εξέτασης είναι διαθέσιμα. Αν επιθυμείτε να δείτε το γραπτό σας, παρακαλώ περάστε την Δευτέρα 6/10 ή την Τετάρτη 8/10 9:30-11πμ.

Κυριακή 1/3: Τα θέματα και τα αποτελέσματα της έκτακτης επαναληπτικής εξέτασης είναι διαθέσιμα. Αν επιθυμείτε να δείτε το γραπτό σας, παρακαλώ περάστε την Τετάρτη 3/3 11-12πμ ή την Παρασκευή 5/3 1-2μμ.

διδακτικό υλικό

M.I.T. Open Courseware: Discrete Stochastic Processes

Μια συλλογή από λυμένα παραδείγματα στις μαρκοβιανές αλυσίδες

Σημειώσεις μου για την ύλη των τελευταίων διαλέξεων.

ΦΥΛΛΑΔΙΑ ΑΣΚΗΣΕΩΝ

Φυλλάδιο Ι, Φυλλάδιο ΙΙ, Φυλλάδιο ΙΙΙ, Φυλλάδιο IV

ΕΡΓΑΣΤΗΡΙΟ

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

Εργαστήριο Ι: Ασκήσεις, markov.py, path.py, multipath.py

βιβλιογραφία

ΣΤΑ ΕΛΛΗΝΙΚΑ

Γιώργος Κοκολάκης: Σημειώσεις στοχαστικών ανελίξεων, Διαθέσιμες από εδώ.

Ουρανία Χρυσαφίνου: Εισαγωγή στις στοχαστικές ανελίξεις, Σοφία 2012

ΣΤΑ ΑΓΓΛΙΚΑ

J.R. Norris: Markov Chains, CUP 1997

D.A. Levin, Yuval Peres, E.L. Wilmer: Markov Chains and Mixing Times, AMS 2009, διαθέσιμο από εδώ.

Olle Häggström: Finite Markov Chains and Algorithmic Applications, CUP 2002

Pierre Brémaud: Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues, Springer 2010

ημερολόγιο μαθήματος

Δευτέρα 7/4: Εισαγωγή, στόχοι του μαθήματος, στοχαστικές διαδικασίες (ΣΔ), χώρος καταστάσεων, κατασκευή ΣΔ.

Τρίτη 8/4: Μαρκοβιανές αλυσίδες, πίνακες πιθανοτήτων μετάβασης.

Δευτέρα 14/4: Πιθανότητες μετάβασης ανώτερης τάξης, εξισώσεις Chapman-Kolmogorov.

Τρίτη 15/4: Κλάσεις επικοινωνίας, ανοιχτές, κλειστές κλάσεις, υποβιβάσιμες αλυσίδες.

Δευτέρα 28/4: Θεωρία Δυναμικού. Πιθανότητες απορρόφησης και αναμενόμενοι χρόνοι άφιξης, σαν λύσεις προβλημάτων συνοριακών τιμών

Τρίτη 29/4: Θεωρία Δυναμικού (συνέχεια), Παραδείγματα υπολογισμών.

Δευτέρα 12/5: Ισχυρή μαρκοβιανή ιδιότητα, εφαρμογές.

Τρίτη 13/5: Παροδικότητα, Επαναληπτικότητα, χαρακτηρισμός κλάσεων.

Δευτέρα 19/5: Απλός τυχαίος περίπατος στους ακεραίους. Παροδικότητα, επαναληπτικότητα

Τρίτη 20/5: Τυχαίος περίπατος στο Ζ με φράγματα. Gambler’s ruin και χρόνος απορρόφησης.

Δευτέρα 26/5: Τυχαίος περίπατος στο Ζ^d, τυχαίοι περίπατοι σε γράφους.

Τρίτη 27/5: Αναλλοίωτα μέτρα, αναλλοίωτες κατανομές: ορισμός, γενικές ιδιότητες. Πιθανοθεωρητική κατασκευή (ύπαρξη) αναλλοίωτου μέτρου για επαναληπτικές αλυσίδες.

Δευτέρα 2/6: Θεώρημα μοναδικότητας για μη υποβιβάσιμες αλυσίδες. Γνήσια Επαναληπτικότητα.

Τρίτη 3/6: Ύπαρξη και μοναδικότητα αναλλοίωτης κατανομής για  μη υποβιβάσιμες γνήσια επαναληπτικές αλυσίδες.

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

Τετάρτη 4/6: Ασκήσεις από τα Φυλλάδια Ι & ΙΙ.

Τρίτη 10/6: Χρονική αντιστρεψιμότητα και συνθήκες ακριβούς ισορροπίας.

Δευτέρα 7/7: Το εργοδικό θεώρημα

Τρίτη 8/7:  Το εργοδικό θεώρημα. Ο αλγόριθμος Pagerank της Google.

Τετάρτη 9/7 (3ώρες): Ασκήσεις από το Φυλλάδιο ΙΙΙ.

Δευτέρα 14/7: Απεριοδικότητα μαρκοβιανών αλυσίδων, ορισμός, ιδιότητες. Σύζευξη (coupling) αλυσίδων.

Τρίτη 15/7: Σύγκλιση της κατανομής μιας αλυσίδας Markov στην αναλλοίωτη κατανομή

Δευτέρα 22/7: Μέθοδοι Μonte Carlo με μαρκοβιανές αλυσίδες (MCMC). Ο αλγόριθμος Metropolis-Hastings

Τρίτη 23/7: Η τεχνική της προσομοιωμένης ανόπτησης.

Τετάρτη 24/7: Παραδείγματα και Ασκήσεις.

Τρίτη 8/11: Μέτρα πιθανότητας- ορισμός, ιδιότητες, παραδείγματα.