Recurrence and transience

Definitions §

Let $(X_n{)}_{n\ge 0}$ be a Markov chain with transition matrix $P$. Define

$$H_i=\inf \{n\ge 0:X_n=i\}\text{hitting time on }i$$ $$T_i=\inf \{n\ge 1:X_n=i\}\text{first passage time to }i$$

using the convention $\inf \varnothing =\infty$. Remark They are different only if $X_0=i$.

We can definte the $r$-th passage time to $i$, setting $T_i^{(0)}=0$ and for $r\ge 1$

$$T_i^{(1)}=T_i{T}_i^{(r+1)}:=\inf \{n>T_i^{(r)}:X_n=i\}$$

and the excursion time beetween visits

$$S_i^{(r)}:=\{\begin{array}{l}{T}_i^{(r)}-T_i^{(r-1)}\text{ if }{T}_i^{(r-1)}<\infty \\ 0\text{ otherwise }\end{array}$$

this explain our choice for $T_i^{(0)}$.

The following lemma should be obvious. Lemma For $r=2,3,\dots$ the random variable $S_i^{(r)}$ is independent of $H_{T_i^{(r-1)}}$ and for all $n\ge 0$

$$P_i(S_i^{(r)}=n|T_i^{(r-1)}<\infty )=P_i(S_i^1=n)=P_i(T_i=n)$$

Proof Since $T_i^{r-1}$ is a stopping time, by the strong Markov property

$${\tilde{X}}_n:=X_{T_i^{(r-1)}+n}Markov({\delta }_i,P)$$ $${\tilde{T}}_i=\inf \{n\ge 1:{\tilde{X}}_n=i\}$$

using the definition of the excurtion time

$$\{S_i^{(r)}=n\}=\{T_i^{(r)}-T_i^{(r-1)}=n,T_i^{(r-1)}<\infty \}$$ $$=\{{\tilde{T}}_i=n,T_i^{(r-1)}<\infty \}$$

so the probability

$$P_i(\{{\tilde{T}}_i=n\}|T_i^{(r-1)}<\infty )=P_i(T_i=n)=P_i(S_i^{(1)}=n)\square$$

Other useful definitions are:

$$V_i=\sum _{n=0}^{\infty }{1}_{X_n=i}\text{number of visits to }i$$ $$f_i=P_i(T_i<\infty )\text{ return probability to }i$$ $$m_i=\mathbb{E}[T_i]\text{ mean return time to }i$$

Def (Recurrent state) We say that the state $i$ is recurrent if

$$i\text{ recurrent}⟺P_i(V_i=\infty )=1$$

a non-recurrent state is called transient.

There is a link beetween recurrent and and return probability.

Lemma For all $r\ge 0$, $P_i(V_i>r)=f_i^r$. Proof By induction. The base case $r=0$ is true (with the convention $0^0=1$). Assume it holds for $r$.

$$P_i(V_i>r+1)=P_i(T_i^{(r+1)}<\infty )=P_i(T_i^{(r+1)}<\infty ,T_i^{(r)}<\infty )$$

or equivalently using the excurtion time

$$=P_i(S_i^{(r+1)}<\infty ,T_i^{(r)}<\infty )$$

using the definition of conditional probability

$$=P_i(S_i^{(r+1)}<\infty |T_i^{(r)}<\infty )P_i(T_i^{(r)}<\infty )$$ $$=\sum _{n\ge 0}{P}_i(S_i^{(r+1)}=n|T_i^{(r)}<\infty )P_i(T_i^{(r)}<\infty )$$

using the strong Markov property

$$=\sum _{n\ge 0}{P}_i(T_i=n)P_i(T_i^{(r)}<\infty )$$ $$=P_i(T_i<\infty )P_i(T_i^{(r)}<\infty )=f_i{f}_i^r=f_i^{r+1}\square$$

since $T_i^{(r)}<\infty$ is the same event as $V_i>r$.

Characterization §

Theorem We have the dichotomy:

1. se $P_i(T_i<\infty )=1$, allora $i$ è ricorrente e

$$\sum _{n=0}^{\infty }{p}_{ii}^{(n)}=\infty$$

2. se $P_i(T_i<\infty )<1$, allora $i$ è transiente e

$$\sum _{n=0}^{\infty }{p}_{ii}^{(n)}<\infty$$

Proof The probability that the state $i$ is recurrent, i.e. the number $V_i$ of visits is infinite is

$$P_i(V_i=\infty )=P_i\left(\bigcap _{r\ge 0}\{V_i>r\}\right)=\underset{r\to \infty }{\lim }P(V_i>r)=\underset{r\to \infty }{\lim }{f}_i^r=1$$

where we have used Continuity of mesure and the previous lemma. Since $P_i(V_i=\infty )=1$, we also know that

$$\infty ={\mathbb{E}}_i[V_i]={\mathbb{E}}_i\left[\sum _{n\ge 0}1(X_n=i)\right]=\sum _{n\ge 0}{P}_i(X_n=i)=\sum _{n\ge 0}{p}_{ii}^{(n)}$$

where we have used Fubini’s theorem.

Doing the same computation for a state such that $P_i(T_i<\infty )<1$ we get

$$P_i(V_i=\infty )=\underset{r\to \infty }{\lim }{f}_i^r=0$$

computing the expected value we get

$${\mathbb{E}}_i[V_i]=\sum _{r\ge 0}{P}_i(V_i>r)=\sum _{r\ge 0}{f}_i^r=\frac{1}{1-f_i}<\infty$$

but also

$${\mathbb{E}}_i[V_i]=\sum _{n\ge 0}{p}_{ii}^{(n)}$$

and the theorem is proven. $\square$

Corollary Every state is either transient of recurrent.

Class property §

We can show that being recurrent or transient is a class property.

Theorem Let $C\subseteq I$ be a communicating class. Then either all state in $C$ are transient or all are recurrent.

Proof Take any pair $i,j\in C$ and suppose $i$ is transient, let’s show that $j$ is also transient. Since $i\leftrightarrow j$ then $\exists n,m\ge 0$ such that

$$P_{ij}^{(n)}>0\text{and}{P}_{ji}^{(m)}>0$$

for all $r\ge 0$

$$P_{ii}^{n+r+m}=(P^n{P}^r{P}^m{)}_{ii}=\sum _{l,k\in I}{P}_{il}^{(n)}{P}_{lk}^{(r)}{P}_{ki}^{(m)}\ge P_{ij}^{(n)}{P}_{jj}^{(r)}{P}_{ji}^{(m)}$$

then

$$\sum _{r\ge 0}{P}_{jj}^{(r)}\le \frac{1}{P_{ij}^{(n)}{P}_{ji}^{(m)}}\sum _{r\ge 0}{P}_{ii}^{n+r+m}<\infty$$

where we have used the fact that $i$ is transient, and the dichotomy. This proves that also $j$ is transient. $\square$

We have proven that if a state $i\in C$ is transient, then the whole class is transient. This means either state are all recurrent, or all transient. $\square$

Theorem Every recurrent class is closed.

Proof Let’s show that if $C$ is open, then it’s transient. Since $C$ is open, then $\exists i\in C$ and $\exists j\notin C$ such that $i\to j$ (but not $j\to i$ since $j\notin C$. This means there exist $n\ge 0$ such that $(P^n{)}_{ij}>0$

$$P_i(V_i>n|\exists m)$$

Theorem Let $P$ be an irreducible recurrent markov chain. Then for every initial distribution $\mu$ every state is visited a.s:

$$P(T_i<\infty )=1$$

Proof Using the w.m.p

$$P(T_i<\infty )=\sum _{j\in I}P(T_i<\infty |X_0=j){\mu }_j$$ $$=\sum _{j\in I}{P}_j(T_i<\infty ){\mu }_j$$

since ${\sum }_j{\mu }_j=1$, if we prove that $P_j(T_i<\infty )=1$ for all $j$ we have done. We now use the recurrence hypotesis

$$1=P_j(V_j=\infty )$$ $$=P_j(\sum _{n=0}^{\infty }1(X_n=j)=\infty )$$

choose an arbitrary time $m\ge 0$

$$=P_j(\sum _{n=0}^{m-1}1(X_n=j)+\sum _{n=m}^{\infty }1(X_n=j)=\infty )$$

since the first sum is less or equal to $m-1$ (a finite number)

$$=P_j(\sum _{n=m}^{\infty }1(X_n=j)=\infty )$$ $$\ge P_j(X_n=j,\exists n\ge m)$$ $$=\sum _{i\in I}{P}_j(X_n=j,\exists n\ge m|X_m=i)P_j(X_m=i)$$ $$=\sum _{i\in I}{P}_i(T_j<\infty )P_j(X_m=i)$$

since the second terms add to one, this implies that

$$P_i(T_j<\infty )=1\square$$