Aim of the thesis is to prove Polya's theorem: a random walker on the ddimensional lattice is bound to return to the starting point when d = 1, 2, but has a positive probability of escaping to infinity without returning to the starting point when d ≥ 3. The proof presented in the thesis exploits the connection between electric network quantities (i.e. capacities, resistances and voltages) and transience and recurrence of networkbased random walks. Electric networks and how they relate to transience and recurrence of irreducible reversible Markov chains are covered in the first two chapters of the thesis. The main result is that the resistance of the graph gives information on the transience/recurrence properties of the chain. Then the proof of Polya's theorem (Chapter 3) proceeds through Rayleigh's shortcut method that consists in adding and cutting edges to get lower and upper bounds for the resistance of the graph.
Aim of the thesis is to prove Polya's theorem: a random walker on the ddimensional lattice is bound to return to the starting point when d = 1, 2, but has a positive probability of escaping to infinity without returning to the starting point when d ≥ 3. The proof presented in the thesis exploits the connection between electric network quantities (i.e. capacities, resistances and voltages) and transience and recurrence of networkbased random walks. Electric networks and how they relate to transience and recurrence of irreducible reversible Markov chains are covered in the first two chapters of the thesis. The main result is that the resistance of the graph gives information on the transience/recurrence properties of the chain. Then the proof of Polya's theorem (Chapter 3) proceeds through Rayleigh's shortcut method that consists in adding and cutting edges to get lower and upper bounds for the resistance of the graph.
Random walks on graphs and electric networks
FLORIO, FRANCESCA
2022/2023
Abstract
Aim of the thesis is to prove Polya's theorem: a random walker on the ddimensional lattice is bound to return to the starting point when d = 1, 2, but has a positive probability of escaping to infinity without returning to the starting point when d ≥ 3. The proof presented in the thesis exploits the connection between electric network quantities (i.e. capacities, resistances and voltages) and transience and recurrence of networkbased random walks. Electric networks and how they relate to transience and recurrence of irreducible reversible Markov chains are covered in the first two chapters of the thesis. The main result is that the resistance of the graph gives information on the transience/recurrence properties of the chain. Then the proof of Polya's theorem (Chapter 3) proceeds through Rayleigh's shortcut method that consists in adding and cutting edges to get lower and upper bounds for the resistance of the graph.File  Dimensione  Formato  

Florio_Francesca.pdf
accesso aperto
Dimensione
505.06 kB
Formato
Adobe PDF

505.06 kB  Adobe PDF  Visualizza/Apri 
The text of this website © Università degli studi di Padova. Full Text are published under a nonexclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/61303