guide:49ad1c72ef

[math] \newcommand{\R}{\mathbb{R}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\N}{\mathbb{N}} \newcommand{\C}{\mathbb{C}} \newcommand{\Rbar}{\overline{\mathbb{R}}} \newcommand{\Bbar}{\overline{\mathcal{B}}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\E}{\mathbb{E}} \newcommand{\p}{\mathbb{P}} \newcommand{\one}{\mathds{1}} \newcommand{\0}{\mathcal{O}} \newcommand{\mat}{\textnormal{Mat}} \newcommand{\sign}{\textnormal{sign}} \newcommand{\CP}{\mathcal{P}} \newcommand{\CT}{\mathcal{T}} \newcommand{\CY}{\mathcal{Y}} \newcommand{\F}{\mathcal{F}} \newcommand{\mathds}{\mathbb}[/math]

Definition (Invariant measure)

Let [math]\mu[/math] be a positive measure on [math]E[/math] such that [math]\mu(x) \lt \infty[/math] for all [math]x\in E[/math] and [math]\mu\not\equiv 0[/math]. We say that [math]\mu[/math] is invariant for the transition matrix [math]Q[/math] if for all [math]y\in E[/math] we get

[[math]] \mu(y)=\sum_{x\in E}\mu(x)Q(x,y). [[/math]]

With matrix notation, this means

[[math]] \mu Q=\mu. [[/math]]

Since for all [math]n\in\N[/math], [math]Q_n=Q^n[/math], we have [math]\mu Q_n\mu=\mu[/math].

Interpretation

Assume that [math]\mu(E) \lt \infty[/math], which is always the case when [math]E[/math] is finite. We can assume that [math]\mu(E)=1[/math]. Then for all measurable maps [math]f:E\to\R_+[/math], we get that

[[math]] \E_\mu[f(X_1)]=\sum_{x\in E}\mu(x)\sum_{y\in E}Q(x,y)f(y)=\sum_{y\in E}f(y)\sum_{x\in E}\mu(x)Q(x,y)=\sum_{y\in E}\mu(y)f(y). [[/math]]

Hence under [math]\p_\mu[/math], we get that [math]X_1[/math] [math]{law}\atop{=}[/math] [math]X_0\sim \mu[/math]. Using the fact that [math]\mu Q_n=\mu[/math], we show that under [math]\p_\mu[/math], we get that [math]X_n\sim \mu[/math]. For all measurable maps [math]F:\Omega\to\R_+[/math] we have

[[math]] \E_\mu[F\circ \Theta_\one]=\E_\mu[\E_{X_1}[F]]=\sum_{x\in E}\mu(x)\E_x[F]=\E_\mu[F], [[/math]]

which implies that under [math]\p_\mu[/math], we get that [math](X_{1+n})_{n\geq 0}[/math] has the same law as [math](X_n)_{n\geq 0}[/math].

Example

For the r.v. on [math]\mathbb{Z}^d[/math], we get [math]Q(x,y)=(y,x)[/math]. One then immediately checks that the counting measure on [math]\mathbb{Z}^d[/math] is invariant.

Definition (Reversible measure)

Let [math]\mu[/math] be positive measure on [math]E[/math] such that [math]\mu(x) \lt \infty[/math] for all [math]x\in E[/math]. [math]\mu[/math] is said to be reversible if for all [math]x,y\in E[/math] we get that

[[math]] \mu(x)Q(x,y)=\mu(y)Q(y,x). [[/math]]

Proposition

A reversible measure is invariant.

Show Proof

If [math]\mu[/math] is reversible, we get that

[[math]] \sum_{x\in E}\mu(x)Q(x,y)=\sum_{x\in E}\mu(y)Q(y,x)=\mu(y). [[/math]]

■

There exists invariant measures which are not reversible, for example the counting measure is not reversible if the [math]\mathcal{G}[/math] is not symmetric, i.e. [math]\mathcal{G}(x)=\mathcal{G}(-x)[/math].

Example

[Random walk on a graph]

The measure [math]\mu(x)=\vert A_x\vert[/math] is reversible. Indeed, if [math]\{x,y\}\in A[/math], we get

[[math]] \mu(x)Q(x,y)=\vert A_x\vert\frac{1}{\vert A_x\vert}=1=\mu(y)Q(y,x). [[/math]]

