Sparivanje

diplomski rad

• Naslov (engleski): Coupling method
• Autor: Nikola Jalšenjak
• Mentor: Bojan Basrak (mentor)
• Član povjerenstva: Bojan Basrak (predsjednik povjerenstva)
• Član povjerenstva: Hrvoje Planinić (član povjerenstva)
• Član povjerenstva: Marko Erceg (član povjerenstva)
• Član povjerenstva: Miljenko Huzak (č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: 2021-09-23, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: teorija vjerojatnosti; maksimalno sparivanje; Poissonova distribucija; Blackwellov teorem obnavljanja; Isingov model
• Ključne riječi (engleski): probability theory; maximal coupling; Poisson distribution; Blackwell’s renewal theorem; Ising model
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:850261
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-10-27 11:50:49