prikaz prve stranice dokumenta Martingalne tehnike i vremena miješanja Markovljevih lanaca
  Preuzmi
PDF 517.23 KB
diplomski rad
Martingalne tehnike i vremena miješanja Markovljevih lanaca
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2014. urn:nbn:hr:217:399599
Planinić, Hrvoje
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Planinić, H. (2014). Martingalne tehnike i vremena miješanja Markovljevih lanaca (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:399599

Planinić, Hrvoje. "Martingalne tehnike i vremena miješanja Markovljevih lanaca." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2014. https://urn.nsk.hr/urn:nbn:hr:217:399599

Planinić, Hrvoje. "Martingalne tehnike i vremena miješanja Markovljevih lanaca." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2014. https://urn.nsk.hr/urn:nbn:hr:217:399599

Planinić, H. (2014). 'Martingalne tehnike i vremena miješanja Markovljevih lanaca', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 23.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:399599

Planinić H. Martingalne tehnike i vremena miješanja Markovljevih lanaca [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2014 [pristupljeno 23.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:399599

H. Planinić, "Martingalne tehnike i vremena miješanja Markovljevih lanaca", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2014. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:399599

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:399599
Podaci o radu
NaslovMartingalne tehnike i vremena miješanja Markovljevih lanaca
AutorHrvoje Planinić
MentorZoran Vondraček (mentor)
Član povjerenstvaZoran Vondraček (predsjednik povjerenstva)
Član povjerenstvaVedran Krčadinac (član povjerenstva)
Član povjerenstvaOzren Perše (član povjerenstva)
Član povjerenstvaDragutin Svrtan (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2014-07-14, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
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.
Sažetak (engleski)
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
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:399599
Studijski programNaziv: Financijska i poslovna matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2019-01-30 10:04:01