Topics in Probability: Random Walks and

Percolation

Ori Gurel-Gurevich  Gideon Amir

November 15, 2005

1 Martingales, Hitting probabilities and Har-

monic functions

1.1 Some notes on martingales

Definition. 1. A sequence of random variables {X_{n}} is called a martingale , (or martingale sequence) , if for any 0 ≤ i, we have E(X_{i+1} | X_{0}, .., X_{i}) = X_{i}

2. A martingale {X_{n}} is called bounded if the there exists M > 0 such that the random variables |X_{i}| are uniformly bounded by M. i.e. ∀i ∈ N P (|X_{i}| > M) = 0

3. A martingale {X_{n}} is said to have Bounded increments if there exists some M > 0 s.t. P (|X_{i+1} − X_{i}| > M) = 0.

Examples - location of SRW on a segment is a bounded martingale, while SRW on Z is not bounded but has bounded increments.

Remark. Martingale is originally the name of a betting strategy where you double your bet each round. Your winnings in such a strategy are also a martingale - but the increments are not bounded.

Definition. Given a sequence of random variables, A stopping rule is a function from finite histories of the random variable sequence into {0, 1} - (0 is Continue, 1 is Stop)

- i.e. If {X_{i}} is our random sequence, than for any finite sequence of events X_{0} = x_{0}, ....X_{n} = x_{n} the stopping rule tells us whether to continue or stop.

A Stopping time is the minimum time in which some stopping rule is satisfied.

Definition. A stopping time τ is bounded if there is a time T such that τ ≤ T a.s. . It is called finite a.s. if we stop with probability 1.

Not all stopping times are a.s. finite - For example, a transient random walk stopped when returning to the origin.

Some facts about martingales:

1. For any 0 ≤ k < n E(X_{n} | X_{k}) = X_{k}.

Proof. By induction on n. For n = k+1 this follows from the definition of a martingale. For n > m + 1 We have

E_{n}(X_{n} | X_{k}) = E_{n−1}(E_{n}(X_{n} | X_{n−1}, X_{k}) | X_{k}) =
= E_{n−1}(X_{n−1} | X_{k}) = X_{k}

Where the first equality follows from the definition of expectation, the second from the fact that {X_{i}} is a martingale, and the third from the induction hypothesis.

2. For any martingale {X_{n}} and any bounded stopping time τ we have E(X_{τ} | X_{0}) = X_{0}.

Proof. Let τ be a stopping time bounded by M. Define a new sequence of random variables {Y_{n}} , that coincides with the original sequence until the X_{n} stops, and than settles on the value it first stopped in. i.e. Y_{n} = X_{n} for n ≤ τ and Y_{n} = X_{τ} for n ≤ τ. Then it is easy to see that {Y_{n}} is a martingale, and Y_{M} = X_{τ} so E(X_{τ} | X_{0}) = E(Y_{M} | Y_{0}) = Y_{0} = X_{0} as desired.

3. Let {X_{n}} be a Bounded martingale , and τ an a.s. finite stopping time, then E(X_{τ} | X_{0}) = X_{0}.

Proof. Let M be an upper bound on {|X_{n}|}. For any ϵ > 0 and any value of X_{0}, there exists some t_{ϵ} > 0 such that P (τ > t_{ϵ} | X_{0}) < ϵ. We will define a new stopping time φ_{ϵ} = min(τ, t_{ϵ}). Then φ_{ϵ} is a bounded stopping time for {X_{n}}, and therefore by the above claim E(X_{φ_{ϵ}} | X_{0}) = X_{0}. And since {X_{n}} is bounded, |E(X_{φ_{ϵ}} | X_{0}) − E(X_{t}au | X_{0})| ≤ P (φ_{ϵ} ≠ τ | X_{0}) ∗ 2M) ≤ 2ϵM. And since ϵ was arbitrary, we are done.

Theorem (Optional stopping theorem). If {X_{n}} is a martingale with bounded increments and τ a finite expectation stopping time. Then E(X_{τ} | X_{0}) = X_{0}. (note finite expectation → a.s. finite)

We leave the proof as an exercise to the reader.

Remark. It is not enough to demand that E(X_{n+1} | X_{n}) = X_{n} (this is called a pseudo martingale). In that case the optional stopping time theorem can fail. (even for bounded stopping times)

An example of such a pseudo-martingale is a RW on Z starting from 0 that when reaching 0 from 1 goes to −1 and vice versa, and acts as a SRW elsewhere (and on the first move from 0).

Since behavior of SRW does not depend on the history other than it’s current location, independence on steps before the last will usually be automatic in the cases we consider.

1.2 SRW on a segment.

