Topics in Probability: Random Walks and

Percolation

Ori Gurel-Gurevich  Gideon Amir

December 7, 2005

1 Random Walks and Electric Networks

1.1 Basic Notions

In this part we shall explore the tight relation between (simple) random walks and electric networks. This will provide us with an exact criteria for recurrency and with the monotonicity law which states that a subgraph of a recurrent graph is recurrent. This part is based on Doyle and Snell [3], which is a much longer, more detailed, but easy, read.

Exercise. Try to prove the monotonicity law. Also, can a finite change (addition or removal of finitely many edges, retaining connectivity) to the graph change its recurrency?

Definition. Let G be a graph with positive weights, w_{e}, assigned to the edge set. The Weighted (simple) Random Walk is a random walk where the transition probabilities are:

P rob(X_{n+1} = y|X_{n} = x) = \frac{w_{(x,y)}}{∑_{z∼x} w_{(x,z)}}

i.e. proportional to the weight of the edge.

If all the weights are 1, we get a simple random walk. We can actually forgo the graph structure (i.e. the edges) and just define the weight of transitions where there is no edge as 0. The reason we might still consider this as a simple random walk is that putting weight 2 to an edge is the same as putting 2 edges connecting the same vertices (as long as we’re not interested in which of the two edges was traversed). If all the weights are integers, or even if they are all commeasurable (there is a number w such that all weights are multiples of w), then there is an equivalent simple random walk.

Now, let’s turn our attention to electric networks. An Electric Network is a graph G with nonnegative weights on the edges called Conductances, denoted C_{xy}. The reciprocal of conductance is called resistance, denoted R_{xy}. Given a finite (for now) electric network and two special vertices in that network a, and b, the theory of electric networks defines two functions - voltage and current. The voltage, denoted v, is a real function of the vertices and the current, denoted i, is a real function of the (directed) edges. The usual setting is when we apply some voltage to a and b (usually 0 and 1) and the rest of the values are determined by the following two rules: Theorem. (Ohm’s Law) for x ∼ y the current satisfies the equality:

i_{xy} = C_{xy}(v(x) − v(y)) = \frac{v(x) − v(y)}{R_{xy}}

Theorem. (Kirchhoff’s Law) For any vertex x, other than a or b:

∑_{y∼x} i_{xy} = 0

We will be more interested in the voltage function, the current being a simple function of the voltage. Substituting the current in Kirchhoff’s law we get

∑_{y∼x} C_{xy}(v(x) − v(y)) = 0

Let C_{x} = ∑_{y∼x} C_{xy}. Thus, we get another formulation of Kirchhoff’s Law.

Theorem. (Kirchhoff’s law, equivalent formulation) For any vertex x, other than a or b:

v(x) = ∑_{y∼x} \frac{C_{xy}}{C_{x}} v(y)

What this means is that the voltage is a harmonic function at all points other than a and b. Note that C_{xy}/C_{x} are exactly the probabilities of transition from x to y in the weighted random walk with weights C_{xy}. Also, the function p(x), denoting the probability of reaching a before b when starting a (weighted) random walk from x is also harmonic everywhere but a and b, with the same coefficients (i.e. C_{xy}/C_{x}). From uniqueness of harmonic functions we deduce:

Conclusion. For an electric network, the voltage at x is exactly the probability of a weighted random walk, with weights equal to the conductances of the network and starting at x, to reach a before b.

This is the fundamental connexion between random walks and electric network.

1.2 Effective Conductance

Definition. Given a network (with specified a and b) the ratio between the total current flowing through the network and the voltage difference of a and b is called the Effective Conductance of the network. In other words:

C_{eff}(G, a ↔ b) = \frac{∑_{y∼a} i_{ay}}{v(a) − v(b)}

The reciprocal of the effective conductance is called the Effective Resistance,R_{eff}.

Exercise. prove that the definition does not depend on the voltages chosen for a and b

Equivalently, if we want to express everything in term of voltages, we get:

C_{eff}(G, a ↔ b) = \frac{∑_{y∼a} C_{ay}(v(a) − v(y))}{v(a) − v(b)}

Exercise. Prove that the current flowing out of a is exactly the current flowing into b. Thus,

C_{eff}(G, a ↔ b) = \frac{∑_{x∼b} C_{xb}(v(x) − v(b))}{v(a) − v(b)}

