VIGRE seminar, summer 2000: Random Walks and Electric Networks, Uniform Spanning Trees

Instructors

Dante DeBlassie, Joel Zinn

Students enrolled

Vincent Lemoine, Nicholas Neumann, Kendra Quesenberry (undergraduate mathematics students); Cesar Garcia, Sachindrana Jayaraman, Lovas Randrianarivony, Darren Rhea, Paul Schumacher, Stephen Shauger, Xiaofei Zhang (graduate mathematics students); Jeffrey Warren, (graduate industrial engineering student)

Description

The deep connection between Brownian motion and Newtonian potential theory provides an important application of probability theory to electric networks. However, a relatively high degree of sophistication is usually required to appreciate this connection. In contrast, this seminar investigated similar connections between Markov chains and electrical networks which require only a little knowledge of probability theory. The basic relationship is the following. Let S be the nodes of an electrical network and denote by C(a,b) the conductance between nodes a and b. If C(a,b)=0, there is no connection between a and b. Let X_k be a Markov chain with state space S and transition probabilities given by C(a,b) (normalized so that their sum is one). This is just the probability that the chain jumps from a to b after one tick of the clock. Let A and B be disjoint subsets of S, held at potentials 1 and 0, respectively. Then the potential at a can be interpreted as the probability that X_k visits A before B, given that X₀ = a.

The list of topics discussed includes:

Random walks on finite networks; Current, voltage and finite Markov chains; Random walks on infinite networks; Polya's Theorem via Rayleigh's method; Random walks on more general infinite graphs; Spanning trees and random walks; Transfer-impedance; Poisson limits; Infinite lattices, dimers and entropy.

Impact

Two of the graduate students in this VIGRE} seminar are now pursuing probability as their major field of graduate study: Jayaraman is studying under Dante DeBlassie and Schumacher is studying under Joel Zinn.