Example

[Ehrenfest's model] This is the Markov chain on [math]\{1,...,k\}[/math] with transition matrix

[[math]] \begin{cases}Q(j,j+1)=\frac{k-j}{k},& 0\leq j\leq k-1\\ Q(j,j-1)=\frac{j}{k},&1\leq j\leq k\end{cases} [[/math]]

A measure [math]\mu[/math] is reversible if and only if for [math]0\leq j\leq k-1[/math] we have

[[math]] \mu(j)\frac{k-j}{k}=\mu(j+1)\frac{j+1}{k}. [[/math]]

One can check that [math]\mu(j)=\binom{k}{j}[/math] is a solution.

Theorem

Let [math]x\in E[/math] be recurrent. The formula

[[math]] \mu(y)=\E_x\left[\sum_{k=0}^{H_x-1}\one_{\{ X_k=y\}}\right] [[/math]]

defines an invariant measure. Moreover, [math]\mu(y) \gt 0[/math] if and only if [math]y[/math] is in the same recurrence class as [math]x[/math].

Show Proof

Let us first note that if [math]y[/math] is not in the same recurrence class as [math]x[/math], then

[[math]] \E_x[N_y]=U(x,y)=0, [[/math]]

which implies that [math]\mu(y)=0[/math]. For [math]y\in E[/math], we get that

[[math]] \begin{multline*} \mu(y)=\E_x\left[\sum_{k=1}^{H_x}\one_{\{ X_k=y\}}\right]=\sum_{z\in E}\E_x\left[\sum_{k=1}^{H_x}\one_{\{ X_{k-1}=z,X_k=y\}}\right]=\sum_{z\in E}\sum_{k\geq 1}\E_x\left[\one_{\{k\leq H_x,X_{k-1}=z\}}\one_{\{ X_k=y\}}\right]\\=\sum_{z\in E}\sum_{k\geq 1}\E_x\left[\one_{\{k\leq H_x,X_{k-1}=z\}}\right]=\sum_{z\in E}\E_x\left[\sum_{k=1}^{H_x}\one_{X_{k-1}=z}\right]Q(z,y)=\sum_{z\in E}\mu(z)Q(z,y). \end{multline*} [[/math]]

We showed that [math]\mu Q=\mu[/math]. Thus, it follows that [math]\mu Q_n=\mu[/math] for all [math]n\geq 0[/math]. In particular, we get

[[math]] \mu(x)=1=\sum_{z\in E}\mu(z)Q_n(z,x). [[/math]]

Let [math]y[/math] be in the same recurrence class as [math]x[/math]. Then there exists some [math]n\geq 0[/math] such that [math]Q_n(y,x) \gt 0[/math], which implies that

[[math]] \mu(y) \lt \infty. [[/math]]

We can also find [math]m\geq 0[/math] such that [math]Q_m(x,y) \gt 0[/math] and

[[math]] \mu(y)=\sum_{z\in E}\mu(z)Q_m(z,y)\geq Q_m(x,x) \gt 0. [[/math]]

■

If there exists several recurrence classes [math]R_i[/math] with [math]i\in I[/math] for some index set [math]I[/math] and if we set

[[math]] \mu_i(y)=\E_{x_i}\left[\sum_{k=0}^{H_{x_i}-1}\one_{\{ X_k=y\}}\right], [[/math]]

we obtain a invariant measure with disjoint supports.

Theorem

Let us assume that the Markov chain is irreducible and recurrent. Then the invariant measure is unique up to a multiplicative constant.

Show Proof

Let [math]\mu[/math] be an invariant measure. We can show by induction that for [math]p\geq 0[/math] and for all [math]x,y\in E[/math], we get

[[math]] \mu(y)\geq \mu(x)\E_x\left[\sum_{k=0}^{p\land (H_x-1)}\one_{\{ X_k=y\}}\right].(\star) [[/math]]

First, if [math]x=y[/math], this is obvious. Let us thus suppose that [math]x\not=y[/math]. If [math]p=0[/math], the inequality is immediate. Let us assume [math](\star)[/math] holds for [math]p[/math]. Then

[[math]] \begin{align*} \mu(y)&=\sum_{z\in E}\mu(z)Q(z,y)\geq \mu(x)\sum_{z\in E}\E_x\left[\sum_{k=0}^{p\land (H_x-1)}\one_{\{ X_k=z\}}\right]Q(z,y)\\ &=\mu(x)\sum_{z\in E}\sum_{k=0}^p\E_x[\one_{\{ X_k=z,k\leq H_x-1\}}]Q(z,y)\\ &=\mu(x)\sum_{z\in E}\sum_{k=0}^p \E_x[\one_{\{ X_k=z,k\leq H_x-1\}}]\one_{\{ X_{k-1}=y\}}\\ &=\mu(x)\E_x\left[\sum_{k=0}^{p\land (H_x-1)}\one_{\{ X_{k-1}=y\}}\right]=\mu(x)\E_x\left[\sum_{k=1}^{(p+1)\land (H_x)}\one_{\{ X_k=y\}}\right]. \end{align*} [[/math]]

This establishes the result for [math]p+1[/math]. Now, if we let [math]p\to\infty[/math] in [math](\star)[/math], we get

[[math]] \mu(y)\geq \mu(x)\E_x\left[\sum_{k=0}^{H_x-1}\one_{\{X_k=y\}}\right]. [[/math]]

Let us fix [math]x\in E[/math]. The measure [math]\nu_x(y)=\E_x\left[\sum_{k=0}^{H_x-1}\one_{\{ X_k=y\}}\right][/math] is invariant and we have [math]\mu(y)\geq \mu(x)\nu_x(y)[/math]. Hence for all [math]n\geq 1[/math] we get

[[math]] \mu(x)=\sum_{z\in E}\mu(z)Q_n(z,x)\geq \sum_{x\in E}\mu(x)\nu_x(z)Q_n(z,x)=\mu(x)\nu_x(x)=\mu(x). [[/math]]

Therefore we get that [math]\mu(z)=\mu(x)=\nu_x(z)[/math] for all [math]z[/math] such that [math]Q_n(z,x) \gt 0[/math]. Since the chain is irreducible, there exists some [math]n\geq 0[/math] such that [math]Q_n(z,x) \gt 0[/math]. This implies finally that

[[math]] \mu(z)=\mu(x)\nu_x(z). [[/math]]

■

Corollary

Let us assume the chain is irreducible and recurrent. Then one of the following hold.

• There exists an invariant probability measure [math]\mu[/math] and for [math]x\in E[/math] we have
  [[math]] \E_x[H_x]=\frac{1}{\mu(x)}. [[/math]]
• All invariant measures have infinite total mass and for [math]x\in E[/math] we get
  [[math]] \E_x[H_x]=\infty. [[/math]]

In the first case, the basis is said to be positive recurrent and in the second case it is said to be negative recurrent.

If [math]E[/math] is finite, then only the first case can occur.

Show Proof

We know that in this situation all invariant measures are proportional. Hence they all have finite mass or infinite mass. For case [math](i)[/math], let [math]\mu[/math] be the invariant probability measure and let [math]x\in E[/math]. Moreover, let

[[math]] \nu_x(y)=\E_x\left[\sum_{k=0}^{H_x-1}\one_{\{ X_k=y\}}\right]. [[/math]]

Then for some [math]C \gt 0[/math] we get [math]\mu=C\nu[/math]. We can determine [math]C[/math] by

[[math]] 1=\mu(E)=C\nu_x(E), [[/math]]

which implies that [math]C=\frac{1}{\nu_x(E)}[/math] and thus

[[math]] \mu(x)=\frac{\nu_x(x)}{\nu_x(E)}=\frac{1}{\nu_x(E)}. [[/math]]

But on the other hand we have

[[math]] \nu_x(E)=\sum_{y\in E}\E_x\left[\sum_{k=0}^{H_x-1}\one_{\{ X_k=y\}}\right]=\E_x\left[\sum_{k=0}^{H_x-1}\left(\sum_{y\in E}\one_{\{ X_k=y\}}\right)\right]=\E_x[H_x]. [[/math]]

In case [math](ii)[/math], [math]\nu_x[/math] is infinite and thus

[[math]] \E_x[H_x]=\nu_x(E)=\infty. [[/math]]

■

General references

Moshayedi, Nima (2020). "Lectures on Probability Theory". arXiv:2010.16280 [math.PR].