1. Hitting probabilities of the two endpoints. Let {X_{n}} be a random walk on [0,K], walking until its hits on of the endpoints of the segment [0, K]. Let p_{i} denote the probability that the walk will hit K before it hits 0, given that X_{0} = i. Then p_{i} = \frac{i}{K}. 2 proofs for the hitting probabilities of the endpoints:

(a) E(X_{n+1}) | E(X_{n})) = \frac{1}{2}(X_{n} −1)+ \frac{1}{2}(X_{n} +1) = X_{n}, so the sequence {X_{i}} is a martingale. Let τ denote the time it hits one of the endpoints (a.s. finite) Since {X_{i}} is clearly bounded, E(X_{τ} | X_{0} = i) = i. But E(X_{τ} | X_{0} = i) = p_{i} ∗ K + (1 − p_{i}) ∗ 0 = p_{i} ∗ K , so p_{i} = \frac{i}{K}.

(b) Solving through equations: p_{i} = \frac{1}{2}p_{i−1} + \frac{1}{2}p_{i+1}. p_{0} = 0, p_{K} = 1. Then p_{i+1} − p_{i} = p_{i} − p_{i−1}. therefore, p_{i} = \frac{i}{K}.

Example. Gamblers ruin. Lets look at the following gambling strategy (for even bets): Bet 1 dollar over and over, stopping when you reach a positive (1 dollar) earning. This is equivalent to doing a random walk on Z starting from 0 and stopping when you reach 1. SRW on Z is a martingale, and since Z is recurrent, the above stopping rule is a.s. finite. But E(X_{τ}) = 1 ≠ X_{0} = 0. So we see that for unbounded martingales, a.s. finite stopping time does not insure E(X_{τ} | X_{0}) = X_{0}. More so, from theorem ?? on martingales with bounded increments and finite expectation stopping times, we conclude E(τ) = ∞.

Exercise. What about the betting strategy of doubling the bet every time until reaching a positive earning?

Exercise. write equations for biased random walk.

Claim (Hitting times of endpoints). Let X be a simple random walk on [−K, K] starting from 0. Let τ be the first time the walk hits one of the endpoints of the segment [-K,K]. Then E(τ) = K^{2}.

Proof. Set Y_{n} = X_{n}^{2} − n. Then {Y_{n}} is a martingale :

E(Y_{n+1} | Y_{0}, .., Y_{n}) = \frac{1}{2}((X_{n} −1)^{2} −(n+1))+ \frac{1}{2}((X_{n} +1)^{2} −(n+1)^{2}) =

= X_{n}^{2} + 1 − n − 1 = X_{n}^{2} − n = Y_{n}

It is easy to see that {Y_{n}} has bounded increments (when X_{n} is inside [−K, K]) and that E(τ) < ∞, and therefore by the optional stopping theorem E(Y_{τ}) = E(Y_{τ} | Y_{0} = 0) = 0. But Y_{τ} = K^{2} − τ so E(τ) = K^{2}.

1.3 Hitting probabilities in Z^{2}

Example 1 - 2 sinkholes , with what probability will we end in each?

Example 2 - Bounded domain. What’s the probability to hit each boundary point.

Observation - hitting probability of a point by SRW is a martingale. For a SRW this probability depends only on the current location so the martingale equation is actually ∑_{u∼v} f(u)/d_{v} = f(v). This is the definition of harmonic function.

Definition. A function f from some graph G = (V, E) is called harmonic at v ∈ V if f(v) = \frac{1}{d_{v}} ∑_{u∼v} f(u). It is called harmonic on S ⊂ V if it is harmonic at each point v ∈ S.

Note that this simply means that the value of f at v is the average of it’s values on all neighbors of v. An harmonic function on G is simply a function harmonic on all of V.

If f and g are harmonic in S then so are f + g and cf for any scalar c. Remark. There are analogues connections between harmonic functions and analytic functions on C. Claim. Let f be harmonic on G, and let X_{i} be a simple random walk on G. Then {f(X_{i})} is a martingale. Proof. For simplicity, we will assume f is 1-1. E(f(X_{i+1}) | X_{i}) = \frac{1}{d_{X_{i}}} ∑_{u∼X_{i}} f(u) = f(RX_{i}). The last inequality following from the fact that f is harmonic. It follows by summation on f^{−1}(f(X_{i})) that E(f(X_{i+1}) |f(RX_{i})) = f(RX_{i}). Definition. (Discrete) Dirichlet problem: Given some connected domain U ⊂ Z^{d}, with boundary σ, and a function f : σ− > R, find a function h : U ∪ σ → R such that h is harmonic on U and h|_{σ} ≡ f.

