Sparivanje

master's thesis

• Title (english): Coupling method
• Author: Nikola Jalšenjak
• Mentor: Bojan Basrak (mentor)
• Committee member: Bojan Basrak (predsjednik povjerenstva)
• Committee member: Hrvoje Planinić (član povjerenstva)
• Committee member: Marko Erceg (član povjerenstva)
• Committee member: Miljenko Huzak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-09-23, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Metoda sparivanja je važna metoda u teoriji vjerojatnosti s mnogobrojnim primjenama. Temelji se na konstrukciji kopija slučajnih elemenata na zajedničkom vjerojatnosnom prostoru kako bi mogli odrediti svojstva i usporediti ih. U ovom radu uvodimo pojam sparivanja s nekoliko primjera i metoda za konstrukciju. Definiramo udaljenost totalne varijacije i nejednakost u sparivanju koje koristimo za usporedbu slučajnih varijabli. Pokazujemo da postoji maksimalno sparivanje. Proučavamo odnos izmedu sparivanja i konvergencije slučajnih varijabli. Primjenjujemo metodu sparivanja na Poissonovu aproksimaciju. Dokazujemo tvrdnje da su sume nezavisnih Bernoullijevih slučajnih varijabli blizu Poissonove distribucije. Također, sparivanje je važno u dokazivanju asimptotskih svojstava stohastičkih procesa. Standardni rezultat dobiven sparivanjem je granični teorem za Markovljeve lance. Definiramo Ornsteinovo sparivanje i epsilon-sparivanje na slučajnim šetnjama za dokaz asimptotskih svojstava. Glavni cilj nam je pokazati Blackwellov teorem obnavljanja. Sparivanje je korisno u egzaktnom uzorkovanju. Opisujemo algoritam sparivanja iz prošlosti za egzaktno uzorkovanje iz konačnog skupa. U ovoj metodi konstruiramo Markovljeve lance iz sve udaljenijih točaka u prošlosti dok god su stanja u sadašnjosti različita. Na taj način algoritam sam određuje kada se treba zaustaviti i vraća vrijednost iz stacionarne distribucije. Uvodimo Isingov model iz fizike koji se može koristiti i za analizu slika. Algoritam sparivanja iz prošlosti implementiramo za Isingov model i pokazujemo rezultate.

Abstract (english)

The coupling method is a versatile proof technique in modern probability theory with a wide range of applications. Coupling consists of constructing copies of random elements on a common probability space in order to deduce properties or discover similarities or relations between them. In this master’s thesis, the notion of coupling is introduced with a few examples and methods of construction. We define the total variation norm and coupling inequalities, which are basic tools for comparing random variables. It is proved that there exists a maximal coupling which is in some sense the best coupling. Furthermore, we study the relation between coupling and convergence of random variables. We use the coupling method in the Poisson approximation. We prove that the sum of Bernoulli random variables is close to the Poisson distribution. Also, coupling is a key tool in the study of asymptotic properties of stochastic processes. The standard result is the Markov chain convergence theorem. We construct two variations of coupling called the Ornstein coupling and the epsilon-coupling of random walks to prove asymptotic results. The main goal is to give the coupling proof of Blackwell’s renewal theorem. Coupling is also useful in exact sampling. We describe the coupling from the past algorithm for exact sampling from a finite set. In this method, coupled Markov chains are started from the points in the more and more distant past and run until they coalesce in the present. Thus, the algorithm determines when to stop and returns value distributed exactly according to the stationary distribution. Furthermore, we introduce the Ising model and describe its application to image analysis. Finally, we implement the algorithm on the Ising model and show the simulation results.

• Keywords: teorija vjerojatnosti; maksimalno sparivanje; Poissonova distribucija; Blackwellov teorem obnavljanja; Isingov model
• Keywords (english): probability theory; maximal coupling; Poisson distribution; Blackwell’s renewal theorem; Ising model
• Language: croatian
• URN:NBN: urn:nbn:hr:217:850261
• Study programme: Title: Mathematical Statistics; 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: 2021-10-27 11:50:49