LECTURE 5

Strong Markov property. Let X_{0}, X_{1}, … be a time homogeneous Markov chain, and τ a stopping time with respect to F_{n} = σ(X_{0}, …, X_{n}). We want to prove the strong Markov property,

E[g(X_{τ+1}) | F_{τ}] = E_{X_{τ}} [g(X_{1})].

Let B be any set in F_{τ}. We want to show

P ({X_{τ+1} = j} ∩ B ∩ {X_{τ} = i} ∩ {τ ≤ n}) = p_{ij}P (B ∩ {X_{τ} = i} ∩ {τ ≤ n}).

Now

P ({X_{τ+1} = j} ∩ B ∩ {X_{τ} = i} ∩ {τ ≤ n}) = ∑_{k=0}^{n} P ({X_{τ+1} = j} ∩ B ∩ {X_{k} = i} ∩ {τ = k}).

Since B ∈ F_{τ}, we have B ∩ {τ = k} ∈ F_{k} so

P (X_{τ+1} = j | B ∩ {X_{k} = i} ∩ {τ = k}) = P (X_{τ+1} = j | X_{k} = i) = p_{ij}.

The strong Markov property follows by summing.

Recurrence and Transience of Markov chains. Suppose p_{ij} are the transition probabilities of a discrete state time homogeneous Markov chain. We say a state i is recurrent if the probability to return to that state is 1. Otherwise the state is called transient. Recurrent states are divided into positive recurrent states and null recurrent states depending on whether the expected time to return is finite or infinite.

We want to use the n-step transition probabilities to check for recurrence and transience.

Let a_{ij}^{(k)} = P_{i}(X_{k} = j, X_{ℓ} ≠ j, ℓ < k) be the probability that the Markov chain starting at X_{0} = i, visits j first at time k:

a_{ij}^{(k)} = P_{i}(X_{k} = j, X_{ℓ} ≠ j, 1 ≤ ℓ < k).

Note that first here does not include the starting point. Then

a_{ii} = ∑_{k=1}^{∞} a_{ii}^{(k)}

is the probability that the walk ever returns, and the state i is recurrent or transient depending on whether a_{ii} is 1 or less than 1.

To go from state i to state j in n steps, you must go from state i to state j first in τ ≤ n steps, and then from state j to state j in n − τ steps. So using the strong Markov property we get the formula

p_{ij}^{(n)} = ∑_{k=1}^{n} a_{ij}^{(k)}p_{jj}^{(n−k)}.

Theorem. State i is recurrent if and only if ∑_{n=1}^{∞} p_{ii}^{(n)} = ∞.

Proof. By the formula,

∑_{n=1}^{∞} p_{ii}^{(n)} = ∑_{n=1}^{∞} ∑_{k=1}^{n} a_{ii}^{(k)}p_{ii}^{(n−k)}.

Changing the order of summation we get

∑_{k=1}^{∞} ∑_{n=k}^{∞} a_{ii}^{(k)}p_{ii}^{(n−k)} = ∑_{k=1}^{∞} ∑_{n=0}^{∞} a_{ii}^{(k)}p_{ii}^{(n)} = a_{ii}(1 + ∑_{n=1}^{∞} p_{ii}^{(n)}).

So if ∑_{n=1}^{∞} p_{ii}^{(n)} < ∞ we have a_{ii} < 1. If ∑_{n=1}^{∞} p_{ii}^{(n)} = ∞ then we do the same thing more carefully,

∑_{i=1}^{N} p_{ii}^{(n)} = ∑_{n=1}^{N} ∑_{k=1}^{n} a_{ii}^{(k)}p_{ii}^{(n−k)} = ∑_{k=1}^{N} ∑_{n=k}^{N} a_{ii}^{(k)}p_{ii}^{(n−k)}.

So

∑_{k=1}^{N} a_{ii}^{(k)} ≥ ∑_{n=1}^{N} p_{ii}^{(n)} (∑_{n=0}^{N} p_{ii}^{(n)})^{−1} .

The right hand side goes to 1 as N → ∞, so a_{ii} ≥ 1. But that means a_{ii} = 1 since it is a probability.

Application. Consider the simple symmetric random walk on the integers. Then

p_{00}^{(n)} = \binom{n}{n/2}2^{−n} ∼ \sqrt{\frac{2}{πn}}.

So ∑_{n=1}^{∞} p_{00}^{(n)} = ∞ so it is recurrent. Now consider a random walk on the d-dimensional integer lattice which at each time moves ±1 in each of the coordinate directions. Then

p_{00}^{(n)} = [\binom{n}{n/2}2^{−n}]^{d} ∼ (\frac{2}{πn})^{d/2}

