RANDOM WALKS AND ELECTRIC NETWORKS

THE CARUS METHEMATICAL MONOGRAPHS are an expression of the desire of Mrs. Mary Hegeler Carus, and of her son, Dr. Edward H. Carus, to contribute to the dissemination of mathematical knowledge by making accessible at nominal cost a series of expository presentations of the best thoughts and keenest researches in pure and applied mathematics. The publication of the first four of these monographs was made possible by a notable gift to the Mathematical Association of America by Mrs. Carus as sole trustee of the Edward C. Hegeler Trust Fund. The sales from these have resulted in the Carus Monograph Fund, and the Mathematical Association has used this as a revolving book fund to publish the succeeding monographs.

The expositions of mathematical subjects which the monographs contain are set forth in a manner comprehensible not only to teachers and students specializing in mathematics, but also to scientific workers in other fields, and especially to the wide circle of thoughtful people who, having a moderate acquaintance with elementary mathematics, wish to extend their knowledge without prolonged and critical study of the mathematical journals and treatises. The scope of this series includes also historical and biographical monographs.

Thefollowing monographs have been published:

No. 1. Calculus of Variations, G. A. BLISS

No. 2. Analytic Functions of a Complex Variable, by D. R. CURTISS

No. 3. Mathematical Statistics, by H. L. RIETZ

No. 4. Projective Geometry, by J. W. YOUNG

No. 5. A History of Mathematics in America before 1900, by D. E. SMITH and JEKUTHIEL GINSBURG (out of print)

No. 6. Fourier Series and Orthogonal Polynominals, by DUNHAM JACKSON

No. 7. Vectors and Matrices, by C. C. MAcDUFFEE

No. 8. Rings and Ideals, by N. H. MCCOY

No. 9. The Theory of Algebraic Numbers, Second edition, by HARRY POLLARD and HAROLD G. DIAMOND

No. 10. The Arithmetic Theory of Quadratic Forms, by B. W. JONES

No. 11. Irrational Numbers, by IVAN NIVEN

No. 12. Statistical Independence in Probability, Analysis and Number Theory, by MARK KAC

No. 13. A Primer of Real Functions, Third edition, by RALPH P. BOAS, JR.

No. 14. Combinatorial Mathematics, by HERBERT JOHN RYSER

No. 15. Noncommutative Rings, by I. N. H ERSTEI N

No. 16. Dedekind Sums, by HANS RADEMACHER and EMII‑GROSSWALD

No. 17. The Schwarz Function and its Applications, by PHII.IPJ. DAVIS

No. 18. Celestial Mechanics, by HARRY POI.1,ARD

No. 19. FieldTheory and its Classical Problems, by CHARI.ES ROBERTHADLOCK

No. 20. The Generalized Rlemann Integral, by
	ROBERTM. M(1.1‑.01)

No. 2 1. From Error‑ Correct 1 ng Codes through Sphere Packings to Simple Groups, by THOMAS M.THOMPSON.

No. 22. Random Walks and Electric Networks, by PETER G. DOYLE and J. LAURIE SNELL

THE

CARUS MATHEMATICAL MONOGRAPHS
Published by
THE MATHEMATICAL ASSOCIATION OF AMERICA

Committee on Publications
ALAN C. TUCKER, Chairman

Subcommittee on Carus Monographs
BARBARA L. OSOFSKY, Chairman
DUANE BAILEY
JOHN KARLOF

The Carus Mathematical Monographs

NUMBER TWENTY‑TWO

RANDOM WALKS AND
ELECTRIC NETWORKS

By

PETER G. DOYLE J. LAURIE SNELL

Dartmouth College

,TICA

‑I‑ P 4iN*

Published and Dis t n'buted by
THE NIA"I'llENIATICAL ASSOCIA"FION OF ANIE'RICA
Washirigtoii, D.C.

The Mathematical Association of Arnerica
1529 Eighteenth Street, NW
Washington, D.C. 20036

@1984 by The Mathematical Association of America, Inc. All rights reserved. Published 1984. Printed in the United States of America. Second printing, 1988.

The Library of Congress has cataloged the first printing of this title as follows:

Doyle, Peter G. Random walks and electric networks / by Peter G. Doyle, J. Laurie Snell. ‑Washington, D.C.: Mathematical Association of America, c1984.

xiii, 159 p.: ill., 20 cm.‑(Carus Mathematical Monographs; no. 22) Bibliography: p. 151‑153. Includes index. ISBN 0‑88385‑024‑9

	1. Random walks (Mathematics) 2. Electric network‑ topology. I. Snell,
J. Laurie (James Laurie), 1925‑	11. Title.III. Series.

QA274.73.D69 1984	519.2'82‑dcl9 	84‑61495

ISBN 0‑88385‑024‑9 (No. 22)
ISBN 0‑88385‑000‑1 (Complete Set)

PREFACE

Probability theory, like much of mathematics, is indebted to physics as a source of problems and intuition for solving these problems. Unfortunately, the level of abstraction of current mathematics often makes it difficult for anyone but an expert to appreciate this fact. In this book we will look at the interplay of physics and mathematics in terms of an example where the mathematics involved is at the college level. The example is the relation between elementary electric network theory and random walks.

