Classification of states

[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]

From now on we will only use the canonical Markov chain. Recall that for [math]x\in E[/math] we have

[[math]] \begin{align*} H_x&=\inf\{n\geq 1\mid X_n=x\},\\ N_x&=\sum_{n\geq 0}\one_{\{ X_n=x\}}. \end{align*} [[/math]]

Proposition (Recurrence and Transience)

Let [math]x\in E[/math]. Then we have two situations, which can occur.

• [math]\p_x[H_x \lt \infty]=1[/math] and [math]N_x=\infty[/math] [math]\p_x[/math]-a.s. In this case [math]x[/math] is said to be reccurrent.
• [math]\p_x[H_x \lt \infty] \lt 1[/math] and [math]N_x \lt \infty[/math] [math]\p_x[/math]-a.s. More precisely
  [[math]] \E_x[N_x]=\frac{1}{\p_x[H_x \lt \infty]} \lt \infty. [[/math]]
  In this case [math]x[/math] is said to be transient.

Show Proof

For [math]k\geq 1[/math], it follows from the strong Markov property that

[[math]] \p_x[N_x\geq k+1]=\E_x[\one_{H_x \lt \infty}\one_{N_x\geq k}\circ \Theta_{H_x}]=\E_x[\one_{H_x \lt \infty}\E_x[\one_{N_x\geq k}]]=\p_x[H_x \lt \infty]\p_x[N_x\geq k]. [[/math]]

Now since [math]\p_x[N_x\geq 1]=1[/math], it follows by induction that

[[math]] \p_x[N_x\geq k]=\p_x[H_x \lt \infty]^{k-1}. [[/math]]

If [math]\p_x[H_x \lt \infty]=1[/math], then [math]\p_x[N_x=\infty]=1[/math]. If [math]\p_x[H_x \lt \infty] \lt 1[/math], then

[[math]] \E_x[N_x]=\sum_{k\geq 1}\p_x[N_x\geq k]=\sum_{k\geq 1}\p_x[H_x \lt \infty]^{k-1}=\frac{1}{1-\p_x[H_x \lt \infty]}=\frac{1}{\p_x[H_x \lt \infty]} \lt \infty [[/math]]

■

Definition (Potential kernel)

The potential kernel of the chain is given by the function

[[math]] U:E\times E\to [0,\infty],(x,y)\mapsto \E_x[N_y]. [[/math]]

Proposition

The following hold.

• For all [math]x,y\in E[/math] we have
  [[math]] U(x,y)=\sum_{n\geq 0}Q_n(x,y). [[/math]]
• [math]U(x,x)=\infty[/math] if and only if [math]x[/math] is recurrent.
• For all [math]x,y\in E[/math] it follows that if [math]x\not=y[/math] then
  [[math]] U(x,y)=\p_x[H_y \lt \infty]U(y,y). [[/math]]

Show Proof

We need to show all three points.

• Note that
  [[math]] U(x,y)=\E_x\left[\sum_{n\geq 0}\one_{\{N_x=y\}}\right]=\sum_{n\geq 0}\p_x[X_n=y]=\sum_{n\geq 0}Q_n(x,y). [[/math]]
• Exercise.
• This follows from the strong Markov property. We get
  [[math]] \E_x[N_y]=\E_x[\one_{\{H_y \lt \infty\}}N_y\circ\Theta_{H_y}]=\E_x[\one_{\{H_y \lt \infty\}}\E_y[N_y]]=\p_x[H_y \lt \infty]U(y,y). [[/math]]

■

Example

Let us consider the Markov chain, starting at 0, on [math]\mathbb{Z}^d[/math] with transition matrix given by

[[math]] Q((x_1,...,x_d),(y_1,...,y_d))=\frac{1}{2^d}\prod_{i=1}^d\one_{\{\vert y_i-x_i\vert=1\}}. [[/math]]

This Markov chain has the same distribution as [math](Y_n^1,...,Y_n^d)_{n\geq 0}[/math], where [math]Y^1,...,Y^d[/math] are iid r.v.'s of a simple random walk on [math]\mathbb{Z}[/math], starting at 0. Hence we get

[[math]] Q_n(0,0)=\p[Y_n^1=0,...,Y_n^d=0]=\p[Y_n^1=0]^d. [[/math]]

