Skip to content

# 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*_{0} =
*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.