Central to the book will be P61ya's beautiful theoreni that a random walker on an infinite street network in d‑diniensional space is bound to return to the starting point when d ‑ 2, but has a positive probability of escaping to infinity without returning to the starting point when (I = 3. Our goal will be to interpret this theoreni its it statenictit about electric networks, and then to prove the theorem using techniques from classical electrical theory. The techniques referred to go back to Lord Rayleigh, who introduced theni in connection with an investigation of musical instruments. The analog of 1361ya's theoreni in this connection is that wind instruments are possible in our three‑dimensional world, but are not possible in Flatland (Abbott [11).

The connection between random walks and electric networks has been recognized for sonic time (see Kakutani [131, Kemeny, Snell, and Knapp [151, and Kelly [141). As for Rayleigh's method, the authors first learned it from Peter's father Bill Doyle, who used it to explain a mysterious

vii

viii 	PREFACE

comment in Feller ([5], p. 425, Problem 14). This comment suggested that a random walk in two dimensions remains recurrent when some of the streets are blocked, and while this is ticklish to prove probabilistically, it is an easy consequence of Rayleigh's method. The first person to apply Rayleigh's method to random walks seems to have been NashWilliams [26]. Earlier, Royden [32] had applied Rayleigh's method to an equivalent problem. However, the true importance of Rayleigh's method for probability theory is only now becoming appreciated. See, for example, Griffeath and Liggett [10], Lyons [22], and Kesten [17].

Here's the plan of the book: In Part I we will restrict ourselves to the study of random walks on finite networks. Here we will establish the connection between the electrical concepts of current and voltage and corresponding descriptive quantities of random walks regarded as finite state Markov chains. In Part 11 we will consider random walks on infinite networks. PO'lya's theorem will be proved using Rayleigh's method, and the proof will be compared with the classical proof using probabilistic methods. We will then discuss walks on more general infinite graphs, and use Rayleigh's method to derive certain extensions of Po'lya's theorem. Certain of the results in Part 11 were obtained by Peter Doyle in work on his Ph.D. thesis.

To read this book, you should have a knowledge of the basic concepts of probability theory as well as a little electric network theory and linear algebra. An elementary introduction to finite Markov chains as presented by Kemeny, Snell, and Thompson [16] would be helpful.

The work of Snell was carried out while enjoying the hospitality of Churchill College and the Cambridge Statistical Laboratory supported by an NSF Faculty Development Fellowship. He thanks Professors Kendall and Whittle for making this such an enjoyable and rewarding visit. Peter Doyle thanks his father for teaching him how to think like a

PREFACE	ix

physicist. We both thank Peter Ney for assigning the problem in Feller that started all this, David Griffeath for suggesting the example to be used in our first proof that 3‑dimensional random walk is recurrent (Part 11 Section 6.9), and Reese Prosser for keeping us going by his friendly and helpful hectoring. Special thanks are due Marie Slack, our secretary extraordinaire, for typing the original and the excessive number of revisions one is led to by computer formatting.

CONTENTS

PAGE

	PREFACE 	Vii
	PART 1. RANDOM WALKS ON FINITE NETWORKS 	I
	CHAPTER 1. RANDOM WALKS IN ONE DIMENSION 	3
	1. 1. A random walk along Madison Avenue 	3
	1.2. The same problem as a penny matching game 	4
	1.3. The probability of winning: basic properties 	4
	1.4. An electric network problem: the same problem? 	5
	I.S. Harmonic functions in one dimension; the Uniqueness
	Principle 	8
	1.6. The solution as a fair game (martingale) 	I I
	CHAPTER 2. RANDOM WALKS INTwo DIMENSIONS 	15
	2.1. An example 	15
	2.2. Harmonic functions in two dimensions 	16
	2.3. The Monte Carlo solution 	18

2.4. The original Dirichlet problem; the method of relaxations 22

	2.5. Solution by solving linear equations 	27
	2.6. Solution by the method of Markov chains 	31

CHAPTER 3. RANDOM WALKS ON MORi. GENERAL NETWORKS ... 39

3.1. General resistor networks and reversible Markov chains . . 39

	3.2. Voltages for general networks; probabilistic interpretation 45
	3.3.	Probabilistic interpretation of current 	49
	3.4.	Effective resistance and the escape probability 	53
	3.5.	Currents minimize energy dissipation 	60

	CHAPTER 4. RAYLEIGH'S MONOTONICITY LAW 	65
	4.1. Rayleigh's Monotonicity Law 	65
	4.2. A probabilistic explanation of the Monotonicity Law 	69
	4.3. A Markov chain proof of the Monotonicity Law 	78

Xi

Xii	CONTENTS

	PART 11. RANDOM WALKS ON INFINITE NETWORKS 	83
	CHAPTER 5. P6LYA's RECURRENCE PROBLEM 	85

	5.1.	Random walks on lattices 	85
	5.2.	The question of recurrence 	86
	5.3.	P61ya's original question 	88
	5.4.	Po'lya's Theorem: recurrence in the plane, transience in
		space 	88

5.5. The escape probability as a limit of escape probabilities

		for finite graphs 	89

	5.6. Electrical formulation of the type problem 	91

5.7. One dimension is easy, but what about higher

	dimensions? 	93
5.8.	Getting around the 
lack of rotational symmetry of the
	lattice 	95
5.9.	Rayleigh: shorting 
shows recurrence in the plane, cutting
	shows transience in space 	96
	CHAPTER 6. RAYLEIGH'S SHORT‑CUT METHOD 	99
	6.1. Shorting and cutting 	99

6.2. The Shorting Law and the Cutting Law; Rayleigh's idea . . 100

	6.3. The plane is easy 	101
	6.4. Space: searching for a residual network 	102
	6.5. Trees are easy to analyze 	103
	6.6. The full binary tree is too big 	106
	6.7. NT3: a "three‑dimensional" tree 	108
	6.8. NT3 has finite resistance 	110
	6.9. But does NT3 fit in the three ‑dime n sional lattice? 	111
	6.10. What we have done; what we will do 	117
	CHAPTER 7. THE CLASSICAL PROOFS OF P6LYA's THEOREM 	119
	7.1. Recurrence is equivalent to an infinite expected number of
	returns 	119
	7.2. Simple random walk in one dimension 	120
	7.3. Simple random walk in two dimensions 	122
	7.4. Simple random walk in three dimensions 	123
	7.5. The probability of return in three dimensions: exact
	calculations 	125

7.6. Simple random walk in two dimensions is the same as two

	independent one‑dimensional random walks 	127

7.7. Simple random walk in three dimensions is not the same

	as three independent random walks 	128

CONTENTS	xiii

	CHAPTER 8. RANDOM WALKS ON MORE GENERAL INFINITE
	NETWORKS 	131
	8.1. Random walks on infinite networks 	131
	8.2. The type problem 	132
	8.3. Comparing two networks 	132
	8.4. The k‑fuzz of a graph 	134
	8.5. Comparing general graphs with lattice graphs 	136
	8.6. Solving the type problems by flows‑a variant of the
	cutting method 	142
	8.7. A proof, using flows, that simple random walk in three
	dimensions is transient 	144
	8.8. Theend 	147
	REFERENCES 	151

	INDEX
	......................................................	155

PART

Random Walks

on

Finite Networks

CHAPTER I

RANDOM WALKS IN ONE DIMENSION

1.1 A Random Walk along Madison Avenue

A random walk, or drunkard's walk, was one of the first chance processes studied in probability; this chance process continues to play an important role in probability theory and its applications. An example of a random walk may be described as follows:

A man walks along a S‑block stretch of Madison Avenue. He starts at corner x and, with probability 1/2, walks one block to the right and, with probability 1/2, walks one block to the left; when he comes to the next corner he again randomly chooses his direction along Madison Avenue. He continues until he reaches corner S, which is home, or corner 0, which is a bar. If he reaches either home or the bar, he stays there.

Bar ()‑_~	flonic

	1	2	3 	4

h6tjHp. 1.1

The problem we pose is to find the probability p(x) that the man, starting at corner x, ~vill reach home

3

4	RANDOM WALKS IN ONE DIMENSION	Ch. I

before reaching the bar. In looking at this problem, we will not be so much concerned with the particular form of the solution, which turns out to be p(x) ‑ x15, as with its general properties, which we will eventually describe by saying "p(x) is the unique solution to a certain Dirichlet problem."

1.2 The Same Problem as a Penny Matching Game

In another form, the problem is posed in terms of the following game: Peter and Paul match pennies; they have a total of 5 pennies; on each match, Peter wins one penny from Paul with probability 1/2 and loses one with probability 1/2; they play until Peter's fortune reaches 0 (he is ruined) or reaches 5 (he wins all Paul's money). Now p(x) is the probability that Peter wins if he starts with x pennies.

1.3 The Probability of Winning: Basic Properties

Consider a random walk on the integers 0, 1, 2, . . ., N. Let p(x) be the probability, starting at x, of reaching N before 0. We regard p(x) as a function defined on the points x ‑ 0, 1, 2, N. The function p(x) has the following properties:

	(a) p (0)	0
	(b) p (N)	1
	(c) p (x)	(112)p(x ‑ 1) + (112)p(x + 1)
	for x	1,2, .,N‑ 1.

Properties (a) and (b) follow from our convention that 0 and N are traps; if the walker reaches one of these positions, he stops there; in the game interpretation, the game ends when one player has all of the pennies.

1.4	AN ELECTRIC NETWORK PROBLEM 	5

Property (c) states that, for an interior point, the probabilityp(x) of reaching home from x is the average of the probabilities p(x ‑ 1) and p(x + 1) of reaching home from the points that the walker may go to from x. We can derive (c) from the following basic fact about probability:

BAsic FACT. Let E be any event, and F and G be eventssuch that one andonly one of the eventsFor Gwill occur. Then

P(E) = P(F) ‑ P(E given T) + P(G) ‑ P(E given G).

In this case, let E be the event "the walker ends at the bar," F the event "the first step is to the left," and G the event "the first step is to the right." Then, if the walker starts at x, P(E) = p(x), P(F) ‑ P(G) ‑ 1/29 P(E given F) ‑ p(x ‑ 1), P(E given G) ‑ p(x + 1), and (c) follows.

1.4 An Electric Network Problem: The Same Problem?

Let's consider a second apparently very different problem. We connect equal resistors in series and put a unit voltage across the ends as in Figure 1.2.

I volt

I I

0

2	3	4	5

HGURE 1.2

6	RANDOM WALKS IN ONE DIMENSION	Ch. I

Voltages v(x) will be established at the points x ‑ 0, 19 2~ 3, 4, 5. We have grounded the point x ‑ 0 so that V(O) ‑ 0. We ask for the voltage v(x) at the points x between the resistors. If we have N resistors, we make v(O) = 0 and v(N) = 1, so v(x) satisfies properties (a) and (b) of Section 1.3. We now show that v(x) also satisfies (c).

By Kirchhoff's Laws, the current flowing into x must be equal to the current flowing out. By Ohm's Law, if points x and Y are connected by a resistance of magnitude R, then the current ixy that flows from x to y is equal to

ixy	V(X) R V(Y)

Thus forx	L 2,	N ‑ I

V(X ‑	‑ V(X)	V(X + 1) 	V(X)

R	+	R 	0.

Multiplying through by R and solving for v(x) gives

V(X) = V(X + 1)	+ V(X
	2

for	X = 1, 2, . . . 9 N ‑ 1.

Therefore, v(x) also satisfies property (c).

We have seen that p(x) and v(x) both satisfy properties (a), (b), and (c) of Section 1.3. This raises the question: are p(x) and v(x) equal? For this simple example, we can easily find v(x) using Ohm's Law, find p(x) using elementary probability, and see that they are the same. However, we want to illustrate a principle that will work for very general circuits. So instead

1.4 	AN ELECTRIC NETWORK PROBLEM

we shall prove that these two functions are the same by showing that there is only one function that satisfies these properties, and we shall prove this by a method that will apply to more general situations than points connected together in a straight line.

EXERCISES

1. Referring to the random walk along Madison Avenue, let X ‑ p(l), Y = p(2), Z = p(3) and W ‑ p(4). Show that properties (a), (b), and (c) of Section 1.3 determine a set of four linear equations with variablesX, Y,Z, and W; showthat these equations have a unique solution. What does this say about p(x) and v(x) for this special case?

2. Assume that our walker has a tendency to drift in one direction: more specifically, assume that each step is to the right with probability p or to the left with probability q ‑ I ‑ p. Show that properties (a), (b), and (c) of Section 1.3 should be replaced by

(a) p (0) 0,
(b) 1) (N) 1,
(c) p(x) q ‑ 10 ‑ 1) + p ‑ p(x +

3. In our electric network problem, assume that the resistors are not necessarily equal. Let R., be the resistance between x and x + 1. Show that

I 	I

V(X)	RX‑1	V(X	+	RX 	V(X +

RX‑1	RX	Rx‑ I 	RX

How should the resistors be chosen to correspond to the random walk of Exercise 2?

8	RANDOM WALKS IN ONE DIMENSION	Ch. 1

1.5 Harmonic Functions in One Dimension; the Uniqueness Principle

Let S be the set of points S ‑ {0, 1, 2, NJ. We call the points of the set D ‑{ 1, 2, . ‑ ‑, N ‑ 11 the interior points of S and those of B = {0, NJ the boundary points of S. A functionf(x) defined on S is harmonic if, at points of D, it satisfies the averaging property

f(x) = f(x ‑ 1) + f(x + 1)

2

As we have seen, p(x) and v(x) are harmonic functions on S having the same values on the boundary: p(O) ‑ v(O) ‑ 0; p(N) ‑ v(N) ‑ 1. Thus both p(x) and v(x) solve the problem of finding a harmonic function having these boundary values. Now the problem of finding a harmonic function given its boundary values is called the Dirichlet problem, and the Uniqueness Principle for the Dirichlet problem asserts that there cannot be two different harmonic functions having the same boundary values. In particular, it follows that p(x) and v(x) are really the same function, and this is what we have been hoping to show. Thus the fact that p(x) = v(x) is an aspect of a general fact about harmonic functions.

We will approach the Uniqueness Principle by way of the Maximum Principle for harmonic functions, which bears the same relation to the Uniqueness Principle as Rolle's Theorem does to the Mean Value Theorem of Calculus.

MAXIMUM PRINCIPLE. A harmonic function f(x) defined on S takes on its maximum value M and its minimum value m on the boundary.

1.5	HARMONIC FUNCTIONS IN ONE DIMENSION 	9

Proo Let M be the largest value of f. Then if f(x) = M for x in D, the same must be true forf(x ‑ 1) andf(x + 1) sincef(x) is the average of these two values. If x ‑ I is still an interior point, the same argument implies that f(x ‑ 2) = M; continuing in this way, we eventually conclude thatf(O) = M. That same argument works for the minimum value m.

UNIQUENESS PRINCIPLE. Iffix) and g(x) are harmonicjunctions on S such thatfix) = g(x) on B, then fix) = g(x)for all x.

Proof. Let h(x) ‑ f(x) ‑ g(x). Then if x is any interior point,

h(x ‑ 1) + h(x + 1) _ f(x ‑ 1) +.I'(x + 1)

2

g(x ‑ 1) + g(x + 1)

‑./'(x) ‑ g(x) ‑ h(x)

and h is harmonic. But h(x) ‑ 0 for x in B, and hence, by the Maximuni Principle, the maximum and mininium values of h are 0. Thtis 10) 0 for all x, and .1'(x) ‑ g(x) for all x.

ThLis we finally prove that 1)(x) v(x); but %N'hat (toes v(x) equal? The Uni(Itieness Principle shows us a way to find a concrete answcr: just guess. For if we can find any harmonic function ' f(x) having the right boundary values, the Uniqueness Principle guarantees that

P W ‑ 1,(x) ‑ f W ‑

10	RANDOM WALKS IN ONE DIMENSION	Ch. 1

The simplest function to try forf (x) would be a linear function; this leads to the solution f (x) ‑ x1N. Notethatf(O) = Oandf(N) = land

	f(X ‑ 1) +f(x + 1)	X ‑ 1 + X +	X =f(x).
	2		2N 	N

Thereforef(x) ‑ p(x) ‑ v(x) ‑ x1N.

As another application of the Uniqueness Principle, we prove that our walker will eventually reach 0 or N. Choose a starting point x with 0 < x < N. Let h(x) be the probability that the walker never reaches the boundary B {0, NJ. Then

	h(x)	(112)h(x + 1) + (112)h(x ‑ 1)
and h is harmonic. Also h(O) ‑ h(N) = 0; thus, by the
Maximum Principle, h(x) = 0 for all x.

ExIERCISES

1. Show that you can choose A and B so that the function f(x) = A(qlp)x + B satisfies the modified properties (a), (b) and (c) of Exercise 2 of Section 1.4. Does this show that f(X) = P(X)?

2. Let m(x) be the expected number of steps, starting at x, required to reach 0 or N for the first time. It can be proven that m(x) is finite. Show that m(x) satisfies the conditions

(a) m (0) ‑ 0

(b) m (N) ‑ 0
(c) M (X) =	1 M(X + 1) +	1 M (X	+
	2 	2

3. Show that conditions in Exercise 2 have a unique solution. Hint: show that if m and M‑ are two solutions, then f = m ‑ M‑ is harmonic with f (0) ‑ f (N) = 0 and hence f(x) ‑ 0 for all x.

1.6 	THE SOLUTION AS A FAIR GAME

4. Show that you can choose A, B, and C such that f W ‑ A + Bx + CX 2 satisfies all the conditions of Exercise 2. Does this show thatf(x) ‑ m(x) for this choice of A, B, and C?

5. Find the expected duration of the walk down Madison Avenue as a function of the walker's starting point (1, 2, 3, or 4).

1.6 The Solution as a Fair Game (Martingale)

Let us return to our interpretation of a random walk as Peter's fortune in a game of penny matching with Paul. On each match, Peter wins one penny with probability 1/2 and loses one penny with probability 1/2. Thus, when Peter has k pennies his expected fortune after the next play is

(112) ‑ (k ‑ 1) + (1 /2) ‑ (k + 1) ‑ k,

so his expected fortune after the next play is equal to his present fortune. This says that lie is playing a fair game; a chance process that can be interpreted as a player's fortune in a fair game is called a martingale.

Now assume that Peter and Paul have a total of N pennies. Let 1)(x) be the probability that, when Peter has x pennies, he will end tip with all N pennies. Then Peter's expected final fortune in this game is

j)W) ‑ 0 + 10) ‑ N = 10) ‑ N.

If we could be sure that a fair game remains fair to the end of the game, then we could conclude that Peter's expected final fortune is equal to his starting fortune x, i.e., x ‑ p(x) ‑ N.

12	RANDOM WALKS IN ONE DIMENSION 	Ch. 1

This would give p(x) = x1N and we would have found the probability that Peter wins using the fact that a fair game remains fair to the end. Note that the time the game ends is a random time, namely, the time that the walk first reaches 0 or N for the first time. Thus the question is, is the fairness of a game preserved when we stop at a random time?

Unfortunately, this is not always the case. To begin with, if Peter somehow has knowledge of what the future holds in store for him, he can decide to quit when he gets to the end of a winning streak. But even if we restrict ourselves to stopping rules where the decision to stop or continue is independent of future events, fairness may not be preserved. For example, assume that Peter is allowed to go into debt and can play as long as he wants to. He starts with 0 pennies and decides to play until his fortune is 1 and then quit. We shall see that a random walk on the set of all integers, starting at 0, will reach the point 1 if we wait long enough. Hence, Peter will end up one penny ahead by this system of stopping.

However, there are certain conditions under which we can guarantee that a fair game remains fair when stopped at a random time. For our purposes, the following standard result of martingale theory will do:

MARTINGALE STOPPING THEOREM. A fair game that is stopped at a random time will remainfair to the end of the game if it is assumed that there is a finite amount of money in the world and a player must stop if he wins all this money or goes into debt by this amount.

This theorem would justify the above argument to obtain p(x) = x1N.

1.6	THE SOLUTION AS A FAIR GAME 	13

Let's step back and see how this martingale argument worked. We began with a harmonic function, the function f (x) ‑ x, and interpreted it as the player's fortune in a fair game. We then considered the player's expected final fortune in this game. This was another harmonic function having the same boundary values and we appealed to the Martingale Stopping Theorem to argue that this function must be the same as the original function. This allowed us to write down an expression for the probability of winning, which was what we were looking for.

Lurking behind this argument is a general principle: If we are given boundary values of a function, we can come up with a harmonic function having these boundary values by assigning to each point the player's expected final fortune in a game where the player starts from the given point and carries out a random walk until he reaches a boundary point, where he receives the specified payoff. Furthermore, the Martingale Stopping Theorern allows us to conclude that there can be no other harmonic function with these boundary values. Thus martingale theory allows us to establish existence and uniqueness Of Solutions to a Dirichlet problem. All this isn't very exciting for the cases we 9 ve been considering, but the nice thing is that the same arguments carry through to the more 9cneral situations that we will be considering later oil.

The Study of martingales was originated by Uvy 1211 and Ville [361. KakUtani 1131 showed the connection between random walks and harmonic functions. Doob [4] developed martingale stopping theorems and showed how to exploit the preservation of fairness to solve a wide variety of problems in probability theory. An informal discussion of martingales may be found in Snell [34].

~ 111' ‑ ‑,

14	RANDOM WALKS IN ONE DIMENSION	Ch. 1

EXERCISES

1. Consider a random walk with a drift; that is, there is a probability p 1/2 of going one step to the right and a probability q 1 ‑ p of going one step to the left. (See Exercise 2 of Section 1.4.) Let w(x) = (qlp)x; show that, if you interpret w(x) as your fortune when you are at x, the resulting game is fair. Then use the Martingale Stopping Theorem to argue that

w(x) ‑ p(x)w(N) + (1 p(x))w(O).

Solve for p(x) to obtain

P (X)	q N

P

2. You are gambling against a professional gambler; you start with A dollars and the gambler with B dollars; you play a game in which you win one dollar with probabilityp < 1/2 and lose one dollar with probability q = 1 ‑ p; play continues until you or the gambler runs out of money. Let RAbe the probability that you are ruined. Use the result of Exercise 1 to show that

1	P B
	q 	‑

RA		N

q

with N = A + B. If you start with 20 dollars and the gambler with 50 dollars and p .45, find the probability of being ruined.

q
P

3. The gambler realizes that the probability of ruining you is at least 1 ‑ (plq)B (Why?). The gambler wants to make the probability at least .999. For this, (plq )B should be at most .001. If the gambler offers you a game with p = .499, how large a stake should she have?

CHAPTER 2

RANDOM WALKS IN TWO
DIMENSIONS

2.1 An Example

We turn now to the more complicated problem of a random walk on a two‑dimensional array. In Figure 2.1 we illustrate such a walk. The large dots represent

E 	E

40	40

E mew E

E	P	P

E 0	1 mop P

Fj(;URF 2.1

boundar~ points; those marked E indicate escape routes and those marked P are police. We wish to find the probability p(x) that our walker, starting at an interior point x, will reach an escape route before he reaches a policeman. The walker moves from X = (a, b) to each of the four neighboring points

15

16	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

(a + 1, b), (a ‑ 1, b), (a, h + 1), (a, h ‑ 1) with probability 1/4. If he reaches a boundary point, he remains at this point.

The corresponding voltage problem is shown in Figure 2.2. The boundary points P are grounded and points E are connected and fixed at one volt by a onevolt battery. We ask for the voltage v(x) at the interior points.

I volt

Fic;URE 2.2

2.2 Harmonic Functions in Two Dimensions

We now define harmonic functions for sets of lattice points in the plane (a lattice point is a point with integer coordinates). Let S ‑ D U B be a finite set of lattice points such that (a) D and B have no points in common, (b) every point of D has its four neighboring points in S, and (c) every point of B has at least one of its four neighboring points in D. We assume further that S hangs together in a nice way, namely, that for any two points P and Q in S, there is a sequence of points Pj in D such that P, P, 9 ... 9 P, Q forms a path from P to Q. We call the points of D the interior points of S and the points of B the boundary points of S.

2.2	HARMONIC FUNCTIONS IN TWO DIMENSIONS 	17

A functionf defined on S is harmonic if, for points (a, b) in D, it has the averaging property

f (a, b) ‑

f(a + 1, h) +f(a ‑ 1, b) +f(a, h + 1) +f(a, b ‑ 1)
4

Note that there is no restriction on the values off at the boundary points.

We would like to prove that p(x) ‑ v(x) as we did in the one‑dimensional case. That p(x) is harmonic follows again by considering all four possible first steps; that v(x) is harmonic follows again by Kirchhoff's Laws since the current coming into x ‑ (a, b) is

	v(a + 1, b) ‑ v(a, b) i‑ v(a ‑ 1, b)	v(a, h)
R	R

+ v(a, b + 1) ‑ v(a, b)	v(a, b	1) ‑ v(a, b)
R		R

= 0.

Multiplying through by R and solving for v(a, b) gives

v((i, b) ‑_

V(a + 1, b) + v(a ‑ 1, b) + v(a, h + 1) + v(a, b ‑ 1)
4

Thus p(x) and v(x) are harmonic functions with the same boundary values. To show froni this that they are the same, we must extend the Uniqueness Principle to two dimensions.

We first prove the Maximum Principle. If M is the maximum value off and if f (P) ‑ M for P an interior point, then sincef(P) is the average of the values off at its neighbors, these values must all equal M also. By

18	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

working our way due south, say, repeating this argument at every step, we eventually reach a boundary point Q for which we can conclude that f (Q) = M. Thus a harmonic function always attains its maximum (or minimum) on the boundary; this is the Maximum Principle. The proof of the Uniqueness Principle goes through as before since again the difference of two harmonic functions is harmonic.

The fair game argument, using the Martingale Stopping Theorem, holds equally well and again gives an alternative proof of the existence and uniqueness to the solution of the Dirichlet problem.

EXERCISES

1. Show that if f and g are harmonic functions so is h a ‑f + b ‑ g for constants a and b. This is called the superposition principle.

2. LetB,,B2, B,, be the boundary points for a region S. Let ej(a, b) be a function that is harmonic in S and has boundary value 1 at B and 0 at the other boundary points. Show that if arbitrary boundary values vj, V2, .. .1 VU are assigned, we can find the harmonic function v with these values from the solutions el, e2, . . ., eu.

2.3 The Monte Carlo Solution

Finding the exact solution to a Dirichlet problem in two dimensions is not always a simple matter, so before taking on this problem, we will consider two methods for generating approximate solutions. In this section we will present a method using random walks. This method is known as a Monte Carlo method, since random walks are random, and gambling involves randomness, and there is a famous gambling casino in

2.3	MONTE CARLO SOLUTION 	19

Monte Carlo. In the next section, we will describe a much more effective method for finding approximate solutions, called the method of relaxations.

We have seen that the solution to the Dirichlet problem can be found by finding the value of a player's final winning in the following game: Starting at x the player carries out a random walk until reaching a boundary point. He is then paid an amountf (y) if y is the boundary point first reached. Thus to findflx), we can start many random walks at x and find the average final winnings for these walks. By the law of averages (the law of large numbers in probability theory), the estimate that we obtain this way will approach the true expected final winningf(x).

Here are some estimates obtained this way by starting 10,000 random walks from each of the interior points and, for each x, estiniatingf(x) by the average winning of the random walkers who started at this point.

.824 ‑ ./8S ‑ I

I ‑ .8 76‑ __ )3‑ .3 17‑‑0

1	0	0

This method is a colorful way to solve the problem, but quite inefficient. We can use probability theory to estimate how inefficient it is. We consider the case with boundary values I or 0 as in our example. In this case, the expected final winning is just the probability

20	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

that the walk ends up at a boundary point with value 1. For each point x, assume that we carry out n random walks; we regard each random walk to be an experiment and interpret the outcome of the ith experiment to be a "success" if the walker ends at a boundary point with a 1 and a "failure" otherwise. Let p ‑ p(x) be the unknown probability for success for a walker starting at x and q = 1 ‑ p. How many walks should we carry out to get a reasonable estimate for p? We estimate p to be the fraction P of the walkers that end at a 1.

We are in the position of a pollster who wishes to estimate the proportion p of people in the country who favor candidate A over B. The pollster chooses a random sample of n people and estimates p as the proportion P of voters in his sample who favor A. (This is a gross oversimplification of what a pollster does‑see Freedman et al. [8] for the real story.) To estimate the number n required, we can use the central limit theorem. This theorem states that, if S,, is the number of successes in n independent experiments, each having probability p for success, then for any k > 0

P(_ k < S11 ‑ np < k) A W

‑sin‑pq

where A (k) is the area under the normal curve between ‑k and k. For k = 2 this area is approximately .95; what does this say aboutp ‑S,,In? Doing a little rearranging, we see that

P ‑2 < _P	P < 2	.95
	q
	n

2.3	MONTE CARLO SOLUTION	21

or

pq 	pq

P(‑ 2	< P ‑p < 2	.95.

Since ‑,Ip‑q <, 1/29

P ‑\Fn < P ‑P < ‑Nfn‑‑ .95.

Thus, if we choose 1 1,~‑n = .01, or n 10,000, there is a 95 percent chance that our estimate P = S, In will not be off by more than .01. This is a large number for rather modest accuracy; in our example we carried out

Iq:	q:

En	jEn

10,000 walks from each point and this required about 5 seconds on the Dartmouth computer. We shall see later, when we obtain an exact solution, that we did obtain the accuracy predicted.

EXERCISE

1. You play a game in which you start a random walk at the center in the grid shown in Figure 2.3. When the walk

‑ 1

40

‑40

‑ I

i‑ I

40 1 1

+ I	‑ I 	+ I

FiGURE 2.3

22	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

reaches the boundary, you receive a payment of + 1 or ‑ 1 as indicated at the boundary points. You wish to simulate this game to see if it is a favorable game to play; how many simulations would you need to be reasonably certain of the value of this game to an accuracy of .01? Carry out such a simulation and see if you feel that it is a favorable game.

2.4 The Original Dirichlet Problem; the Method of Relaxations

The Dirichlet problem we have been studying is not the original Dirichlet problem, but a discrete version of it. The original Dirichlet problem concerns the distribution of temperature, say, in a continuous medium; the following is a representative example.

Suppose we have a thin sheet of metal gotten by cutting out a small square from the center of a large square. The inner boundary is kept at temperature 0 and the outer boundary is kept at temperature 1 as indicated in Figure 2.4. The problem is to find the temperature at points in the rectangle I s interior. If u(x, y) is the temperature at (x, y), then u satisfies Laplace's differential equation

U XX + Uyy = 0.

A function that satisfies this differential equation is called harmonic. It has the property that the value u(x, y) is equal to the average of the values over any circle with center (x, y) lying inside the region. Thus to determine the temperature u(x, y), we must find a harmonic function defined in the rectangle that takes on the prescribed boundary values. We have a problem entirely analogous to our discrete Dirichlet problem, but with continuous domain.

2.4	DIRICHLET PROBLEM	23

0

x.::00

Xz.

.0:.

...........

............

Fi(AjRi‑~ 2.4

The method of relaxations was iIItr0dUCCd as a way to get approximate solutions to the original Dirichlet problem. This niethod is actually niore closely connected to the discrete Dirichlet probleni than to the continuous problem. Why? Because, faced Nvith the continuous probleni just described, no physicist will hesitate to replace it Nvith an analogous discrete probleni, approximating the continuous medium by an array of lattice points such as that depicted in Figure 2.5, and searching for a function that is harnionic in our discrete sense and that takes on the appropriate

24	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

U

0

FIGURE 2.5

boundary values. It is this approximating discrete problem to which the method of relaxations applies.

Here's how the method goes. Recall that we are looking for a function that has specified boundary values, for which the value at any interior point is the average of the values at its neighbors. Begin with any function having the specified boundary values, pick an interior point, and see what is happening there. In general, the value of the function at the point we are looking at will not be equal to the average of the values at its neighbors. So adjust the value of the function to

2.4	DIRICHLET PROBLEM 	25

be equal to the average of the values at its neighbors. Now run through the rest of the interior points, repeating this process. When you have adjusted the values at all of the interior points, the function that results will not be harmonic, because most of the time after adjusting the value at a point to be the average value at its neighbors, we afterwards came along and adjusted the values at one or more of those neighbors, thus destroying the harmony. However, the function that results after running through all the interior points, if not harmonic, is more nearly harmonic than the function we started with; if we keep repeating this averaging process, running through all of the interior points again and again, the function will approximate more and more closely the solution to our Dirichlet problem.

We do not yet have the tools to prove that this method works for a general initial guess; this will have to wait until Chapter 3 (see Exercise 2 of Section 3.5). We will start with a special choice of initial values for which we can prove that the method works (see Exercise 2 of this section).

We start with all interior points 0 and keep the boundary points fixed.

1‑0‑0‑ 1

1 ‑0‑0‑0‑0

1	0 	0

26	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

After one iteration we have:

I 	I

1 	.5 47 ‑ .6 48 ‑ I

188 ‑ .047 ‑ 0

1	0	0

Note that we go from left to right moving up each column replacing each value by the average of the four neighboring values. The computations for this first iteration are

.75 ‑ (1/4)(1 + 1 + 1 + 0)

.1875 ‑ (1/4)(.75 + 0 + 0 + 0)

.5469	(1/4)(.1875 + 1 + 1 + 0)

.0469	(1/4)(.1875 + 0 + 0 + 0)

.64844	(1/4)(.0469 + .5769 + 1 + 1)

We have printed the results to three decimal places. We continue the iteration until we obtain the same results to three decimal places. This occurs at iterations 8 and 9. Here's what we get:

I ‑‑ .823	.787 ‑‑‑ I

.876	S D6	.3 23 	0

1	0	0

2.5	LINEAR EQUATIONS 	27

We see that we obtain the same result to three places after only nine iterations and this took only a fraction of a second of computing time. We shall see that these results are correct to three place accuracy. Our Monte Carlo method took several seconds of computing time and did not even give three place accuracy.

The classical reference for the method of relaxations as a means of finding approximate solutions to continuous problems is Courant, Friedrichs, and Lewy [3]. For more information on the relationship between the original Dirichlet problem and the discrete analog, see Hersh and Griego [11].

EXERCISES

I . Apply the method of relaxations to the discrete problem illustrated in Figure 2.5.

2. Consider the method of relaxations started with an initial guess with the property that the value at each point is < the average of the values at the neighbors of this point. Show that the Successive values at a point u are monotone increasing with a limitflu) and that these limits provide a solution to the Dirichlet problem.

2.5 Solution by Solving Linear Equations

In this section we will show how to find an exact solution to a two‑dimensional Dirichlet probleni by solving a system of linear equations. As usual, we will illustrate the method in the case of the example introduced in Section 2. 1. This example is shown again in Figure 2.6; the interior points have been labelled a, b, c, d, and e. By our averaging property, we have

28	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

Xa	Xb + Xd+ 2

4

Xa + Xe + 2

4

Xb

XC = Xd+ 3
	4

Xd = Xa + XC + Xe
	4

Xe ‑ Xb + Xd

	4
We can rewrite these equations in matrix form as

1	‑1/4	0	‑1/4	0	Xa 	1/2

‑1/4	1	0	0	‑1/4	Xb 	1/2

0	0	1	‑1/4	0	XC	‑ 	3/4

‑1/4	0	‑1/4	1	‑1/4	Xd 	0

0	‑1/4	0	‑1/4	1 ~~Xe~	0 ~

a	b
		0‑1

d	e

1	0	0

FIGURE 2.6

2.5	LINEAR EQUATIONS 	29

We can write this in symbols as

Ax ‑ u.

Since we know there is a unique solution, A must have an inverse and

X = A‑1u.

Carrying out this calculation we find

.823

. 787

Calculated x	.876

.506

.323

Here, for comparison, are the approximate solutions found earlier:

.824	.823
.785	.787

Monte Carlo x	.876	Relaxed x	.876
	.503		.506
	.317		.323

We see that our Monte Carlo approximations were fairly good in that no error of the simulation is greater than .01, and our relaxed approximations were very good indeed, in that the error does not show up at all.

30	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

EXERCISES

1. Consider a random walker on the graph of Figure 2.7. Find the probability of reaching the point with a I before any of the points with O's for each starting point a, b, c, d.

2. Solve the discrete Dirichlet problem for the graph shown in Figure 2.8. The interior points are a, b, c, d. (Hint: See Exercise 2 of Section 2.2.)

0 	0

1 ~ 	40

b
	0

'low,	d	0 0

0 	0

FIGURE 2.7

1 0
401

	a	b
3 0			2

C	d	‑4

5

FIGURE 2.8

2.6	MARKOV CHAINS 	31

3. Find the exact value, for each possible starting point, for the game described in Exercise 1 of Section 2.3. Is the game favorable starting in the center?

2.6 Solution by the Method of Markov Chains

In this section, we describe how the Dirichlet problem can be solved by the method of Markov chains. This method may be viewed as a more sophisticated version of the method of linear equations.

A finite Markov chain is a special type of chance process that may be described informally as follows: we have a set S ‑ {S~, S2, . . .1 S,j of states and a chance process that moves around through these states. When the process is in state si, it moves with probability P4 to the state s.j. The transition probabilities Pij are represented by an r‑by‑r matrix P called the transition matrix. To specify the chance process completely we must give, in addition to the transition matrix, a method for starting the process. We do this by specifying a specific state in which the process starts.

According to Kemeny, Snell, and Thompson [16], in the Land of Oz, there are three kinds of weather: rain, nice, and snow. There are never two nice days in a row. When it rains or snows, half the time it is the same the next day. If the weather changes, the chances are equal for a change to each of the other two types of weather. We regard the weather in the Land of Oz as a Markov chain with transition matrix:

R	N 	S

R 1/2 1/41/4

	P = N 1/2	0	1/2
	S ~1/4	1/41/2~

32	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

When we start in a particular state, it is natural to ask for the probability that the process is in each of the possible states after a specific number of steps. In the study of Markov chains, it is shown that this information is provided by the powers of the transition matrix. Specifically, if P" is the matrix P raised to the nth power, the entries P'~ represent the probability that the chain, started in state si, will, after n steps, be in state sj. For example, the fourth power of the transition matrix P for the weather in the Land of Oz is

R	N 	S

R .402 .199.398

p4 ‑ N .398 .203 .398

	S .398 .199.402

Thus, if it is raining today in the Land of Oz, the probability that the weather will be nice four days from now is .199. Note that the probability of a particular type of weather four days from today is essentially independent of the type of weather today. This Markov chain is an example of a type of chain called a regular chain. A Markov chain is a regular chain if some power of the transition matrix has no zeros. In the study of regular Markov chains, it is shown that the probability of being in a state after a large number of steps is independent of the starting state.

As a second example, we consider a random walk in one dimension. Let us assume that the walk is stopped when it reaches either state 0 or 4. (We could use 5 instead of 4, as before, but we want to keep the matrices small.) We can regard this random walk as a Markov chain with states 0, 1, 2, 3, 4 and transition matrix given by

2.6	MARKOV CHAINS	33

	0	1	2	3	4
0	1	0	0	0 	0

1	1/2	0	1/2	0 	0

P ‑ 2	0	1/2	0	1/2 	0

3	0	0	1/2	0 	1/2

4	0	0	0	0	1 ~

The states 0 and 4 are traps or absorbing states. These are states that, once entered, cannot be left. A Markov chain is called absorbing if it has at least one absorbing state and if, from any state, it is possible (not necessarily in one step) to reach at least one absorbing state. Our Markov chain has this property and so is an absorbing Markov chain. The states of an absorbing chain that are not traps are called nonabsorbing.

When an absorbing Markov chain is started in a non‑absorbing state, it will eventually end up in an absorbing state. For non‑absorbing state si and absorbing statesi, we denote by Bil the probability that the chain starting in si will end up in states, . We denote by B the matrix with entries B,,..'Fliis matrix will have as many rows as non‑absorbing states and as many columns as there are absorbing states. For our random walk example, the entries B,.,, will give the probability that our random walker, starting at x, will reach 4 before reaching 0. Thus, if we can find the matrix B by Markov chain techniques, we will have a way to solve the Dirichlet problem.

We shall show, in fact, that the Dirichlet problem has a natural generalization in the context of absorb

34	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

ing Markov chains and can be solved by Markov chain methods.

Assume now that P is an absorbing Markov chain and that there are u absorbing states and v non‑absorbing states. We reorder the states so that the absorbing states come first and the non‑absorbing states come last. Then our transition matrix has the canonical form:

1 0

P =	‑
	" R

Here I is a u‑by‑u identity matrix; 0 is a matrix of dimension u‑by‑v with all entries 0.

For our random walk example this canonical form is:

	0	4	1	2	3
0	1	0	0	0 	0

4	0	1	0	0	0

	P = 1	1/2	0	0	1/2	0
	2	0	0	1/2	0	1 /2
	3	0	1/2	0	1/2	0

The matrix N = (I ‑ Q) ‑ 1 is called the fundamental matrix for the absorbing chain P. The entries Nij of this matrix have the following probabilistic interpretation: N~j is the expected number of times that the chain

0)

will be in state sj before absorption when it is started in si. (To see why this is true, think of how (I ‑ Q)‑1 would look if it were written as a geometric series.) Let 1 be a column vector of all I's. Then the vector t ‑ NI

2.6	MARKOV CHAINS 	35

gives the expected number of steps before absorption for each starting state.

The absorption probabilities B are obtained from N by the matrix formula

B = (I ‑ Q)‑'R.

This simply says that to get the probability of ending up at a given absorbing state, we add up the probabilities of going there from all the non‑absorbing states, weighted by the number of times we expect to be in those (non‑absorbing) states.

For our random walk example

0	1/2 	0

Q	1/2	0 	1/2

0	1/2 	0

1	‑1/2 	0

‑1/2	1 	‑1/2

0 	‑1/2

	1	2	3
1 3/2	1 		2

N	2 1	2 	1

3 1/2 1 3/2

( 3/2 1 1/2	1 	3

t	NI	1	2	1 ) (1) 	~4)

1/2 1 3/2 1

36	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

3/2 1 1/2 1/2	0

B = NR ‑	1	2	1	0	0
	1/2	1	3/2	0	1/2

0	4
A 1 4

‑ 2 1/2 1/2

3 1/43/4

Thus, starting in state 3, the probability is 3/4 of reaching 4 before 0; this is in agreement with our previous results. From t we see that the expected duration of the game, when we start in state 2, is 4.

For an absorbing chain P, the nth power P" of the transition probabilities will approach a matrix P' of the form

1 0

POO

B 0

We now give our Markov chain version of the Dirichlet problem. We interpret the absorbing states as boundary states and the non‑absorbing states as interior states. Let B be the set of boundary states and D the set of interior states. Let f be a function with domain the state space of a Markov chain P such that for i in D

f U) ‑ E Piif U

Thenf is a harmonic function for P. Nowf again has an averaging property and extends our previous defini

2.6	MARKOV CHAINS 	37

tion. If we represent f as a column vector f, f is harmonic if and only if

Pf ‑ f. This implies that

p2f ‑ p. pf ‑ pf ‑ f and in general

pnf = f.

Let us write the vector f as

f 	fB)

fD

where fB represents the values of f on the boundary and fD values on the interior. Then we have

fB	1 0 fB

f D) (B 0)(fD) and