So ∑_{n=1}^{∞} p_{00}^{(n)} = ∞ if d ≤ 2 and ∑_{n=1}^{∞} p_{00}^{(n)} < ∞ if d ≥ 3. It says that a drunken man in a two dimensional city will find his way home, but not in a three dimensional city (eg. Manhattan).

Strong Markov property of Brownian motion. This says that if B_{t}, t ≥ 0 is a Brownian motion adapted to some filtration F_{t}, t ≥ 0 and τ is a bounded stopping time, then

E[g(B_{τ+t}) | F_{τ}] = E_{B_{τ}} [g(B_{t})].

Another way to say it is that B̃_{t} = B_{τ+t} − B_{τ} is a Brownian motion independent of F_{τ}. It means that Brownian motion starts afresh at every stopping time.

Note that for continuous time Markov processes the strong Markov property is not always true and has to be proved.

Regularity of the Brownian paths. Let B_{t}, t ≥ 0 be a Brownian motion on a probability space (Ω, F, P). For each ω, B_{t}(ω) is a function of t, called a sample path. How nice is the path? Since \frac{B_{t}−B_{s}}{|t−s|^{α}} is N (0, |t − s|^{1−2α}) we expect that it goes to zero as s → t for any α < 1/2. This suggests that the paths are continuous, with

sup_{0≤s,t≤1} \frac{B_{t} − B_{s}}{|t − s|^{α}} = C_{α}

finite for α < 1/2 (one says they are Hölder of order α), but they are not differentiable. This is true, but it is a bit tricky to prove so we leave it for later.

Multidimensional Brownian motion. If B_{t}^{1}, …, B_{t}^{d} are d independent Brownian motions, then B_{t} = (B_{t}^{1}, …, B_{t}^{d}) is a d-dimensional Brownian motion. Another way to say it is that d-dimensional Brownian motion is the Markov process with transition probabilities

p(s, x, t, y) = (2π(t − s))^{−d/2}e^{−|y−x|^{2}/2(t−s)}.

Of course you have to specify the point x where the process starts. We use P_{x} and E_{x} to specify the probability and expectation for the process starting at x.

The Dirichlet problem. Given a domain D ⊂ R^{d} with boundary ∂D and a function f defined on ∂D, the Dirichlet problem is to find a function u on D satisfying

\begin{matrix}Δu = 0, & in D, \\ u = f, & on ∂D. \end{matrix}

Here Δ = ∑_{i=1}^{d} \frac{∂^{2}}{∂x_{i}^{2}} is the Laplacian. Functions u satisfying Δu = 0 are called harmonic. It is not hard to check that a function is harmonic if and only if it has the mean value property; for every sphere S(r, x) = {y : |y − x| = r} contained in D,

u(x) = \frac{1}{|S|} ∫_{S} u(y)ds

where ds is the element of surface area and |S| = ∫_{S} ds is the surface area. The right hand side is nothing but the average value of u on the surface S. Note we are using 3 dimensional words like surface and sphere, but it works in any dimension. The solution of the Dirichlet problem is unique by the maximum principle which says that a harmonic function cannot take its maximum inside the region. If there were two solutions then the difference would be zero on the boundary and harmonic inside, so by the maximum principle it would have to be ≤ 0 inside. Taking the difference the other way, we see that it is ≥ 0 as well. So the difference of two solutions is zero, meaning they are really the same solution.

Brownian motion and the Dirichlet problem. Let x ∈ D. Let τ be the first time that the Brownian motion starting at x exits D. The claim is that

u(x) = E_{x}[f(B_{τ})]

is the solution of the Dirichlet problem. There are two things to check: 1. Δu = 0 in D.

2. u = f of ∂D. To check 1: We just have to check that u so defined satisfies the mean value property. So let S(r, x) be any sphere contained in D. Let σ be the first time that the Brownian motion starting at x hits S(r, x). Then

u(x) = E_{x}[f(B_{τ})] = E_{x}[E_{x}[f(B_{τ}) | F_{σ}]].

But by the strong Markov property

E_{x}[f(B_{τ}) | F_{σ}] = E_{B_{σ}}[f(B_{τ})] = u(B_{σ}).

So

u(x) = E_{x}[u(B_{σ})].

But B_{σ} ∈ S so if π(A) = P (B_{σ} ∈ A) for A ∈ S then

u(x) = ∫_{S} u(y)dπ(y).

So it only remains to check that π is the uniform probability measure on S, i.e. that starting at the center of S, the hitting distribution on S is spherically symmetric. This follows from the spherical symmetry of Brownian motion, which follows immediately from the spherical symmetry of its transition probabilities.

We leave the proof of 2 till next class.

Recurrence and transience of Brownian motion. Consider the annulus

D = {y ∈ R^{d} : δ < |y| < R}.

Let

