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

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

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

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

Δευτέρα 9/3: Την Δευτέρα 16/3 & Τρίτη 17/3 το μάθημα δεν θα γίνει λόγω απουσίας μου. Θα ακολουθήσει ανακοίνωση για τις ώρες αναπλήρωσης.

Κυριακή 29/3: Λόγω της προγραμματισμένης εκπαιδευτικής εκδρομής του 3ου έτους την Δευτέρα 30/3 και την Τρίτη 31/3 δεν θα γίνει μάθημα. Οι ώρες θα αναπληρωθούν μετά τις διακοπές του Πάσχα.

Σάββατο 25/4: Οι αναπληρώσεις των μαθημάτων που χάθηκαν πριν το Πάσχα θα γίνουν τις επόμενες τέσσερις Πέμπτες 5-7μμ, ξεκινώντας από την 30/4. Την Δευτέρα θα έχουμε μάθημα 10:45-12:30 και την Τρίτη 8:45-10:30, σύμφωνα με το πρόγραμμα.

Τρίτη 16/6: Την ερχόμενη Πέμπτη στις 12:45 θα γίνει έκτακτο μάθημα με λύση των φυλλαδίων V και VI στην αίθουσα 101 των Ν.Κτ. της ΣΕΜΦΕ.

Δευτέρα 22/6: Η εξέταση του μαθήματος θα γίνει την Τετάρτη 8/7 στις 8:30 στα Ν.Κτ ΣΕΜΦΕ, αίθουσες 101 και 102.

Τετάρτη 8/7: Τα θέματα της κανονικής εξεταστικής είναι διαθέσιμα.

Παρασκευή 14/8: Τα αποτελέσματα της κανονικής εξεταστικής είναι διαθέσιμα.

Παρασκευή 11/9: Τα θέματα της επαναληπτικής εξεταστικής είναι διαθέσιμα.

Πέμπτη 12/11: Τα αποτελέσματα της επαναληπτικής εξεταστικής είναι διαθέσιμα.

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

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

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

Οι ασκήσεις των Φυλλαδίων V και VI που δεν προλάβαμε να κάνουμε στην τάξη

H σελίδα του περυσινού μαθήματος είναι εδώ.

ΣΗΜΕΙΩΣΕΙΣ

Κεφ. ΙΙΙ (θεωρία δυναμικού), Κεφ. VΙ (αναλλοίωτες κατανομές), Κεφ. VII (ασυμπτωτικά θεωρήματα), Κεφ. VΙII (εφαρμογές)

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

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

ΕΡΓΑΣΤΗΡΙΟ

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

ΕΡΓΑΣΤΗΡΙΟ Ι    Οδηγός εγκατάστασης της Python, Εργαστηριακή Άσκηση

                            Κώδικες (LICENCE): simple_markov_chain_lib.py, test.py, ex1.py

ΕΡΓΑΣΤΗΡΙΟ ΙΙ  Οδηγός χρήσης γραφικού περιβάλλοντος, Εργαστηριακή Άσκηση

                            Κώδικες (LICENCE): example_plot.py, variance.py, markov_chain_lib.py, srw2d.py

ΕΡΓΑΣΤΗΡΙΟ ΙΙI  Εργαστηριακή Άσκηση

                            Κώδικες (LICENCE): ergodic.py, ising.py, sim_annealing.py, simulated_annealing_tsp.py

                                                              plot_lib.py, eu.csv, europe.csv

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

ΣΤΑ ΕΛΛΗΝΙΚΑ

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

Ουρανία Χρυσαφίνου: Εισαγωγή στις στοχαστικές ανελίξεις, Σοφία 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

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

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

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

Δευτέρα 23/3: Πιθανότητες μετάβασης ανώτερης τάξης, τρόποι υπολογισμού.

Τρίτη 24/3: Κλάσεις επικοινωνίας, χρόνος άφιξης σ’ ένα υποσύνολο του χώρου καταστάσεων.

Δευτέρα 20/4: Θεωρία δυναμικού: πιθανότητες απορρόφησης

Τρίτη 21/4: Θεωρία δυναμικού: αναμενόμενοι χρόνοι άφιξης

Δευτέρα 27/4: Ισχυρή μαρκοβιανή ιδιότητα, χρόνοι διακοπής

Τρίτη 28/4: Παροδικότητα, επαναληψιμότητα, ιδιότητες, κριτήρια χαρακτηρισμού

Δευτέρα 4/5: Τυχαίοι περίπατοι στο Ζ^d

Τρίτη 5/5: Αναλλοίωτες κατανομές, ορισμός, ιδιότητες.

Πέμπτη 7/5: Ασκήσεις Φυλλαδίων Ι & ΙΙ

Δευτέρα 11/5: Πιθανοθεωρητική κατασκευή αναλλοίωτης κατανομής

Τρίτη 12/5: Γνήσια επαναληπτικότητα, μοναδικότητα αναλλοίωτης κατανομής για μη υποβιβάσιμες αλυσίδες

Πέμπτη 14/5: Χρονική αντιστρεψιμότητα, συνθήκες ακριβούς ισορροπίας, τυχαίοι περίπατοι σε γράφους

Δευτέρα 18/5: Ο αλγόριθμος Pagerank(TM), αναλογία μαρκοβιανών αλυσίδων και ηλεκτρικών κυκλωμάτων, η αρχή του Rayleigh.

Τρίτη 19/5: Απεριοδικότητα: ορισμός, ιδιότητες. Σύζευξη (coupling) παραδείγματα.

Πέμπτη 21/5: Ασκήσεις Φυλλαδίου ΙΙΙ

Δευτέρα 25/5: Ασυμπτωτική συμπεριφορά μαρκοβιανών αλυσίδων, σύγκλιση στην αναλλοίωτη κατανομή για μη υποβιβάσιμες, γνησίως επαναληπτικές απεριοδικές αλυσίδες.

Τρίτη 26/5: Το εργοδικό θεώρημα για μη υποβιάσιμες αλυσίδες

Πέμπτη 28/5: Το εργοδικό θεώρημα για υποβιβάσιμες αλυσίδες.

Τρίτη 1/6: Ο αλγόριθμος Metropolis-Hastings.

Πέμπτη 3/6: Ασκήσεις Φυλλαδίου ΙV

Δευτέρα 7/6: Προσομοιωμένη ανόπτηση, το πρόβλημα του πλανόδιου πωλητή.

Τρίτη 8/6: Διαδικασίες Poisson, ορισμός βασικές ιδιότητες

Δευτέρα 15/6: Διαδικασίες Poisson, ανεξάρτητες διαδικασίες Poisson, εκλέπτυνση.

Τρίτη 16/6: Αλματικές διαδικασίες συνεχούς χρόνου.

Πέμπτη 17/6: Ασκήσεις Φυλλαδίου VI