LECTURE 4

Stochastic processes. A stochastic process is an indexed set of random variables. Usually the index set is R_{+} or R (continuous time) or N_{+} or N (discrete time). The plus just means non-negative real numbers or non-negative integers. If you have n random variables X_{1}, …, X_{n} then you can just think of it as a random n-vector or a random element of R^{n} and all the statistical information is contained in the distribution function

F (x_{1}, …, x_{n}) = P (X_{1} ≤ x_{1}, …, X_{n} ≤ x_{n}).

Analogously a discrete stochastic process X_{1}, X_{2}, … can be thought of as a random sequence or a random element of ∏_{i=1}^{∞} R and a continuous stochastic process X_{t}, t ≥ 0 can be thought of as a random function or a random element of ∏_{t≥0} R. The statistical information is contained in the family of finite dimensional distributions

F_{t_{1},...,t_{n}}(x_{1}, …, x_{n}) = P (X_{t_{1}} ≤ x_{1}, …, X_{t_{n}} ≤ x_{n}).

Another way of saying this is that the statistical distribution of a random sequence or a random function is determined by the collection of all distributions of finite subsets.

It is not always natural to have R as the state space. For example X_{t}, t ≥ 0 could be the positions of a particle hopping around on some set S with a σ-field F. Then the finite dimensional distributions can be written

μ_{t_{1},...,t_{n}}(A_{1}, …, A_{n}) = P (X_{t_{1}} ∈ A_{1}, …, X_{t_{n}} ∈ A_{n})

where the sets A_{i} are elements of F.

Gaussian processes. A process is called Gaussian if all the finite dimensional distributions are Gausssians.

Martingales. Let (Ω, F, P) be a probability space and F_{t}, t ≥ 0 be a filtration (increasing family of sub-σ-fields), and X_{t}, t ≥ 0 a stochastic process with X_{t} ∈ L^{1} for all t ≥ 0. X_{t} is a martingale with respect to F_{t} if for any s ≤ t,

E[X_{t} | F_{s}] = X_{s} a.s.

(If the equality is replaced by ≥ it is a submartingale and by ≤ it is a supermartingale.) Note that it is automatic in the definition that X_{t} is measurable with respect to F_{t}. Markov chains. A sequence X_{0}, X_{1}, … is called a Markov chain if for any function

g,

E[g(X_{n+1}) | X_{1}, …, X_{n}) = E[g(X_{n+1}) | X_{n}].

In words: What you will do in the future depends only on where you are and not how you got there. Or: The future is independent of the past, given the present.

Examples. i. Random walk.

ii. (Ehrenfest model) There are two containers containing k balls. At each time step a ball is chosen at random and moved to the other container. X_{i} is the number of balls in the first container after the ith step.

iii. (Discrete time diffusions) A particle moves on the real line. If it is at x at time n then it makes a jump which is normally distributed with mean \frac{1}{n}b(x) and variance \frac{1}{n}a(x) where b(x) and a(x) ≥ 0 are some given functions.

Note that a Markov chain is completely determined by its initial distribution, i.e. the distribution of X_{0}, and the transition probabilities

P (X_{n+1} ∈ A | X_{n} = x).

This is because the finite dimensional distributions can be written in terms of these transition probabilities. In particular, by the Markov property, for any n_{0} ≤ n_{1} ≤ n_{2} we have the Chapman-Kolmogorov equation,

P (X_{n_{2}} ∈ A | X_{n_{0}} = x_{0}) = ∫ P (X_{n_{2}} ∈ A | X_{n_{1}} = x_{1})P (X_{n_{1}} ∈ dx_{1} | X_{n_{0}} = x_{0}).

Applying this repeatedly we get

\begin{matrix}P (X_{n_{1}} ∈ A_{1}, …, X_{n_{k}} ∈ A_{k}) \\ = ∫_{A_{k−1}} ⋯ ∫_{A_{1}} ∫ P (X_{0} ∈ dx_{0})P (X_{n_{1}} ∈ dx_{1} | X_{0} = x_{0}) ⋯ P (X_{n_{k}} ∈ A_{k} | X_{n_{k−1}} = x_{k−1}). \end{matrix}