What is the significance of effective conductance? If we have a network, G and two vertices c and d in it, such that when we remove c and d the network splits into two networks, G_{1} and G_{2}, disconnected from each other, with a and b both in G_{1}, then we can replace G_{2} with a single edge from c to d with a conductance equal to the effective conductance of G_{2} from c to d. We can replace means that voltages (and thus currents) computed for the transformed network are the same as for the original network.

Exercise. Prove this fact.

Since this is true for electric networks, it is also true for random walks. This is useful when we want to compute hitting probabilities.

Two important cases for computing effective conductance are serial and parallel composition.

XXX enter figures

If our network is composed of just two vertices a and b and two edges between them with conductances C_{1} and C_{2}, then the currents flowing through them are C_{i}(v(a) − v(b)) respectively. Therefore the effective conductance is

C_{eff} = \frac{C_{1}(v(a) − v(b)) + C_{2}(v(a) − v(b))}{v(a) − v(b)} = C_{1} + C_{2}

Exercise. Find and prove the formula for effective conductance of serial composition, i.e. a is connected to c which is connected to b with conductances C_{1} and C_{2} respectively.

Note that although these two formulas are very useful, they are not enough to calculate the effective conductance of a general network. Even very simple network like this

XXX enter figure

cannot be analyzed using these simple rules.

Now let’s turn our attention back to random walks. We have already seen that v(x) is exactly the probability of a random walk, starting at x to reach a before b (assuming that v(a) = 1 and v(b) = 0). Now let’s ask ourselves: what is the probability that a random walk, starting at a will reach a before b, when we ignore time 0 ? i.e. we don’t count starting at a as reaching a.

The answer is simple: for each neighbor of a we already know the answer - it is v(x), so we just have to average v(x) over all neighbors of a with the correct probabilities. All in all we get:

p_{return} = \frac{∑_{x∼a} C_{ax}v(x)}{C_{a}}

If we’re interested in the probability of escape rather then return, i.e. of reaching b before returning to a, we get:

p_{escape} = 1−p_{return} = \frac{C_{a} − ∑_{x∼a} C_{ax}v(x)}{C_{a}} = \frac{∑_{x∼a} C_{ax}(v(a) − v(x))}{C_{a}} = \frac{∑_{x∼a} i_{ax}}{C_{a}}

Recall that C_{eff} = ∑_{x∼a} i_{ax}/(v(a) − v(b)), and since in our case v(a) = 1 and v(b) = 0 we get:

p_{escape} = \frac{C_{eff}}{C_{a}}

Now things gets interesting. Suppose we have an infinite graph G. Choose some vertex to be a and let G_{r} be the ball of radius r around a. Let ∂_{r} be all the outermost vertices (i.e. at distance r from a). Now we have:

P rob(a SRW goes to distance r before visiting a) = \frac{C_{eff}(G_{r}, a ↔ ∂_{r})}{C_{a}}

Definition. For an infinite graph G and some vertex a in it:

C_{eff}(G, a ↔ ∞) = lim_{r→∞} C_{eff}(G_{r}, a ↔ ∂_{r})

Now we can prove the following.

Theorem. A weighted SRW on a graph G (with weights) is recurrent if and only if C_{eff}(G, a ↔ ∞) = 0, for some (and every) a ∈ G. More precisely, p_{esc}(G, a) = C_{eff}(G, a ↔ ∞)/C_{a}.

Proof. Let x_{t} be a weighted SRW. Denote the event ”x goes to distance r before visiting returning to x_{0}” by E_{r}. We’ve shown that P rob(E_{r}) = C_{eff}(x_{0} ↔ ∂_{r}). Obviously, E_{r+1} ⊂ E_{r}. Let E = ⋂_{r∈ℕ} E_{r}. Since E_{r} is a monotone sequence of events

P rob(E) = lim_{r→∞} P rob(E_{r}) = \frac{C_{eff}(G, a ↔ ∞)}{C_{x_{0}}}

All that is left to show is that E ≡ F where F is the event ”x never returns to x_{0}” and equivalent is in measure (i.e. P rob(E△F) = 0). Obviously, E ⊂ F, since if x travels infinitely far before returning to x_{0}, it never returns to x_{0}. Conversely, we have to prove that the probability that x never reaches ∂_{r} nor x_{0} is zero.

Exercise. Prove that.

