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 Xk
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
Xk visits A before
B, given that X0 =
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.