f 1) = BfB

We again see that the values of a harmonic function are determined by the values of the function at the boundary points.

Since the entries B,., of B represent the probability, starting in i, that the process ends at./, our last equation states that if you play a game in which your fortune isfj when you are in statej, then your expected final fortune is equal to your initial fortune; that is, fairness is preserved. As remarked above, from Markov chain theory B ‑ NR where N ‑ (I ‑ Q) Thus fD =(I ‑Q)‑'RfB‑ '

38	RANDOM WALKS IN TWO DIMENSIONS	Ch. 2

(To make the correspondence between this solution and the solution of Section 2.5, put A = I ‑ Q and u ‑ RfB)

A general discussion of absorbing Markov chains may be found in Kemeny, Snell, and Thompson [16].

ExERCISE

1. Consider the game played on the grid in Figure 2.9. You start at an interior point and move randomly until a boundary point is reached and obtain the payment indicated at this point. Using Markov chain methods find, for each starting state, the expected value of the game. Find also the expected duration of the game.

__ I

I	FIGURE 2.9

CHAPTER 3

RANDOM WALKS ON MORE
GENERAL NETWORKS

3.1 General Resistor Networks and Reversible Markov Chains

Our networks so far have been very special networks with unit resistors. We will now introduce general resistor networks, and consider what it means to carry out a random walk on such a network.

A graph is a finite collection of points (also called vertices or nodes) with certain pairs of points connected by edges (also called branches). The graph is connected if it is possible to go between any two points by moving along the edges.

0	1 0
Connected graph 	Disconnected graph

FIGURE 3.1

We assume that G is a connected graph and assign to each edge xy a resistance R.,Y; an example is shown

39

40 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

in Figure 3.2. The conductance of an edge xy is CxY = 11RxY; the conductances for our example are shown in Figure 3.3.

	C
R = I		R 	I

R

a	'R	I	b
		2

< 	R

1

d

Resistances

FIGURE 3.2

C= 	C

	C
a	C = 2 b

C

C <~>= 2

d

Conductances

FIGURE 3.3

We define a random walk on G to be a Markov chain with transition matrix P given by

PXY ‑ CXY

CX

3.1	GENERAL RESISTOR NETWORKS 	41

with CX ‑ EY CXY . For our example, Q, = 2, Cb= 3, cc = 4 andCd ‑ 5, and the transition matrix P for the associated random walk is

	a	b	c	d
a	0	0	1/2	1/2
b	0	0	1/3	2/3
c 1/4	1/4	0	1/2
d 1/5	2/5	2/5	0

Its graphical representation is shown in Figure 3.4.
	C

4		4
	2		b

	5
2

2
5