If P (X_{n+1} ∈ A | X_{n} = x) does not depend on n then we say the chain is homogeneous and we can write it as p(x, A).

Discrete space. Note that all the integrations are summations if S is a discrete space. Also in this case the process is determined by all the p(x, {y}) which are then called p_{xy} and usually written as a matrix. Then the n step transition probabilities are given by P (X_{m+n} = y | X_{m} = x) = p_{xy}^{(n)} where p^{(n)} is the product of the matrix p with itself n times.

Suppose μ is a probability measure on S. Suppose we start the Markov chain with distribution μ as initial distribution, i.e. P (X_{0} = x) = μ({x}) = μ_{x} and then look at the distribution of X_{1}. It is just μp or p^{∗}μ, i.e.

P (X_{1} = x) = ∑_{y} μ_{y}p_{yx}.

A distribution μ on S is called invariant if μp = μ, i.e. for all x ∈ S,

μ_{x} = ∑_{y} μ_{y}p_{yx}.

An invariant measure is called reversible if for all x, y ∈ S,

μ_{x}p_{xy} = μ_{y}p_{yx}.

If you start a Markov chain with an invariant measure then the resulting process is stationary, i.e.

P (X_{n_{1}+m} ∈ A_{1}, …, X_{n_{k}+m} ∈ A_{k}) = P (X_{n_{1}} ∈ A_{1}, …, X_{n_{k}} ∈ A_{k}).

It just means you have no sense of absolute time.

If you start a Markov chain with a reversible measure then the resulting process looks the same backward and forward in time.

Warning. Not every Markov chain has an invariant measure let alone a reversible one. When they do, they may not be unique.

The ergodic theorem for finite state Markov chains says that if there is a number k such that p_{x,y}^{(k)} > 0 for all x and y, then there is a unique invariant measure μ and furthermore, for each y,

lim_{n→infty} p_{xy}^{(n)} = μ_{y}.

What happens is that for a finite state Markov chain with a unique invariant measure it forgets in time what distribution it started in, and more and more looks like a stationary process starting from the invariant measure. In general though, things can get pretty complicated.

Suppose that X_{n} is a time homogeneous Markov chain with transition matrix p_{xy} and let g be a function. Then pg is just the function

pg_{x} = ∑_{y} p_{xy}g_{y}.

Then

M_{n} = g_{X_{n}} − ∑_{i=0}^{n−1} pg_{X_{i}} − g_{X_{i}}

is a martingale with respect to F_{n} = σ(X_{1}, …, X_{n}) since

E[g_{X_{n}} | F_{n−1}] = E[g_{X_{n}} | X_{n−1}] = pg_{X_{n−1}}.

Markov processes. A process X_{t}, t ≥ 0 is called a Markov process if for any function g and any t ≥ s,

E[g(X_{t}) | X_{u}, 0 ≤ u ≤ s] = E[g(X_{t}) | X_{s}].

The process is uniquely determined by the initial distribution and the transition probabilities

p(s, x, t, A) = P (X_{t} ∈ A | X_{s} = x)

for s < t with

\begin{matrix}P (X_{t_{1}} ∈ A_{1}, …, X_{t_{n}} ∈ A_{n}) \\ = ∫_{A_{n−1}} ⋯ ∫_{A_{1}} ∫ P (X_{0} ∈ dx_{0})p(0, x_{0}, t_{1}, dx_{1})p(t_{1}, x_{1}, t_{2}, dx_{2}) ⋯ p(t_{n−1}, x_{n−1}, t_{n}, A_{n}). \end{matrix}

The Chapman-Kolmogorov equations read,

p(s, x, t, A) = ∫ p(s, x, u, dy)p(u, y, t, A) for s ≤ u ≤ t.

If the process is time homogeneous then there is another way to write this. For any function u define

P_{t}u(x) = E_{x}[u(X_{t})] = ∫ u(y)p(0, x, t, dy).

The subscript x on the expectation just notes that the process starts at x. All the P_{t} are linear operators which take functions to functions. It is clear that P_{0} is just the identity. The Chapman-Kolmogorov equations become

P_{t+s} = P_{t}P_{s}.

