{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1319216"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1319216","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Ο χρόνος μίξης για αλυσίδες Markov","abstract":"Ο στόχος αυτής της εργασίας είναι να μπορέσουμε να εκτιμήσουμε το χρόνο που χρειάζεται ώστε η κατανομή μιας Μαρκοβιανής αλυσίδας να πλησιάσει τη στάσιμή της κατανομή. Ο αριθμός των βημάτων που απαιτούνται για να επιτευχθεί αυτή ονομάζεται χρόνος μίξης της της αλυσίδας.Στο Κεφάλαιο 1 παρουσιάζουμε βασικούς ορισμούς και θεωρήματα των Μαρκοβιανών αλυσίδων σε διακριτό χρόνο. Επίσης δίνουμε παραδείγματα αλυσίδων που εφαρμόζονται συχνά. Στο Κεφάλαιο 2 αναφερόμαστε στο χρόνο μίξης μιας Μαρκοβιανής αλυσίδας.Ένα χαρακτηριστικό παράδειγμα είναι το ανακάτεμα μιας τράπουλας. Έστω λοιπόν οτι θέλουμε να ανακατέψουμε μια τράπουλα με Ν=52 φύλλα. Είναι σαφές οτι αν ανακατέψουμε την τράπουλα ικανοποιητικά αρκετές φορές, τα τραπουλόχαρτα θα βρεθούν σε τυχαία σειρά. Πρώτα όμως πρέπει να ξεκαθαρίσουμε τι εννοούμε ως \"τυχαία σειρά\", και έπειτα θέλουμε να προσδιορίσουμε τον χρόνο που απαιτείται ώστε να συμβεί αυτό. Το μέγεθος που χρησιμοποιούμε για να μετρήσουμε την απόσταση απο την πλήρη τυχαιότητα είναι η ολική κύμανση. Σε αυτό το κεφάλαιο, εισάγουμε αυτή την έννοια, και διατυπώνουμε διάφορα θεωρήματα χαρακτηρισμού της. Στη συνέχεια αποδεικνύουμε το θεώρημα σύγκλισης και τέλος δίνουμε τον ορισμό του χρόνου μίξης. Στο Κεφάλαιο 3, εισάγουμε την έννοια της σύζευξης δύο Μαρκοβιανών αλυσίδων. Η σύζευξη παρέχει τον βασικότερο τρόπο προσδιορισμού άνω φραγμάτων στο χρόνο μίξης.Στο Κεφάλαιο 4, ασχολούμαστε με την εύρεση των κάτω φραγμάτων για τον χρόνο μίξης. Η βασική τεχνική είναι να εκμεταλλευτούμε την γεωμετρία του χώρου καταστάσεων, και πιο συγκεκριμένα την ύπαρξη μιας τουλάχιστον στενωπού που καθυστερεί τη διαδρομή της αλυσίδας στο χώρο. Σε αυτό, όπως και στο προηγούμενο κεφάλαιο, δίνονται εφαρμογές των τεχνικών σε συγκεκριμένες αλυσίδες.","abstract_html":"Ο στόχος αυτής της εργασίας είναι να μπορέσουμε να εκτιμήσουμε το χρόνο που χρειάζεται ώστε η κατανομή μιας Μαρκοβιανής αλυσίδας να πλησιάσει τη στάσιμή της κατανομή. Ο αριθμός των βημάτων που απαιτούνται για να επιτευχθεί αυτή ονομάζεται χρόνος μίξης της της αλυσίδας.Στο Κεφάλαιο 1 παρουσιάζουμε βασικούς ορισμούς και θεωρήματα των Μαρκοβιανών αλυσίδων σε διακριτό χρόνο. Επίσης δίνουμε παραδείγματα αλυσίδων που εφαρμόζονται συχνά. Στο Κεφάλαιο 2 αναφερόμαστε στο χρόνο μίξης μιας Μαρκοβιανής αλυσίδας.Ένα χαρακτηριστικό παράδειγμα είναι το ανακάτεμα μιας τράπουλας. Έστω λοιπόν οτι θέλουμε να ανακατέψουμε μια τράπουλα με Ν=52 φύλλα. Είναι σαφές οτι αν ανακατέψουμε την τράπουλα ικανοποιητικά αρκετές φορές, τα τραπουλόχαρτα θα βρεθούν σε τυχαία σειρά. Πρώτα όμως πρέπει να ξεκαθαρίσουμε τι εννοούμε ως &quot;τυχαία σειρά&quot;, και έπειτα θέλουμε να προσδιορίσουμε τον χρόνο που απαιτείται ώστε να συμβεί αυτό. Το μέγεθος που χρησιμοποιούμε για να μετρήσουμε την απόσταση απο την πλήρη τυχαιότητα είναι η ολική κύμανση. Σε αυτό το κεφάλαιο, εισάγουμε αυτή την έννοια, και διατυπώνουμε διάφορα θεωρήματα χαρακτηρισμού της. Στη συνέχεια αποδεικνύουμε το θεώρημα σύγκλισης και τέλος δίνουμε τον ορισμό του χρόνου μίξης. Στο Κεφάλαιο 3, εισάγουμε την έννοια της σύζευξης δύο Μαρκοβιανών αλυσίδων. Η σύζευξη παρέχει τον βασικότερο τρόπο προσδιορισμού άνω φραγμάτων στο χρόνο μίξης.Στο Κεφάλαιο 4, ασχολούμαστε με την εύρεση των κάτω φραγμάτων για τον χρόνο μίξης. Η βασική τεχνική είναι να εκμεταλλευτούμε την γεωμετρία του χώρου καταστάσεων, και πιο συγκεκριμένα την ύπαρξη μιας τουλάχιστον στενωπού που καθυστερεί τη διαδρομή της αλυσίδας στο χώρο. Σε αυτό, όπως και στο προηγούμενο κεφάλαιο, δίνονται εφαρμογές των τεχνικών σε συγκεκριμένες αλυσίδες.","abstract_has_math":false,"creators":["Κοτζαμπασάκη Ελένη"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-11-19T05:25:36Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1319216"],"render_values":[{"text":"uoadl:1319216","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1319216","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1319216","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1319216","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Κοτζαμπασάκη Ελένη"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1319216","https://pergamos.lib.uoa.gr/uoa/dl/object/1319216"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ο στόχος αυτής της εργασίας είναι να μπορέσουμε να εκτιμήσουμε το χρόνο που χρειάζεται ώστε η κατανομή μιας Μαρκοβιανής αλυσίδας να πλησιάσει τη στάσιμή της κατανομή. Ο αριθμός των βημάτων που απαιτούνται για να επιτευχθεί αυτή ονομάζεται χρόνος μίξης της της αλυσίδας.Στο Κεφάλαιο 1 παρουσιάζουμε βασικούς ορισμούς και θεωρήματα των Μαρκοβιανών αλυσίδων σε διακριτό χρόνο. Επίσης δίνουμε παραδείγματα αλυσίδων που εφαρμόζονται συχνά. Στο Κεφάλαιο 2 αναφερόμαστε στο χρόνο μίξης μιας Μαρκοβιανής αλυσίδας.Ένα χαρακτηριστικό παράδειγμα είναι το ανακάτεμα μιας τράπουλας. Έστω λοιπόν οτι θέλουμε να ανακατέψουμε μια τράπουλα με Ν=52 φύλλα. Είναι σαφές οτι αν ανακατέψουμε την τράπουλα ικανοποιητικά αρκετές φορές, τα τραπουλόχαρτα θα βρεθούν σε τυχαία σειρά. Πρώτα όμως πρέπει να ξεκαθαρίσουμε τι εννοούμε ως \"τυχαία σειρά\", και έπειτα θέλουμε να προσδιορίσουμε τον χρόνο που απαιτείται ώστε να συμβεί αυτό. Το μέγεθος που χρησιμοποιούμε για να μετρήσουμε την απόσταση απο την πλήρη τυχαιότητα είναι η ολική κύμανση. Σε αυτό το κεφάλαιο, εισάγουμε αυτή την έννοια, και διατυπώνουμε διάφορα θεωρήματα χαρακτηρισμού της. Στη συνέχεια αποδεικνύουμε το θεώρημα σύγκλισης και τέλος δίνουμε τον ορισμό του χρόνου μίξης. Στο Κεφάλαιο 3, εισάγουμε την έννοια της σύζευξης δύο Μαρκοβιανών αλυσίδων. Η σύζευξη παρέχει τον βασικότερο τρόπο προσδιορισμού άνω φραγμάτων στο χρόνο μίξης.Στο Κεφάλαιο 4, ασχολούμαστε με την εύρεση των κάτω φραγμάτων για τον χρόνο μίξης. Η βασική τεχνική είναι να εκμεταλλευτούμε την γεωμετρία του χώρου καταστάσεων, και πιο συγκεκριμένα την ύπαρξη μιας τουλάχιστον στενωπού που καθυστερεί τη διαδρομή της αλυσίδας στο χώρο. Σε αυτό, όπως και στο προηγούμενο κεφάλαιο, δίνονται εφαρμογές των τεχνικών σε συγκεκριμένες αλυσίδες.","The aim of this work is to be able to estimate the time required the distribution of a Markov chain to approach it's stationary distribution. The number of steps required to achieve this is called mixing time of this chain.In Chapter 1 we present basic definitions and theorems of Markov chains in discrete time. We also give examples of chains that are often applied. In Chapter 2, we refer to the mixing time of a Markov chain. A typical example is shuffling a deck. Suppose that we want to shuffle a deck of N = 52 cards. It is clear that if you shuffle the deck sufficiently several times, the cards are placed at random order. But first we have to clarify what we mean by \"random order\", and then we can determine the time required to make this happen.The size we use to measure the distance from the complete randomness is the total variance. In this chapter, we introduce this definition, and formulate several theorems characterization. Then we prove the convergence theorem and finally we give the definition of mixing time. In Chapter 3, we introduce the concept of coupling two Markov chains. The coupling provides the most basic way of determining upper bounds on the mixing time. In Chapter 4, we deal with finding lower bounds for the mixing time. The basic technique is to utilize the geometry of the state space, and more specifically the existence of at least one bottleneck which delays route of the chain in space. In this, as in the previous chapter, we give applications of techniques in specific chains."]},{"key":"dc:title","label":"Title","values":["Ο χρόνος μίξης για αλυσίδες Markov"]}]}],"canonical_facts":{"dc:creator":["Κοτζαμπασάκη Ελένη"],"dc:date":["2015"],"dc:description":["Ο στόχος αυτής της εργασίας είναι να μπορέσουμε να εκτιμήσουμε το χρόνο που χρειάζεται ώστε η κατανομή μιας Μαρκοβιανής αλυσίδας να πλησιάσει τη στάσιμή της κατανομή. Ο αριθμός των βημάτων που απαιτούνται για να επιτευχθεί αυτή ονομάζεται χρόνος μίξης της της αλυσίδας.Στο Κεφάλαιο 1 παρουσιάζουμε βασικούς ορισμούς και θεωρήματα των Μαρκοβιανών αλυσίδων σε διακριτό χρόνο. Επίσης δίνουμε παραδείγματα αλυσίδων που εφαρμόζονται συχνά. Στο Κεφάλαιο 2 αναφερόμαστε στο χρόνο μίξης μιας Μαρκοβιανής αλυσίδας.Ένα χαρακτηριστικό παράδειγμα είναι το ανακάτεμα μιας τράπουλας. Έστω λοιπόν οτι θέλουμε να ανακατέψουμε μια τράπουλα με Ν=52 φύλλα. Είναι σαφές οτι αν ανακατέψουμε την τράπουλα ικανοποιητικά αρκετές φορές, τα τραπουλόχαρτα θα βρεθούν σε τυχαία σειρά. Πρώτα όμως πρέπει να ξεκαθαρίσουμε τι εννοούμε ως \"τυχαία σειρά\", και έπειτα θέλουμε να προσδιορίσουμε τον χρόνο που απαιτείται ώστε να συμβεί αυτό. Το μέγεθος που χρησιμοποιούμε για να μετρήσουμε την απόσταση απο την πλήρη τυχαιότητα είναι η ολική κύμανση. Σε αυτό το κεφάλαιο, εισάγουμε αυτή την έννοια, και διατυπώνουμε διάφορα θεωρήματα χαρακτηρισμού της. Στη συνέχεια αποδεικνύουμε το θεώρημα σύγκλισης και τέλος δίνουμε τον ορισμό του χρόνου μίξης. Στο Κεφάλαιο 3, εισάγουμε την έννοια της σύζευξης δύο Μαρκοβιανών αλυσίδων. Η σύζευξη παρέχει τον βασικότερο τρόπο προσδιορισμού άνω φραγμάτων στο χρόνο μίξης.Στο Κεφάλαιο 4, ασχολούμαστε με την εύρεση των κάτω φραγμάτων για τον χρόνο μίξης. Η βασική τεχνική είναι να εκμεταλλευτούμε την γεωμετρία του χώρου καταστάσεων, και πιο συγκεκριμένα την ύπαρξη μιας τουλάχιστον στενωπού που καθυστερεί τη διαδρομή της αλυσίδας στο χώρο. Σε αυτό, όπως και στο προηγούμενο κεφάλαιο, δίνονται εφαρμογές των τεχνικών σε συγκεκριμένες αλυσίδες.","The aim of this work is to be able to estimate the time required the distribution of a Markov chain to approach it's stationary distribution. The number of steps required to achieve this is called mixing time of this chain.In Chapter 1 we present basic definitions and theorems of Markov chains in discrete time. We also give examples of chains that are often applied. In Chapter 2, we refer to the mixing time of a Markov chain. A typical example is shuffling a deck. Suppose that we want to shuffle a deck of N = 52 cards. It is clear that if you shuffle the deck sufficiently several times, the cards are placed at random order. But first we have to clarify what we mean by \"random order\", and then we can determine the time required to make this happen.The size we use to measure the distance from the complete randomness is the total variance. In this chapter, we introduce this definition, and formulate several theorems characterization. Then we prove the convergence theorem and finally we give the definition of mixing time. In Chapter 3, we introduce the concept of coupling two Markov chains. The coupling provides the most basic way of determining upper bounds on the mixing time. In Chapter 4, we deal with finding lower bounds for the mixing time. The basic technique is to utilize the geometry of the state space, and more specifically the existence of at least one bottleneck which delays route of the chain in space. In this, as in the previous chapter, we give applications of techniques in specific chains."],"dc:identifier":["uoadl:1319216","https://pergamos.lib.uoa.gr/uoa/dl/object/1319216"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Ο χρόνος μίξης για αλυσίδες Markov"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:25:36Z"}