Martingalne tehnike i vremena miješanja Markovljevih lanaca

master's thesis

• Author: Hrvoje Planinić
• Mentor: Zoran Vondraček (mentor)
• Committee member: Zoran Vondraček (predsjednik povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Committee member: Ozren Perše (član povjerenstva)
• Committee member: Dragutin Svrtan (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-07-14, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Na početku ovog rada dajemo kratak uvod u teoriju Markovljevih lanaca na konačnom prostoru stanja. Glavni rezultat je da ireducibilan Markovljev lanac na konačnom prostoru stanja ima jedinstvenu stacionarnu distribuciju, te da uz dodatni zahtjev aperiodičnosti, distribucija lanca konvergira prema stacionarnoj distribuciji. Zanima nas brzina te konvergencije. Ključni pojmovi za njeno kvantificiranje su udaljenost potpune varijacije i vrijeme miješanja Markovljevog lanca. Središnji pojam ovog rada je proces evoluirajućih skupova koji pridružujemo svakom Markovljevom lancu. To je Markovljev lanac na podskupovima stanja originalnog lanca, sa jednostavnim prijelaznim pravilom koje povećava ili smanjuje trenutno stanje (skup). Pokazujemo osnovna svojstva tog procesa, vezu sa vremenima miješanja originalnog lanca, te definiramo Doobovu transformaciju evoluirajućih skupova. U ostatku radu koristimo evoluirajuće skupove i martingalne tehnike u rješavanju problema vezanih uz miješanje Markovljevih lanaca. Najprije se upoznajemo sa standardnom tehnikom ograničavanja vremena miješanja Markovljevih lanaca koja koristi jako stacionarna vremena. Sparivanjem Markovljevog lanca i pripadne Doobove transformacije evoluirajućih skupova, konstruiramo jako stacionarno vrijeme za originalni lanac. Nadalje, koristeći evoluirajuće skupove, poboljšavamo dosada poznate ograde na vremena miješanja Markovljevog lanca u terminima radijusa toka (engl. conductance) podskupova pripadnog prostora stanja. Ključan pojam tog dijela je funkcija radijusa toka, koja je direktna generalizacija omjera uskog grla. Na kraju, definiramo jednostavnu slučajnu šetnju na grafu, te uz pomoć evoluirajućih skupova dajemo ogradu na povratne vjerojatnosti slučajne šetnje u terminima maksimalnog stupnja pripadnog grafa.

Abstract (english)

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

• Keywords: Markovljev lanac; Markovljevi lanci; ireducibilan Markovljev lanac; Doobova transformacija evoluirajućih skupova; evoluirajući skupovi
• Keywords (english): Markov chains; irreducible Markov chain; Doob transform of the evolving set process; evolving sets
• Language: croatian
• URN:NBN: urn:nbn:hr:217:399599
• Study programme: Title: Finance and Business Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-30 10:04:01