Its called a semigroup.

Brownian motion. The special case where

p(s, x, t, dy) = \frac{1}{\sqrt{2π(t − s)}}e^{− \frac{|x−y|^{2}}{2(t−s)}}

is called Brownian motion. What it means is that conditioned on X_{u}, u ≤ s, X_{t} = X_{s}+ an independent N (0, t − s).

Brownian motion and the heat equation. If we let

u(x, t) = P_{t}f(x)

then u solves the heat equation

\frac{∂u}{∂t} = \frac{1}{2} \frac{∂^{2}u}{∂x^{2}}, u(x, 0) = f(x).

Independent increments. By construction Brownian motion has independent increments, i.e. if 0 < t_{1} < ⋯ < t_{n} then

X_{t_{1}}, X_{t_{2}} − X_{t_{1}}, …, X_{t_{n}} − X_{t_{n−1}}

are independent.

Covariance. Clearly E[X_{t}] = ∫ x\frac{1}{\sqrt{2πt}}e^{− \frac{x^{2}}{2t}} dx = 0 and

E[(X_{t})^{2}] = ∫ x^{2} \frac{1}{\sqrt{2πt}}e^{− \frac{x^{2}}{2t}} dx = t.

The covariance is given by

E[X_{t}X_{s}] = E[(X_{t} − X_{s})X_{s}] + E[(X_{s})^{2}] = s

if s ≤ t since X_{t} − X_{s} is independent of X_{s} and mean 0.

Brownian motion as the limit of random walks. Let Y_{1}, Y_{2}, … be a simple symmetric random walk. Consider the process

X_{t}^{n} = \frac{1}{\sqrt{n}}Y_{⌊nt⌋}.

Here ⌊x⌋ is the greatest integer ≤ x. X_{t}^{n} is a random walk which jumps up or down 1/\sqrt{n} every time 1/n. Let us look at the process at times t_{1}, …, t_{m}. By the central limit theorem, for large n, the m-dimensional random vector

X_{t_{1}}^{n}, …, X_{t_{m}}^{n}

is approximately Gaussian. What is its covariance? Well,

E[(X_{t}^{n})^{2}] = E[(\frac{1}{\sqrt{n}}Y_{⌊nt⌋})^{2}] = t + O(1/n)

and

E[(X_{t}^{n} − X_{s}^{n})X_{s}^{n}] = O(1/n)

so in the limit we have

lim_{n→∞} E[X_{t}^{n}X_{s}^{n}] = min(t, s)

which says that in the limit we have a Brownian motion. More precisely, what we showed is that if F_{t_{1},...,t_{m}}^{n}(x_{1}, …, x_{m}) are the finite dimensional distributions of X_{t}^{n}, t ≥ 0, and F_{t_{1},...,t_{m}}(x_{1}, …, x_{m}) are the finite dimensional distributions of Brownian motion X_{t}, t ≥ 0, then

lim_{n→∞} F_{t_{1},...,t_{m}}^{n}(x_{1}, …, x_{m}) = F_{t_{1},...,t_{m}}(x_{1}, …, x_{m}).

PROBLEMS.

1. Show that for a Markov chain on a discrete state space the n step transition probabilities are obtained from the one step transition probabilities by multiplying the matrix by itself n times.

2. Let X_{1}, X_{2}, … be a Markov chain on the two state space S = {0, 1}. Let the trans-

ition matrix be ( \begin{matrix}a & b \\ c & d \end{matrix} ). Find all the invariant measures, check for reversibility and

determine conditions so that the ergodic theorem holds .

3. Let X_{i}, i = 1, 2, … be a simple random walk on the integers {1, 2, …, n} with prob-

ability p to step +1 and 1 − p to step −1. Write down the transition matrix assuming i. Absorbing barriers: When the walk gets to 1 or n it stays there forever. ii. Reflecting barriers: When the walk gets to 1 or n attempted jumps to 0 or n + 1

are interpreted as staying put. iii. Periodic boundary conditions: We just pretend n + 1 = 1 and 0 = n.

4. Write down the transition probabilities for the Ehrenfest model and show that the Binomial distribution is invariant and reversible.