Topics in Probability: Random Walks and

Percolation

Ori Gurel-Gurevich  Gideon Amir

November 15, 2005

1 Random Walks - Basics

What is a random walk? hard to define in general. Better start with an example.

Here’s THE example from the founder of the field, George Polya:

”... he and his fiancee (would) also set out for a stroll in the woods, and then suddenly I met them there. And then I met them the same morning repeatedly, I don’t remember how many times, but certainly much too often and I felt embarrassed: It looked as if I was snooping around which was, I assure you, not the case. I met them by accident - but how likely was it that it happened by accident and not on purpose?”

We model this setup by two walkers, each taking a step north, south, east or west with equal probabilities every second. Will they meet?

On ℤ^{2} this is equivalent to a single walker, asking if and how often he comes back.

Definition. A Simple Random Walk on a graph G is a stochastic process x_{i} with P rob(x_{i+1} = v) = \frac{1}{d_{x_{i}}} for v ∼ x_{i}, and 0 otherwise.

Definition. a graph G is called recurrent if a SRW on G returns to x_{0} with probability 1. If G is not recurrent, it is called transient. Exercise. Show that the definition does not depend on x_{0}. Exercise. Is the 2 walkers model always equivalent to 1 walker? i.e. is there a recurrent graph where 2 independent SRWs do not meet infinitely often?

Other interesting questions besides recurrency: Hitting times and hitting probabilities. Example. A man plays in the casino fair games with 1$ bets. How much time till he earns 1$? how much is he likely to lose before he recovers? Example. A drunkard leaves his house. When is he likely to return? Example. A SRW on ℤ^{2} stops when it hits the set {(0, −1), (0, 0), (0, 1)}. What is the distribution? if the walk starts far enough does it matter in which direction? Theorem. (Stirling’s formula)

lim_{n→∞} \frac{n!}{\sqrt{2πn}(\frac{n}{e})^{n}} = 1

Proof. For a really short proof see [1]. Theorem. (Polya) SRW on ℤ and ℤ^{2} is recurrent. Proof. First, consider a SRW on ℤ. The probability, p_{2n} of the walk visiting 0 at time 2n is exactly \binom{2n}{n}2^{−2n}. Using Stirling’s Formula we get that

p_{2n} ∼ \frac{\sqrt{2π2n}(\frac{2n}{e})^{2n}}{2πn(\frac{n}{e})^{2n}} 2^{−2n} = \frac{1}{\sqrt{πn}}

Therefore, ∑_{n=0}^{∞} p_{2n} = ∞. This is exactly the expected number of times the SRW visits 0.

Now, suppose that the probability of return to 0 is P < 1. The number of times the SRW returns to 0 is distributed geometrically with parameter P, because every time we are at 0 there is a probability P to return again, and 1 − P to cease visiting 0. The expectation is this distribution is 1/(1 − P). But our calculation showed this expectation to be infinite, so P cannot be less than 1.

Now for ℤ^{2}. First, lets take a look at a RW which alternatingly takes a step on the X and Y axis. For this (non simple) RW the probability of visiting 0 at time 4n is

p_{4n} = (\binom{2n}{n}2^{−2n})^{2} ∼ \frac{1}{πn}

Since ∑_{n=0}^{∞} p_{4n} = ∞, the expected number of returns is infinite and this RW is recurrent, for exactly the same reasons as before.

Now, notice that 2 steps of this alternating RW will take us from (x, y) to either of (x+1, y +1), (x+1, y −1), (x−1, y +1), (x−1, y −1) with equal probabilities. Therefore, our alternating RW is actually a simple RW on the diagonal lattice, which consists of all the integer coordinates (x, y) with x+y even, and with edges between (x, y) and (x′, y′) iff |x − x′| = 1 and |y − y′|. The graph of the diagonal lattice is exactly that of ℤ^{2}, so a SRW on ℤ^{2} must be recurrent too.

Theorem. (Polya) ℤ^{d} for d ≥ 3 is transient.

Proof.

If G is d-regular then the probability of a path x_{0}, .., x_{n} is exactly d^{−n}. In particular, P r(x_{0}, .., x_{n}) = P r(x_{n}, .., x_{0}). If G is not regular then P r(x_{0}, .., x_{n}) = P r(x_{n}, .., x_{0})d_{x_{0}}/d_{x_{n}}. If the graph is of bounded degree then the probability of a path and its reversal are the same up to a multiplicative constant. This simple observation turns out to be very powerful.

Definition. For a graph G and a vertex v ∈ V_{G}, a set C ⊂ V_{G} of vertices is called a cutest if the component of v in G \ C is finite.

Definition. Given two cutsets, C and D we say that C is nested in D if S is contained in the (finite) component of v in G \ C.

Theorem. (Nash-Williams [2]) For G a bounded degree graph, if there exists a series of disjoint cutsets C_{i}, each nested in its successor, such that ∑_{i=0}^{∞} |C_{i}|^{−1} = ∞ then the graph is recurrent.

Proof.

The Nash-Williams criterion is sufficient but not necessary.

Exercise. Find a bounded degree recurrent graph which does not meet this criterion.

References

[1] Romik, D. Stirling’s approximation for n!: the ultimate short proof? Amer. Math. Monthly 107 (2000), 556-557 http://www.stat.berkeley.edu/ romik/papers.html

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