Moreover, [math]\p[Y_n^1=0]=0[/math] if [math]n[/math] is odd and for [math]n=2k[/math] we get

[[math]] \p[Y_{2k}^1=0]=2^{-2k}\binom{2k}{k}. [[/math]]

Therefore we get that

[[math]] U(0,0)=\sum_{k\geq 0}Q_{2k}(0,0)=\sum_{k\geq 0}\left(2^{-2k}\binom{2k}{k}\right)^d. [[/math]]

Now with Stirling's formula we get

[[math]] 2^{-2k}\binom{2k}{k}\approx_{k\to\infty}\frac{\left(\frac{2k}{e}\right)^{2k}\sqrt{4\pi k}}{2^{2k}\left(\left(\frac{k}{e}\right)^k\sqrt{2\pi k}\right)^2}\approx_{k\to\infty}\sqrt{\frac{1}{\pi k}}. [[/math]]

Consequently, 0 is recurrent if [math]d=1[/math] and transient if [math]d\geq 2[/math].

Now let us denote the set of all recurrent points by [math]R[/math]. Then we can obtain the following lemma.

Lemma

Let [math]x\in R[/math] and let [math]y\in E[/math] such that [math]U(x,y) \gt 0[/math]. Then [math]y\in R[/math] and

[[math]] \p_y[H_x \lt \infty]=1. [[/math]]

In particular we get that [math]U(y,x) \gt 0[/math].

Show Proof

Let us first show that [math]\p_y[H_x \lt \infty]=1[/math]. We have that

[[math]] \begin{multline*} 0=\p_x[N_x \lt \infty]\geq \p_x[H_y \lt \infty, H_x\circ\Theta_{H_y}=\infty]=\E_x[\one_{\{H_y \lt \infty\}}\one_{\{H_x=\infty\}}\circ\Theta_{H_y}]\\=\E_x[\one_{\{H_y \lt \infty\}}\p_y[H_x=\infty]]=\p_x[H_y \lt \infty]\p_y[H_x=\infty]. \end{multline*} [[/math]]

Then [math]U(x,y) \gt 0[/math] implies that [math]\p_x[H_y \lt \infty] \gt 0[/math] and thus [math]\p_y[H_x=\infty]=0[/math]. Hence we can find [math]n_1,n_2\geq 1[/math] such that

[[math]] Q_{n_1}(x,y)\geq 0, Q_{n_2}(y,x) \gt 0. [[/math]]

Then for all [math]p\geq 0[/math] we get that

[[math]] Q_{n_1+p+n_2}(y,y)\geq Q_{n_2}(y,x)Q_p(x,x)Q_{n_1}(x,y), [[/math]]

and thus we have

[[math]] U(y,y)\geq\sum_{p=0}^\infty Q_{n_1+p+n_2}(y,y)\geq Q_{n_2}(y,x)\left(\sum_{p=0}^\infty Q_p(x,x)\right)Q_{n_1}(x,y)=\infty, [[/math]]

since [math]x\in R[/math].

■

The above lemma has the following important consequence. If [math]x\in R[/math] and [math]y\in E\setminus R[/math], then [math]U(x,y)=0[/math], which means that one cannot go from a recurrent point to a transient point.

Theorem (Classification of states)

Let [math]R[/math] be the set of all recurrent points and let [math]N_x[/math] be defined as above. Then there exists a partition of [math]R[/math], denoted [math](R_i)_{i\in I}[/math] for some index set [math]I[/math], i.e.

[[math]] R=\bigcup_{i\in I}R_i, [[/math]]

such that the following properties hold.

• If [math]x\in R[/math] and [math]i\in I[/math] such that [math]x\in R_i[/math], we get that \begin{itemize
• [math]N_y=\infty[/math], [math]\p_x[/math]-a.s. for all [math]y\in R_i[/math],
• [math]N_y=0[/math], [math]\p_x[/math]-a.s. for all [math]y\in E\setminus R_i[/math].} \end{itemize}
• If [math]x\in E\setminus R[/math] and [math]T=\inf\{n\geq 0\mid X_n\in R\}[/math], we get that \begin{itemize
• [math]T=\infty[/math] and [math]N_y \lt \infty[/math], [math]\p_x[/math]-a.s. for all [math]y\in E[/math],
• [math]T \lt \infty[/math] and then there exists [math]j\in I[/math] such that for all [math]n\geq T[/math] we get [math]X_n\in R_j[/math], [math]\p_x[/math]-a.s.} \end{itemize}

