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.