Unit:
Κατεύθυνση Στατιστική και Επιχειρησιακή ΈρευναLibrary of the School of Science
Author:
Κοτζαμπασάκη Ελένη
Supervisors info:
Χελειώτης Δημήτριος Επίκ. Καθηγητής (Επιβλέπων), Οικονόμου Αντώνιος Λέκτορας, Παπαδάτος Νικόλαος Επίκ. Καθηγητής
Original Title:
Ο χρόνος μίξης για αλυσίδες Markov
Translated title:
Mixing time for Markov chains
Summary:
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.
Keywords:
Markov chain, Total variation, Coypling, Mixing time, Bottleneck
File:
File access is restricted.
document.pdf
1 MB
File access is restricted.
