Random Walks On Trees And Electric Networks

In this thesis we will discuss some problems about random walks on trees. We will mainly introduce the relation between elementary electric network theory and random walks, central to the work will be Polya’s theorem. Namely, a random walker on an infinite street network in d-dimensional space is certain to return to the starting point when d=2, but it has a positive escaping probability to infinity without returning to the starting point when d≥3. Our purpose will be to interpret this theorem as a statement about electric networks, and then to prove the theorem by using methods from classical electrical theory.The main part of the article can be divided into two parts:Firstly, we will dis-cuss random walks on finite networks. Here we establish the connection between the electrical concepts of current and voltage and corresponding descriptive quantities of random walks regarded as finite state Markov chains. Secondly, we will consider random walks on infinite networks. By using Rayleigh’s method we prove Polya’s theorem and compare the proof with the classical proof in probability theory. Then we will discuss random walks on more general infinite graphs and derive certain extensions of Polya’s theorem by using Rayleigh’s method.