Show Proof

For [math]x,y\in R[/math], let us note [math]x\sim Y[/math] if [math]U(x,y) \gt 0[/math]. It follows from lemma 3.3. that this is an equivalence relation on [math]R[/math]. Let [math]i\in I[/math] and [math]x\in R_i[/math]. We have that [math]U(x,y)=0[/math] for all [math]y\in E\setminus R_i[/math] and hence [math]N_y=0[/math], [math]\p_x[/math]-a.s. for all [math]y\in E\setminus R_i[/math]. If [math]y\in R_i[/math], we have from lemma 3.3. that [math]\p_x[H_y \lt \infty]=1[/math] and it follows from the strong Markov property that

[[math]] \p_x[N_y=\infty]=\E_x[\one_{\{H_y \lt \infty\}}\one_{\{N_y=\infty\}}\circ\Theta_{H_y}]=\p_x[H_y \lt \infty]\p_y[N_y=\infty]=1. [[/math]]

If [math]x\in E\setminus R[/math] and [math]T=\infty[/math], it easily follows from the strong Markov property that [math]N_y \lt \infty[/math] for all [math]y\in E\setminus R[/math]. If [math]T \lt \infty[/math], let [math]j\in I[/math] such that [math]X_T\in R_j[/math]. Then apply the strong Markov property with [math]T[/math] and the first part of the theorem, which then gives us that [math]X_n\in R_j[/math] for all [math]n\geq T[/math].

■

Definition (Irreducibility)

A chain is called irreducible if [math]U(x,y) \gt 0[/math] for all [math]x,y\in E[/math].

Corollary

If the chain is irreducible, then the following hold.

• Either all states are recurrent and there exists a recurrent chain and for all [math]x\in E[/math] we get
  [[math]] \p_x[N_y=\infty, \forall y\in E]=1, [[/math]]
• or all states are transient and then for all [math]x\in E[/math] we get
  [[math]] \p_x[N_y \lt \infty,\forall y\in E]=1. [[/math]]
  Moreover, if [math]\vert E\vert \lt \infty[/math], then only the first case can occur.

Show Proof

If there exists a recurrent state, the lemma 3.3. shows that all states are recurrent with [math]U(x,y) \gt 0[/math] for all [math]x,y\in E[/math] and there is only one recurrent chain. If [math]\vert E\vert \lt \infty[/math] and if all states are transient, then we get [math]\p_x[/math]-a.s. that

[[math]] \sum_{y\in E}N_y \lt \infty, [[/math]]

but we know

[[math]] \sum_{y\in E}N_y=\sum_{y\in E}\sum_{n\geq 0}\one_{\{X_n=y\}}=\sum_{n\geq 0}\sum_{y\in E}\one_{\{X_n=y\}}=\infty. [[/math]]

■

Example

Let us first recall that the results obtained for the canonical Markov chain hold for any arbitrary Markov chain. Now let [math](Y_n)_{n\geq 0}[/math] be a Markov chain with transition matrix [math]Q[/math]. For instance, if [math]Y_0=y[/math] and [math]N_x^Y=\sum_{n\geq0} \one_{\{ Y-n=x\}}[/math], we have for that [math]k\in\bar\N[/math]

[[math]] \p[N_x^Y=k]=\p_y[N_x=k], [[/math]]

since the left hand side is [math]\p[(Y_n)_{n\geq 0}\in B][/math] with [math]B:=\{\omega\in E^\N\mid N_x(\omega)=k\}[/math].

Theorem

Let [math](\xi_j)_{j\geq 1}[/math] be iid r.v.'s having the law [math]\mu[/math] with [math]\xi_j\in\mathbb{Z}[/math] for all [math]j\geq 1[/math] and assume that [math]\E[\vert\xi_1\vert] \lt \infty[/math] and [math]m=\E[\xi_1][/math]. Moreover, set [math]Y_n=Y_0+\sum_{j=1}^n\xi_j[/math]. Then

• if [math]m\not=0[/math], then all states are transient.
• if [math]m=0[/math], then all states are recurrent. Moreover, the chain is irreducible if and only if the subgroup given by [math]\{y\in\mathbb{Z}\mid \mu(y) \gt 0\}[/math] is in [math]\mathbb{Z}[/math].

