Slučajne šetnje na beskonačnim grafovima

master's thesis

• Title (english): Random walks on infinite graphs
• Author: Lovro Bajramović
• Mentor: Zoran Vondraček (mentor)
• Committee member: Zoran Vondraček (predsjednik povjerenstva)
• Committee member: Hrvoje Planinić (član povjerenstva)
• Committee member: Nikola Sandrić (član povjerenstva)
• Committee member: Vanja Wagner (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2024-11-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu glavni je cilj proučiti prolaznost i povratnost slučajnih šetnji na beskonačnim grafovima ovisno o geometriji grafa. Na početku rada dane su definicije pojmova iz teorije grafova i teorije Markovljevih lanaca te su obrađeni osnovni, ali i drugi važni rezultati vezani uz Markovljeve lance. Uvodi se pojam slučajne šetnje na grafu te se definiraju njezina svojstva poput ograničenog dosega i uniformne ireducibilnosti. Promatranjem skupova vrhova i bridova grafa kao Hilbertovih prostora s mjerom, uvođenjem pojmova iz teorije potencijala kao što su provodljivost, otpor, tok i energija te pridruživanjem pojma mreže Markovljevu lancu obrađeni su razni nužni i dovoljni uvjeti prolaznosti reverzibilnih i nereverzibilnih Markovljevih lanaca, jedan od kojih je postojanje konačnog toka energije. Također, definiranjem mreže kratkog spoja pokazan je Nash-Williamsov kriterij povratnosti. Primjenom dobivenih rezultata napravljena je usporedba, u vidu svojstva povratnosti, različitih slučajnih šetnji na grafu s ograničenom geometrijom, a zatim i usporedba različitih grafova. Naposljetku, dodatno se proučava povratnost slučajne šetnje na beskonačnim stablima koristeći se funkcijom rasta slučajne šetnje te promatrajući beskonačne putove i logaritamski kapacitet.

Abstract (english)

In this thesis, the main goal is to study transience and recurrence of random walks on infinite graphs depending on the geometry of the graph. At the beginning of the thesis, definitions of terms from the theory of graphs and the theory of Markov chains are given, and basic and other important results related to Markov chains are discussed. The concept of a random walk on a graph is introduced and its properties such as bounded range and uniform irreducibility are defined. By observing the sets of vertices and edges of the graph as Hilbert spaces with measure, by introducing terms from potential theory such as conductivity, resistance, flow and energy, and by associating the term network to the Markov chain, various necessary and sufficient conditions for transience of reversible and non-reversible Markov chains have been studied, one of which is the existence of a finite flow of energy. Also, by defining the shorted network, the Nash-Williams recurrence criterion was demonstrated. By applying the obtained results, a comparison was made, in terms of the recurrence property, of different random walks on a graph with bounded geometry, and then a comparison of different graphs. Finally, the return of the random walk on infinite trees is further studied using the growth function of the random walk and looking at infinite paths and logarithmic capacity.

• Keywords: slučajna šetnja; beskonačni grafovi i stabla; povratnost i prolaznost; teorija potencijala Markovljevih lanaca; geometrija grafa; logaritamski kapacitet
• Keywords (english): random walks; infinite graphs and trees; recurrence and transience; Markov Chains potential theory; geometry of graph; logarithmic capacity
• Language: croatian
• URN:NBN: urn:nbn:hr:217:742101
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-11-12 12:57:39