Now we have a nice characterization of recurrence. It immediately proves that ℤ is recurrent, for instance. It is also easy to prove that way that the binary tree is transient and, more generally, solve the prolonged binary tree exercise in part 2. It still isn’t clear how to use this characterization to show that ℤ^{2} is recurrent or that ℤ^{3} isn’t because we haven’t provided a way to compute the effective conductance, except by solving the linear equations which describe the voltage. If we only had a way to estimate, or bound, the effective conductance of a network...

Luckily, there is such a way.

Before we get into that, let’s see how we handle the binary tree case. For this we need the following lemma.

Lemma. For any network G, if we have two vertices with v(x) = v(y) and C_{xy} < ∞ we can change C_{xy} to any value without affecting the voltage or currents.

Exercise. The trivial proof is left as an exercise to the reader.

At first, it might seem that this lemma is not of any value when we want to compute effective conductances, for we have to find the voltages before using it. Closer inspection reveals that we can sometimes find pairs of vertices that must have the same voltage by symmetry considerations.

Example. The binary tree.

Example. The n-th dimensional hypercube, H_{n} = {0, 1}^{n}. Calculate the effective conductance between 0^{n} and 1^{n} and conclude that the corresponding hitting probability tends to \frac{1}{2}.

1.3 Energy

Definition. For a single edge xy with conductance C_{xy}, given voltages v(x) and v(y) the Energy Dissipation is

E_{xy} = i_{xy}(v(x) − v(y)) = C_{xy}(v(x) − v(y))^{2} = R_{xy}i_{xy}^{2}

For a network G with given voltages v(a) and v(b) at the endpoints, the Total Energy Dissipation, E, is the sum of the energy dissipation over all the edges.

We are not physicists, so we’ll call it simply Energy. Since the energy is unchanged when we reverse x and y, we can write

E(G) = \frac{1}{2} ∑_{x,y∈G} i_{xy}(v(x) − v(y)) = \frac{1}{2} ∑_{x,y∈G} C_{xy}(v(x) − v(y))^{2} = \frac{1}{2} ∑_{x,y∈G} R_{xy}i_{xy}^{2}

Theorem. (conservation of energy) For any network G we have:

E(G) = C_{eff}(G, a ↔ b)(v(a) − v(b))^{2}

What this means is that we can regard a network as a single edge, also for the purpose of energy.

Proof. By the definition of energy

E(G) = \frac{1}{2} ∑_{x,y∈G} i_{xy}(v(x) − v(y)) = \frac{1}{2}( ∑_{x,y∈G} i_{xy}v(x) − ∑_{x,y∈G} i_{xy}v(y))

= \frac{1}{2}(∑_{x∈G} v(x) ∑_{y∈G} i_{xy} − ∑_{y∈G} v(y) ∑_{x∈G} i_{xy})

For any x ≠ a, b we have ∑_{y∈G} i_{xy} = 0. Therefore

E(G) = \frac{1}{2}(v(a) ∑_{y∈G} i_{ay} + v(b) ∑_{y∈G} i_{by} − v(a) ∑_{x∈G} i_{xa} − v(b) ∑_{x∈G} i_{xb})

Recall that i_{xy} = −iyx and that ∑_{x∈G} i_{ax} = ∑_{y∈G} i_{yb} = C_{eff}(G, a ↔ b)(v(a) − v(b)). Put together, this yields

E(G) = C_{eff}(G, a ↔ b)(v(a) − v(b))^{2}

Note that what we actually proved is that

\frac{1}{2} ∑_{x,y∈G} i_{xy}(v(x) − v(y)) = ∑_{x∈G} i_{ax}(v(a) − v(b))

for any function v and any flow from a to b. We haven’t used Ohm’s law that connects the current and voltage.

Theorem. (Thomson’s Principle, one form) Among all functions u, with given boundary values u(a) and u(b), the function which minimizes the energy

E(u) = ∑_{x,y∈G} C_{xy}(v(a) − v(b))^{2}

is the voltage, v.

Proof. For some x ∈ G, take the part of the sum which involves x, i.e.

s = ∑_{y∈G} C_{xy}(u(x) − u(y))^{2}

Differentiate with respect to u(x) to get

s′ = 2 ∑_{y∈G} C_{xy}(u(x) − u(y))

This is equal to 0 if u(x) = ∑_{y∈G}(C_{xy}/C_{x})u(y), i.e. if u is harmonic at x. This is the minimum of s over values of u(x). This means the if u is not v, it is not harmonic at some point, x and the energy can be lowered by changing the value of u(x).

