Martingalne tehnike i vremena miješanja Markovljevih lanaca

Planinić, Hrvoje (2014) Martingalne tehnike i vremena miješanja Markovljevih lanaca. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (529kB) | Preview

Abstract

In the beginning of this paper, we give a short introduction into theory of finite Markov chains. The key result is that every irreducible and finite Markov chain has a unique stationary distribution, and in the case when the chain is aperiodic, the distribution of the chain converges to its stationary distribution. The goal is to determine the rate of that convergence. We define total variation distance and mixing time of a Markov chain, the key tools for quantifying that convergence. Given a Markov chain, we define the evolving set process, a Markov chain whose states are subsets of the state space of the original chain. The transition rule of that process is a simple procedure which grows or shrinks the current state. We show the basic properties of the evolving set process, the connection with mixing time of the original chain, and define the Doob transform of the evolving sets. In the rest of the paper, we present some applications of the evolving set process using martingale techniques. At first, we introduce a standard technique for bounding mixing time of a Markov chain which uses strong stationary times. Then we construct one such time by coupling a Markov chain and the Doob transform of the evolving set process. Next, we use the evolving set process to give sharp bounds on mixing time of Markov chains in terms of conductance. An extension of the bottleneck ratio, the conductance function of a Markov chain, is key to this part. In the end, we define a simple random walk on a graph, and use evolving sets to bound the return probabilities of the random walk in terms of maximum degree of the underlying graph.

Item Type: Thesis (Diploma thesis)
Supervisor: Vondraček, Zoran
Date: 2014
Number of Pages: 65
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 17 Jun 2015 10:28
Last Modified: 17 Jun 2015 10:28
URI: http://digre.pmf.unizg.hr/id/eprint/4055

Actions (login required)

View Item View Item