Examples

Ω_{j}

1 \leq j \leq n

is a partition of

Ω

such that

P (Ω_{j}) > 0

F^{'} = σ (Ω_{j}, 1 \leq j \leq n)

. Prove that

E (X | F^{'}) = \sum_{j} \frac{1}{P (Ω_{j})} E (X; Ω_{j}) I_{Ω_{j}} .

Moreover on the set

Ω_{j}

we have

P (A | F^{'}) = P (A \cap Ω_{j}) / P (Ω_{j}) = : P (A | Ω_{j})

and therefore

P (A | F^{'}) = \sum_{j} P (A | Ω_{j}) I_{Ω_{j}} .

be a probability measure on

P

R^{2}

with density

ρ

X, Y

denote the projections

(x, y) \mapsto x

, then for all measurable

(x, y) \mapsto y

respectively. If

\int ρ (x, y) d x > 0

f : R^{2} \to [0, \infty]

(suggested solution):

E (f | Y = y) = \frac{\int f (x, y) ρ (x, y) d x}{\int ρ (x, y) d x},

where

E (f | Y = y) \in R

is a convenient notation for the value of

E (f | Y) : = E (f | σ (Y))

on the set

[Y = y]

. If

P

is the uniform distribution on

(a, b) \times (c, d)

, the normalized Haar measure

E (f | X = x) = \frac{1}{d - c} \int_{c}^{d} f (x, y) d y and E (f | Y = y) = \frac{1}{b - a} \int_{a}^{b} f (x, y) d x .

In polar coordinates

(x, y, z) = (\cos φ \cos θ, \sin φ \cos θ, \sin θ)

φ \in (0, 2 π)

θ \in (- π / 2, π / 2)

σ

on the

2

-sphere

S^{2}

has density

(4 π)^{- 1} \cos θ

. Thus the conditional expectations of

f : S^{2} \to R

given

θ

, respectively, are given by

φ

\begin{array}{rcl} E (f | θ) & = & \frac{1}{2 π} \int_{0}^{2 π} f (\cos φ \cos θ, \sin φ \cos θ, \sin θ) d φ and \\ E (f | φ) & = & \frac{1}{2} \int_{- π / 2}^{π / 2} f (\cos φ \cos θ, \sin φ \cos θ, \sin θ) \cos θ d θ . \end{array}

Markov chains and Markov operator

is a (homogeneous) Markov chain in a Polish space

(X_{n}, F_{n}, P^{x})

S

is an increasing sequence of sub

F_{n}

σ

-algebras of

F

X_{n}

is an

F_{n}

-measurable random variable, i.e.

X_{n} : (Ω, F_{n}) \to (S, B (S))

is a probability measure on

x \in S

P^{x}

S

such that

P^{x} (X_{0} = x) = 1

is called the Markov operator and

x \mapsto P^{x} (A)

is measurable for all

A \in F

There is a positive (i.e. $f \geq 0$ implies $P f \geq 0$ ) linear operator $P : B (S) \to B (S)$ mapping bounded measurable functions to bounded measurable functions such that for all $x \in S$ and all $f \in B (S)$ : $E^{x} (f (X_{n + 1}) | F_{n}) = P f (X_{n}) P^{x} -a.s.$ That's called the Markov property !

P

X_{n}

is a (homogeneous) Markov chain under

P^{x}

starting in

x

. If in addition

P : C_{b} (S) \to C_{b} (S)

, then the Markov chain is called a Feller chain and

P

a Feller operator . Sometimes

C_{b} (S)

is replaced with

C_{b u} (S)

C_{0} (S)

- in the latter case

S

is assumed to be locally compact (cf. section) - this is just a technical issue.

We have for all bounded measurable

f : S \to R

and all

x \in S

E^{x} (f (X_{n + 1}) | F_{n}) = E^{x} (f (X_{n + 1}) | X_{n})

- because the left hand side is

P f (X_{n})

, which is measurable with respect to the

σ

-algebra generated by

X_{n}

- and

E^{x} f (X_{1}) = E^{x} E^{x} (f (X_{1}) | F_{0}) = E^{x} P f (X_{0}) = P f (x) .

Prove by induction on

m

that for all

n, m \in N_{0}

E^{x} (f (X_{n + m}) | F_{n}) = P^{m} f (X_{n})

is a sequence of transition functions on

Transition functions

Let us put for

A \in B (S)

and

x \in S

P (x, A) : = P I_{A} (x) = P^{x} (X_{1} \in A) .

Then

A \mapsto P (x, A)

is a probability measure,

x \mapsto P (x, A)

is measurable and by the Markov property

P (X_{n}, A)

is the conditional probability that

X_{n + 1} \in A

given

F_{n}

, i.e.

P (X_{n}, A) = P^{x} (X_{n + 1} \in A | F_{n}) P^{x} - a . s .

These conditions simply say that

P (X_{n}, A)

is a regular conditional probability for

X_{n + 1}

given

F_{n}

. Therefore we also have

\forall f \in B (S) : E^{x} (f (X_{n + 1}) | F_{n}) = \int f (y) P (X_{n}, d y) .

Finally the Markov operator is given by

\begin{matrix} (MAR1) & P f (x) = \int f (y) P (x, d y) \end{matrix}

The mapping

P : S \times B (S) \to [0, 1]

(x, A) \mapsto P (x, A)

, is called a Markovian transition function.

P_{n} (x, A)

S

a sequence of measurable functions such that

p_{n} : S \to [0, 1]

\sum p_{n} (x) = 1

is a transition function. Describe the corresponding Markov chain.

P (x, A) : = \sum_{n} p_{n} (x) P_{n} (x, A)

n, m \in N_{0}

P^{x} (X_{n} \in A, X_{n + m} \in B) = \int_{A} P^{m} I_{B} (y) P_{X_{n}}^{x} (d y) .

By exam we have:

\begin{array}{rcl} P^{x} (X_{n} \in A, X_{n + m} \in B) & = & E^{x} (I_{A} (X_{n}) E^{x} (I_{B} (X_{n + m}) | F_{n})) \\ = & E^{x} (I_{A} (X_{n}) P^{m} I_{B} (X_{n})) = \int_{A} P^{m} I_{B} (y) P_{X_{n}}^{x} (d y) . \end{array}

Any transformation

θ : S \to S

defines a simple Markov chain, just put

P (x, A) = 1

θ (x) \in A

and otherwise

P (x, A) = 0

, i.e.

P (x, A) = δ_{θ (x)} (A)

be a finite undirected graph ,

G = (V, E)

V

the set of vertices and

E

the set of edges. For

x \neq y \in V

write

x \sim y

{x, y} \in E

and put

d (x) : = | {y \in V : y \sim x}

- the degree of the vertex

x

. As

G

is undirected we have

x \sim y

iff

y \sim x

G

is said to be regular , if every vertex has the same degree. Now put

P (x, {y}) = 1 / d (x)

y \sim x

is a Markovian transition function. We say the corresponding Markov chain

P (x, {y}) = 0

otherwise. Then

P (x, A)

X_{n}

performs a random walk on the graph

G

. Compute its Markov operator.

A lonely knight starts a random walk at the corner of a chess board (performing permissible moves only). Determine all vertices of the graph and all edges: two vertices i.e. two positions

x

of the knight are connected iff the knight can make a permissible move from position

y

x

to position

y

. Finally compute the degree of each vertex.

Define a Markov operator on a directed graph

G = (V, E)

More generally, if

S

is a finite (or countable) set and

p (x, y)

x, y \in S

a so called stochastic matrix , i.e.

for all $x, y \in S$ : $p (x, y) \geq 0$ ,
for all $x \in S$ : $\sum_{y} p (x, y) = 1$ .

Then

P (x, {y}) : = p (x, y)

is a Markovian transition function. Compute its Markov operator. Cf. e.g. R. Durrett, Probability: Theory and Examples

1. Show that the spectrum

S p e c (P)

of every stochstic matrix

P

- i.e. the set of its eigenvalues - is contained in the set

{z \in C : | z | \leq 1}

. 2. Which stochastic matrices

P \in M (n, R)

are orthogonal?

are stochastic matrices. Then their Kronecker product

P, Q

P \otimes Q

is also a stochastic matrix. If

S

and

T

are the state spaces of

P

and

Q

, respectively, then

S \times T

is a state space for

P \otimes Q

and the Markov chain is

(X_{n}, Y_{n})

and

P^{(x, y)} (X_{1} = u, Y_{1} = v) = P^{x} (X_{1} = u) P^{y} (Y_{1} = v) = p (x, u) q (y, v) .

Y_{1}, Y_{2}, \dots : (Ω, P) \to S

is an i.i.d. sequence in

S

. Put for

x \in S

P^{x} : = δ_{x} \otimes P

X_{0} (x, ω) = x

X_{j} (x, ω) = Y_{j} (ω)

is a Markov chain defined on

F_{n} = σ (X_{0}, \dots, X_{n})

. Then

(X_{n}, F_{n}, P^{x})

S \times Ω

with values in

S

and the Markov operator maps any

f \in B (S)

to the constant function

E f (Y_{1})

X_{1}, X_{2}, \dots

is an i.i.d. sequence in

R^{d}

P^{x} (S_{0} = x) = 1

. The Markov operator is given by:

S_{n + 1} : = S_{n} + X_{n + 1}

is a Markov chain on

R^{d}

with

F_{n} : = σ (X_{0}, \dots, X_{n})

P f (y) = \int_{R^{d}} f (y + z) μ (d z)

where

μ

is the distribution of

X_{1}

under

P^{x}

. Moreover if

E^{x} X_{1} = 0

(S_{n}, F)

is a martingale (under

P^{x}

), i.e. for all

n \in N_{0}

E^{x} (S_{n + 1} | F_{n}) = S_{n}

be a Markov chain with Markov operator

(X_{n}, F_{n}, P^{x})

P

. Then for all bounded measurable

f : S \to R

E^{x} (f (X_{n}) | F_{m}) = P^{n - m} f (X_{m})

. In particular

P^{n - m} f (X_{m})

m = 0, \dots, n

, is a martingale.

By the Markov property and exam we have:

E^{x} (f (X_{n}) | F_{m}) = P^{n - m} f (X_{m})

be a Markov chain with Markov operator

(X_{n}, F_{n}, P^{x})

P

and put

L : = P - 1

. Then for all bounded measurable

f : S \to R

M_{n}^{f} : = f (X_{n}) - f (X_{0}) - \sum_{j = 0}^{n - 1} L f (X_{j})

is a martingale with respect to

P^{x}

, i.e. for all

n \in N_{0}

E^{x} (M_{n + 1}^{f} | F_{n}) = M_{n}^{f}

be i.i.d. random variables uniformly distributed on the sphere

Z_{1}, Z_{2}, \dots

S^{d - 1}

(cf. e.g. section). For a bounded domain

D

R^{d}

put for any

x \in \overset{―}{D}

R (x) : = d (x, D^{c})

S_{0} : = x

and

S_{n + 1} : = S_{n} + R (S_{n}) Z_{n + 1}

. Then

S_{n}

is a Markov chain with respect to

F_{n} : = σ (Z_{1}, \dots, Z_{n})

and the Markov operator is given by:

P f (y) = \int_{S^{d - 1}} f (y + R (y) z) σ (d z) .

where

σ

denotes the normalized Haar measure on

S^{d - 1}

For

f \in B (R^{d})

we get by independence of

Z_{n + 1}

from

F_{n}

\begin{array}{rcl} P f (S_{n}) & = & E (f (S_{n + 1}) | F_{n}) \\ = & E (f (S_{n} + R (S_{n}) Z_{n + 1}) | F_{n}) = \int f (S_{n} + R (S_{n}) z) σ (d z) . \end{array}

Write a program which generates a random variable uniformly distributed on the sphere

S^{d - 1}

, cf. section. Suggested solution.

is a Markov chain with respect to

| a | < 1

Z_{1}, Z_{2}, \dots

i.i.d. in

S = R^{d}

with distribution

μ

and put

X_{n} = a X_{n - 1} + Z_{n}

. Then

X_{n}

F_{n} = σ (Z_{1}, \dots, Z_{n})

. This chain is called an autoregressiv moving average process, ARMAP for short. Show that its Markov operator is given by

P f (y) = \int_{R^{d}} f (a y + z) μ (d z)

2. In case

μ

is standard normal we get (suggested solution):

P^{n} f (y) = \int_{R^{d}} f (a^{n} y + z \sqrt{\frac{1 - a^{2 n}}{1 - a^{2}}}) μ (d z) .

Shift operator and invariant measures

As we have already seen any tansformation

θ : S \to S

defines a simple Markov chain. Next we are going to establish the converse result: every Markov chain

X_{n}

in a Polish space

S

may be seen as a transformation on

Ω = S^{N}

. For this it suffices to assume that there is a mapping

Θ : Ω \to Ω

such that for all

n

X_{n} \circ Θ = X_{n + 1};

Θ

is called the shift operator of the Markov chain and its existence usually follows from the construction of the underlying probability space: this operator is just the Bernoulli shift for the standard construction! Now the Markov property admits an important extension : Let

F : Ω \to R

be bounded and measurable with respect to the

σ

-algebra

F_{\infty}^{X}

generated by

X_{0}, X_{1}, \dots

. Then for all

x \in S

and alle

n \geq 0

\begin{matrix} (MAR2) & E^{x} (F \circ Θ_{n} | F_{n}) = E^{X_{n}} F P^{x} -a.s. \end{matrix}

where

E^{X_{n}} F

is the mapping

ω \mapsto E^{X_{n} (ω)} F

(which is

σ (X_{n})

-measurable) and

Θ_{n}

is a short hand for the

n

-fold product:

Θ \circ \dots \circ Θ

. The proof is very similar to the proof of proposition and can be found in almost all text books on Markov chains, in particular in R. Durrett, Probability: Theory and Examples. For e.g.

F = f (X_{m})

we have

F \circ Θ_{n} = f (X_{m + n})

and

E^{X_{n}} f (X_{m}) = P^{m} f (X_{n})

; hence in this special case

(MAR2)

is just exam.

n, m \in N_{0}

, all

A \in F_{n}

B \in B (S)

(compare exam):

P^{x} (X_{n + m} \in B, A) = E^{x} (P^{m} I_{B} (X_{n}); A)

Since

X_{n + m} \in B

iff

X_{n} \circ Θ_{m} \in B

we infer from e.g. the extended Markov property:

P^{x} (X_{n + m} \in B, A) = E^{x} (E^{x} (I_{[X_{m} \in B]} \circ Θ_{n} | F_{n}) I_{A}) = E^{x} (P^{X_{n}} (X_{m} \in B) I_{A}) = E^{x} (P^{m} I_{B} (X_{n}); A) .

Finally let

μ

be a probability measure on

S

and put for all

A \in F

P^{μ} (A) : = \int P^{x} (A) μ (d x)

Then

P^{μ}

is a probability measure on

Ω

F \in L_{1} (P^{μ})

E^{μ} F = \int E^{x} F μ (d x)

Actually under

P^{μ}

Therefore the initial distribution is

X_{0}, X_{1}, X_{2}, \dots

is a Markov chain in

S

with

P^{μ} (X_{0} \in B) = \int P^{x} (X_{0} \in B) μ (d x) = \int_{B} 1 μ (d x) = μ (B) .

μ

. To check the Markov property, i.e.

E^{μ} (f (X_{n + 1}) | F_{n}) = P f (X_{n})

, we notice that for all

x \in S

E^{x} (f (X_{n + 1}) | F_{n}) = P f (X_{n})

and thus for all

A \in F_{n}

\begin{array}{rcl} E^{μ} (P f (X_{n}); A) & = & \int_{S} E^{x} (P f (X_{n}); A) d μ \\ = & \int_{S} E^{x} (E^{x} (f (X_{n + 1}) | F_{n}); A) d μ \\ = & \int_{S} E^{x} (f (X_{n + 1}); A) d μ = E^{μ} (f (X_{n + 1}); A) . \end{array}

Hence by the definition of conditional expectations

P^{μ}

a.e.:

E^{μ} (f (X_{n + 1}) | F_{n}) = P f (X_{n})

μ

is said to be an invariant measure for the Markov chain, if

\begin{matrix} (MAR3) & \forall B \in B (S) : P^{μ} (X_{n + 1} \in B) = P^{μ} (X_{n} \in B) \end{matrix}

This shows that

μ

is invariant iff for all

n \in N_{0}

P^{μ} (X_{n} \in A) = μ (A)

. We also say that under

P^{μ}

is stationary . Can we check stationarity by just inspecting the Markov operator? Yes! because this holds if and only if

X_{0}, X_{1}, \dots

\begin{matrix} (MAR4) & \forall f \in B (S) : \int P f d μ = \int f d μ . \end{matrix}

This is because the Markov property implies (compare exam or the previous reasoning for

A = Ω

and

f = I_{B}

P^{μ} (X_{n + 1} \in B) = E^{μ} P I_{B} (X_{n}) = \int P I_{B} d P_{X_{n}}^{μ} .

Thus if

μ

is invariant, then for all

n

P_{X_{n}}^{μ} = μ

and in particular

P^{μ} (X_{n + 1} \in B) = μ (B)

. Hence for all

B \in B (S)

\int P I_{B} d μ = μ (B)

and this is easily seen to be equivalent to

(MAR4)

. Conversely if

(MAR4)

holds, then we get for

n = 0

P^{μ} (X_{1} \in B) = \int P I_{B} d μ = μ (B) = P^{μ} (X_{0} \in B)

and the assertion follows by induction on

n

. We notice that

(MAR4)

also makes sense for arbitrary measures

μ

Lebesgue measure is an invariant measure both for the Markov chain in exam and in exam.

However we will almost exclusively stick to probability measures!

μ = P_{Y_{1}}

is the distribution of

Y_{1}

is invariant for the Markov chain

μ

is invariant for the Markov chain in exam. This Markov chain is also called a Bernoulli scheme, cf. also exam.

μ

X_{n}

, then for all

n \in N_{0}

Next we verify that the invariance of

A, B \in B (S)

P^{μ} (X_{n} \in A, X_{n + m} \in B) = \int_{A} P^{m} I_{B} (y) μ (d y) .

μ

implies invariance of

P^{μ}

by the shift operator

Θ

preserves the probability measure

Θ

P^{μ}

Ω

: indeed, by the extended Markov property

(MAR2)

we have for an invariant measure

μ

and any bounded

F_{\infty}^{X}

-measurable

F : Ω \to R_{0}^{+}

E^{μ} (F \circ Θ) = E^{μ} E^{μ} (F \circ Θ | F_{1}) = E^{μ} E^{X_{1}} F = E^{μ} F,

i.e.

P^{μ}

is a probability measure on

(Ω, F)

invariant under

Θ

. Thus any Markov chain with invariant measure can be regarded as a sort of discrete dynamical system on

(Ω, F)

discussed in the previous section, provided

Ω

is Polish!

Given a stochastic matrix

p (x, y)

on an discrete Polish space

S

. The associated Markov operator

P

. 1. If for each finite subset

ℓ_{\infty} (S)

K

S

and each

ϵ > 0

there is another finite subset

E

S

such that for all

x \notin E

P (x, K) < ϵ

(i.e.

P (., K) \in c_{0} (S)

), then

P

c_{0} (S)

and thus

P^{*}

is isometrically isomorphic to

ℓ_{1} (S)

(the dual of

c_{0} (S)

ℓ_{1} (S)

). 2. A (signed) measure

μ

S

is just a vector

μ \in ℓ_{1} (S)

. Verify that if

P

c_{0} (S)

then

μ

is invariant iff

P^{*} μ = μ

Give an example of an infinite stochastic matrix such that

\forall x \in S : \sum_{y \in S} μ (y) p (y, x) = μ (x) .

P

doesn't map

c_{0} (S)

into

c_{0} (S)

is called doubly stochastic if for all

A stochstic matrix

P = (p (x, y))

x, y

\sum_{z} p (x, z) = \sum_{z} p (z, y) = 1

. 1. The normalized counting measure is an invariant probability measure for

P

. 2. A finite undirected graph

G = (V, E)

(cf. exam) is doubly stochastic iff for all

y \in V

\sum_{z \sim y} \frac{1}{d (z)} = 1

. 3. Permutation matrices are doubly stochastic.

are stochastic matrices with invariant measures

P, Q

μ

, respectively. Then their Kronecker product

ν

P \otimes Q

(cf. exam) has invariant measure

μ \otimes ν

Ergodicity

Formally the Markov operator

P

is only defined on the vector space

B (S)

of bounded, measurable functions on

S

. Now the existence of an invariant measures

μ

allows us to define

P

as a positive, linear contraction on the Hilbert space

L_{2} (μ)

μ

is invariant then

P : L_{2} (μ) \to L_{2} (μ)

is a contraction.

Proof :

1. By Jensen's inequality we have for all

f \in B (S)

and all

x \in S

(P f)^{2} (x) = (\int f (y) P (x, d y))^{2} \leq \int f (y)^{2} P (x, d y) = P (f^{2}) (x)

and by invariance for

f \in B (S) \cap L_{2} (μ)

\int (P f)^{2} d μ \leq \int P (f^{2}) d μ = \int f^{2} d μ .

Since

B (S) \cap L_{2} (μ)

is dense in

L_{2} (μ)

, there is a unique bounded, linear extension of

P

L_{2} (μ)

and this extension is obviously a positive contraction.

qed

μ

is invariant for the Markov operator

P

, then for all

f \geq 0

E n t (P f) \leq E n t (f)

, where

E n t (f) : = \int f \log f d μ

is called the entropy of

f

with respect to

μ

. Beware, in physics and especially in thermodynamics the entropy is defined by

- \int f \log f d μ

! Hence, to physicists the entropy of a Markov chain increases as time goes on.

φ : x \mapsto x \log x

is convex on

R^{+}

, we infer from Jensen's inequality:

\int φ (P f (x)) μ (d x) = \int φ (\int f (y) P (x, d y)) μ (d x) \leq \int P (φ (f)) (x) μ (d x) = \int φ (f) d μ .

μ

is invariant for the Markov operator

P

with invariant probability measure

P

is a contraction on all

L_{p} (μ)

1 \leq p \leq \infty

A Markov operator

P

S

μ

is said to be ergodic if

f \in L_{2} (μ)

is ergodic iff all eigen functions of

P f = f

imply that

f

μ

a.e. constant.

Hence

P : L_{2} (μ) \to L_{2} (μ)

P

for the eigenvalue

1

are constant functions.

The Markov operator in exam is evidently ergodic.
If $(p (x, y))$ is a finite stochastic matrix with a unique invariant probability measure, then the associated Markov operator is ergodic, cf. proposition.

is a stochastic matrices with invariant measures

P

μ

. If

P

is ergodic on

L_{2} (μ)

, then the Kronecker product

P \otimes P

(cf. exam) need not be ergodic on

L_{2} (μ \otimes μ)

. Hint: If

- 1

is an eigenvalue of

P

with eigen vector

x

, then

(P \otimes P) x \otimes x = x \otimes x

. You may take for

P

the permutation matrix of the permutation

(2, 1) \in S (2)

Let us remark that there is another commonly used notion of ergodicity for stochastic matrices (irreducible and aperiodic states), which is a bit stronger than the notion we employ! However, we will never refer to that stronger notion.

Any measure

μ

supported on

\partial D

, is an invaraint measure of the Markov operator

μ ((\partial D)^{c}) = 0

P

in exam. 2. If

f : D \to R

is harmonic then

P f = f

. Hence

P

is not ergodic, no matter what measure we take.

μ

is supported on

\partial D

, then for all bounded

f \in B (\overset{―}{D})

\int P f d μ = \int \int f (y + R (y) z) σ (d z) μ (d y) = \int \int f (y + R (y) z) μ (d y) σ (d z) = \int \int f (y) μ (d y) σ (d z) = \int f (y) μ (d y) .

f

is harmonic iff for all

x \in D

and all

r > 0

satisfying

B_{r} (x) \subseteq D

\int f (x + r z) σ (d z) = f (x)

. Hence for harmonic functions

f

we have

P f = f

.
Remark: Starting at

x \in D

the sequence

X_{n}

converges 'weakly' to a random variable

X

, whose distribution is the harmonic measure on

\partial D

with respect to

x

. Hence for all continuous

f : \partial D \to R

the function

u (x) : = E^{x} f (X)

is the harmonic extension

u : D \to R

f

into the interior of

D

Invariant measures on finite sets

For every finite stochastic matrix

P = (p (x, y))

we have

\dim \ker (P^{*} - 1) \geq 1

, because

1

is an eigenvalue for

P

and thus

\bar{1} = 1

is an eigenvalue for

P^{*}

- the spectrum of

P^{*}

is the complex conjugate of the spectrum of

P

! Thus

\dim \ker (P^{*} - 1) \geq 1

. Yet we don't know if

\ker (P^{*} - 1)

contains a measure.

Given a stochastic matrix on a finite set

S

. Then there is an invariant probability measure

μ

. Moreover if there is a unique invariant probability measure

μ

, then for any probability measure

ν

S

A_{n}^{*} ν : = \frac{1}{n} \sum_{j = 0}^{n - 1} P^{* j} ν

converges to

μ

and for all functions

f : S \to R

converges to the constant function

A_{n} f : = \frac{1}{n} \sum_{j = 0}^{n - 1} P^{j} f

\sum_{y} f (y) μ (y)

and thus

P

is ergodic. For a more general result cf. exam.

Proof :

1. Suppose

| S | = n

, then the associated Markov operator

P : ℓ_{\infty}^{n} \to ℓ_{\infty}^{n}

and its adjoint

P^{*} : ℓ_{1}^{n} \to ℓ_{1}^{n}

are given by

P f (x) : = \sum_{y} p (x, y) f (y) and P^{*} μ (x) : = \sum_{y} p (y, x) μ (y) .

Let

M_{1} \subseteq ℓ_{1}^{n}

be the set of probability measures on

S

M_{1}

is compact and convex. Since

P^{*} (M_{1}) \subseteq M_{1}

we infer from Brouwer's fixed point theorem that there is some

μ \in M_{1}

such that

P^{*} μ = μ

.
2. Alternatively and more elementary we may take any

ν \in M_{1}

and define

\forall n \in N : μ_{n} : = A_{n}^{*} ν

Then

‖ P^{*} μ_{n} - μ_{n} ‖ \leq 2 / n

and thus any accumulation point

μ

of the sequence

μ_{n}

is a fixed point of

P^{*}

. This also shows that

A_{n}^{*} ν

converges to

μ

μ

is the unique invariant probability measure. Hence for all

f : S \to R

A_{n} f (x) = \int A_{n} f d δ_{x} = \int f d A_{n}^{*} δ_{x} \to \int f d μ = \sum_{y} f (y) μ (y) .

P f = f

, then for all

n

f = A_{n} f \to \int f d μ

and therefore

f

must be constant

qed

Noteworthy the alternative proof also works if the sequence

μ_{n}

has some accumulation point with respect to some metric

d

, say, which is weaker than the metric defined by the norm, i.e.

d (x, y) \leq C ‖ x - y ‖

for some constant

C > 0

.
Computationally the presented proofs don't work well because averaging gives a pretty slow algorithm. Usually a certain convex combination

Q

of the powers of

P

yields a stochastic matrix with strictly positive entries (cf. exam) and the sequence

Q^{* n} ν

for any

ν \in M_{1}

converges (exponentially fast) to the invariant measure

μ \in M_{1}

Q

, which is also the invariant measure of

P

, provided it's unique.

Given a finite set

S

and a transformation

θ : S \to S

. Prove that there is a

θ

invariant probability measure

μ

S

. Algebraically that means that there is a measure

μ \in M_{1}

such that for all

x \in S

μ (θ^{- 1} (x)) = μ (x)

Stochastic matrices are frequently used in text analysis and text generation, cf. e.g. text generation. Here is a C code generating random text based on Molly's soliloquy in J. Joyce's Ulysses. This can also be used to get a certain graph structure of poems: e.g. Poe's poem Alone.

are measurable with respect to

F_{n}

is a filtration and

X_{n} : Ω \to S

F_{n}

. Assume that there is some

m \in N

such that for all bounded measurable

f : S \to R

-Markov chain. Verify that

n

E (f (X_{n + 1}) | F_{n}) = E (f (X_{n + 1}) | σ (X_{n}, \dots, X_{n - m + 1})) .

Then

X_{n}

is called an

m

Z_{n} : = (X_{n}, \dots, X_{n - m + 1})

is a Markov chain with respect to

F_{n}

S^{m}

Given a finite stochastic matrix

This C code generates text by means of an

m

-Markov chain. Short texts such as Time will almost be reproduced (for

m = 2

), wheras long texts such as Mann get jumbled (for

m \leq 2

P = (p (x, y))

. If

μ

is an invariant probability measure for

P

S_{0} = {x \in S : μ (x) = 0}

then for all

y \in S ∖ S_{0}

. The Markov chain will never jump from a point in

x \in S_{0}

p (y, x) = 0

S ∖ S_{0}

to any point in

S_{0}

A finite stochastic matrix

P = (p (x, y))

has a unique invariant probability measure if and only if

\dim \ker (P^{*} - 1) = 1

. Solution by T. Speckhofer

We will see (cf. theorem) that if for all

x, y \in S

p (x, y) > 0

, then

\dim \ker (P^{*} - 1) = 1

and the unique invariant probability measure

μ

is strictly positive, i.e. for all

x \in S

μ (x) > 0

is linear (and diagonalizable) such that all eigenvalues

P^{*} : ℓ_{1}^{n} \to ℓ_{1}^{n}

λ

satisfy:

| λ | \leq 1

. Prove that the sequence

A_{n}^{*} : = \frac{1}{n} (1 + P^{*} μ + \dots + P^{* n - 1})

converges to the projection

Q

onto the kernel of

P^{*} - 1

(

Q

is defined by

Q | \ker (P^{*} - λ) = 0

for all eigenvalues

λ \neq 1

. 3. If there is some eigenvalue

Q

is the identity on

\ker (P^{*} - 1)

). 2. If all eigenvalues

λ

satisfy:

| λ | < 1

λ = 1

. Then the sequence

P^{* n}

converges to

Q μ

λ \neq 1

satisfying

| λ | = 1

, then the sequence

P^{* n}

doesn't converge.

Determine all invariant probability measures of the following stochastic matrices:

(\begin{array}{ccc} 0 & 1 & 0 \\ 0 & .5 & 0.5 \\ .5 & 0 & .5 \end{array}), (\begin{array}{ccc} .5 & .3 & .2 \\ .2 & .8 & 0 \\ .3 & .3 & .4 \end{array}), (\begin{array}{ccc} .6 & .1 & .3 \\ .3 & .6 & .1 \\ .1 & .3 & .6 \end{array}),

Any two state (

S = {1, 2}

) stochastic matrix is given by

P : = (\begin{array}{ccc} 1 - a & a \\ b & 1 - b \end{array}), a, b \in [0, 1] .

P \neq 1

Find the stochastic matrix describing the random walk on the vertices of the

a + b > 0

The invariant probability measure is given by $μ (1) = a / (a + b)$ , $μ (2) = b / (a + b)$ .
Compute all eigenvalues and eigen spaces of $P$ .
Prove that for all $n \in N$ : $P^{n} = \frac{1}{a + b} (\begin{array}{ccc} a & a \\ b & b \end{array}) + \frac{(1 - a - b)^{n}}{a + b} (\begin{array}{ccc} a & - b \\ - a & b \end{array})$
Give an example of a symmetric stochastic matrix $P$ such that $P^{n}$ does not converge!

3

-dimensional unit ball of

ℓ_{1}^{3}

. What about

ℓ_{1}^{n}

Reversible Markov chains

X_{n}

(or

μ

) is said to be reversible if for all

A, B \in B (S)

\begin{matrix} (MAR5) & P^{μ} (X_{n} \in A, X_{n + 1} \in B) = P^{μ} (X_{n + 1} \in A, X_{n} \in B) \end{matrix}

A reversible measure is invariant, for

P^{μ} (X_{n} \in A) = P^{μ} (X_{n} \in A, X_{n + 1} \in S) = P^{μ} (X_{n + 1} \in A, X_{n} \in S) = P^{μ} (X_{n + 1} \in A) .

Moreover, for all

f, g \in B (S)

\begin{array}{rcl} E^{μ} (f (X_{n}) g (X_{n + 1})) & = & E^{μ} (f (X_{n}) E^{μ} (g (X_{n + 1}) | F_{n})) \\ = & E^{μ} (f (X_{n}) P g (X_{n})) = \int f (x) P g (x) μ (d x) \end{array}

and analogously

E^{μ} (f (X_{n + 1}) g (X_{n})) = \int P f (x) g (x) μ (d x)

. Thus for all

f, g \in B (S)

\int f \cdot P g d μ = \int P f \cdot g d μ

μ

is reversible, then

P : L_{2} (μ) \to L_{2} (μ)

is self-adjoint.

Proof :

This follows immediately from the relation

\int f . P g d μ = \int P f \cdot g d μ

for all

f, g \in B (S)

, and the fact that

B (S)

is dense in

L_{2} (μ)

qed

Conversely, if the Markov operator

P : L_{2} (μ) \to L_{2} (μ)

is self-adjoint then the corresponding Markov chain is reversible.

A Markov operator

P : L_{2} (μ) \to L_{2} (μ)

is self-adjoint iff for all disjoint subsets

A, B \in B (S)

\int_{A} P (x, B) μ (d x) = \int_{B} P (x, A) μ (d x) .

Proof :

For arbitrary

A, B \in B (S)

put

D : = A \cap B

. Since both

A ∖ D

B ∖ D

D

are disjoint we conclude by the additivity of

B ∖ D

C \mapsto P (x, C)

\begin{array}{rcl} \int_{A} P (x, B) μ (d x) & = & \int_{D} P (x, B) μ (d x) + \int_{A ∖ D} P (x, B) μ (d x) \\ = & \int_{D} P (x, D) μ (d x) + \int_{D} P (x, B ∖ D) μ (d x) + \int_{A ∖ D} P (x, B) μ (d x) \\ = & \int_{D} P (x, D) μ (d x) + \int_{B ∖ D} P (x, D) μ (d x) + \int_{B} P (x, A ∖ D) μ (d x) \\ = & \int_{B} P (x, D) μ (d x) + \int_{B} P (x, A ∖ D) μ (d x) = \int_{B} P (x, A) μ (d x) . \end{array}

qed

Put

D = \sum_{x} d (x) = 2 | E |

. Then the probability measure

μ (x) : = d (x) / D

is reversible for the Markov chain in exam. In particular the normalized counting measure is a reversible probability measure for the random walk on a regular undirected graph. Suggested solution.

μ = P_{Y_{1}}

is the distribution of

Y_{1}

, then the Markov chain in exam is reversible with respect to

μ

be a convex and symmetric body in

B

R^{d}

(i.e.

B

is compact, convex, symmetric and

B^{\circ} \neq \emptyset

D

a bounded domain in

R^{d}

an i.i.d. sequence uniformly distributed on

Z_{n}

B

. Put

X_{n + 1} = X_{n} + Z_{n + 1}

X_{n} + Z_{n + 1} \in D

is a Markov chain and the Markov operator is given by:

X_{n + 1} = X_{n}

otherwise. Then

X_{n}

P f (x) = \frac{1}{λ (B)} (f (x) λ (D^{c} \cap (B + x)) + \int_{D \cap (B + x)} f (y) d y) .

Moreover the normalized Lebesgue measure on

D

is a reversible probability measure.