|
|
Strong stationary times and convergence of Markov chains
Suk, Luboš ; Prokešová, Michaela (advisor) ; Kříž, Pavel (referee)
In this thesis we study the estimation of speed of convergence of Markov chains to their stacionary distributions. For that purpose we will use the method of strong stationary times. We focus on irreducible and aperiodic chains only since in that case the existence of exactly one stationary distribution is guaranteed. We introduce the mixing time for a Markov chain as the time needed for the marginal distribution of the chain to be sufficiently close to the stationary dis- tribution. The distance between two distributions is measured by the total variation distance. The main goal of this thesis is to construct an appropriate strong stationary time for selected chains and then use it for obtaining an upper bound for the mixing time.
|
|
|
Convergence of the Markov chain Monte Carlo method
Dzurilla, Matúš ; Beneš, Viktor (advisor) ; Dostál, Petr (referee)
This thesis deals with the problem of random q-coloring from graph theory, in which goal is to color all vertices of graph by q colors so that no adjacent vertices have the same color. The aim is to generate random q-coloring from uniform distribution on the set of relevant solutions. The problem was expres- sed through Markov chain and approach was done through Markov Chain Monte Carlo method, namely the Gibbs sampler. The aim was to modify theorem of fast convergence of Gibbs sampler from systematic sweep to random sweep. It was ne- cessary to prove several auxiliary theorems, and in the proof of main theorem the "coupling" method was used. We managed to estimate the number of iterations needed to make the distance, in terms of total variation,from the distribution on the chain to the target distribution sufficiently small. The meaning og the the- orem was demonstrated in numerical examples and example od simulation was also added. 24
|
|
|
Convergence of the Markov chain Monte Carlo method
Dzurilla, Matúš ; Beneš, Viktor (advisor) ; Dostál, Petr (referee)
This thesis deals with the problem of random q-coloring from graph theory, in which goal is to color all vertices of graph by q colors so that no adjacent vertices have the same color. The aim is to generate random q-coloring from uniform distribution on the set of relevant solutions. The problem was expres- sed through Markov chain and approach was done through Markov Chain Monte Carlo method, namely the Gibbs sampler. The aim was to modify theorem of fast convergence of Gibbs sampler from systematic sweep to random sweep. It was ne- cessary to prove several auxiliary theorems, and in the proof of main theorem the "coupling" method was used. We managed to estimate the number of iterations needed to make the distance, in terms of total variation,from the distribution on the chain to the target distribution sufficiently small. The meaning og the the- orem was demonstrated in numerical examples and example od simulation was also added. 24
|
|
|
Strong stationary times and convergence of Markov chains
Suk, Luboš ; Prokešová, Michaela (advisor) ; Kříž, Pavel (referee)
In this thesis we study the estimation of speed of convergence of Markov chains to their stacionary distributions. For that purpose we will use the method of strong stationary times. We focus on irreducible and aperiodic chains only since in that case the existence of exactly one stationary distribution is guaranteed. We introduce the mixing time for a Markov chain as the time needed for the marginal distribution of the chain to be sufficiently close to the stationary dis- tribution. The distance between two distributions is measured by the total variation distance. The main goal of this thesis is to construct an appropriate strong stationary time for selected chains and then use it for obtaining an upper bound for the mixing time.
|
guest ::
