Abstract: Even if random walks and electric networks do not sound related to each other, it turns out that there are interesting relationships between these two areas. We can consider a random walk on Z^2 as follows: We imagine streets of a city and a man now starts from a certain corner. With probability 1/d, where d denotes the number of adjacent streets of that corner, he walks to one of the streets. When he comes to the next corner he again randomly chooses his direction. How is this related to electric networks? We choose two points a and b and put a one-volt battery across these points establishing a voltage v(a) = 1 and v(b) = 0. We are interested in finding the voltages v(x) at the other vertices and the currents i(x,y) which flow through the network. The probabilistic interpretations of voltage and current turn out to be very useful: The voltage can be interpreted as a hitting probability, i.e. the voltage v(x) at any point x represents the probability that a walker starting from x will return to a before reaching b. Also the probabilistic interpretation of current is very interesting: We are going to see that the current i(x,y) flowing through the edge connecting x to y is equal to the expected net number of times that a walker, starting at a and walking until he reaches b, will move along the edge from x to y. Moreover, we will observe how we can solve the type problem with the results of the electric networks: Is the wandering point certain to return to its starting point during the course of its wanderings? And what is the connection between random walks and uniform spanning trees? We will see that Aldous-Broder algorithm and Wilson's algorithm simulate random walks to generate random spanning trees. A nice result will be that the inclusion probabilities of edges in the tree can be related to quantities in the electric network.
Minden érdeklõdõt szeretettel várunk,
Péter