This theorem has a dual form, dealing with the current, instead of voltage.

Theorem. (Thomson’s Principle, dual form) Among all flows j, with total flow out of a (and into b) of 1, the flow which minimizes the energy

E(j) = \frac{1}{2} ∑_{x,y∈G} R_{xy}j_{xy}^{2}

is the current, i.

Proof. Let j be such a flow and i the current. Let d_{xy} = j_{xy} − i_{xy}. d is a flow with total flow 0 (exercise: give an example of such a flow). Then

E(j) = \frac{1}{2} ∑_{x,y∈G} R_{xy}j_{xy}^{2} = \frac{1}{2} ∑_{x,y∈G} R_{xy}(i_{xy} + d_{xy})^{2}

= \frac{1}{2} ∑_{x,y∈G} R_{xy}i_{xy}^{2} + ∑_{x,y∈G} R_{xy}i_{xy}d_{xy} + \frac{1}{2} ∑_{x,y∈G} R_{xy}d_{xy}^{2}

= E(i) + ∑_{x,y∈G}(v(x) − v(y))d_{xy} + E(d)

By the conservation of energy, we get that the middle term is 0. Since E(d) ≥ 0 we get E(j) ≥ E(i).

The importance of Thomson’s principle is that it gives us Rayleigh’s monotonicity law on a silver plate.

Theorem. (Rayleigh’s Monotonicity Law) if C_{xy} and D_{xy} are two sets of conductances for graph G, with C_{xy} ≤ D_{xy} for all edges. Then the effective conductance of the network with conductances C_{xy} is at most that with conductances D_{xy}.

Proof. Let v be the voltage function for conductances C_{xy} and u for D_{xy}. Since C_{xy} ≤ D_{xy} we have

C_{eff}({C_{xy}}) = ∑_{x,y∈G} C_{xy}(v(x) − v(y))^{2} ≤ ∑_{x,y∈G} C_{xy}(u(x) − u(y))^{2}

≤ ∑_{x,y∈G} D_{xy}(u(x) − u(y))^{2} = C_{eff}({D_{xy}})

Note the strict monotonicity does not hold. For some networks, we can increase or decrease the conductance at some edges without changing the effective conductance.

Corollary. A subgraph of a recurrent graph is recurrent.

Note that the monotonicity law allows us to change conductances to/from 0 or ∞ as well. 0 conductance means no edge, so changing conductance to 0 means deleting an existing edge. Conductance ∞ is formally not defined. If we consider it as a limit of unbounded sequence of conductances, we can see that it corresponds to merging the two vertices into one.

Exercise. prove the Nash-Williams criteria for recurrence based on the monotonicity law.

Show recurrence of ℤ^{2}.

Define branching tree T (b, l).

R_{eff}(T (b, l)) = ∑_{i=0}^{∞} \frac{1}{b}(\frac{l}{b})^{i} = \frac{1}{b − l}

Show embedding of T (2, 2) into ℤ^{2}, deduce that resistance to ∂_{r} is Θ(log(r)). Conclude that the number of points visited by SRW up to time n is Θ(n/ log(n)).

Show embedding of T (3, 2) (with R_{eff} = 1) in ℤ^{3}. Conclude that p_{esc} ≥ 1/6. Using 2 copies of T (3, 2) we get p_{esc} ≥ 1/3. Using 8 copies of T (3, 2) connected to the corners of a cube show that p_{esc} ≥ 35/72. Actually, p_{esc} ≅ 0.66.

Exercise. (?) Show that p_{esc}(ℤ^{d}) → 1 when d → ∞. Give explicit asymptotic bounds.

Exercise. (Important) Prove that the effective conductance function is convex.

References

[1] Lawler, G., Cut times for simple random walk. Electronic Journal of Probability 1 (1996) Paper 13.

[2] Nash-Williams, C. St. J. A., Random walks and electric currents in networks, Proc. Cambridge Phil. Soc. 55 (1959), 181-194.

[3] Doyle, P. and Snell, L., Random Walks and Electric Networks, http://front.math.ucdavis.edu/math.PR/0001057 (1984).

[4] Benjamini,  I. and Gurel-Gurevich O.,  Almost Sure
Recurrence  of  the  Simple  Random  Walk  Path,

http://www.arxiv.org/abs/math.PR/0508270 (2005)