f = \{ \begin{matrix}0 & on |y| = R; \\ 1 & on |y| = δ. \end{matrix}

Then

u(x) = E_{x}[f(B_{τ})] = P_{x}(B_{t} hits |y| = δ before |y| = R)

is the solution of the Dirichlet problem,

\begin{matrix}Δu = 0, & in D, \\ u = f, & on ∂D. \end{matrix}

But in this case there is a well known solution,

u(x) = \{ \begin{matrix}\frac{log R−log |x|}{log R−logδ} & d = 2 \\ \frac{|x|^{2−d}−R^{2−d}}{δ^{2−d}−R^{2−d}} & d ≥ 3. \end{matrix}

So now we know that P_{x}(B_{t} hits |y| = δ before |y| = R) is just this function above. Theorem. In two or more dimensions Brownian motion does not hit points.

Proof.

P_{x}(B_{t} hits 0 before |y| = R)

= lim_{δ→0} P_{x}(B_{t} hits |y| = δ before |y| = R)

= lim_{δ→0} \frac{log R − log |x|}{log R − logδ}

= 0.

Theorem. In two dimensions Brownian motion is recurrent. In three or more dimensions it wanders off to ∞.

Proof.

P_{x}(B_{t} ever hits |y| = δ)

= lim_{R→∞} P_{x}(B_{t} hits |y| = δ before |y| = R)

= \{ \begin{matrix}1 & d = 2; \\ (\frac{|x|}{δ})2−d & d ≥ 3. \end{matrix}

This proves that in d = 2 it is recurrent. In d ≥ 3, we have by the Markov property

P_{x}(B_{t} hits |y| = δ after time t) = ∫ \frac{e^{− \frac{|x−z|^{2}}{2t}}}{(2πt)^{d/2}} (\frac{|z|}{δ})^{2−d} dz.

This vanishes as t → ∞.

PROBLEMS.

1. Let B(t), t ≥ 0 be Brownian motion and let λ > 0. Show that

X(t) = tB(1/t) Y (t) = λ^{−1}B(λ^{2}t)

are also Brownian motions.

2. i. Let B_{t}, t ≥ 0 be Brownian motion, f_{1} and f_{2} functions on [0, 1] and let X_{i} =

∫_{0}^{1} f_{i}(t)B_{t}dt. Find the distribution of X = (X_{1}, X_{2}). ii. Compute the Fourier series of Brownian motion on [0, 1]. ie. if a_{n} = ∫_{0}^{1} e^{2πint}B_{t}dt

compute all finite dimensional distributions of the sequence a_{n}.

3. Suppose that X_{1}, X_{2}, … is a Markov chain with state space S and f : S → R. Is f(X_{1}), f(X_{2}), … a Markov chain? Is X_{n}, X_{n−1}, …, X_{1} ?

4. (Discrete queue) At unit intervals of time the server serves one customer in the queue (if there is even one customer, otherwise he stands around doing nothing) and then X_{i} new customers arrive in the queue. The random variables X_{1}, X_{2}, … are i.i.d. Show that the number of customers Q_{n} at time n form a Markov chain and write down the transition probabilities.

5. Let σ and τ be stopping time with respect to a filtration F_{t}, t ≥ 0. Show that τ + σ, min(τ, σ), and max(τ, σ) are all stopping times.

6. Let X_{n} be a Markov chain on Z^{d}, the d-dimensional integer lattice. Let τ_{z} be the

hitting time of z,

τ_{z} = min{n : X_{n} = z}.

Let σ_{N} be the first exit time from the ball |x| ≤ N,

σ_{N} = min{n : |X_{n}| > N}.

For |y|, |z| ≤ N let

G_{N}(y, z) = E_{y}[ ∑_{n=0}^{σ_{N} −1} 1_{{X_{n}=z}}].

Show that

P_{y}(τ_{z} ≤ σ_{N}) = \frac{G_{N}(y, z)}{G_{N}(z, z)}.

Here P_{y} and E_{y} refer to the process starting at y at time 0.

7. i. Let B(t), t ≥ 0 be a d-dimensional Brownian motion. Show that the density f(t) of B(t) satisfies the heat equation,

\frac{∂f}{∂t} = \frac{1}{2} ∑_{i=1}^{d} \frac{∂^{2}f}{∂x_{i}^{2}} .

ii. Let r(t) = |B_{t}| where |x| = \sqrt{x_{1}^{2} + ⋯ + x_{d}^{2}} is the Euclidean distance. Compute the density f(t) of r(t) and show that it satisfies Bessel’s equation,

\frac{∂f}{∂t} = \frac{1}{2} \frac{∂^{2}f}{∂r^{2}} + \frac{d − 1}{2r} \frac{∂f}{∂r} .