Svojstvene vrijednosti prijelaznih matrica Markovljevih lanaca i primjene

diplomski rad

• Naslov (engleski): Eigenvalues of transition matrices of Markov chains and applications
• Autor: Anna-Lena Batković
• Mentor: Zoran Vondraček (mentor)
• Član povjerenstva: Vanja Wagner (predsjednik povjerenstva)
• Član povjerenstva: Andrej Dujella (član povjerenstva)
• Član povjerenstva: Filip Najman (član povjerenstva)
• Član povjerenstva: Goran Radunović (č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 obrane: 2023-07-19, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Cilj ovoga rada je proučiti granično ponašanje Markovljevih lanaca. Na početku dajemo kratak pregled osnovnih definicija i teorema iz područja Markovljevih lanaca. Teorem o konvergenciji ireducibilnog aperiodičnog lanca ka stacionarnoj distribuciji motivira nas na proučavanje brzine te konvergencije. Zato uvodimo normu potpune varijacije kao mjeru udaljenosti između dvije distribucije, te vrijeme miješanja kao broj koraka potreban da se lanac svojom distribucijom dovoljno približi stacionarnoj distribuciji. Promatrajući prijelaznu matricu reverzibilnog lanca kao linearan operator u odgovaraju ćem unitarnom prostoru, pokazujemo da je ta matrica hermitska te konstruiramo jednu ortonormiranu bazu. Također, pomoću svojstvenih vrijednosti prijelazne matrice definiramo pojmove (apsolutnog) spektralnog razmaka i vremena relaksacije, koji u konačnici odreduju gornju i donju ogradu na vrijeme miješanja. Takoder, proučit ćemo dvije važne primjene. Prva primjena je optimalno miješanje karata, pitanje koje je potaknulo razvoj teorije vremena miješanja. U drugom primjeru poopćujemo ideju jakog zakona velikih brojeva i čebiševljeve nejednakosti na Markovljeve lance, što je dio teorijske podloge na kojoj se zasnivaju MCMC metode simuliranja.

Sažetak (engleski)

The aim of this paper is to study the limiting behavior of Markov chains. We begin by introducing the fundamental definitions and theorems of Markov chain theory. A theorem which states that an irreducible and aperiodic Markov chain approaches its stationary distribution motivates us to study the speed of that convergence. Therefore, we define the total variation norm as a measure of distance between two probability distributions, and mixing times as the number of steps needed for a Markov chain to come close to the stationary distribution. Applying the theory of linear operators on a reversible transition matrix within a appropriately defined unitary space allows us to prove that the matrix is self-adjoint and so we construct an orthonormal basis which will be useful in upcoming proofs. Using eigenvalues of the transition matrix, we define the (absolute) spectral gap and relaxation time of a Markov chain and show how those values are used to establish upper and lower bounds on mixing time. We also discuss two important consequences of the mixing time theory. The first example is a problem that sparked the development of the mixing time theory in the first place – the optimal number of shuffles for a deck of cards. The second application is a generalization of the law of large numbers and Chebyshev inequality to Markov chains, which is strongly related to the theory MCMC methods are built upon.

• Ključne riječi: Markovljevi lanci; konvergencija; stacionarna distribucija; ortonormirana baza
• Ključne riječi (engleski): Markov chains; convergence; stationary distribution; orthonormal basis
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:720170
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-08 10:47:07