Solving the Dirichlet problem consists of 3 parts: Does a solution exist? How to find a solution? And is the solution unique? Remark. Analog Dirichlet problem on C.

1. Existence of solution using SRW. Q: If the function h is 1 on some y ∈ σ and 0 elsewhere - how do we find f? General solution - Let X be a random walk on U ∪ σ. For any x ∈ U define f(x) = E(f(X_{τ}) |X_{0} = x) where τ is the first time the walk hits σ. It is easy to verify that f satisfies the harmonic condition f(u) = \frac{1}{d_{u}} ∑_{v∼u} f(v) for any u ∈ U.

2. What about uniqueness?

Claim (Maximum Principle). If f is harmonic and non-constant in some connected domain U then f does not have any maximum points in U. In Particular, if U is finite with finite boundary σ and f is defined on U ∪ σ, then f attains its maximum on the boundary σ. (Same for minimum, or for |f|)

Proof. If x ∈ U is a maximum point for f, then since f(x) equals the average of f over all neighbors of x, f(v) = f(x) for all neighbors of x, and thus any point y connected to x by some finite path also has f(y) = f(x) and thus f is constant on U. If U and σ are finite, then since f has a maximum , it must be on σ.

Maximum principle implies uniqueness. If f and g are two solutions for the Dirichlet problem for some Domain U ∪ σ and some function h on σ, then f − g is also harmonic in U, and (f − g)|_{σ} ≡ 0, so by the maximum principle f − g ≡ 0.

3. Actual solution using linear equations. For each x ∈ U we can write a simple linear equation f(x) = \frac{1}{d_{x}} ∑_{v∼x} f(v), where our variables are {f(x)}_{x∈U}. This is a system of |U| linear equations in |U| variables, which can be solved efficiently. From Existence and uniqueness of the solution to the Dirichlet problem, we know that a unique solution to this system exists.

Remark. What about outer Dirichlet problem? For a recurrent graph existence is shown using RW as before. We will show (?) that the solution has a limit at infinity, no matter in which direction. For transient graphs things get more complicated, as we need to condition on the event that the RW reaches our set.

1.4 Liouville property

Definition. A graph G is said to be Liouville (or have the Liouville property) if any bounded harmonic function on G is constant. Remark. Analog to Liouville theorem on C - Any entire bounded analytic function on C is constant. Theorem. Any recurrent graph is Liouville. Proof. Let f be some bounded harmonic function on G. Let X be a simple random walk on G starting from some u ∈ V (G). Then by ?? f(X_{i}) is a bounded martingale. Fix v_{0} ∈ V (G) and define the stopping time τ to be the first time X hits v_{0}. since G is recurrent, τ is a.s. finite, and therefore by theorem ?? f(v_{0}) = E(f(X_{τ})) = f(u) Since u was arbitrary, we conclude f is constant. Example. Tree is not Liouville. Exercise. What are the bounded harmonic functions on the infinite binary tree. Definition. Given two random variables X and Y, a coupling of X and Y is a distribution on pairs (x, y) such that the marginal distribution of the first coordinate is the distribution of X, and the marginal distribution of the second coordinate is that of Y. (i.e. we define a joint distribution of X and Y on some new probability space) Example. Coupling of two uniform [0, 1] variables U and V. We can couple them in such a way that U and V are independent, in a way that U ≡ V and in a way that insures P (U > V) > 0.9. Example. If X is SRW on Z starting at i, and Y is a (1/3, 2/3) biased random walk on Z starting from i, then we can couple them in such a way that X is always to the left of Y (or both in same place), and conclude that the probability of Y exiting the segment [0, K] at K is greater than that of X.

Theorem. Z^{d} is Liouville.

Proof. We will use a coupling argument, to couple between 2 random walks X and Y staring at u_{0} and v_{0} respectively, to show that f(u_{0}) = f(v_{0}). If we can define a coupling such that the two walks meet (couple) with probability 1, then {f(X_{i}) − f(Y_{i})} will be a bounded martingale sequence, and the coupling time (meeting time) will be an a.s. finite stopping time. And then by the optional stopping theorem 0 = E(f(X_{τ})−f(Y_{τ}) | X_{0} = u_{0}, Y_{0} = v_{0}) = f(u_{0}) − f(v_{0}), and thus f is constant.

We define the desired coupling as follows. X and Y always walk on the same axis together, and always toward each other. And if one coordinate coincides, they always walk this coordinate in the same direction. We show that up to odd/even coordinates, each coordinate couples with probability 1.

Example. Example: Z^{3} + Z^{3} is not Liouville.

Exercise. Is there a transient exponential-growth graph which is Liouville (with bounded degree? vertex transitive?).