Slučajne šetnje na beskonačnim grafovima

diplomski rad

• Naslov (engleski): Random walks on infinite graphs
• Autor: Lovro Bajramović
• Mentor: Zoran Vondraček (mentor)
• 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: 2024-11-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: slučajna šetnja; beskonačni grafovi i stabla; povratnost i prolaznost; teorija potencijala Markovljevih lanaca; geometrija grafa; logaritamski kapacitet
• Ključne riječi (engleski): random walks; infinite graphs and trees; recurrence and transience; Markov Chains potential theory; geometry of graph; logarithmic capacity
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:742101
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-11-12 12:57:39