Prolaznost i povratnost slučajnih šetnji na grafovima

diplomski rad

• Autor: Hrvoje Grill
• Mentor: Nikola Sandrić (mentor)
• Član povjerenstva: Nikola Sandrić (predsjednik povjerenstva)
• Član povjerenstva: Siniša Slijepčević (član povjerenstva)
• Član povjerenstva: Ilja Gogić (č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: 2019-04-25, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Tema ovog diplomskog rada je prolaznost i povratnost slučajnih šetnji na grafovima. Diplomski rad je podijeljen u tri poglavlja. U prvom poglavlju cilj je upoznati se s Markovljevim lancima i njihovim osnovnim svojstvima. Također, uvodimo pojmove kao što su povratnost, prolaznost i reverzibilnost. U drugom poglavlju uvodimo pojam grafa te se upoznajemo s osnovnim pojmovima vezanim za graf. Uvodimo slučajnu šetnju na grafu i na električnoj mreži. Također, uvodimo pojam energije. U trećem poglavlju dajemo kriterij za prolaznost i povratnost reverzibilnog Markovljevog lanca. Također, dajemo i dovoljan uvjet za povratnost Markovljevog lanca poznat kao Nash-Williamsov kriterij. Zatim, dajemo teorem koji, uz neke dodatne pretpostavke na Markovljev lanac X, daje dovoljne uvjete za prolaznost tog lanca. Za kraj, dajemo nekoliko primjera.

Sažetak (engleski)

The topic of this thesis is transience and recurrence of random walks on graphs. The thesis is divided into three chapters. In the first chapter, the goal is to get acquainted with Markov chains and their basic properties. We also introduce the notions of recurrence, transience and reversibility. In the second chapter, we introduce the concept of a graph and get familiar with the basic concepts related to graphs. We introduce the notion of a random walk on a graph and on the electrical network. In the third chapter, we give a criterion for recurrence and transience of Markov chains. We also provide sufficient conditions for the recurrence of Markov chains known as the Nash-Williams criterion. Then we give a theorem which, with some additional assumptions on the Markov chain X, provides sufficient conditions for transience of that chain. We conclude the thesis with several examples.

• Ključne riječi: slučajne šetnje na grafovima; Markovljev lanac; Nash-Williamsov kriterij
• Ključne riječi (engleski): random walks on graphs; Markov chain; Nash-Williams criterion
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:305520
• 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: 2019-07-19 10:02:48