Random Walks and Electric Networks

Peter G. Doyle and J. Laurie Snell
Publisher:
Mathematical Association of America
Publication Date:
1984
Number of Pages:
159
Format:
Hardcover
Price:
24.95
ISBN:
978-0883850244
Category:
Textbook
BLL Rating:

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Bill Wood
, on
06/22/2010
]

Mathematics needs more books like this.

Begin with the classical simple random walk. A drunkard walks along a street in such a way that at every block he decides randomly whether to continue along the street or turn around. His home and his bar are on opposite ends the street, five blocks apart, and he will stay at whichever location he encounters first. If the drunkard begins x blocks from home in the direction of the bar, we would like to understand the function p(x) that reports the probability that he will hit the bar first.

Now consider a different problem. Suppose five equal resistors are placed in series and we connect a battery to opposite ends of the chain of resistors. We now want to understand the function v(x) that reports the voltage x units from the ground of the battery.

These turn out to be the same problem, but the really interesting part is why. It is not difficult to prove using elementary properties of probability and electric networks that both functions satisfy the averaging property f(x) = (f(x+1)+f(x–1))/2 for any x not on the boundary (bar or home, the battery terminals, or in both cases, simply x=0 or x=5). Both functions also take the same values on the boundary: f(0)=0 and f(5)=1.

The averaging property is familiar from classical harmonic functions and one goal of this book is to exploit this connection. In particular, both of the above scenarios are solutions to the same discrete Dirichlet problem, in which we find a discrete harmonic function inside a network with prescribed values on the boundary. It turns out that these problems have unique solutions, and therefore the functions p(x) and v(x) — and their associated problems — are the same. This allows the authors to use tools from both fields to approach the subject by appealing to probabilistic intuition to explain current flow or using Kirchoff’s Laws to solve problems in random walks. Indeed, elementary circuit reduction is a frequently used tool.

The book is divided into two parts. The first part deals entirely in finite graphs and develops discrete harmonic functions and discrete Dirichlet problems. The primary tool is Rayleigh’s Method, in which the effective resistance through one circuit is bounded by the effective resistance through another formed by adding or removing resistors. The graphs are infinite in the second part, where the central question is of recurrence: whether or not a random walker is likely to return to his starting point. The authors’ primary objective is Pólya’s Theorem, which addresses the recurrence and transience of the cubic lattice in finite-dimensional Euclidean space. It is here that we see the real power of Rayleigh’s Method as the authors elegantly prove Pólya’s Theorem by investigating embedded trees in the lattice.

The beauty of the topic lies in how different ideas fit together and as such it does not require much background to fully understand. Probability, linear algebra, electric networks, and graph theory all make appearances, but rarely is anything more than an introductory understanding necessary. Indeed, this book could inspire great projects in the corresponding undergraduate courses. This is a rare thing in mathematics — a book that an early-career undergraduate could fully explore, yet is still cited in active mathematical research.

The material is perfectly suited to the conversational tone of the book. The book is also fairly short at 118 generously margined and illustrated pages and is presented in a way that a non-expert could pick it up and be exploring new ideas in the topic almost immediately. There are also several nice exercises peppered throughout the text. It is a bit annoying that there is no table of contents or index, but the book is sufficiently well-organized and short that it’s not too much of a problem.

The availability of this text demands some explanation. The original book was published in 1986 in the MAA’s Carus Mathematical Monographs series but has since been made freely available on the internet under the GNU public license. The most recent version is dated 2006 and can be found at Peter Doyle’s website http://www.math.dartmouth.edu/~doyle/docs/walks/walks.pdf. A 2000 version is also on the arXiv at http://arxiv.org/abs/math/0001057. Differences among the versions are not carefully documented and this reviewer did not execute a careful comparison, but there does not appear to be much variation.

Bill Wood is a freelance mathematician living in Conway, Arkansas. He can be contacted at mailto:billarama@gmail.com.