Prolaznost i povratnost slučajnih šetnji na grafovima

master's thesis

• Author: Hrvoje Grill
• Mentor: Nikola Sandrić (mentor)
• Committee member: Nikola Sandrić (predsjednik povjerenstva)
• Committee member: Siniša Slijepčević (član povjerenstva)
• Committee member: Ilja Gogić (član povjerenstva)
• Committee member: Goran Radunović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-04-25, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

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