Show Proof

We need to show both points.

• If [math]m\not=0[/math], we know from the strong law of large numbers that [math](Y_n)\xrightarrow{n\to\infty\atop a.s.}\infty[/math] and hence all states are transient.
• Assume [math]m=0[/math] and [math]0[/math] is transient. Thus [math]U(0,0) \lt \infty[/math]. We can assume that [math]Y_0=0[/math]. For [math]x\in\mathbb{Z}[/math] we get
  [[math]] U(0,x)\leq U(x,x)=U(0,0). [[/math]]
  Therefore we get that for all [math]n\geq 1[/math]
  [[math]] \sum_{\vert x\vert\leq n}U(0,x)\leq (2n+1)U(0,0)\leq Cn, [[/math]]
  where [math]C=3 U(0,0)[/math]. Moreover, by the law of large numbers, there exists some [math]N[/math] sufficiently large such that for all [math]n\geq N[/math]
  [[math]] \p[\vert Y_n\vert\leq \varepsilon n] \gt Y_2 [[/math]]
  with [math]\varepsilon=\frac{1}{6C}[/math], or equivalently
  [[math]] \sum_{\vert x\vert\leq \varepsilon n}Q_n(0,x)\geq \frac{1}{2}. [[/math]]
  If [math]p\geq n\geq N[/math], then
  [[math]] \sum_{\vert x\vert\leq \varepsilon n}Q_p(0,x)\geq \sum_{\vert x\vert\leq \varepsilon p}Q_p(0,x) \gt \frac{1}{2}, [[/math]]
  and by summing over [math]p[/math], we get
  [[math]] \sum_{\vert x\vert\leq \varepsilon n}U(0,n)\geq \sum_{p=N}^n\sum_{\vert x\vert\leq \varepsilon p}Q_p(0,x) \gt \frac{n-N}{\varepsilon}. [[/math]]
  But if [math]\varepsilon n\geq 1[/math], then
  [[math]] \sum_{\vert x\vert\leq \varepsilon n}U(0,x)\leq C\varepsilon n=\frac{n}{6}, [[/math]]
  which leads to a contradiction for [math]n[/math] sufficiently large. For the last statement, write [math]G=\langle x\in\mathbb{Z}\mid \mu(x) \gt 0\rangle[/math]. Then, since [math]Y_0=0[/math], we get
  [[math]] \p[Y_n\in G\mid \forall n\in \N]=1. [[/math]]
  If [math]G\not=\mathbb{Z}[/math], then obviously [math](Y_n)_{n\geq 0}[/math] is irreducible. If [math]G=\mathbb{Z}[/math], then write
  [[math]] H:=\{x\in\mathbb{Z}\mid U(0,x) \gt 0\}. [[/math]]
  It follows that [math]H[/math] is a subgroup of [math]\mathbb{Z}[/math], indeed, for [math]x,y\in H[/math], we get that
  [[math]] Q_{n+p}(0,x+y)\geq Q_n(0,x)Q_p(x,x+y)=Q_n(0,x)Q_p(0,y), [[/math]]
  and thus we get that [math]x+y\in H[/math]. For [math]x\in H[/math] and with [math]0[/math] being recurrent, we get that [math]U(0,x) \gt 0[/math] implies that [math]U(x,x) \gt 0[/math] and therefore [math]U(x,0)=U(0,-x)[/math], which implies that [math]-x\in H[/math]. Now since [math]H\supset\{ x\in\mathbb{Z}\mid \mu(x) \gt 0\}[/math], we get that [math]H=\mathbb{Z}[/math] and the claim follows.

■

Example

Let [math]\mu=\frac{1}{2}\delta_{-2}+\frac{1}{2}\delta_{2}[/math]. Then all states are recurrent but there are two recurrence classes.

Random variable on a graph

Assume that [math]\vert E\vert \lt \infty[/math]. Moreover, let [math]A\subset\mathcal{P}(E)[/math] and for [math]x\in E[/math] let

[[math]] A_x=\{y\in E\mid \{x,y\}\in A\}\not=\varnothing. [[/math]]

A graph [math]\mathcal{G}[/math] is said to be connected if every pair of vertices in the graph is connected.

Proposition

The simple random walk on a finite graph is recurrent and irreducible.

Show Proof

Exercise.

■

General references

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