d
H(S‑UM., 3.4

Since the graph is connected, it is possible for the walker to go betw een any two states. A Markov chain

2

3

2
3

with this property is called an ergodlic Markov chain. Regular chains, which were introduced in Section 2.6, are always ergodic, but ergodic chains are not always regular (see Exercise 1).

P ‑

42 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

For an ergodic chain, there is a unique probability vector w that is a fixed vector for P, i.e., wP ‑ w. The component wJ of w represents the proportion of times, in the long run, that the walker will be in state.j. For random walks determined by electric networks, the fixed vector is given by w_, = C_, IC where C ‑ E_, C, (You are asked to prove this in Exercise 2.) For our example Q, = 2, Cb = 3, C, ‑ 4, Cd ‑ 5 and C = 14. Thus w ‑ (2/14, 3/14, 4/14, 5/14). We can check that w is a fixed vector by noting that

0	0	1/21/2

	(2 3 4 5	0	0	113	2/3			4 5).
						(_2 3
	4 14 14 4) 1/4	1/4	0	1/2		4 14 14 14
		1/5	2/5	2/5	0

In addition to being ergodic, Markov chains associated with networks have another property called reversibility. An ergodic chain is said to be reversible if WXP_V = WyPyx for all x, y. That this is true for our network chains follows from the fact that

CXPXY = CX CXY ‑ C XY = CyX = Cy		‑ CyPyX
	CX 	CY

Thus, dividing the first and last term by C, we have

WXPXY ‑ WY I~Vx *

To see the meaning of reversibility, we start our Markov chain with initial probabilities w (in equilibrium) and observe a few states, for example

	a	C h d.
The probability that this sequence occurs is

WapacpcbPbd	2 . 1 . 1 . 2 	1

14 2 4 3	84

3.1	GENERAL RESISTOR NETWORKS 	43

The probability that the reversed sequence

d	b	C 	a

occursis

WdPdbPbcPca	5 . 2 . 1 . 1 	1

14 5 3 4 	84'

Thus the two sequences have the same probability of occurring.

In general, when a reversible Markov chain is started in equilibrium, probabilities for sequences in the correct order of time are the same as those with time reversed. Thus, from data, we would never be able to tell the direction of time.

If P is any reversible ergodic chain, then P is the transition matrix for a random walk on an electric network; we have only to define C,Y ‑WXPXY. Note, however, if PXX # 0 the resulting network will need a conductance froni x to x (see Exercise 4). Thus reversibility characterizes those ergodic chains that arise from electrical networks. This has to do with the fact that the physical laws that govern the behavior of steady electric currents are invariant Linder time‑reversal (see Onsager 1271).

When all the conductances of a network are equal, the associated randoni walk on the graph G of tile network has the property that, from each point, there is an equal probability of moving to each of the points connected to this point by an edge. We shall refer to this random walk as simple random walk on G. Most of the examples we have considered so far are simple random walks. Our first example of a random walk on Madison Avenue corresponds to simple random walk on the graph with points 0, 1, 21 ... I N and edges the streets connecting these points. Our walks on two dimensional graphs were also simple random walks.

44 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

EXERCISES

1. Give an example of an ergodic Markov chain that is not regular. (Hint: a chain with two states will do.)

2. Show that, if P is the transition matrix for a random walk determined by an electric network, then the fixed vector w is given by w_, ‑ CIC where C, ‑ Ey Cy and C ‑ EX CX.

3. Show that, if P is a reversible Markov chain and a, b, c are any three states, then the probability, starting at a, of the cycle ahca is the same as the probability of the reversed cycle acha. That is PabPbcPca ‑ PacPcbPba ‑Show, more generally, that the probability of going around any cycle in the two different directions is the same. (Conversely, if this cyclic condition is satisfied, the process is reversible. For a proof, see Kelly [14].)

4. Assume that P is a reversible Markov chain with PXX = 0 for all x. Define an electric network by CXY = WXPXY * Show that the Markov chain associated with this circuit is P. Show that we can allow PXX > 0 by allowing a conductance from x to x.

5. For the Ehrenfest urn model, there are two urns that together contain N balls. Each second, one of the N balls is chosen at random and moved to the other urn. We form a Markov chain with states the number of balls in one of the urns. For N = 4, the resulting transition matrix is

	0	1	2	3	4
0	0	1	0	0 	0

1	1/4	0	3/4	0 	0

P = 2	0	1/2	0	1/2 	0

3 ( 0 0 3/4 0 1/4

4	0	0	0	1 	0

3.2	VOLTAGES FOR GENERAL NETWORKS 	45

Show that the fixed vector w is the binomial distribution w ‑ (1/16, 4/16, 6/16, 4/16, 1/16). Determine the electric network associated with this chain.

3.2 Voltages for General Networks; Probabilistic
Interpretation

We assume that we have a network of resistors assigned to the edges of a connected graph. We choose two points a and b and put a one‑volt battery across these points establishing a voltageVa ‑ 1 andVb ‑ 0, as illustrated in Figure 3.5. We are interested in finding the voltages v, and the currents ixy in the circuit and in giving a probabilistic interpretation to these quantities.

C

R = I		R ‑	I
a	R		b

2

R ‑

~R‑ I	R
		2

d

I volt

F I G U R E 3.5

We begin with the probabilistic interpretation of voltage. It will come as no surprise that we will interpret the voltage as a hitting probability, observing that both functions are harmonic and that they have the same boundary values.

46 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

By Ohm's Law, the currents through the resistors are determined by the voltages by

ixy ‑ Vx RXY VY ‑ (Vx ‑ VY)CxY.

Note that ixy ‑ ‑,iyx. Kirchhoff's Current Law requires that the total current flowing into any point other than a or b is 0. That is, for x # a,h

E ixy ‑ 0.

Y

This will be true if

E (Vx ‑ VY)CxY ‑ 0 Y

or

Vx E CXY 	CXY VY ‑

Y 	Y

Thus Kirchhoff's Current Law requires that our voltages have the property that

Vx = E CXY V Y		PXY VY
	Y Cx 	Y

for x # a, b. This means that the voltage vx is harmonic at all points x # a, b.

Let hx be the probability, starting at x , that state a is reached before b. Then hx is also harmonic at all points x # a, b. Furthermore

Va ‑ ha ‑ 1 and

Vb ‑hb ‑ 0

Thus if we modify P by making a and b absorbing states, we obtain an absorbing Markov chain P and v

3.2	VOLTAGES FOR GENERAL NETWORKS 	47

and h are both solutions to the Dirichlet problem for the Markov chain with the same boundary values. Hence v ‑ h.

For our example, the transition probabilities PXY are shown in Figure 3.6. The function vx is harmonic for P

with boundary values v,,	1, vb = 0.

C

	4			4
a		2			b
		5	2

b

	2
	2
S	S

d

Fi(;URE .1.0

To sum up, we have the following:

INTREPRETATION OF VOLTAGE. When a unit voltage is applied hetween a and b, making v,, ‑ I and Vb = 0, the voltage v., at any point x represents the probability that a walker startingfrom x will return to a before reaching b.

In this probabilistic interpretation of voltage, we have assumed a unit voltage, but we could have assumed an arbitrary voltage v,, between a and b. Then the hitting probability hx would be replaced by an

48 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

expected value in a game where the player starts at x and is paid v,, if a is reached before b and 0 otherwise.

Let's use this interpretation of voltage to find the voltages for our example. Referring back to Figure 3.6, we see that

Va = 1

Vh	0

VC		+		Vd
	4		2
	1		2

Vd 	+ ‑ VC.

5	5

Solving these equations yields vc ‑ 7/16 andVd ‑ 3/8. From these voltages we obtain the current i‑,,. For exampleicd ‑ ((7/16) ‑ (3/8)) ‑ 2 = 1/8. The resulting voltages and currents are Shown in Figure 3.7. The

‑ 7

V ‑ ‑

16

		C			C
				9		7
R	I		R	16		16

v= I	a	R		b V	0	a I .	2	b
			2				16

	R	I	R	‑ 1	10	12
			d	2	16 d	16

R

~6

				0
	R	I	R
q	t_	i = !~

V = ‑
	16

I volt	I volt

Voltages	Currents

FIGURE 3.7

3.3	INTERPRETATION OF CURRENT 	49

voltage at c is 7/16 and so this is also the probability, starting at c, of reaching a before b.

3.3 Probabilistic Interpretation of Current

We turn now to the probabilistic interpretation of cur
rent. This interpretation is found by taking a naive
view of the process of electrical conduction: We imag
ine that positively charged particles enter the network
at point a and wander around from point to point until
they finally arrive at point b, where they leave the net
work. (It would be more realistic to imagine negatively
charged particles entering at b and leaving at a, but
realism is not what we're after.) To determine the cur
rent iXV along the branch from x toy, we consider that
in the course of its peregrinations the point may pass
once or several times along the branch from x toy, and
in the opposite direction from y to x. We may now hy
pothesize that the current i, ‑, is proportional to the ex
pected net number of movements along the edge from
x toy, where movements f rom y back to x are counted
as negative. This hypothesis is correct, as we will now
show.

The walker begins at a and walks until lie reaches b; note that if he returns to a before reaching b, he keeps on going. Let ux be the expected number of visits to state x before reaching b. Then ul, = 0 and, for x :~L a, b,

11X	11VPVX.

This last equation is true because, for x # (i, h, every entrance to x must come from some v.

We have seen that CXPXV ‑ Cvp,,x; thus

11X	11V PXV CX

Y , 	CY

50 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

or

Ux 	UY

	EP XY
CX	Y 	CY

This means that vX ‑ Ux 1Cx is harmonic for x # a, h. We have alsoVb= 0 and va ‑ Ua I Ca. This implies that VX is the voltage at x when we put a battery from a to h that establishes a voltageUa lCa at a and a voltage 0 at h. (We remark that the expressionVa Ua /Camay be understood physically by viewingUa as charge andCa as capacitance; see Kelly [14] for more about this.)

We are interested in the current that flows from x to y. This is

ixy ‑ (VX ‑ VY ) CXY	U X ‑ ‑'~V C':"

CX	CY

‑ UXCXY UY CyX = U
	XPXY ‑ UYPYX

CX	CY

Now uXPXY is the expected number of times our walker will go from x toy and uYPYx is the expected number of times he will go from y to x. Thus the current ixy is the expected value for the net number of times the walker passes along the edge from x to y. Note that for any particular walk this net value will be an integer, but the expected value will not.

As we have already noted, the currents ixy here are not those of our original electrical problem, where we apply a 1‑volt battery, but they are proportional to those original currents. To determine the constant of proportionality, we note the following characteristic property of the new currents ixy: The total current flowing into the network at a (and out at h) is 1. In symbols,

E iay ‑ 1.

Y

3.3	INTERPRETATION OF CURRENT 	51

Indeed, from our probabilistic interpretation of ixy ~ this sum represents the expected value of the difference between the number of times our walker leaves a and enters a. This number is necessarily one and so the current flowing into a is 1.

This unit current flow from a to b can be obtained from the currents in the original circuit, corresponding to a 1‑volt battery, by dividing through by the total amount of current

E iay

Y

flowing into a; doing this to the currents in our example yields the unit current flow shown in Figure 3.8.

9

	7
19
	19

2

I ‑‑	b

9

9

	12
1 0

=~ ~;	19

t 19

'I 11C 111111 ctirreld ll()%%

Fi(;UM, 3.h

This shows that the constant of proportionality we were seeking to determine is the reciprocal of the amount of current that flows through the circuit when a I ‑volt battery is applied between a and b. This quantity, called the effective resistance between a and b, is discussed in detail in the next section.

52 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

To sum up, we have the following:

INTERPRETATION OF CURRENT. When a unit currentflows into a and out of b, the current iyflowing through the branch 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 branch from x to y. These currents are proportional to the currents that arise when a unit voltage is applied between a and b, the constant of proportionality being the effective resistance of the network.

We have seen that we can estimate the voltages by simulation. We can now do the same for the currents. We have to estimate the expected value for the net number of crossings of xy. To do this, we start a large number of walks at a and, for each one, record the net number of crossings of each edge and then average these as an estimate for the expected value. Carrying out 10,000 such walks yielded the results shown in Figure 3.9.

C 	C

.47S4	3672	.4737	3684

<4 	36 ‑

a	1082	b	a	.10S3 b
t			t		6316

S263

.5246	.6328

d

Fslimales of currcnts by sinitila(1011	Calculaled curivilts

FIGURE 3.9

3.4	EFFECTIVE RESISTANCE 	53

The results of simulation are in good agreement with the theoretical values of current. As was the case for estimates of the voltages by simulation, we have statistical errors. Our estimates have the property that the total current flowing into a is 1, out of b is 1, and into any other point it is 0. This is no accident; the explanation is that the history of each walk would have these properties, and these properties are not destroyed by averaging.

EXERCISE

1. Kingman [18] introduced a different model for current
flow. Kelly [14] gave a new interpretation of this model.
Both authors use continuous time. A discrete time version of
Kelly's interpretation would be the following: At each point
of the graph there is a black or a white button. Each second
an edge is chosen; edge xy is chosen with probability C, ‑,, IC
where C is the sum of the conductances. The buttons on the
edge chosen are then interchanged. When a button reaches
a it is painted black, and when a button reaches b it is
painted white. Show that there is a linliting probability 1),
that site x has a black button and that px is the voltage v_, at
X when a unit voltage is imposed between a and b. Show that
the current ix,, is proportional to the net flow of black but
tons along the edge x~,. Does this suggest a hypothesis about
the behavior of conduction electrons in metals?

3.4 Effective Resistance and the Escape Probability

When we impose a voltage v between points a and b, a voltage v,, = v is established at a and vj, ‑ 0, and a current ia = E X iaxwill flow into the circuit from the outside Source. The amount of current that flows depends upon the overall resistance in the circuit. We define the effective resistance RE,,‑Fbetween a and b by

54 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

REFF= v,, lia. The reciprocal quantity CEFF= 11REFF ‑ ia Iva is the effective conductance. If the voltage between a and b is multiplied by a constant, then the currents are multiplied by the same constant, so REFFdepends only on the ratio0f Va to ia ‑

Let us calculate REFFfor our example. When a unit voltage was imposed, we obtained the currents shown in Figure 3.7. The total current flowing into the circuit is ia ‑ 9/16 + 10/16 = 19/16. Thus the effective resistance is

Va	1	16

REFF

la	19	19

16

We can interpret the effective conductance probabilistically as an escape probability. WhenVa ‑ 1, the effective conductance equals the total current i, flowing into a. This current is

ia =	E (va	Vy)Cay		(va ‑ Vy)	Cay Ca
	Y		Y		Ca

= C a(l	Payvy)

Y

C aP escape

where Pescape is the probability, starting at a, that the walk reaches b before returning to a. Thus

CEFF ‑ CaPescape

and

P escape ‑ CEFF

Ca

3.4	EFFECTIVE RESISTANCE 	55

	In our example Q, = 2 and we found that ia
19/16. Thus

	19
P escape
	32

In calculating effective resistances, we shall use two important facts about electric networks. First, if two resistors are connected in series, they may be replaced by a single resistor whose resistance is the sum of the

R, 	R 2

R, ‑+ R2

FIGURE 3. 10

two resistances. Secondly, two resistors in parallel may be replaced by a single resistor with resistance R such that

I	I + I	R I R

R	R I	R2	R, + R2

R,

R,	R2

AAAI%‑

FIGURE 3.11

56 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

The second rule can be stated more simply in terms of conductances: If two resistors are connected in parallel, they may be replaced by a single resistor whose conductance is the sum of the two conductances.

We illustrate the use of these ideas to compute the effective resistance between two adjacent points of a unit cube of unit resistors, as shown in Figure 3.12.

C	9

d a

AA~	h

b f

FIGURE 3.12

We put a unit battery between a and h. Then, by symmetry, the voltages at c and d will be the same as will those at e andf. Thus our circuit is equivalent to

the circuit shown in Figure 3.13.

(c, d)

a	9

b

Je, f

FIGURE 3.13

3.4	EFFECTIVE RESISTANCE	57

a	2 	2

2 b

2 	2

2 a

	2
1 2

b 2 0

2

2

2 +
	2

h	2
	a

7
5

h

a

7

5	12
7

b

1‑)(;uRu .3.14

Using the laws for the effective resistance of resistors in series and parallel, this network can be successively reduced to a single resistor of resistance 7/12 ohms, as shown in Figure 3.14. Thus the effective resistance is 7/12. The current flowing into a from the battery will

58 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

be ia ‑ 11REFF‑ 12/7. The probability that a walk starting at a will reach b before returning to a is

12

	P escape ‑ ia	7	4
	Ca	3	7

This example and many other interesting connections between electric networks and graph theory may be found in Bolloba's [2].

b

a 0

FIGURE 3.15

EXERCISES

1 ‑ A bug walks randomly on the unit cube (see Figure 3.15). If the bug starts at a, what is the probability that it reaches food at b before returning to a?

2. Consider the Ehrenfest urn model with N = 4 (see Exercise 5 of Section 3. 1). Find the probability, starting at 0, that state 4 is reached before returning to 0.

3. Consider the ladder network shown in Figure 3.16. Show that if Rn is the effective resistance of a ladder with n rungs then R I = 2 and

Rn+1 ‑ 2 + 2R

2 + R11

Use this to show that limn‑‑*Oo R I, ‑ ‑\/‑2.

3.4	EFFECTIVE RESISTANCE	59

	I	I	1	1
1	2	4	8	211‑ 1

‑AAOV
	VVVN‑J7A

2	4	2t'	2

Fic;URE 3.16

4. A drunken tourist starts at his hotel and walks at random through the streets of the idealized Paris shown in Figure 3.17. Find the probability that he reaches the Arc de Triomphe before he reaches the outskirts of town.

A rc

Fi(;URE .3.17

60 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

3.5 Currents Minimize Energy Dissipation

We have seen that when we impose a voltage between a and h voltages vX are established at the points and currents ixy flow through the resistors. In this section we shall give a characterization of the currents in terms of a quantity called energy dissipation. When a current ixy flows through a resistor, the energy dissipated is

i2RXY;

XY

this is the product of the current ixy and the voltage vXY i XYRXY, The total energy dissipation in the circuit is

E ‑ 1 E i2 RXY

2 x ly xy

Since iXYRXY ‑ VX vy we can also write the energy dissipation as

E ‑ ‑ E ixy (VX ‑ VY).

2 Zy

The factor 1/2 is necessary in this formulation since each edge is counted twice in this sum. For our example, we see from Figure 3.7 that

	2		2		7
E		+ ~10		1 +		1

(‑i‑6) ~ 1‑6

+ (_2	122 1

	i ‑ ‑	‑
6)' ‑ 12 + 16	2

19

16

If a source (battery) establishes voltagesVaandVbat a and b, then the energy supplied is (Va ‑ Vb)iawhere

3.5	CURRENTS MINIMIZE ENERGY DISSIPATION 	61

ia = E X iax * By conservation of energy, we would expect this to be equal to the energy dissipated. In our example v,,‑ Vb ‑ 1 and i,, ‑19/16, so this is the case. We shall show that this is true in a somewhat more general setting.

Define a flow j from a to b to be an assignment of numbersjxy to pairs xy such that

(a) j, ‑jyx

(b) E ixy 0 if x # a, b

y

(c)	0 	if x and y are not adjacent.

We denote by J, ‑ Ey j,.,, the flow into x from the

outside. By (b) j, ‑‑ 0 for x	a, b. Of course./*h
‑ Ja ‑ To verify this, note that

Ja + Jb rl.ix r' . i xY

X	X Y

(jxv‑ + J VIX	0

2 X31

since.ixy 	IYX'

With this terminology, we can now formulate the following version of the principle of conservation of energy:

CONSERVATION OF ENERGY. Let w be any function defined on the points oJ' the graph and j aflow from a to b. Then

(Wa ‑ Wb)j.	_(Wx ‑ Vi'.,)jx,

2 xy

62 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

Proof.

	(WX WYYXY ‑ E (WX EiXY) ‑ E (WY EiXY)
X'Y		X	Y	Y 	X

‑ Wa	Ejay + Wb	Eiby
	Y 	Y

Wa Ejxa ‑ Wb Ejxb

X 	X

‑	Waia + Wbib	Wa(‑j.)
	‑ Wb(‑jb)

2(wa ‑ Wb)ja

Thus

1

(Wa ‑ Wb)Ja = ‑ E (W X ‑ W Y VXY

2 Zy

as was to be proven.

If we now impose a voltageVabetween a and b with Vb= 0, we obtain voltages vx and currents ixy . The currents i give a flow from a to b and so by the previous result, we conclude that

Va ia = 1 E (VX ‑ VY ) ixy 	Ei2RXY*

2 Zy	2 XY xy

Recall that REFF ‑ Va lia . Thus in terms of resistances we can write this as

i2 REFF ‑ 1 Ei2R

a	2 X'Y xy	XY

If we adjust Va so that ia ‑ 1, we call the resulting flow the unit current flow from a to b. The unit current flow from a to b is a particular example of a unit flow

3.5	CURRENTS MINIMIZE ENERGY DISSIPATION 	63

from a to b, which we define to be any flow ixy from a to b for which ia = _ib 1. The formula above shows that the energy dissipated by the unit current flow is just REFF. According to a basic result called Thomson's Principle, this value is smaller than the energy dissipated by any other unit flow from a to b. Before proving this principle, let us watch it in action in the example worked out above.

Recall that, for this example, we found the true values and some approximate values for the unit current flow; these were shown in Figure 3.9. The energy dissipation for the true currents is

	16
E = REFF	19 	8421053.

Our approximate currents also form a unit flow and, for these, the energy dissipation is

E ‑ (.4754)2. 1 + (.5246)2. 1 + (.3672)2. 1

	+ (.1082)2 1 + (.6328)2 ‑ 1
2 	2

‑ .8421177.

We note that E is greater than E, though just barely.

THomSON'S PRINCIPLE. (Thomson [35]). ~f i is the unitflow from a to b detertnined by Kirchhoff's Law, then the energy dissipation 1/2 E i2 R nz 1 . n t . ‑

X "y XY _,~V

2 R ainong all

tnizes the energy dissipation 1/2 EX1.V XY X.V unit flows jfronz a to b.

	Proo Let j be any unit flow from a to b and let
		~f
dXy ixy ‑ ixy. Then d is a flow from a to b with

da	E Xdax ‑ 1 ‑ 1 = 0.

64 RANDOM WALKS ON MORE GENERAL NETWORKS Ch. 3

xy )2

Ej'R	E (i + d	RxY
	XY _)Y		XY

X,Y	XY

Ei'R + 2Ei R d + Ed 2 R

XY	XY	XY	XY XY	XY 	XY

X,Y	XY 	XY

E i2 R + 2E (vx ‑ vy dxy + E d 2 R

XY	XY	XY 	XY

X,Y	XY	XY

Setting w ‑ v and j ‑ d in the conservation of energy result above shows that the middle term is 4(va ‑ Vb)da

0. Thus

Ej2		E i2		2	>
	R		R + Ed R		E i2 R

	XY	XY		XY	XY		XY	XY		XY	XY
X,Y			XY			XY			XY

This completes the proof.

EXERCISES

1. The following is the so‑called "dual form" of Thomson's Principle. Let u be any function on the points of the graph G of a circuit such that u, ‑ I andUb= 0. Then the energy dissipation

1 E (UX ‑ U Y)2Cxy

2 xy

is minimized by the voltages vx that result when a unit voltage is established between a and b, i.e., Va ‑ 1, Vh= 0, and the other voltages are determined by Kirchhoff's Laws. Prove this dual principle. This second principle is known nowadays as the Dirichlet Principle, though it too was discovered by Thomson.

2. In Section 2.4 we stated that, to solve the Dirichlet problem by the method of relaxations, we could start with an arbitrary initial guess. Show that when we replace the value at a point by the average of the neighboring points the energy dissipation, as expressed in Exercise 1, can only decrease. Use this to prove that the relaxation method converges to a solution of the Dirichlet problem for an arbitrary initial guess.

CHAPTER 4

RAYLEIGH'S MONOTONICITY LAW

4.1 Rayleigh's Monotonicity Law

In this chapter we will study Rayleigh's Monotonicity Law. This law from electric network theory will be an important tool in our future study of random walks. In this first section we will give an example of the use of this law.

Consider a random walk on streets of a city as in Figure 4. 1. Let p,,,,P, be the probability that a walker starting from (i reaches b before returning to (i. Assign to each edge a unit resistance and maintain a voltage of

b

a

FIGURE 4.1

65

66	RAYLEIGH'S MONOTONICITY LAW 	Ch. 4

one volt between a and b; then a current i,, will flow into the circuit and we showed in Section 3.4 that

P escape = ia ‑ ia

Ca	4

Now suppose that one of the streets (not connected to a) becomes blocked. Our walker must choose from the remaining streets if he reaches a corner of this street. The modified graph will be as in Figure 4.2. We want to show that the probability of escaping to b from a is decreased.

b

a

FIGURE 4.2

Consider this problem in terms of our network. Blocking a street corresponds to replacing a unit resistor by an infinite resistor. This should have the effect of increasing the effective resistance REFFof the circuit between a and b. If so, when we put a unit voltage between a and b less current will flow into the circuit and

P escape ‑ ia 	1

4	4 REFF

will decrease.

4.1	RAYLEIGH'S MONOTONICITY LAW 	67

Thus we need only show that when we increase the resistance in one part of a circuit, the effective resistance increases. This fact, known as Rayleigh's Monotonicity Law, is almost self‑evident. Indeed, the father of electromagnetic theory, James Clerk Maxwell, regarded this to be the case. In his Treatise on Electricity and Magnetism ([23], p. 427), he wrote

"If the specific resistance of any portion of the conductor be changed, that of the remainder being unchanged, the resistance of the whole conductor will be increased if that of the portion is increased, and diminished if that of the portion is diminished. This principle may be regarded as self‑evident ......

RAYLEIGH'S MONOTONICITY LAW. If the resistances of a circuit are increased, the effective resistance RE,.‑,., betvveen any tvvo points can only increase. If they are decreased, it can on~v decrease.

Proof. Let i be the unit Current flow from a to b with the resistors R.,‑,,Let j be the unit Current flow from a to b with the resistors R.VV with R., R.,.,,. Then

R pjq.. ‑ ‑ j2

X

2

> ‑	V V R.V V

j.2

2

But sincej is a unit flow from a to b, Thomson's Principle tells us that the energy dissipation, calculated with resistors Rx,, . is bigger than that for the true currents determined by these resistors: that is

‑2 	1

R	i2 R 	R

JXV XT	‑q XV	EFF

2 X I‑V	2 X,Y

68	RAYLEIGH'S MONOTONICITY LAW 	Ch. 4

Thus REFF>, REFF. The proof for the case of decreasing resistances is the same.

EXERCISES

1. Consider a graph G and let RXV and RXY be two different assignments of resistances to the edges of G. Let R ‑

XY

RXY + RXY I Let REFF, REFFand REFFbe the effective resistances when R, R and R, respectively, are used. Prove that

REFF >, REFF+ REFF.

Conclude that the effective resistance of a network is a concave function of any of its component resistances (Shannon and Hagelbarger [331).

R11	R 12
R 21	R22

FiGURE 4.3

R11	R 12

E:::=

R 21 	R22

FIGURE 4.4

2. Show that the effective resistance of the circuit in Figure 4.3 is greater than or equal to the effective resistance of the circuit in Figure 4.4. Use this to show the following inequality for R ij '> 0:

4.2	PROBABILISTIC EXPLANATION	69

1	_>_ ‑ I	+ 	1

+	1 + I	‑ 1 ‑ +

R I I + R12	R21 + R22	R11	R21	R12 	R22

See the note by Lehman [20] for a proof of the general Minkowski inequality by this method.

3. Let P be the transition matrix associated with an electric network and let a, b, r, s be four points on the network. Let P be a transition matrix defined on the state‑space S = la, b, r, sj. LetPii = 0 andfori #j definePiito be the probability that, if the chain P is started in state i, then the next time it is in the set S ‑ I i I it is in the statej. Show that P is a reversible Markov chain and hence corresponds to an electric network of the form of a Wheatstone Bridge, shown in Figure 4.5. Explain how this proves that, in order to prove the Monotonicity Law, it is sufficient to prove that REFFis a monotone function of the component resistances for a Wheatstone Bridge. Give a direct proof of the Monotonicity Law for this special case.

FiutjHi~ 4.5

4.2 A Probabilistic Explanation of the Monotonicity Law

We have quoted Maxwell's assertion that Rayleigh's Monotonicity Law may be regarded as self‑evident, but one might feel that any argument in terms of elec

70	RAYLEIGH'S MONOTONICITY LAW 	Ch. 4

tricity is only self‑evident if we know what electricity is. in Cambridge, they tell the following story about Maxwell: Maxwell was lecturing and, seeing a student dozing off, awakened him, asking, "Young man, what is electricity?" "I'm terribly sorry, sir," the student replied, "I knew the answer but I have forgotten it." Maxwell's response to the class was, "Gentlemen, you have just witnessed the greatest tragedy in the history of science. The one person who knew what electricity is has forgotten it."

To say that our intuition about the Monotonicity Law is only as solid as our understanding of electricity is not really a valid argument, of course, because in saying that this law is self‑evident we are secretly depending on the analogy between electricity and the flow of water (see Feynman [6], Vol. 2, Chapter 12). We just can't believe that if a water main gets clogged the total rate of flow out of the local reservoir is going to increase. But as soon as we admit this, some pedant will ask if we're talking about flows with low Reynolds' number, or what, and we'll have to admit that we don't understand water any better than we understand electricity.

Whatever our feelings about electricity or the flow of water, it seems desirable to have an explanation of the Monotonicity Law in terms of our random walker. We now give such an explanation.

We begin by collecting some notation and results from previous sections. As usual, we have a network of conductances (streets) and a walker who moves from point x to pointy with probability

PXY = CXY

CX

4.2	PROBABILISTIC EXPLANATION 	71

where CXY is the conductance from x to y and Cx _EY CXY, We choose two preferred points a and b. The walker starts at a and walks until he reaches h or returns to a. We denote by vx the probability that the walker, starting at x, reaches a before b. Then v,, ‑ 1, Vb= 0, and the function vX is harmonic at all points x # a, b. We denote by Pescape the probability that the walker, starting at a, reaches b before returning to a. Then

Pescape 	Paxvx.

X

Now we have seen that the effective conductance between a and b is

C a P esca pe

We wish to show that this increases whenever one of the conductances CrS is increased. If a is different from r or s, we need only show that p,,c,,1,, increases. The case where r or s coincides with a is easily disposed of (see Exercise 1). The case where r or s coincides with b is also easy (see Exercise 2). Hence frorn now oil we will assurne that r, s ‑‑t‑ a and r, s :tb.

Instead of increasing Crs, we can think of adding a new edge of conductance ( between r and s. (See Figure 4.6.) We will call this new edge a "bridge" to distinguish it from the other edges. Note that the graph with the bridge added will have more than one edge between r and s (unless there was no edge between r and s in the original graph), and this will complicate any expression that involves suninling over edges. Everything we have said or will say in this book holds for graphs with "multiple edges" as well as for graphs without them. So far, we have chosen to keep our expressions simple by assuming that an edge is determined by its

72	RAYLEIGH'S MONOTONICITY LAW	Ch. 4

'IGURE 4.6

endpoints. The trade‑off is that in the manipulations below, whenever we write a sum over edges we will have to add an extra term to account for the bridge.

Why should adding the bridge increase the escape probability? The first thing you think is, "Of course, it opens up new possibilities of escaping! " The next instant you think, "Wait a minute, it also opens up new possibilities of returning to the starting point. What ensures that the first effect will outweigh the second?" As we shall see, the proper reply is, "Because the walker will cross the bridge more often in the good direction than in the bad direction." To turn this blithe reply into a real explanation will require a little work, however.

To begin to make sense of the notion that the bridge gets used more often in the good direction than the bad, we will make a preliminary argument that applies to any edge of any graph. Let G be any graph, and let rs be any edge with endpoints not a or b. Assume that

4.2	PROBABILISTIC EXPLANATION 	73

Vr >, vs. Since he has a better chance to escape from s than from r, this means that to cross this edge in the good direction is to go from r to s. We shall show that the walker will cross the edge from r to s more often on the average than from s to r.

Let ux be the expected number of times the walker is at x and uxy the expected number of times he crosses the edge xy from x toy before he reaches b or returns to a. The calculation carried out in Section 3.3 shows that UX /CX is harmonic for x # a, b withUa/Ca ‑ I lCaand UbICb ‑ 0. But the function Vx lCa also has these properties, so by the Uniqueness Principle

UX ‑ VX

CX	Ca

Now

11 rs = llrprs ‑ Ur Crs ‑ vr Crs

Cr	c(I

and

11sr ‑ 11.5psr = us C.sr ‑ Vs Csr

CS	C11

Since CrS = Csr, and since by assumption Vr >1 v, this means that urS >, 11srTherefore, we see that any edge leads the walker more often to the more favorable of the points of the edge.

Now let's go back and think about the graph with the bridge. The above discussion shows that the bridge helps in the sense that, on the average, the bridge is crossed more often in the direction that improves the chance of escaping. While this fact is suggestive, it doesn't tell us that we are more likely to escape than if the bridge weren't there; it only tells us what goes on

74	RAYLEIGH'S MONOTONICITY LAW	Ch. 4

once the bridge is in place. What we need is to make a "before and after" comparison.

Recall that we are denoting the conductance of the bridge by E. To distinguish the quantities pertaining to the walks with and without the bridge, we will put csuperscripts on quantities that refer to the walk with the bridge, so that, e,g*~ Pescape denotes the escape probability with the bridge.

Now let d' denote the expected net number of times the walker crosses from r to s. As above, we have

( = UE	E	‑	E 	E

Id	r Cr +	us C S +
E 	E

Ur_	us

Cr + C_	CS + E

CLAIM: Pe'scape ‑ Pescape + (Vr ‑ vs)df.

	Why? Every time you use the bridge to go from r to
s, you improve your chances of escaping by

(1 ‑ Vs) ‑ 0 ‑ Vr) ‑ Vr ‑ VS 9

assuming that you would continue your walk without using the bridge. To get the probability of escaping with the bridge, you take the probability of escaping without the bridge, and correct it by adding in the change attributable to the bridge, which is the difference in the original escape probabilities at the ends of the bridge, multiplied by the net number of times you expect to cross the bridge.

Proof. Suppose you're playing a game where you walk around the graph with the bridge, and your fortune when you're at x is vX . which is the probability

4.2	PROBABILISTIC EXPLANATION 	75

that you would return to a before reaching b if the bridge weren't there. You start at a, and walk until you reach b or return to a.

This is not a fair game. Your initial fortune is I since you start at a and v,, 1. Your expected final fortune is

P escape ) + 0 P escape

P escape

The amount you expect to lose by participating in the game is

P escape

(Note that escaping has suddenly become a bad thing!)

Let's analyze where it is that you expect to lose money. First of all, you lose money when you take the first step away from a. The amount you expect to lose is

Pax Vx x

P escape

Now if your fortune were given by v' instead of vx, x

the game would be fair after this first step. However, the function vx is not harmonic for the walk with the bridge; it fails to be harmonic at r and s. Every time you step away from r, You expect to lose an amount

		Crx		E
	Vr ‑ (E		. Vx +		V
	X	Cr + E	Cr + (	S)

(V r ‑ VS)	E
	Cr + E

76	RAYLEIGH'S MONOTONICITY LAW 	Ch. 4

Similarly, every time you step away from s you expect to lose an amount

(Vs ‑ Vr)

C, +

The total amount you expect to lose by participating in the game is:

expected loss at first step

• (expected loss at r) ‑ (expected number of times at r)

• (expected loss at s) ‑ (expected number of times at s)

P escape

+ (Vr ‑ VS)	E	U
	Cr + C	r
+ (V, ‑ Vr)	E	U E

CS + IE s

Pescape + (Vr ‑ Vs )dE.

Equating this with our first expression for the expected cost of playing the game yields the formula we were trying to prove.

According to the formula just established,

		U E	USE
P	(V ‑ V	r		E.

T escape		escape		r	S) ( Cr +	CS +

For small E, we will have

U 4E	U (	Ur 	us

r 	S

Cr + e CS + IE Cr CS

Vr 	VS

Ca	Ca

4.2	PROBABILISTIC EXPLANATION	77

so for small E

	E
s)2

Pescape ‑ Pescape ‑‑'= (Vr ‑ V 	Ca

This approximation allows us to conclude that

f

Pescape >‑, Pescape >~' 0

for small E. But this is enough to establish the monotonicity law, since any finite change in e can be realized by making an infinite chain of graphs each of which is obtained from the one before by adding a bridge of infinitesimal conductance.

To recapitulate, the difference in the escape probabilities with and without the bridge is obtained by taking the difference between the original escape probabilities at the ends of the bridge, and multiplying by the expected net number of crossings of the bridge. This quantity is positive because the walker tends to cross the bridge more often in the good direction than in the bad direction.

EXERCISES

I . Give a probabilistic argument to show that Capmape increases with Car for any r. Give an example to show that Pescape by itself may actUally decrease.

2. Give a probabilistic argUnient to show that Cap,,c,~pc increases with Crb for any r.

3. Show that when vr ‑ VS, changing the value of Cr, does not change p,,c,,P,.

4. Show that

	2
Mrs REFF ‑ irs

78	RAYLEIGH'S MONOTONICITY LAW	Ch. 4

5. In this exercise we ask you to derive an exact formula for the change in escape probability

P cEscape ‑ P escape

in terms of quantities that refer only to the walk without the bridge.

(a) Let Ny denote the expected number of times in statey for a walker who starts at x and walks around the graph without the bridge until he reaches a or h. It is a fact that

f 	IE

Ur	r + Ur' C + (Nsr + 1 ‑ Nrr)

+ U, ‑ E	(Nrr ‑ Nsr)

S CS + E

Explain in words why this formula is true.

(b) This equation for u' can be rewritten as follows:

r

Cr	U E = U	(Nsr ‑ Nrr)

Cr +	r	r + d(

Prove this formula. (Hint: Consider a game where your fortune at x is Nxr, and where you start from a and walk on the graph with the bridge until you reach b or return to a.)

(c) Write down the corresponding formula for u', and use

S

this formula to get an expression for d' in terms of quantities that refer to the walk without the bridge.

(d) Use the expression for d' to express Pe,cap, ‑ P escape in terms of quantities that refer to the walk without the bridge, and verify that the value of your expression is >, 0 for e >, 0.

6. Give a probabilistic interpretation of the energy dissipation rate.

4.3 A Markov Chain Proof of the Monotonicity Law

Let P be the ergodic Markov chain associated with an electric network. When we add an E bridge from r to s,

4.3	1 MARKOV CHAIN PROOF 	79

we obtain a new transition matrix P1 that differs from P only for transitions from r and s. We can minimize the differences between P and P' by replacing P by the matrix P corresponding to the circuit without the bridge but with an E conductance added from r to r and from s to s. This allows the chain to stay in states r and s but does not change the escape probability from a to b. Thus, we can compare the escape probabilities for the two matrices P and P', which differ only by

P		P	0
	rr	Cr + 1E		rr

Crs	E ‑ Crs +

PrS	Cr + E	Prs	Cr + S
P		P 6 S	0
	SS	CS + 6	S
P	Csr	P	Csr +
	sr	CS + 6	sr	CS +

We make states a and b into absorbing states. Let N and N' be the fundamental matrices for the absorbing chains obtained from P and P respectively. Then N = (I ‑ Q) ‑1 and N' = (I ‑ Q') ‑'where 0 and Q' differ only for the four components involving only r and s. That is,

r 	S

E	E

r	Cr + E	Cr + E

Q6 ‑ Q +

		E
S	CS	+	CS + E

Q + ho

80	RAYLEIGH'S MONOTONICITY LAW 	Ch. 4

where h is the column vector with only components r and s non‑zero

r

Cr + h

S	CS +

and 0 is a row vector with only components r and s non‑zero r S

J. G. Kemeny has pointed out to us that if A is any matrix with inverse N and we add to A a matrix of the form hB, then A ‑ h,8 has an inverse if and only if PNh I and, if so, S ‑ (A ‑ h,8)‑l is given by & ‑ N + c(Nh) (ON)

where c = 1 /(1 ‑ ONh). You are asked to prove this in Exercise 1. Adding ‑ho to A I ‑ Q and using this result, we obtain

N	N + c(Nh) (ON).

Using the simple nature of h and we obtain

.A 	A

.A	Nir E 	Nis c

N I'J~ = N Ij + ( C r + E	CS + E ) (Nsj ‑ Nrj)

and

C =

+ Nrr E	NrE + N,, c‑	NrS E

Cr + E	Cr + IE	CS + E	CS + E

4.3	MARKOV CHAIN PROOF 	81

Since.N is the expected number of times in r startrr

ing in r and ~Vr is the expected number of times in r started in s 9 Nrr ‑>1 Nsr ‑ Similarly, Ns, > Nrs and so the denominator is >, 1. In particular, it is positive.

Recall that the absorption probabilities for state b are given by

Bib ‑ E NikPkb k

Since Pkb Pkb

	NirE	Nis E
ib			B	B

BE = Bib + C Cr + 1E	CS + IE	Sh	rb).

Since P' 	ai i

P

		UrE	USE	B
Pescape	P_ escape + C ( Cr^+ E	CS + E		sb ‑Brh

where U‑X is the expected number of times that the ergodic chain P, started at state a, is in state x before returning to a or reaching b for the first time. The absorption probability B,, is the quantity vx introduced in the previous section. As shown there, reversibility allows us to conclude that

	fix ‑	BXU	fixil
	CX	C(j	c(I
so that

f	CC	‑	‑ )2

Pescape Pescape + ‑ (Bsb ‑Brh
	ca

and this shows that the Monotonicity Law is true.

The change from P to P was merely to make the calculations easier. As we have remarked, the escape probabilities are the same for the two chains as are the

82	RAYLEIGH'S MONOTONICITY LAW 	Ch. 4

absorption probabilities Bib. Thus we can remove the hats and write the same formula.

	EC	)2
P escape _‑ P escape + Ca (Bsb ‑Brb

The only quantity in this final expression that seems to depend upon quantities from P is c. In Exercise 2 you are asked to show that c can also be expressed in terms of the fundamental matrix N obtained from the

original P.

EXERCISES
1. Let A be a matrix with inverse N ‑ A	Let h be a
column vector and 0 a row vector. Show that
		N ‑ (A ‑ hP)_1
exists if and only if ONh # 1 and, if so,
			(Nh) (ON)
	N = N +
			1 ‑ ONh

2. Show that c can be expressed in terms of the fundamen
tal matrix N of the original Markov chain P by

C
	+ Nrr 6 N, E + N,, c‑ N, E

Cr	Cr	CS	CS

PART 11

Random Walks

on

Infinite Networks

CHAPTER 5

POLYA'S RECURRENCE PROBLEM

5.1 Random Walks on Lattices

In 1921 George Po"Iya [28] investigated random walks on certain infinite graphs, or as he called them, "street networks." The graphs he considered, which we will refer to as lattices, are illustrated in Figure 5. 1.

	0	0 0 0 9
1‑diniensional kmicc

2‑dinictisimial lattice

3‑dilliclISIMIA lamcc

FI(I I I R 1'. "), I

To construct a d‑dimensional lattice, we take as vertices those points (xl, ‑ ‑ ‑, x,l) of R" all of whose coordinates are integers, and we join each vertex by an undirected line segment to each of its 2d nearest neighbors. These connecting segments, which repre

85

86	P6LYA'S RECURRENCE PROBLEM	Ch. 5

sent the edges of our graph, each have unit length and run parallel to one of the coordinate axes of R1. We will denote this d‑dimensional lattice by Zd. We will denote the origin (0, 0, . . ., 0) by 0.

Now let a point walk around at random on this lattice. As usual, by walking at random we mean that, upon reaching any vertex of the graph, the probability of choosing any one of the 2d edges leading out of that vertex is 112d. We will call this random walk simple random walk in d dimensions.

When d = 1, our lattice is just an infinite line divided into segments of length one. We may think of the vertices of this graph as representing the fortune of a gambler betting on heads or tails in a fair coin tossing game. Simple random walk in one dimension then represents the vicissitudes of his or her fortune, either increasing or decreasing by one unit after each round of the game.

When d ‑ 2, our lattice looks like an infinite network of streets and avenues, which is why we describe the random motion of the wandering point as a 'walk. "

When d = 3, the lattice looks like an infinite "jungle gym," so perhaps in this case we ought to talk about a "random climb," but we will not do so. It is worth noting that when d = 3, the wanderings of our point could be regarded as an approximate representation of the random path of a molecule diffusing in an infinite cubical crystal. Figure 5.2 shows a simulation of a simple random walk in three dimensions.

5.2 The Question of Recurrence

The question that Po"Iya posed amounts to this: "Is the wandering point certain to return to its starting point

5.2	THE QUESTION OF RECURRENCE 	87

h(,m(i ~,2

during the course of its wanderings?" If so, we say that the walk is recurrent. If not, that is, if there is a positive probability that the point will never return to its starting point, then we say that the walk is transient.

If we denote the probability that the point never returns to its starting point bypscp, then the chain is

88	P6LYA'S RECURRENCE PROBLEM	Ch. 5

recurrent if Pescape ‑ 01

transient If Pescape > 0

We will call the problem of determining recurrence or transience of a random walk the type problem.

5.3 Po'lya's Original Question

The definition of recurrence that we have given differs from Po" lya's original definition. Po"Iya defined a walk to be recurrent if, with probability one, it will pass through every single point of the lattice in the course of its wanderings. In our definition, we require only that the point return to its starting point. So we have to ask ourselves, "Can the random walk be recurrent in our sense and fail to be recurrent in P61ya's sense?"

The answer to this question is, "No, the two definitions of recurrence are equivalent." Why? Because if the point must return once to its starting point, then it must return there again and again, and each time it starts away from the origin, it has a certain non‑zero probability of hitting a specified target vertex before returning to the origin. And anyone can get a bull'seye if he or she is allowed an infinite number of darts, so eventually the point will hit the target vertex.

EXERCISE

1. Write out a rigorous version of the argument just given.

5.4 Po'* lya's Theorem: Recurrence in the Plane, Transience in Space

In the paper cited above, PO'* lya proved the following theorem:

5.5	ESCAPE PROBABILITY 	89

PO'LYA's THEOREM. Simple random walk on a ddimensional lattice is recurrentfor d = 1, 2 and transientfor d > 2.

The rest of this book will be devoted to trying to understand this theorem. Our approach will be to exploit once more the connections between questions about a random walk on a graph and questions about electric currents in a corresponding network of resistors. We hope that this approach, by calling on methods that appeal to our physical intuition, will leave us feeling that we know "why" the theorem is true.

EXERCISES

1. Show that P61ya's theorem implies that if two random walkers start at 0 and wander independently, then in one and two dimensions they will eventually meet again, but in three dimensions there is positive probability that they won't.

2. Show that P61ya's theorem implies that a random walker in three dimensions will eventually hit the line defined by x = 2, Z = 0.

5.5 The Escape Probability as a Limit of Escape Probabilities for Finite Graphs

We can determine the type of an infinite lattice from properties of bigger and bigger finite graphs that sit inside it. The simplest way to go about this is to look at the lattice analog of balls (solid spheres) in space. These are defined as follows: Let r be an integer‑this will be the radius of the ball. Let G(r) be the graph gotten from Z" by throwing out vertices whose distance from the origin is >r. By "distance from the origin" we mean here not the usual Euclidean distance, but

90	P6LYA'S RECURRENCE PROBLEM	Ch. 5

the distance "in the lattice;" that is, the length of the shortest path along the edges of the lattice between the two points. Let S(r) be the "sphere" of radius r about the origin, i.e., those points that are exactly r units from the origin. In two dimensions, S(r) looks like a square. In three dimensions, it looks like an octahedron.

SO)

G"' in Z2

FiGURE 5.3

We define a random walk on G(r) as follows: The walk starts at 0 and continues as it would on Z' until it reaches a point on S(r) and then it stays at this point. Thus the walk on G(r) is an absorbing Markov chain with every point of S(r) an absorbing state.

Let pescapebe the probability that a random walk on G(r) Starting at 0, reaches S(r) before returning to 0. Then p(r) decreases as r increases and p

escape 	escape

(r)

limr‑o‑ P escape is the escape probability for the infinite graph. If this limit is 0, the infinite walk is recurrent. If it is greater than 0, the walk is transient.

5.6	ELECTRICAL FORMULATION 	91

5.6 Electrical Formulation of the Type Problem

Now that we have expressed things in terms of finite graphs, we can make use of the electrical methods introduced in Part 1. To determine P escape electrically, we simply ground all the points of S'(r), maintain 0 at one volt, and measure the current i(r) flowing into the circuit.

I volt

FiGURE5.4

From Section 3.4 of Part 1, we have

(r)	‑ i (r)

P cScape 	2d'

where d is the dimension of the lattice. (Remember that we have to divide by the number of branches coming out of the starting point.) Since the voltage being applied is 1, i(r) is just the effective conductance between 0 and SH 9 i.e. ~

92	P6LYA'S RECURRENCE PROBLEM	Ch. 5

REFF

where R(r) is the effective resistance from 0 to S(*).

EFF

Thus

W

P escape
	2d REFF

Define REFF, the effective resistance from zero to infinity, to be

REFF	lim REFF
	r‑ oo

This limit exists since R is an increasing function of

EFF

r. Then

P escape 2d REFF'

Of course REFFmay be infinite; in fact, this will be the case if and onlyifPescap, ‑ 0. Thus the walk is recur

‑W 	VA

0Y.

Random walk recurrence?	Resistance to infinity infinite?

Fi(;URE 5.5

5.7	HIGHER DIMENSIONS 	93

rent if and only if the resistance to infinity is infinite, which makes sense.

The success of this electrical formulation of the type problem will come from the fact that the resistance to infinity can be estimated using classical methods of electrical theory.

5.7 One Dimension is Easy, but what about Higher Dimensions?

We now know that simple random walk on a graph is recurrent if and only if a corresponding network of 1‑ohm resistors has infinite resistance "out to infinity." Since an infinite line of resistors obviously has infinite resistance, it follows that simple random walk on the I ‑dimensional lattice is recurrent, as stated by P61ya's theorem.

RCSIstalicc Io Infinity infillitc!

5.0

What happens in higher dimensions? We are asked to decide whether a d‑dimensional lattice has infinite resistance to infinity. The difficulty is that the d‑dimensional lattice Zd lacks the rotational symmetry of the Euclidean space R d in which it sits.

To see how this lack of symmetry complicates electrical problems, we determine, by solving the appropriate discrete Dirichlet problem, the voltages for a

94	P6LYA'S RECURRENCE PROBLEM	Ch. 5

one‑volt battery attached between 0 and the points of S(') in Z'. The resulting voltages are:

0

0	.091	0

0	.182 .364 .182	0

0 .091 .364	1	.364 .0910

0	.182 .364 .182	0

0	.091 	0

0

The voltages at points of S(') are equal, but the voltages at points of S(') are not. This means that the resistance from 0 to S(3) cannot be written simply as the sum of the resistances from 0 to S('), S(1) to S(2) , and S(2) to S(3). This is in marked contrast to the case of a continuous resistive medium to be discussed in the next section.

EXERCISES

	(3),		(3) andp (3)
1. Using the voltages given for G	find REFF 	escape

2. Consider a one‑dimensional infinite network with resistors R it ‑ 1/2" from n to n + 1 for n = 0, ± 1, ± 2,

Describe the associated random walk and determine whether the walk is recurrent or transient.

3. A random walk moves on the non‑negative integers; when it is in state n, n > 0, it moves with probability p, to n + 1 and with probability 1 ‑ p,, to n ‑ 1. When at 0, it moves to 1. Determine a network that gives this random walk and give a criterion in terms of the p,, for recurrence of the random walk.

5.8	GETTING AROUND LACK OF SYMMETRY 	95

5.8 Getting Around the Lack of Rotational
Symmetry of the Lattice

Suppose we replace our d‑dimensional resistor lattice by a (homogeneous, isotropic) resistive medium filling all of R d and ask for the effective resistance to infinity. Naturally we expect that the rotational symmetry will make this continuous problem easier to solve than the original discrete problem. If we took this problem to a physicist, he or she would probably produce something like the scribblings illustrated in Figure 5.7 and conclude that the effective resistance is infinite for d ‑ 1, 2 and finite for d > 2. The analogy to P61ya's theorem is obvious, but is it possible to translate these calculations for continuous media into information about what happens in the lattice?

dr

A rca ‑ r

R	dr	00 for d ‑ 1, 2

I'd ‑‑ I < oo for d < 3

FIGURF 5.7

This can indeed be done, and this would certainly be the most natural approach to take. We will come back to this approach at the end of the book. For now, we

96	P6LYA'S RECURRENCE PROBLEM	Ch. 5

will take a different approach to getting around the asymmetry of the lattice. Our method will be to modify the lattice in such a way as to obtain a graph that is symmetrical enough so that we can calculate its resistance out to infinity. Of course, we will have to think carefully about what happens to that resistance when we make these modifications.

5.9 Rayleigh: Shorting Shows Recurrence in the Plane, Cutting Shows Transience in Space

Here is a sketch of the method we will use to prove Po'*Iya's theorem. The details will be given in Chapter 6.

To take care of the case d = 2, we will modify the 2dimensional resistor network by shorting certain sets of nodes together so as to get a new network whose resistance is readily seen to be infinite. As shorting can only decrease the effective resistance of the network, the resistance of the original network must also be infinite. Thus the walk is recurrent when d ‑2.

To take care of the case d ‑ 3, we will modify the 3dimensional network by cutting out certain of the resistors so as to get a new network whose resistance is readily seen to be finite. As cutting can only increase the resistance of the network, the resistance of the original network must also be finite. Thus the walk is transient when d = 3.

The method of applying shorting and cutting to get lower and upper bounds for the resistance of a resistive medium was introduced by Lord Rayleigh. (Rayleigh [31]; see also Maxwell [23], Jeans [12], Po"Iya and Szegb [30]). We will refer to Rayleigh's techniques collectively as Rayleigh's short‑cut method. This does not

5.9	SHORTING AND CUTTING 	97

do Rayleigh justice, for Rayleigh's method is a whole bag of tricks that goes beyond mere shorting and cutting‑but who can resist a pun?

Rayleigh's method was apparently first applied to random walks by C. St. J. A. Nash‑Williams [26], who used the shorting method to establish recurrence for random walks on the 2‑dimensional lattice.

CHAPTER 6

RAYLEIGH'S SHORT‑CUT METHOD

6.1 Shorting and Cutting

In its simplest form, Rayleigh's method involves modifying the network whose resistance we are interested in so as to get a simpler network. We consider two kinds of modifications, shorting and cutting. Cutting involves nothing more than clipping some of the branches of the network, or what is the same, simply deleting them from the network. Shorting involves connecting a given set of nodes together with perfectly conducting wires, so that current can pass freely be

Colycl.

Cut 	Short

Fi(;URE 6.1

99

100	RAYLEIGH'S SHMT‑CUT METHOD 	Ch. 6

tween them. In the resulting network, the nodes that were shorted together behave as if they were a single node.

6.2 The Shorting Law and the Cutting Law; Rayleigh's Idea

The usefulness of these two procedures (shorting and cutting) stems from the following observations:

SHORTING LAW. Shorting certain sets of nodes together can only decrease the effective resistance of the network between two given nodes.

CUTTING LAW. Cutting certain branches can only increase the effective resistance between two given nodes.

These laws are both equivalent to Rayleigh's Monotonicity Law, which was introduced in Chapter 4 of Part I (see Exercise 1):

MONOTONICITY LAW. The effective resistance between two given nodes is monotonic in the branch resistances.

Rayleigh's idea was to use the Shorting Law and the Cutting Law above to get lower and upper bounds for the resistance of a network. In Section 3 we apply this method to solve the recurrence problem for simple random walk in dimensions 2 and 3.

6.3	THE PLANE IS EASY 	101

EXERCISE

1. Show that the Shorting Law and the Cutting Law are both equivalent to the Monotonicity Law.

6.3 The Plane is Easy

When d ‑ 2, we apply the Shorting Law as follows: Short together nodes on squares about the origin, as shown in Figure 6.2. The network we obtain is equivalent to the network shown in Figure 6.3.

IGURE 6.2

1	2	3	n	n

	4	12	20	hit 1 4
	branches	branches	branches	branches

Fi(;URE 6.3

102	RAYLEIGH'S SHORT‑CUT METHOD 	Ch. 6

Now as n 1‑ohm resistors in parallel are equivalent to a single resistor of resistance 11n ohms, the modified network is equivalent to the network shown in Figure 6.4. The resistance of this network out to infinity is

co	I
E 		= 00

n=O 8n + 4

As the resistance of the old network can only be bigger, we conclude that it too must be infinite, so that the walk is recurrent when d = 2.

0				2		3	n	n
		ohm	I ohm	I ohm			ohm
	4		12		20		8n + 4

FIGURE6.4

EXERCISE

1. Using the shorting technique, give an upper bound for (3)

P escape and compare this with the exact value obtained in Exercise I of Section 5.7.

6.4 Space: Searching for a Residual Network

When d ‑ 3, what we want to do is delete certain of the branches of the network so as to leave behind a residual network having manifestly finite resistance. The problem is to reconcile the "manifestly" with the "finite." We want to cut out enough edges so that the effective resistance of what is left is easy to calculate, while leaving behind enough edges so that the result of the calculation is finite.

6.5	TREES ARE EASY TO ANALYZE 	103

6.5 Trees are Easy to Analyze

Trees‑that is, graphs without circuits‑are undoubtedly the easiest to work with. For instance, consider the full binary tree, shown in Figure 6.5. Notice that sitting inside this tree just above the root are two copies

etc.

R0()t

Fi(Amt, ().5

3rd generati(r)

2nd generatil(l)

Ist generatimi

Root

FIGURE 6.6

104	RAYLEIGH'S SHORT‑CUT METHOD 	Ch. 6

of the tree itself. This self‑similarity property can be used to compute the effective resistance R,,,, from the root out to infinity. (See Exercise 1.) It turns out that R co = 1. We will demonstrate this below by a more direct method.

To begin with, let us determine the effective resistance R , between the root and the set of nth generation branch points. To do this, we should ground the set of branch points, hook the root up to a I ‑volt battery, and compute

1

R11 = current through battery

For n = 3, the circuit that we would obtain is shown in Figure 6.7.

ground

I volt

FiGURE 6.7

In the resulting circuit, all branch points of the same generation are at the same voltage (by symmetry). Nothing happens when you short together nodes that are at the same potential. Thus shorting together branch points of the same generation will not affect the

6.5	TREES ARE EASY TO ANALYZE 	105

distribution of currents in the branches. In particular, this modification will not affect the current through the battery, and we conclude that

Rn	current in original	current in modified
	circuit 	circuit

For n = 3, the modified circuit is shown in Figure 6.8. This picture shows that R3 ‑ 1/2 + 1/4 + 1/8 ‑ I ‑ 1/23. More generally,

I	1	1 	1

R	+	+ ‑ ‑ I

11	2	4	211	2n

Letting n oo, we get

R,, ‑ lim R,, ‑ lim I ‑ I ‑ 1.

11‑M	/I ~ 00	2

	I	I	I
R	‑ I	‑ f

2	4 	8

I voll

~~F~

T__

ground

F1(;uHt; oJi

Figure 6.9 shows another closely related tree, the tree homogeneous of degree three: Note that all nodes of this tree are similar‑there is no intrinsic way to distinguish one from another. This tree is obviously a

106	RAYLEIGH'S SHORT‑CUT METHOD	Ch. 6

etc.		etc.
	etc.

The (rcc 11(111(gencous of degrec 3

FiGURE 6.9

close relative of the full binary tree. Its resistance to infinity is 2/3.

EXERCISE

1. (a) Show, using the self ‑similarity of the full binary tree, that the resistance R,,,, to infinity satisfies the equation

00 = R co + 1

2

and conclude that either R,,,, ‑ 1 or R 0,, ‑ oo.

(b) Again using the self ‑similarity of the tree, show that

R11+1 = R11 + 1
	2

where Rn denotes the resistance out to the set of the nth generation branch points. Conclude that Rc,,, limn‑‑*m R11 ‑ 1.

6.6 The Full Binary Tree is Too Big

Nothing could be nicer than the two trees we have just described. They are the prototypes of networks having

6.6	THE FULL BINARY TREE 	107

manifestly finite resistance to infinity. Unfortunately, we can't even come close to finding either of these trees as a subgraph of the three‑dimensional lattice. For in these trees, the number of nodes in a "ball" of radius r grows exponentially with r, whereas in a d‑dimensional

d

lattice, it grows like r , i.e., much slower. (See Figure 6.10.) There is simply no room for these trees in any finite‑ dimensional lattice.

Radius r	Nodes wl'thin r of origin

Full binary tree	Tree lioniogclleous
			Of degree 3
<
			4
	3	y

2

7

<~	>‑Z~

3

22

r	2r+ I ‑ i	3‑2r ‑ 2

FiGURE 6. 10

108	RAYLEIGH'S SHORT‑CUT METHOD 	Ch. 6

6.7 NT3: A "Three‑Dimensional" Tree

These observations suggest that we would do well to look for a nice tree NT3where the number of nodes within a radius r of the root is on the order of r 3 . For we might hope to find something resembling NT3 in the 3‑dimensional lattice, and if there is any justice in the world, this tree would have finite resistance to infinity, and we would be done.

Before introducing NT3,' let's have a look at NT2, our choice for the tree most likely to succeed in the 2‑dimensional lattice (see Figure 6.11). The idea behind NT2 is that, since a ball of radius r in the graph ought to contain something like r 2 points, a sphere of radius r ought to contain something like r points, so the number of points in a sphere should roughly dou

etc.

balls ‑ r 2 spheres ‑ r

NT2

FIGURE 6.11

6.7	NT3: A "THREE‑DIMENSIONAL" TREE 	109

ble when the radius of the sphere is doubled. For this reason, we make the branches of our tree split in two every time the distance from the origin is (roughly) doubled.

Similarly, in a 3‑dimensional tree, when we double the radius, the size of a sphere should roughly quadruple. Thus in NT3, we make the branches of our tree split in four where the branches of NT2 would have split in two. NT3 is shown in Figure 6.12. Obviously, NT3 is none to happy about being drawn in the plane.

etc.

NT3

FIGURE 6.12

110	RAYLEIGH'S SHORT‑CUT METHOD 	Ch. 6

6.8 NT3has Finite Resistance

To see if we're on the right track, let's work out the resistance of our new trees. These calculations are shown in Figures 6.13 and 6.14.

Rroot,oo(NT2)	R,.t,.	0

I ohm
	2 ohms
		4 ohms

00

I <oh

m	2 ohms~

Rrwi,	0

<	2,

	I ohm	4	8
		2 ohm
	resistors	resistors	4 ohm

resistors

R roo(,M	0	0 	‑4

1 ohm	I ohm	I ohm

2	2	2

I + I + I +

2	2 	2

00 1

Fi(;URE 6.13

6.9	DOES NT3 FIT?	ill

Rrmo..(NTI)

	4	16	64
	I ohm	2 ohm	4 ohm
	resistors	resistors 	resistors

R r(x)(. 0.	0	0	0	‑90 0 0

1 ohm	I ohm 	ohm

4	8	16

I + I + I +

4	8 	16

2

Fi 6 u R 1‑‑‑ 0. 14

As we would hope, the resistance of NT2 is infinite, but the resistance of NT3 is not.

EXERCISE

I ‑ Use self ‑similarity argunietits to compute the resistatice of NT2 and NT3.

6.9 But Does NT3Fit in the Three‑Dimensional Lattice?

We would like to embed NT3 in Z3. We start by trying to embed NT2 in Z2 . The result is shown in Figure 6.15.

112	RAYLEIGH'S SHORT‑CUT METHOD	Ch. 6

FIGURE 6. IS

To construct this picture, we start from the origin and draw 2 rays, one going north, one going east. Whenever a ray intersects the line x + y = 2" ‑1 for some n, it splits into 2 rays, one going north, and one going east. The sequence of pictures in Figure 6.16 shows successively larger portions of the graph, along with the corresponding portions of NT2

Of course this isn't really an embedding, since certain pairs of points that were distinct in NT2get identified, that is, they are made to correspond to a single point in the picture. In terms of our description, some

6.9	DOES NT3 FIT? 	113

times a ray going north and a ray going east pass through each other. This could have been avoided by allowing the rays to "bounce" instead of passing through each other, at the expense of embedding not NT2but a close relative‑see Exercise 3. However, because the points of each identified pair are at the same distance from the root of NT2, when we put a battery between the root and the nth level they will be at the same potential. Hence, the current flow is not affected by these identifications, so the identifications have no effect on REFF. For our purposes, then, we have done just as well as if we had actually embedded NT2

Fi(;URE 0. 16

114	RAYLEIGH'S SHORT‑CUT METHOD	Ch. 6

T~71

.vo

‑, r

Fic;URE 6.17

6.9	DOES NT3 FIT? 	115

To construct the analogous picture in three dimensions, we start three rays off from the origin going north, east, and up. Whenever a ray intersects the plane x + y + z ‑ 2 n ‑ 1 for some n, it splits into three rays, going north, east, and up. This process is illustrated in Figure 6.17.

Surprisingly, the subgraph of the 3‑dimensional lattice obtained in this way is not NT3 ! Rather, it represents an attempt to embed the tree shown in Figure 6.18.

‑‑‑‑‑‑‑‑‑‑‑‑‑‑

GE

NT2.5849 ...
	FIGURE 6.18

116	RAYLEIGH'S SHORT‑CUT METHOD 	Ch. 6

We call this tree NT2.5849. * ' because it is 2.5849. . . ‑dimensional in the sense that when you double the radius of a ball, the number of points in the ball gets multiplied roughly by 6 and

6 = 210926 = 2 2.5849....

Again, certain pairs of points of NT2.5849 ... have been allowed to correspond to the same point in the lattice, but once again the intersections have no effect on REFF.

So we haven't come up with our embedded NT3yet. But why bother? The resistance of NT2.5849... out to infinity is

1 +	2 +	4 +	1	+ 2 +	2 2 +
3	9	27	3	3	3

	3	2
		3

Thus we have found an infinite subgraph of the 3‑dimensional lattice having finite resistance out to infinity, and we are done.

EXERCISES

1. This exercise deals with the escape probability Pewape for simple random walk in 3 dimensions. The idea is to turn upper and lower bounds for the resistance of the lattice into bounds for P escape ‑ Bounds are the best we can ask for using our method. The determination of the exact value will be discussed in Section 7.5. It is roughly .66.

6.10	WHAT WE HAVE DONE 	117

(a) Use a shorting argument to get an upper bound for Pescape ‑

(b) We have seen that the resistance of the 3‑dimensional lattice is at most one ohm. Show that the corresponding lower bound for P ... ape is 1/6. Show that this lower bound can be increased to 1/3 with no extra effort.

2. Prove that simple random walk in any dimension d > 3 is transient.

3. Show how the not‑quite embeddings of NT2 and NT2.5849... can be altered to yield honest‑to‑goodness embeddings of "stretched ‑out" versions of these trees, obtained by replacing each edge of the tree by 3 edges in series. (Hint: "bounce.")

6.10 What We Have Done; What We Will Do

We have finally finished our electrical proof of P61ya's theorem. The proof of recurrence for d = 1, 2 was straight‑ forward, but this could hardly be said of the proof for d = 3. After all, we started out trying to embed NT3 and ended up by not quite embedding something that was not quite NT.3!

This is not bad in itself, for one frequently sets Out to do something and in the process of trying to do it gets a better idea. The real problem is that this explicit construction is just too clever, too artificial. We seem to be saying that a simple random walk in 3 dimensions is transient because Z' happens to contain a beautifully symmetrical SUbgraph that is in some sense 2.5849 ‑ ‑ ‑ ‑ dimensional! Fine, but what if we hadn't Stumbled upon this subgraph? Isn't there some other, more natural way?

We will see that indeed there are more natural approaches to showing transience for d ‑ 3. One such

118	RAYLEIGH'S SHORT‑CUT METHOD 	Ch. 6

approach uses the same idea of embedding trees, but depends on the observation that one doesn't need to be too careful about sending edges to edges. Another approach, based on relating the lattice not to a tree but to Euclidean space, was already hinted at in Section 5.8. The main goal for the rest of this book will be to explore these more natural electrical approaches to P61ya's theorem.

Before jumping into this, however, we are going to go back and take a look at a classical‑i.e., probabilistic‑approach to Po"Iya's theorem. This will give us something to compare our electrical proofs with.

CHAPTER 7

THE C.LASSICAL PROOFS
OF POLYA'S THEOREM

7.1 Recurrence is Equivalent to an Infinite Expected Number of Returns

In this chapter, all of our random walks will be simple. Let u be the probability that a random walker, starting at the origin, will return to the origin. The probability that the walker will be there exactly k times (counting the initial time) is u"(1 ‑ u). Thus, if nz is the expected number of times at the origin,

cc

r, ku"(1 ‑ u)

k ~‑ I

If in = oo then u 1, and hence the walk is recurrent. If nz < oo then u < 1, so the walk is transient. Thus m determines the type of the walk.

We shall use an alternate expression for m. Let u,, be the probability that the walk, starting at 0, is at 0 on the nth step. Since the walker starts at 0, lio ‑ 1. Let en be a random variable that takes on the value I if, at time n, the walker is at 0 and 0 otherwise. Then

119

120	CLASSICAL PROOFS OF P6LYA'S THEOREM	Ch. 7

00

T = E e,,

n=O

is the total number of times at 0 and

00

M __ E(T)	E E(ej.

11=0

But E(e,,) = 1 ‑ u,, + 0 ‑ (1 ‑ uj = u, Thus

00

M	E	U111
	11=Z0

Therefore, the walk will be recurrent if the series E000 u,, diverges and transient if it converges.

n =

EXERCISE

1. Let NXY be the expected number of visits to y for a random walker starting in x. Show that NXY is finite if and only if the walk is transient.

7.2 Simple Random Walk in One Dimension

Consider a random walker in one dimension, started at 0. To return to 0, the walker must take the same number of steps to the right as to the left; hence, only even times are possible. Let us computeU2,, ‑ Any path that returns in 2n steps has probability 1/2"'. The number of possible paths equals the number of ways that we can choose the n times to go right from the 2n possible times. Thus

U 2n	2n 	1

(n ) 2 2n

7.2	RANDOM WALK IN ONE DIMENSION 	121

We shall show that En U2n ‑ oo by using Stirling's approximation:

n

		n! ‑ N[2‑7‑rn e‑"n
Thus
	(2 n)! I 	~i_2_~_2n e ‑ 2n (2n )2n

U2n	n1n! 2 2n 	(,12 _7r n e ‑n n n)2 2 2n

‑ ~,, 1 ‑7 _rn‑ '

Therefore,

U 2n 	00

ti `\/ 7T‑n

and a simple random walk in one dimension is recurrent.

Recall that this case was trivial by the resistor argument.

EXERCISES

1. We showed in Part I that a random walker starting at x with 0 < x < N has probability x1N of reaching N before 0. Use this to show that a simple random walk in one dimenSion is recurrent.

2. Consider a random walk in one dimension that moves from n to n + I with probability p and to n ‑ I with probability q ‑ I ‑ p. Assume that p > 1/2. Let hx be the probability, starting at x, that the walker ever reaches 0. Use Exercise I of Section 1.6 in Part I to show that hX = (qlp)x for x >, 0 and ‑ I for x < 0. Show that this walk is transient.

3. For a simple random walk in one dimension, it follows from Exercise 4 of Section 1.5 in Part I that the expected

122	CLASSICAL PROOFS OF PbLYA'S THEOREM	Ch. 7

time, for a walker starting at x with 0 < x < N, to reach 0 or N is x(N ‑ x). Prove that for the infinite walk, the expected time to return to 0 is infinite.

4. Let us regard a simple random walk in one dimension as the fortune of a player in a penny matching game where the players have unlimited credit. Show that the result is a martingale (see Part 1, Section 1.6). Show that you can describe a stopping system that guarantees that you make money.

7.3 Simple Random Walk in Two Dimensions

For a random walker in two dimensions to return to the origin, the walker must have gone the same number of times north and south and the same number of times east and west. Hence, again, only even times for return are possible. Every path that returns in 2n steps has probability 1/4 2n . The number of paths that do this by taking k steps to the north, k south, n ‑k east and n ‑ k west is

2n	2n!

(k, k, n k, n ‑ k) k! k! (n k)! (n ‑ k)!

Thus

(20!

U2n	f ‑2t T E
	4 k = o k! k! (n ‑ k)! (n	k)!

1 n (20! 	n!n!

42n E

k=O tz!n! k!k!(n ‑ k)!(n ‑ k)!

1 ~2n~ /10 (n)2

‑4Tn‑ ~ n ) E

k = k

But En=0 (n)2 = (2n) (see Exercise 1). Hence
	k	k 	n

1 (2n))2

U2n	(2 2t' n

7.4	RANDOM WALK IN THREE DIMENSIONS 	123

This is just the square of the one dimension result (not by accident, either‑see Section 7.6). Thus we have

1

M	U 2n	E	= 00.

n	117rn

Recall that the resistor argument was very simple in this case also.

EXERCISE

n)2 = (2n).

1. Show that E'k=o (k	n (Hint: Think of choosing

n balls from a box that has 2n balls, n black and n white.)

7.4 Simple Random Walk in Three Dimensions

For a walker in three dimensions to return, the walker must take an equal number of steps in the three different directions. Thus we have

U2n = 	E

62n 1',k J! P k! k! (n	0! (n 	k)!

where the sum is taken over all.i, k withJ + k	n.

Following Feller [5], we rewrite this sum as

U 2n ‑ I 2n F, ( I	n! 	2

22n ( 11 i,k 3n J I k! (n ‑ J ‑ k)! )

Now consider placing n balls randomly into three boxes, A, B, C. The probability thatj balls fall in A, k in B, and n ‑j ‑ kin Cis

I rz	n 	n

3 J, k, n ‑j ‑ k	3 r, j! k! (n ‑ j ‑ k)!

Intuitively, this probability is largest whenj, k, and n ‑ j ‑ k are as near as possible to n 13, and this can

124	CLASSICAL PROOFS OF P6LYA'S THEOREM	Ch. 7

be proved (see Exercise 1). Hence, replacing one of the factors in the square by this larger value, we have:

U 2n ~<

1	2n	1 	n!

n ) 3 11 [n [n [n]	1,k3n j! k! (n 	k)!

3 3‑* 3 *

Where [n13] denotes the greatest integer <nl3. The last sum is 1 since it is the sum of all probabilities for the outcomes of putting n balls into 3 boxes. Thus

U 2n <1 1 (2n) 1 n!

221,	n	3n [,1 3

3

Applying Stirling's approximation yields

	K
U2n <1 ‑
	n312

for suitable constant K. Therefore

1

M	U2n <, K	‑3/2 < 00
		n

and a simple random walk in three dimensions is recurrent.

While this is a complex calculation, the resistor argument was also complicated in this case. We will try to make amends for this presently.

EXERCISES

1. Prove that Gk,n "'‑k)is largest whenj, k, and n ‑j ‑ k are as close as possible to n13.

7.5	PROBABILITY OF RETURN 	125

2. Find an appropriate value for the "suitable constant" K that was mentioned above, and derive an upper bound for m. Use this to get a lower bound for the probability of escape for simple random walk in three dimensions.

7.5 The Probability of Return in Three Dimensions: Exact Calculations

Since the probability of return in three dimensions is less than one, it is natural to ask, "What is this probability? " For this we need an exact calculation. The first such calculation was carried out in a pioneering paper of McCrea and Whipple [24]. The solution outlined here follows Feller [5], Exercise 28, Chapter 9, and Montroll and West [25].

Let p(a, b, c; n) be the probability that a random walker, starting at 0, is at (a, b, c) after n steps. Then p(a, b, c; n) is completely determined by the fact that

P (0, 0, 0; 0) ‑

and

p (a, b, c; n)

I		I
‑ p(a ‑ 1, b, c; n	+ ‑ p(a + 1, b, c; n ‑ 1)
6		6

• _p(a, b ‑ 1, c; n ‑ 1) + _p(a, b + 1, c; n ‑ 1)
	6 	6

1 	1

• _p(a, b, c ‑ 1; n ‑ 1) + _p(a, b, c + 1; n
	6 	6

Using the technique of generating functions, it is possible to derive a solution of these equations as

126	CLASSICAL PROOFS OFP6LYA'S THEOREM	Ch. 7

p (a, b, c; n) ‑_ 1 .
	(2 70 3

?r 7r ~ r 7r '~ r 7. COS (X) + COS (Y) + cos(z) 3

cos (xa) cos (yb) cos (zc)dxdydz.

Of course, we can just verify that this formula satisfies our equations once someone has suggested it. Having this formula, we put a = b = c = 0 and sum over n to obtain the expected number of returns as

3 M = _.

(27r)3

7 7 ~ T 7r ~ Ir	dxdydz.

7r Q ‑ (cos x + cosy + cos z))

This integral was first evaluated by Watson [37] in terms of elliptic integrals, which are tabulated. A simpler result was obtained by Glasser and Zucker [9] who evaluated this integral in terms of gamma functions. Using this result, we get

1	7

M	‑IF

3273 (24	2‑4

1.516386059137 ...

where ]P(x) is Euler's gamma function, r(x) ‑

100 e‑t'‑'dt. (Incidentally, the value given by Glasser

0
and Zucker [9] for the integral above needs to be cor
rected by multiplying by a factor of 1/(3847r).

Recall that m 1/(1 ‑ u) so that u = (ni ‑ 1)1m. This gives

U	.340537329544 

7.6	RANDOM WALK IN TWO DIMENSIONS 	127

7.6 Simple Random Walk in Two Dimensions is the Same as Two Independent One‑Dimensional Random Walks

We observed that the probability of return at time 2n in two dimensions is the square of the corresponding probability in one dimension. Thus it is the same as the probability that two independent walkers, one walking in the x direction and the other in they direction, will, at time 2n, both be at (0, 0). Can we see that this should be the case? The answer is yes. Just change our axes by 45 degrees to new axes X‑ and y as in Figure 7. 1.

Y

Y

FiGURE 7.1

Look at the possible OUtconies for the first step using the x, y coordinates and the X, ‑11 coordinates. We have

X~ y coordinates X9 y coordinates

(09 1)
(01 ‑1)
(1,0)

128	CLASSICAL PROOFS OFP6LYA'S THEOREM	Ch. 7

Assume that we have two independent walkers, one moving with step size 1 1‑~f2_ randomly along the XY axis and the other moving with the same step size along the Y axis. Then, if we plot their positions using the X, Y axes, the possible outcomes for the first step would agree with those given for the ‑above X‑,.~ coordinates. The probabilities for each pair of outcomes would also be (0/2)) ‑ (0/2)) ‑ 1/4. Thus, we cannot distinguish a simple random walk in two dimensions from two independent walkers along the X‑ andy axes making steps of magnitude 1/‑~_2_. Since this probability of return does not depend upon the magnitude of the steps, the probability that our two independent walkers are at (0, 0) at time 2n is equal to the product of the probabilities that each separately is at 0 at time 2n, namely (1/22n )( 2n ). Therefore, the probability that the stan2n )(2n))2

dard walk will be at (0, 0) at time 21l is ((1/2	as
observed earlier.

7.7 Simple Random Walk in Three Dimensions is Not The Same as Three Independent Random Walks

In three dimensions, the probability that three independent walkers are each back to 0 after time 2n is

‑ ((2n) 1 1 .

V2n ‑	_f 2 ‑n /

This does not agree with our result for a simple random walk in three dimensions. Hence, the same trick cannot work. However, it is interesting to consider a random walk which is the result of three independent walkers. Let (ij, k) be the position of three indepen

7.7	RANDOM WALK IN THREE DIMENSIONS 	129

dent random walkers. The next position is one of the eight possibilities

(i + 1 j + 1, k + 1), (i + 1,j + 1, k ‑ 1)9 (i + 1 9 j 19 k + 1), (i + 1, j 1, k ‑ 1), (i ‑ 1,j + 19 k + 1), U ‑ 1 9 j + 1, k ‑ 1), (i ‑ 1~j ‑ 11 k + 09 U ‑ 1,j ‑ 1, k ‑ 1). Thus we may regard their progress as a random walk on the lattice points in three dimensions. If we center a cube of side 2 at (i, j, k), then the walk moves with equal probabilities to each of the eight corners of the cube. It is easier to show that this random walk is transient (using classical methods) than it is for simple random walk. This is because we can again use the onedimension calculation. The probability V 2n for return

at time 2n is

2n

V2n	2n

21	1

_V1 7

Thus

M =	( 1 )3/2 < 00
	E V 2,, ‑ E ‑

it	11 	711

and the walk is transient.

The fact that this three independent walkers model and simple random walk are of the same type suggests

130	CLASSICAL PROOFS OF POLYA'S THEOREM	Ch. 7

that when two random walks are "really about the same," they should either both be transient or both be recurrent. In the next section we will see that this is indeed the case. Thus we may infer the transience of simple random walk in 3 dimensions from the transience of the three independent walkers model without going through the involved calculation of Section 7.4.

CHAPTER 8

RANDOM WALKS ON MORE
GENERAL INFINITE NETWORKS

8.1 Random Walks on Infinite Networks

From now on we assume that G is an infinite connected
graph. We assume that it is of bounded degree, by
which we mean that there is some integer E such that
the number of edges from any point is at most E. We
assign to each edge xy of G a conductance C, > 0 with
resistance RX 'V I /Cxy, The graph G together with the
conductances C = (CXV) is called a network and de
noted by (G, Q. Given a network (G, Q, we define a
random walk by

PXV ‑ C‑V

Cx

where Cx ‑ EY Cx V. When all the conductances are equal, we obtain a random walk that moves along each edge with the same probability: In agreement with our previous terminology, we call this walk simple random walk on G.

We have now a quite general class of infinite state Markov chains. As in the case of finite networks, the chains are reversible Markov chains: That is, there is a positive vector w such that wxPxy ‑ WYPYx. As in the 131

132	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

finite case, we can take w_, = C, since CPxy ‑ C‑V
CYX ‑ CY PYX ‑

8.2 The Type Problem

Let (G, Q be an infinite network with random walk P. Let 0 be a reference point. Let p,,,p, be the probability that a walk starting at 0 will never return to 0. If Pescape = 0 we say that P is recurrent, andifPmap, >0 we say that it is transient. You are asked to show in Exercise 1 that the question of recurrence or transience of P does not depend upon the choice of the reference point. The type problem is the problem of determining if a random walk (network) is recurrent or transient.

In Section 5.5 we showed how to rephrase the type problem for a lattice in terms of finite graphs sitting inside it. In Section 5.6 we showed that the type problem is equivalent to an electrical network problem by showing that simple random walk on a lattice is recurrent if and only if the lattice has infinite resistance to infinity. The same arguments apply with only minor modifications to the more general infinite networks as well. This means that we can use Rayleigh's short‑cut method to determine the type of these more general networks.

EXERCISE

1. Show that the question of recurrence or transience of P does not depend upon the choice of the reference point.

8.3 Comparing Two Networks

Given two sets of conductances C and C on G, we say that (G, Q < (G, Q if C‑,y < Cxy for all xy, or equiva

8.3	COMPARING TWO NETWORKS 	133

lently, if R,.y >, R, for all xy. Assume that (G,

(G, Q. Then by the Monotonicity Law, REFF> REFF. Thus if random walk on (G, Q is transient, i.e., if REFF< co, then random walk on (G, Q is also transient. If random walk on (G, Q is recurrent, i.e., if REFF= oo, then random walk on (G, Q is also recurrent.

THEOREM. If (G, Q and (G, C') are networks, and if there exist constants u, v with 0 < u <, v < oo such that

ucxy <_ C~ <1 VCXY

for all x and y, then random walk on (G, C') is of the same type as random walk on (G, Q.

P~f‑	and Y,,y = vCx,,,. Then

roo	Let UX,'V 	u CX'_V

(G, U) <, (G, C) <_ (GI V). But the random walks for (G, U) and (G, V) are the same as random walk on (G, Q. Thus random walk for (G, C') is of the same type as random walk on (G, Q.

COROLLARY. Let (G, Q be a network. ~ffor every edgex‑y of G we have 0 < u < Cxv < v < oofor some constants u and v, then the random walk on (G, Q has the same type as simple random walk on G.

EXERCISES

I . Consider the two‑dimensional lattice. For each edge, we toss a coin to decide what kind of resistor to put across this edge. If heads turns up, we put a two‑ohm resistor across this edge; if tails turns up, we put a one‑ohm resistor across the edge. Show that the random walk on the resulting network is recurrent.

2. Consider the analogous problem in 3 dimensions.

134	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

8.4 The k‑Fuzz of a Graph

For any integer k, the k‑fuzz of a graph G is the graph Gkobtained from G by adding an edge xy if it is possible, to go from x to y in at most k steps. For example, the 2‑fuzz of the two‑dimensional lattice is shown in Figure 8. 1; please note that horizontal and vertical edges of length 2, such as those joining (0, 0) to (0, 2), have not been indicated.

X X

X~Xx
XX><D<

FIGURF_ 8.1

THEOREM. Simple random walk on G and on the k‑fuzz Gkof G have the same type.

‑ Proof. Let P be simple random walk on G. Define p = (p + p2 + . .. + P')Ik. Then P may be considered to be P, watched at one of the first k steps chosen at random, then at a time chosen at random from the next k steps after this time, etc. Thinking of P in this way, we see that P is in state 0 at least once for every time P in state 0. Hence, if P is recurrent so is P. Assume now that P is transient. Choose a finite set E so that 0 cannot be reached in k steps from a point outside of E. Then, since the walk P will be outside E from some time on, the walk P cannot be at 0 after this time,

8.4	THE K‑FUZZ OF A GRAPH 	135

and P is also transient. Therefore, P and P are of the same type.

Finally, we show that P has the same type as simple random walk on Gk . Here it is important to remember our restriction that G is of bounded degree, so that for some E no vertex has degree >E. We know that P is reversible with wP ‑ w where wX is the number of edges coming out of x. From its construction, P is also reversible and wp = w. P is the random walk on a net

work (Gk, Q with CXY ‑ WXP‑'CY' if PXY > 0, there is a path x, X1, X2, ‑ ‑ ‑, Xnz‑1 ~ y in G from x toy of length rn < k. Then PXY ~>, (Ilk)(11E)"' >, (11k)(IIE)k . )Ek <

Thus 0 < (Ilk	XV <, I a n d ( I / k)E' <, Cxv <, E.
Therefore, by the theorem on the irrelevance of
bounded twiddling proven in Section 8.3, P and simple
random walk on Gk are of the same type. So G and Gk
are of the same type.

NOTE: This is the only place where we use probabilistic methods of proof. For the purist who wishes to avoid probabilistic methods, Exercise 2 of Section 8.6 indicates an alternative electrical proof.

We show how this theorem can be used. We say that a graph G can be embedded in a graph G if the points x of G can be made to correspond in a one‑to‑one fashion to points X‑ of G in Such a way that if xy is an edge in G, then X‑y" is an edge in G.

THEOREM. If simple random walk on G is transient, and if G can be embedded in a k‑fuzz Gk QfGj then simple random walk on G is also transient. Simple random walk on G and G are oj'the same type if each graph can be embedded in a k‑JUzz of the other graph.

136	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

Proof. Assume that simple random walk on G is transient and that G can be embedded in a k‑fuzz Gk of G. Since REFFfor G is finite and G can be embedded in Gk, REFFfor Gk is finite. By our previous theorem, the same is true for G and simple random walk on G is transient.

If we can embed G in Gkand G in Gk, then the random walk on G is transient if and only if the random walk on G is.

EXERCISE

1. We have assumed that there is a bound E for the number of edges coming out of any point. Show that if we do not assume this, it is not necessarily true that G and Gk are of the same type. (Hint: Consider a network something like that shown in Figure 8.2.)

~AL :%VA

I

Fi(;URE h.2

8.5 Comparing General Graphs with Lattice Graphs

We know the type of simple random walk on a lattice Z'. Thus to determine the type of simple random walk on an arbitrary graph G, it is natural to try to compare G with Z'. This is feasible for graphs that can be drawn in some Euclidean space R' in a civilized manner.

DEFINITION. A graph G can be drawn in a Euclidean space R' in a civilized manner if its vertices can be embedded in R d so that for some r < oo, s > 0,

(a) The length of each edge is <, r.

8.5	COMPARING GRAPHS 	137

(b) The distance between any two points is >s.

Note that we make no requirement about being able to draw the edges of G so they don't intersect.

THEOREM. If a graph can be drawn in R d in a civilized manner, then it can be embedded in a k fuzz of the lattice Zd.

Proof. We carry out the proof for the case d ‑ 2. Assume that G can be drawn in a civilized manner in R'. We want to show that G can be embedded in a kfuzz Of Z2. We have been thinking of Z2 as being drawn in R 2 with perpendicular lines and adjacent points a unit distance apart on these lines, but this embedding is only one particular way of representing Z2 . To emphasize this, let's talk about L 2 instead of Z2 . Figure 8.3 shows another way of drawing L2 in R 2 . From a graph ‑theoretical point of view, this is the same as Z2. 2

In trying to compare G to L , we take advantage of this flexibility by drawing L 2 so small that points of G can be moved onto points of L 2 without bumping into each other.

Fic;URE 8.3

138	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

Specifically, letL 2 be a two‑dimensional rectangular lattice with lines a distance s12 apart. In any square of L 2 , there is at most one point of G. Move each point x of G to the southwest corner XY of the square that it is in, as illustrated in Figure 8.4.

Fic,URE 8.4

Now since any two adjacent points x, y in G were within r of each other in R 2 , the corresponding points X~ y in L 2 will have Euclidean distance <r + 2s. Choose k so that any two points of L 2 whose Euclidean distance is < r + 2s can be connected by a path in L 2 of at most k steps. Then X‑ and ‑ will be adjacent in L 2

y 	k

and‑since the prescription for k does not depend on x
	2

and y‑we have embedded G in the k‑fuzz Lk

COROLLARY. If G can be drawn in a civilized manner in R' or R 2 , then simple random walk on G is recurrent.

Proof. Assume, for example, that G can be drawn in a civilized manner in R 2 . Then G can be embedded

8.5	COMPARING GRAPHS 	139

in a k‑fuzz Z' of Z'. If simple random walk on G were

k

transient, then the same would be true for Z' and Z'.

k

But we know that simple random walk on Z' is recurrent. Thus simple random walk on G is recurrent.

Our first proof that random walk in three dimensions is transient consisted in showing that we could embed a transient tree in Z3. We now know that it would have been sufficient to show how to draw a transient tree in R 3 in a civilized manner: This is easier (see Exercise 1).

The corollary implies that simple random walk on any sufficiently symmetrical graph in R' is recurrent. For example, simple random walk on the regular graph made up of hexagons shown in Figure 8.5 is recurrent.

FIGURE 8.5

We can even consider very irregular graphs. For example, on the cover of the January 1977 Scientific American, there is an example due to Conway of an infinite non‑periodic tiling using Penrose tiles of the form shown in Figure 8.6. It is called the cartwheel

140	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

pattern; part of it is shown in Figure 8.7. A walker walking randomly on the edges of this very irregular infinite tiling will still return to his starting point.

Z~~	41~

FIGURE 8.6

FIGURE 8.7

Assume now that G can be drawn in a civilized manner in R'. Then to show that simple random walk on G is of the same type as Z', namely transient, it is sufficient to show that we can embed Z' in a k‑fuzz of G. This is clearly possible for any regular lattice in R' * The three lattices that have been most studied and for which exact probabilities for return have been found are called the SC, BCC, and FCC lattices. The SC

8.5	COMPARING GRAPHS 	141

(simple cubic) lattice is just Z'. The walker moves each time to a new point by adding a random choice from the six vectors ( ± 1 9 0, 0), (0, ± 1, 0), (0, 0, ± 1). For the BCC (body centered cubic) lattice, the choice is one of the eight vectors (± 1, ± 1, ± 1). This was the walk that resulted from three independent one‑dimensional walkers. For the FCC (face centered cubic) lattice, the random choice is made from the twelve vectors (±1, ± 1, 0), (± 1, 0, ± 1), (09 ± 1 9 ± 1). For a discussion of exact calculations for these three lattices, see Montroll and West [25].

As we have seen, once the transience of any one of these three walks is established, no calculations are necessary to determine that the other walks are transient also. Thus we have yet another way of establishing P61ya's theorem in three dimensions: Simply verify transience of the walk on the BCC lattice via the simple three independent walkers computation, and infer that walk on the SC lattice is also transient since the BCC lattice can be embedded in a k‑fuzz of it.

EXERCISES

I ‑ When we first Set OU t to prove Po'lya's theorem for tl = 3 way back in Section 3.2, our idea was to embed NT.3 in Z3. As it turned out, what we ended LIP embedding was not NT3 but NT 5849..., and we didn't quite embed it at that. We

2., tried to improve the situation by finding (in Exercise 3 of Section 6.9) an ho nest‑ to‑good ness embedding of a relative of NT2.5849. .. , but NT3was still left completely out in the cold. Now, however, we are in a position to embed NT3, if not in Z3 then at least in a k‑fuzz of it. All we need to do is to draw NT3 in R 3 in a civilized manner. Described how to do this, and thereby give one more proof of Po'lya's theorem for d = 3.

142	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

2. Find a graph that can be embedded in a civilized manner in R 3 but not in R 2 , but is nonetheless recurrent.

3. Assume that G is drawn in a civilized manner in R 3 . To show that simple random walk on G is transient, it is enough to know that Z3 can be embedded in a k‑fuzz of G. Try to come up with a nice condition that will guarantee that this is possible. Can you make this condition simple, yet general enough so that it will settle all reasonably interesting cases? In other words, can you make the condition nice enough to allow us to remember only the condition, and forget about the general method lying behind it?

8.6 Solving the Type Problem by Flows‑a Variant of the Cutting Method

In this section we will introduce a variant of the cutting method whereby we use Thomson's Principle directly to estimate the effective resistance of a conductor.

Thomson's Principle says that, given any unit flow through a resistive medium, the dissipation rate of that flow gives an upper bound for the effective resistance of the medium. This suggests that to show that a given infinite network is transient, it should be enough to produce a unit flow out to infinity having finite energy dissipation.

In analogy with the finite case, we say that j is a flow from 0 to infinity if

(a) j, = ‑jyx

(b)	E jxy ‑ 0	x # 0.
	Y

We definejo = Eyjoy. If jo = 1, we say that j is a unit flow to infinity. Again in analogy with the finite case, we call (1/2) Exy j2 R the energy dissipation of the

XY	XY

flowjxy.

8.6	FLOWS‑A VARIANT OF CUTTING METHOD 	143

THEOREM. The effective resistance REFFfrom 0 to infinity is less than the energy dissipation of any other unitflowfrom 0 to infinity.

Proo	Assume that we have a unit flow j from 0 to

	~f
infinity with energy dissipation E ‑ (1/2) E Yj2 RXY,
		x xy

We claim that REFF,< E. Restrictingjxy to the edges of the finite graph G(r), we have a unit flow from 0 to S(r) in G(r). Let i(r) be the unit current flow in G(r) from 0 to S("). By the results of Section 3.5 of Part 1,

R (r) = 1 E (i (r) ) 2 R

EFF	2 G(r) 'Y 	XY

<,	I E j2 RxV
	2 G(r) XY ‑

< I 	j2 RxV ‑ El

2	Xy

whereEG(r) is short for

	X J, (f (;(r)
xy an edge

EXERCISES

I ‑ We have billed the method of using Thomson's Principle directly to estimate the effective resistances of a network as a variant of the cutting method. Since tile cutting method was derived from Thomson's Principle, and not vice versa, it would seem that we have got the cart before the horse. Set this straight by giving an informal ("heuristic") derivation of Thomson's Principle from the cutting method. (Hint: see Maxwell [23], Chapter V111, Paragraph 307.) For more on this question, see Onsager [27].

2. Let G be an infinite network and Gk the network obtained from the k‑fuzz of G. Using electric network argu

144	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

ments, show that REFF < oo for G if and on ly if REFF <
oo for Gk ‑ 	1

8.7 A Proof, Using Flows, that Simple Random Walk in Three Dimensions is Transient

We now apply this form of the cutting method to give another proof that simple random walk on the threedimensional lattice is transient. All we need is a flow to infinity with finite dissipation. The flow we are going to describe is not the first flow one would think of. In case you are curious, the flow described here was constructed as a side effect of an unsuccessful attempt to derive the isoperimetric inequality (see Po"Iya [29]) from the "max‑flow min‑cut" theorem (Ford and Fulkerson [7]). The idea is to find a flow in the positive orthant having the property that the same amount flows through all points at the same distance from 0.

Again, it is easiest to show the construction for the two‑dimensional case. Let G denote the part of Z2 lying in the first quadrant. The graph G(') is shown in Figure 8.8.

FIGURE 8.8

We choose our flow so that it always goes away from 0. Into each point that is not on either axis there are two flows, one vertical and one horizontal. We want

8.7	A PROOF USING FLOWS 	145

the sum of the corresponding values of j, to be the same for all points the same distance from 0. These conditions completely determine the flow. The flow out of the point x, y with x + y = n is as shown in Figure 8.9. The values for the currents out to the fourth level are shown in Figure 8.10.

Y + I

(n + 2)(n +

	x +
(n + ‑2)(n + 1)

FIGURE 8.9

4

20 t

12 t 20 .3

20 t

t I t 2) t

0	2		2(
		12 		20

2

2 t t t t

6	12	20

‑‑‑4w 	‑‑‑400

	2	.3	4
2	0	12	20

FIGURE 8. 10

146	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

in general, the flow out of a point (x, y) with x + y n is

x +	+ 	Y + 1

(n + 2) (n + 1)	~n_+ 2) (n + 1)	n + 1

and the flow into this point is

‑ x	+ 	Y

n(n +	n (n + 1)	n + I

Thus the net flow at (x, y) is 0. The flow out of 0 is (1/2) + (1/2) ‑ 1. For this two‑dimensional flow, the energy dissipation is infinite as it would have to be. For three dimensions, the uniform flow is defined as follows: out of (x, y, z) with x + y + z ‑ n we have the flow indicated in Figure 8.11. The total flow out of

(x, y, z) is then

	2(x + 1)	+	2(y + 1)
	(n + 3) (n + 2) (n + 1)		(n + 3) (n + 2) (n + 1)
		+	2(z + 1)
			(n + 3) (n + 2) (n + 1)
			2
		(n + 2) (n + 1)

2(z + 1)	t

(it + 3)(n + 2)(n ‑f 1)

	2(y + 1)
Z~~n + 3)(n + 2)(n + 1)

	2(x + 1)
(it + 3)(n + 2)(n + 1)

FIGURE 8.11

8.8	THE END 	147

The flow into (x, y, z) comes from the points (x ‑ 1, y, z), (x, Y ‑ 1, z), (x, y, z ‑ 1) and, hence, the total flow into (x, Y, Z) is

2x	+	2y

(n + 2) (n + On		(n + 2) (n + On
	+	2z

(n + 2) (n + On

2

(n + 2)(n + 1)

Thus the net flow for (x, y, z) is 0. The flow out of 0 is (113) + (1/3) + (113) ‑ 1. We have now to check finiteness of energy dissipation. The flows coming out of the edges at the nth level are all < 21(n + 1)2. There are (n + 1)(n + 2)/2 points a distance n from 0, and thus there are (3/2)(n + Mn + 2) < 3(n + 1)2 edges coming out of the nth level. Thus the energy dissipation E has

E ‑<, E 3 (n + 11 )2	2	)2 ‑ 12
	n	(11 + 1)2		n (n + 1) 2 < 00

and the random walk is transient.

8.8 The End

We have come to the end of our labors, and it seems fitting to look back and try to say what it is we have learned.

To begin with, we have seen how phrasing certain mathematical questions in physical terms allows us to draw on a large body of physical lore, in the form of established methods and ways of thought, and thereby often leads us to the answers to those questions.

148	RANDOM WALKS ON INFINITE NETWORKS 	Ch. 8

In particular, we have seen the utility of considerations involving energy. In took hundreds of years for the concept of energy to emerge and take its rightful place in physical theory, but it is now recognized as perhaps the most fundamental concept in all of physics. By phrasing our probabilistic problems in physical terms, we were naturally led to considerations of energy, and these considerations showed us the way through the difficulties of our problems.

As for P(o1ya's theorem and the type problem in general, we have picked up a bag of tricks, known collectively as "Rayleigh's short‑cut method," which we may expect will allow us to determine the type of almost any random walk we are likely to embark on. In the process, we have gotten some feeling for the connection between the dimensionality of a random walk and its type. Furthermore, we have settled one of the main questions likely to occur to someone encountering Po"Iya's theorem, namely: "If two walks look essentially the same, and if one has been shown to be transient, must not the other also be transient?"

Another question likely to occur to someone contemplating Po'lya's theorem is the question raised in Section 5.8: "Since the lattice Z' is in some sense a discrete analog of a resistive medium filling all of R', should it not be possible to go quickly and naturally from the trivial computation of the resistance to infinity of the continuous medium to a proof of Po"Iya's theorem? " Our shorting argument allowed us to do this in the two‑dimensional case; that leaves the case of three (or more) dimensions. Again, it is considerations of energy that allow us to make this connection. The trick is to start with the flow field that one gets by solving the continuous problem, and adapt it to the lattice, so as to get a lattice flow to infinity having finite dissipation

8.8	THE END 	149

rate. We leave the working out of this as an exercise, so as not to rob readers of the fun of doing it for themselves.

EXERCISE

1. Give one final proof of PO'lya's theorem in 3 dimensions by showing how to adapt the 1 Ir 2 radial flow field to the lattice. (Hint: "cubes. ")

REFERENCES	151

REFERENCES

1. Abbott, Edwin, Flatland, Little, Brown and Company, Boston, 1899.

2. BollobAs, B., Graph Theory: An Introductory Course, Springer‑ Verlag, New York, 1979.

3. Courant, R., K. Friedrichs, and H. Lewy, Uber die partiellen Differenzengleichungen der mathernatischen Physik, Math. Ann., 100 (1928), 32‑74. Translation: On the Partial Difference Equations of Mathematical Physics, IBM J. Research and Development, 11 (1967), 215‑237.

4. Doob, J. L., Stochastic Processes, John Wiley & Sons, New York, 1953.

5. Feller, William, An Introduction to Probability Theory and Its Applications, Vol 1, 3rd edition, John Wiley & Sons, New York, 1968.

6. Feynman, Richard, The Feynman Lectures on Physics, Addison‑Wesley, Reading, Mass, 1964.

7. Ford, L. R. and D. R. Fulkerson, Maximal Flow through a Network, Can J. Math., 8 (1956), 399‑404.

8. Freedman, D., R. Pisani, and R. Purves, Statistics, W. W. Norton, New York, 1978.

9. Glasser, M. L. and 1. J. Zucker, Extended Watson Integrals for the Cubic Lattices, Proc. Natl. Acad. Sci., USA, 74 (1977),1800‑1801.

10. Griffeath, D. and T. M. Liggett, Critical Phenomena for Spitzer's Reversible Nearest Particle Systems, Ann. of Probability, 10 (1982), 881‑895.

11. Hersh, R. and R. J. Griego, Brownian Motion and Potential Theory, Scient~fic American (March 1969), 66‑74.

12. Jeans, James, The Mathematical Theory of Electricity and Magnetism, Sth Edition, Cambridge, 1966.

13. Kaktitani, S., Markov Processes and the Dirichlet Problem, Proc. Jap. Acad., 21 (1945), 227‑233.

14. Kelly, F., Reversibility and Stochastic Networks, John Wiley & Sons, New York, 1979.

15. Kemeny, J. G., J. L. Snell, and A. W. Knapp, Denumberable Markov Chains, Springer‑Verlag, New York, 1976.

16. Kemeny, J. G., J. L. Snell, and G. L. Thompson, Finite Mathematics, 3rd Edition, Prentice‑Hall, Englewood Cliffs, N.J., 1974.

152 	REFERENCES

17. Kesten, Harry, Percolation Theory for Mathematicians, Birkhduser, Boston, 1982.

18. Kingman, J. F. C., Markov Population Processes, J. Appl. Prob., 6 (1969), 1‑18.

19. Kirchhoff, Gustav, Vorlesungen iiber Electricitdt und Magnetismus, Leipzig, 1891.

20. Lehman, A., A Resistor Network Inequality, Problem 605, SIAM Review, 4 (1965), 150‑154.

21. Le'vy, Paul, Theorie de I'addition des variables aMatoires, Paris, 1937.

22. Lyons, T., A Simple Criterion for Transience of a Reversible Markov Chain, Ann. of Probability, 11 (1983), 393‑402.

23. Maxwell, James Clerk, A Treatise on Electricity and Magnetism, 3rd Edition, Clarendon, 1918, reprinted by Dover, New York, 1954.

24. McCrea, W. H. and F. J. W. Whipple, Random Paths in Two and Three Dimensions, Proc. of the Royal Soc. of Edinburgh, 60 (1940), 281‑298.

25. Montroll, E. W. and B. J. West, Fluctuation Phenomena, in: Lebowitz and Montroll, eds. , Studies ‑in Statistical Mechanics , 7, North‑Holland, 1979, pp. 61‑175.

26. Nash‑Williams, C. St. J. A., Random Walks and Electric Currents in Networks, Proc. of the Cambridge Philosophical Soc., 55 (1959)9 181‑194.

27. Onsager, L., Reciprocal Relations in Irreversible Processes, Phys. Rev., 37 (1931), 405‑426; 38 (1931), 2265‑2279.

28. Po'lya, G. Ober eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz, Mathematische Annalen , 84 (1921)9 149‑160.

29. Po'lya, G., How To Solve It, 2nd Edition, Princeton, 1957.

30. Po'lya, G. and G. Szegb, Isoperimetric Inequalities of Mathematical Physics, Princeton, 1951.

31. Rayleigh, J. W. S. , On the Theory of Resonance, Philosophical Transactions, CLXI (1870), reprinted in: Collected Scientific Papers, Vol 1, Cambridge, 1899, pp. 33‑75.

32. Royden, H. L., Harmonic Functions on Open Riemann Surfaces, Trans. Amer. Math. Soc., 73 (1952).

33. Shannon, C. E. and D. W. Hagelbarger, Concavity of Resistance Functions, J. of Appl. Phys. , 27 (1956), 42‑43.

34. Snell, J. L., Gambling, Probability and Martingales, The Mathematical Intelligencer, Vol. 4, No. 3, 1982.

REFERENCES	153

35. Thomson, W. and P. G. Tait, Treatise on Natural Philosophy, Cambridge, 1879,

36. Ville, J., ttude critiques de la notion de collectif, Gauthier‑ Vil I ars, Paris, 1939.

37. Watson, G. N., Three Triple Integrals, Quarterly J. Math. (Oxford), 10 (1939), 266‑276.

INDEX

Abbott, Edwin, vii	Conway, J., 139
Are de Triomphe, 59	Courant, R., 27
averaging property, see	current
	harmonic function		Kingman‑Kelly model, 53
			probabilistic interpretation
Bolloba's, B., 58			of, 49‑52
Boston Garden, 72		unit, 62
boundary points, 8, 16	Cutting Law, 100, see also
bounded degree, 131‑135, 136			Monotonicity Law
bounded twiddling, see	cutting method, see short‑cut
	irrelevance of bounded			method
	twiddling	cyclic condition, 44

capacitance, 50	distance, in the lattice, 90
cartwheel pattern, 139	dimension of a tree, 106‑109
charge, 50	Dirichlet Principle, 64
civilized manner, 136‑142	Dirichlet problem
comparing graphs, see		in a continuous medium, 22
		comparing networks		in one dimension, 4
comparing networks, 132‑142		in two dimensions, 15, 93
	with comparable		for Markov chains, 36
		conductances, 133		Maximum Principle, 8, 17
	by embedding, 135, see also		solution by
		embedding trees			Markov chains, 31
	with a k‑fuzz, 134‑135			martingales, 11, 18
	with a lattice, 136‑142			method of relaxations, 22,
conductance, 40			27, 64
	effective, 54			Monte Carlo method, 19
	from x to x, 44, 79			solving linear equations,
connected graph, 39			27‑29

155

156 	INDEX

Dirichlet problem (Continued)	Feynmann, Richard, 70
	Uniqueness Principle, 8, 9,	flow
		17		unit, 62
dissipation, see energy		unit current, 62
		dissipation		from zero to infinity, 142
Doob, J. L., 13	flows, method of, see short‑cut
Doyle, P. G., viii			method
drunkard's walk, 3	Ford, L. R., 144
			Freedman, D., 20
effective conductance, 54	Friedrichs, K., 27
effective resistance, 53	Fulkerson, D. R., 144
Ehrenfest urn model, 44, 58	fuzz of a graph, see k‑fuzz of a
electric network formulation			graph
	of Dirichlet problem
		in one dimension, 4	gamma function, 126
		in two dimensions, 16	Glasser, M. L., 126
	of type problem, 91	graph, 39
elliptic integral, 126		connected, 39
embedding trees, 102, 106‑		drawn in a civilized manner,
		107, 111‑117, 141			136

	NT2.5849 	not quite in	embedded, 135

Z3, 114‑115	infinite, 131

	not uite NT2.5849 	in	k‑fuzz of a, 134‑135, 138

		Z 117		random walk on, 40
	NT3 in not quite Z3, 141		tree, 103
energy dissipation, 60, 78, 147	Griego, R. J., 27
	minimum, see Thomson's	Griffeath, D., viii
		Principle
energy	Hagelbarger, D. W., 68
	conservation of, 61	harmonic functions
	dissipation, 60, 142		for a Markov chain, 36
	importance of, 148		in one dimension, 8
escape probability		in two dimensions, 16
	bounds for, 116, 125	Hersh, R., 27
	exact value in three
		dimensions, 125‑126
	for finite graphs, 54, 65	independent random walks,
	,for infinite graphs, 90			127‑130
Euler's gamma function, 126	interior points, 8, 16
			interpretation, see
fair game, I I			probabilistic
Feller, William, viii, 125			interpretation

INDEX	157

irrelevance of bounded	Martingale Stopping Theorem,
	twiddling, 133, 135		12, 14

isoperimetric inequality, 144	martingale, 11, 122
	max‑flow min‑cut theorem,
Jeans, James, 96		144
	Maximum Principle, 8, 17

k‑fuzz of a graph, 134‑135,	Maxwell, James CWrk, 67, 96,
	138		143

Kakutani, S., vii, 13		"what is electricity?", 69‑70
Kelly, F., vii, 44, 50, 53		on Monotonicity Law, 67
Kemeny, J. G., vii, viii, 31,	McCrea, W. H., 125
		38, 80	method of relaxations, 19,
Kesten, Harry, viii			23‑27, 29
Kingman, J. F. C., 53	Minkowski inequality, 69
Kirchhoff's Laws, 6, 46	Monotonicity Law, 67, 100
Knapp, A. W., vii		proofs
					electrical, 67
ladder network, 58			Markov chain, 78‑82
Land of Oz, 31			probabilistic, 69, 69‑78
Laplace's differential			from Shorting or Cutting
		equation, 22			Law, 101
L6vy, Paul, 13		self‑evident, 67, 69‑70
Lehman, A., 69	Monte Carlo method, 18, 27,
Lewy, H., 27			29
Liggett, T. M., viii		current, 52‑53, 63
linear equations, see solving		voltage, 19‑21, 29
		linear equations	Montroll, E. W., 125, 141
loops, 44, 79	multiple edges, 71
Lyons, T., viii
			Nash‑Williams, C. St. J. A.,
Markov chain			viii, 97
	absorbing, 33	NT2, 108
	absorption probabilities, 35	NT2.5849 ‑ ‑ ‑, 115
	canonical form, 34	NT3, 108
	Ehrenfest urn model, 44, 58
	ergodic, 41, 44	Ohm's Law, 6, 46
	fundamental matrix, 34	Onsager, L., 43, 143
	harmonic function for a, 36	Oz, 31
	regular, 32, 44
	reversible, 42, 131	Paris, 59
	transition matrix, 31	penny matching game, 4
	transition probabilities, 31	physicist's approach, 23, 95

158 	INDEX

Pisani, R., 20			general graphs, 131
PO'lya's recurrence problem,		recurrent, 87, 132
		vii, 85‑88, see also type			expected time to return,
		problem			122
PO'lya's theorem, 12, 89		simple random walk
	classical proofs, 120‑123			on finite graphs, 43
	electrical proofs			on infinite graphs, 131
		for d = 1, 93		transient, 87, 132
		for d = 2, 101, 139		type problem, 88, 132
		for d = 3, 102‑113, 117,	Rayleigh, J. W. S., vii, 96
		140‑141, 141, 144‑147,	Rayleigh's method, see short
		148‑149			cut method
	extensions, 138‑142	Rayleigh's Monotonicity Law,
	physicist's "proof", 95, 100,			see Monotonicity Law
		118,148‑149	relaxation method, see method
PO'lya, G., 85, 96, 144			of relaxations
pollster, 20	resistance
probabilistic interpretation		effective, 53
	current, 52		from zero to infinity, 92
	energy dissipation, 78	reversible Markov chain, 42,
	voltage, 47			131
probabilistic proofs		cyclic condition, 44
	Monotonicity Law, 69, 69‑	Royden, H. L., viii
		78
	PO'lya's theorem, 120‑123	Shannon, C. E., 68
Purves, R., 20	short‑cut method, 96‑97, 100,
						132, 142‑143, see also
random walks			PO'lya's theorem
	on finite networks		cutting, 96, 142‑143, see
		1‑dimensional lattice, 3			also embedding trees
			with a drift, 7, 10, 14		flows, 142‑147, 149
			expected duration, 11,		shorting, 96, 101
			121	Shorting Law, 100, see also
		2‑dimensional lattice, 15			Monotonicity Law
		general graphs, 40	shorting method, see short‑cut
	on infinite networks			method
		d‑dimensional lattice, 85,	Snell, J. L., vii, viii, 13, 319 38
		see also PO'lya's theorem	superposition principle, 18
			expected number of	Szegb, G., 96
			times at origin, 119
			with random transition	Tait, P. G. 9 63
			probabilities, 133	Thompson, G. L., viii, 31, 38

INDEX	159

Thomson, W., 63	type problem, 88, 132, see also
Thomson's Principle, 63, 64,		PO'Iya's recurrence
		67, 142		problem
tiling, 139
total energy dissipation, see	Uniqueness Principle, 8, 9, 17
		energy dissipation
tree, 103	Ville, J., 13
	full binary tree, 109	voltage, probabilistic
	homogeneous of degree		interpretation of, 47
		three, 109
	NT2, 108	Watson, G. W., 126
	NT2.5849‑ ‑ ‑ 115	West, B. J., 125, 141
	NT3, 108	Wheatstone bridge, 69
trees, embedding, see	Whipple, F. J. W., 125
		embedding trees
twiddling, see irrelevance of
		bounded twiddling	Zucker, 1. J., 126