Κατεύθυνση Στατιστική και Επιχειρησιακή Έρευνα
Βιβλιοθήκη Σχολής Θετικών Επιστημών

2015-02-02

2015

Κοτζαμπασάκη Ελένη

Χελειώτης Δημήτριος Επίκ. Καθηγητής (Επιβλέπων), Οικονόμου Αντώνιος Λέκτορας, Παπαδάτος Νικόλαος Επίκ. Καθηγητής

Ο χρόνος μίξης για αλυσίδες Markov

Ελληνικά

Mixing time for Markov chains

Ο στόχος αυτής της εργασίας είναι να μπορέσουμε να εκτιμήσουμε το χρόνο που
χρειάζεται ώστε η κατανομή μιας Μαρκοβιανής αλυσίδας να πλησιάσει τη στάσιμή
της κατανομή. Ο αριθμός των βημάτων που απαιτούνται για να επιτευχθεί αυτή
ονομάζεται χρόνος μίξης της της αλυσίδας.Στο Κεφάλαιο 1 παρουσιάζουμε βασικούς
ορισμούς και θεωρήματα των Μαρκοβιανών αλυσίδων σε διακριτό χρόνο. Επίσης
δίνουμε παραδείγματα αλυσίδων που εφαρμόζονται συχν܈.
Στο Κεφάλαιο 2 αναφερόμαστε στο χρόνο μίξης μιας Μαρκοβιανής αλυσίδας.Ένα
χαρακτηριστικό παράδειγμα είναι το ανακάτεμα μιας τράπουλας. Έστω λοιπόν οτι
θέλουμε να ανακατέψουμε μια τράπουλα με Ν=52 φύλλα. Είναι σαφές οτι αν
ανακατέψουμε την τράπουλα ικανοποιητικά αρκετές φορέςˆ, τα τραπουλόχαρτα θα
βρεθούν σε τυχαία σειρ܈. Πρώτα όμως πρέπει να ξεκαθαρίσουμε τι εννοούμε ως
"τυχαία σειρά", και έπειτα θέλουμε να προσδιορίσουμε τον χρόνο που απαιτείται
ώστε να συμβεί αυτό.
Το μέγεθος που χρησιμοποιούμε για να μετρήσουμε την απόσταση απο την πλήρη
τυχαιότητα είναι η ολική κύμανση. Σε αυτό το κεφάλαιο, εισάγουμε αυτή την
έννοια, και διατυπώνουμε διάφορα θεωρήματα χαρακτηρισμού της. Στη συνέχεια
αποδεικνύουμε το θεώρημα σύγκλισης και τέλος δίνουμε τον ορισμό του χρόνου
μίξης. Στο Κεφάλαιο 3, εισάγουμε την έννοια της σύζευξης δύο Μαρκοβιανών
αλυσίδων. Η σύζευξη παρέχει τον βασικότερο τρόπο προσδιορισμού άνω φραγμάτων
στο χρόνο μίξης.Στο Κεφάλαιο 4, ασχολούμαστε με την εύρεση των κάτω φραγμάτων
για τον χρόνο μίξης. Η βασική τεχνική είναι να εκμεταλλευτούμε την γεωμετρία
του χώρου καταστάσεων, και πιο συγκεκριμένα την ύπαρξη μιας τουλάχιστον
στενωπού που καθυστερεί τη διαδρομή της αλυσίδας στο χώρο. Σε αυτό, όπως και
στο προηγούμενο κεφάλαιο, δίνονται εφαρμογές των τεχνικών σε συγκεκριμένες
αλυσίδες.

Μαρκοβιανές αλυσίδες, Ολική κύμανση, Σύζευξη, Χρόνος μίξης, Συμφόρηση

Όχι

0

Ναι

6

59

Δεν επιτρέπεται η πρόσβαση στο αρχείο.

https://pergamos.lib.uoa.gr/uoa/dl/object/1319216