Aim of the thesis is to prove Polya's theorem: a random walker on the d-dimensional 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 network-based 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 short-cut 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 d-dimensional 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 network-based 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 short-cut 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

#### Abstract

Aim of the thesis is to prove Polya's theorem: a random walker on the d-dimensional 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 network-based 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 short-cut method that consists in adding and cutting edges to get lower and upper bounds for the resistance of the graph.
##### Scheda Scheda DC
2022
Random walks on graphs and electric networks
Aim of the thesis is to prove Polya's theorem: a random walker on the d-dimensional 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 network-based 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 short-cut method that consists in adding and cutting edges to get lower and upper bounds for the resistance of the graph.
Markov chains
Random walks
Polya's theorem
File in questo prodotto:
File
Florio_Francesca.pdf

accesso aperto

Dimensione 505.06 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/20.500.12608/61303`