Recurrence Transience and Hitting Times for Markov Chains — Examples

The four displayed rows are nonnegative and each sums to one. Because $P$ is a transition matrix, every unlisted entry in each row must therefore be zero; the matrix is fully specified as displayed.

By induction using [F4], for every $n\ge 0$ the row $p^{(n)}(0,\cdot )$ is concentrated at $0$, while the rows from $1$ and $2$ alternate deterministically between those two states. Thus $0$ reaches neither $1,2,3$, and $1,2$ reach neither $0$ nor $3$. Since $p(1,2)=p(2,1)=1$, states $1,2$ communicate. State $3$ communicates with itself, and it reaches $0$, but $0$ cannot reach $3$; its rows also show it reaches neither $1$ nor $2$. Hence the communication classes are exactly $\{0\}$, $\{1,2\}$, and $\{3\}$.

From state $0$ the chain stays at $0$, so $T_0^{+}=1$ almost surely. From states $1$ and $2$ it alternates deterministically, so $T_1^{+}=T_2^{+}=2$ almost surely. In all three cases the positive return probability is one, so $0,1,2$ are recurrent by [F6].

From state $3$, the first step is a return to $3$ with probability $p(3,3)=1\mathrm{/}2$. With the remaining probability $1\mathrm{/}2$ the chain moves to $0$ and then stays there forever, so there is no later return to $3$. Therefore ${\mathbb{P}}_3(T_3^{+}<\mathrm{\infty })=1\mathrm{/}2<1$, and state $3$ is transient by [F7].

The example fixes a four-state space, so the empty-space and one-state cases do not arise. Zero entries are forced by row normalization and are used in the access calculation; the deterministic rows and absorbing state are covered directly. Accessibility includes the zero-step identity, whereas $T_x^{+}$ starts at time one. All calculations are finite and choice-free. This example gives a state classification, not an iff theorem.

For each $x\in E_N$, define a measure-valued row by $K_N(x,\cdot )=\{\begin{array}{ll}{\delta }_0,& x=0,\\ {\delta }_N,& x=N,\\ \frac{1}{2}{\delta }_{x-1}+\frac{1}{2}{\delta }_{x+1},& 1\le x<N\mathrm{.}\end{array}$ By [F2], each row is a probability measure; because $E_N$ is finite and discrete, the map $x\mapsto K_N(x,B)$ is measurable for each $B\subseteq E_N$. Thus $K_N$ is a probability kernel. By [F4], its transition matrix is exactly the one in the Statement, including the zero weights off the listed transitions.

Define boundary data $f_N(0)=0$, $f_N(N)=1$, and set $g_N(i)=i\mathrm{/}N$ on $E_N$. The function $g_N$ is bounded and agrees with $f_N$ on $A_N$. If $1\le i<N$, then [F4] and direct arithmetic give $P_N{g}_N(i)=\frac{1}{2}{g}_N(i-1)+\frac{1}{2}{g}_N(i+1)=\frac{(i-1)+(i+1)}{2N}=\frac{i}{N}=g_N(i)\mathrm{.}$ Thus $g_N$ satisfies the boundary and harmonic equations, with no interior equations required when $N=1$.

For each $i\in E_N$, take the canonical chain with kernel $K_N$ and initial law ${\delta }_i$, and write its law and expectation as ${\mathbb{P}}_i$ and ${\mathbb{E}}_i$. By [A1, F3], all these deterministic-start chains exist on the canonical path space and have the stated transition matrix.

Define the bounded path functional $H_N:E_N^{{\mathbb{N}}_0}\to \{0,1\}$ by $H_N(w)=1$ exactly when $1\le w_0<N$ and $w_s=\max \{w_0-s,0\}(1\le s\le N),$ and set $H_N(w)=0$ otherwise. It is measurable because it depends on finitely many coordinates in a finite discrete space. Under ${\mathbb{P}}_i$, for $1\le i<N$, the event $H_N=1$ specifies exactly $i$ left moves, each of probability $1\mathrm{/}2$, followed by the absorbing self-loop at $0$; hence [F5] gives ${\mathbb{E}}_i{H}_N(X_0,X_1,\dots )=2^{-i}\mathrm{.}$ For $i=0$ or $i=N$ the expectation is zero by the definition of $H_N$. Thus the canonical expectation function is $h_N(i)=\{\begin{array}{ll}{2}^{-i},& 1\le i<N,\\ 0,& i\in \{0,N\}\mathrm{.}\end{array}$

Put $A_N=\{0,N\}$ and $T=T_{A_N}$. By [F6], for every $m\ge 0$, ${\mathbb{E}}_i[H_N(X_m,X_{m+1},\dots )\mid {\mathcal{F}}_m]=h_N(X_m)\text{almost surely}\mathrm{.}$ On $\{T>mN\}$ the state $X_{mN}$ lies in $\{1,\dots ,N-1\}$. The event $H_N(X_{mN},X_{mN+1},\dots )=1$ then forces a visit to $0$ within the next $N$ steps, so $T\le (m+1)N$. Therefore [F6, F7] imply $\begin{array}{rl}{\displaystyle {\mathbb{P}}_i(T>(m+1)N)}& {\displaystyle ={\mathbb{E}}_i\text{\hspace{0.17em}⁣}[{\mathbf{1}}_{\{T>mN\}}{\mathbb{E}}_i[{\mathbf{1}}_{\{T>(m+1)N\}}\mid {\mathcal{F}}_{mN}]]}\\ {\displaystyle }& {\displaystyle \le (1-2^{-N}){\mathbb{P}}_i(T>mN)}\end{array}$ for every interior start; here $2^{-X_{mN}}\ge 2^{-N}$ on the survival event. Induction gives ${\mathbb{P}}_i(T>mN)\le (1-2^{-N}{)}^m$. Since $\{T=\mathrm{\infty }\}\subseteq \{T>mN\}$ for every $m$ and the bound tends to zero, ${\mathbb{P}}_i(T<\mathrm{\infty })=1$. From either boundary state $T=0$, so every start hits $A_N$ almost surely.

By [A1, F8] and step 3.1, the hypotheses of the bounded Dirichlet theorem hold for the chain with kernel $K_N$, boundary $A_N$, and data $f_N$. Its expected boundary payoff is the unique bounded solution of those equations. Step 1.2 shows that this solution is $g_N$.

For a path with $T<\mathrm{\infty }$, the endpoints are distinct and $T$ is the first visit to one of them, so $f_N(X_T)=1$ exactly when $T_N<T_0$. If $T=\mathrm{\infty }$, both hitting times are infinite and the theorem's payoff is zero, so the same indicator identity holds. Since $T<\mathrm{\infty }$ almost surely by step 3.1, [F8, step 4.1] yield ${\mathbb{P}}_i(T_N<T_0)={\mathbb{E}}_i[f_N(X_T)]=g_N(i)=\frac{i}{N}\mathrm{.}$

The assumption $N\ge 1$ makes $E_N$ nonempty and $0,N$ distinct, so an empty state space, a one-state space, or an empty boundary set is inapplicable. For $N=1$ both states are boundary states and there is no interior equation; for $N=2$ the single interior equation in step 1.2 applies. At $i=0$, the time-zero convention gives $T_0=0$ and both sides are zero; at $i=N$, it gives $T_N=0<T_0$ and both sides are one. All unlisted transition weights are zero, and the boundary rows are absorbing. AC is assumed and used through the canonical chain laws, conditional-expectation properties and bounded-future Markov identity, and the Dirichlet theorem. The claim is a hitting-probability identity, not an iff statement.

For $x<y$, the path that takes consecutive upward steps from $x$ to $y$ has probability ${\prod }_{k=x}^{y-1}{p}_k>0$; for $x>y$, consecutive downward steps have probability ${\prod }_{k=y+1}^x{q}_k>0$. By [F8], each such path gives positive $n$-step probability, so [F5] shows that every pair of states communicates. Thus the chain is irreducible. Every $q_j\mathrm{/}{p}_j$ is finite and strictly positive, so every $s_m$ is well-defined and positive, and $1\le S\le +\mathrm{\infty }$.

Fix integers $M>i\ge 1$ and set $E_M=\{0,1,\dots ,M\}$ and ${\tau }_M=T_{\{0,M\}}$. On $E_M$ define the matrix ${\widehat{p}}_M$ by making $0$ and $M$ absorbing and retaining the original row $(q_j,r_j,p_j)$ at each $1\le j<M$. For $x\in E_M$ and $B\subseteq E_M$, set ${\widehat{K}}_M(x,B)={\sum }_{y\in E_M}{\widehat{p}}_M(x,y){\delta }_y(B)\mathrm{.}$ Each row is a finite nonnegative weighted sum of Dirac probability measures; its weights sum to one, so [F10]–[F12] show that ${\widehat{K}}_M$ is a probability kernel. Under each original ${\mathbb{P}}_x$, $x\in E_M$, define $Y_n=X_{n\wedge {\tau }_M}$. This process stays in $E_M$. When ${\tau }_M\le n$ it is already at an absorbing endpoint; when ${\tau }_M>n$, it is at an interior state and its next original transition remains in $E_M$. Applying [F9] to the bounded functional $G(\omega )={\mathbf{1}}_B({\omega }_1)$ gives the conditional law of the next original state. Splitting on the ${\mathcal{F}}_n$-measurable events $\{{\tau }_M\le n\}$ and $\{{\tau }_M>n\}$ gives ${\mathbb{E}}_x[{\mathbf{1}}_{\{Y_{n+1}\in B\}}\mid {\mathcal{F}}_n]={\mathbf{1}}_{\{{\tau }_M\le n\}}{\mathbf{1}}_B(Y_n)+{\mathbf{1}}_{\{{\tau }_M>n\}}K(X_n,B);$ on the second event $X_n=Y_n$ is interior and its birth–death row, given by [F4], is exactly the corresponding ${\widehat{K}}_M$ row; on the first event $Y_n$ is an absorbing endpoint and the first term is its row probability. Thus this conditional expectation is ${\widehat{K}}_M(Y_n,B)$, so $Y$ is a finite-state Markov chain with kernel ${\widehat{K}}_M$ and deterministic start $x$.

For $1\le j<M$, the event that $Y$ takes $j$ consecutive downward steps from $j$ to $0$ has probability $q_j{q}_{j-1}\cdots q_1>0$ by [F8]. Let ${\epsilon }_M={\min }_{1\le j<M}{\prod }_{k=1}^j{q}_k>0.$ At any block time $kM$, if $Y_{kM}=j$ is interior, the conditional probability of following those $j$ downward steps is at least ${\epsilon }_M$ by [F9]; the boundary is then hit within the next $M$ steps. If the chain is already at a boundary, it has already hit one. Therefore, writing ${\sigma }_M=T_{\{0,M\}}$ for $Y$, ${\mathbb{P}}_x({\sigma }_M>(k+1)M)\le (1-{\epsilon }_M){\mathbb{P}}_x({\sigma }_M>kM),{\mathbb{P}}_x({\sigma }_M>kM)\le (1-{\epsilon }_M{)}^k\mathrm{.}$ This holds for every $x\in E_M$; hence $Y$ hits $\{0,M\}$ almost surely from every state.

Define $H(0)=0$ and $H(i)={\sum }_{m=0}^{i-1}{s}_m$ for $i\ge 1$. For $i\ge 1$, $H(i+1)-H(i)=s_i,H(i)-H(i-1)=s_{i-1},p_i{s}_i=q_i{s}_{i-1},$ where the last equality follows from the product definition of $s_i$. Consequently $p_i(H(i+1)-H(i))=q_i(H(i)-H(i-1)),$ which, together with $p_i+q_i+r_i=1$, gives $H(i)=p_{i}H(i+1)+r_{i}H(i)+q_{i}H(i-1)\mathrm{.}$ Thus $H\mathrm{/}H(M)$ is harmonic at every interior state of the finite chain, equals zero at $0$, and equals one at $M$.

By step 2.1, the finite-state chain $Y$ satisfies the all-start almost-sure boundary-hitting hypothesis of [F13]. Apply [F13] with boundary $\{0,M\}$ and payoff zero at $0$, one at $M$. Its hitting payoff is ${\mathbb{P}}_i(T_M<T_0)$, and [F14] identifies the unique bounded harmonic extension as $H(i)\mathrm{/}H(M)$ by step 2.2. Therefore ${\mathbb{P}}_i(T_M<T_0)=\frac{H(i)}{H(M)}\mathrm{.}$

The stopped path $Y$ equals the original path $X$ through its first hit of $\{0,M\}$. Hence from the interior start $i$ the event that $Y$ first hits $M$ rather than $0$ is exactly the original event $\{T_M<T_0\}$. Thus the probability in step 3.1 is the original-chain probability, not a new boundary convention.

As $M>i$ increases, the events $A_M=\{T_M<T_0\}$ decrease: reaching $M+1$ before $0$ requires first reaching $M$ before $0$. If $T_0<\mathrm{\infty }$, the path has a finite maximum before its first hit of $0$, so it fails to belong to $A_M$ for every $M$ above that maximum. Conversely, for each fixed $M$, step 2.1 shows that the first hit of $\{0,M\}$ is almost surely finite; on $\{T_0=\mathrm{\infty }\}$ this forces $T_M<T_0$ almost surely. Taking the countable intersection over $M>i$ proves ${\mathbb{P}}_i\text{\hspace{0.17em}⁣}(\{T_0=\mathrm{\infty }\}\mathrm{△}{\bigcap }_{M>i}{A}_M)=0.$ By [F15] and steps 3.1 and 4.1, ${\mathbb{P}}_i(T_0=\mathrm{\infty })={\lim }_{M\to \mathrm{\infty }}\frac{H(i)}{H(M)}\mathrm{.}$ Since $H(M)={\sum }_{m=0}^{M-1}{s}_m\uparrow S$, this limit is $H(i)\mathrm{/}S$ when $S<+\mathrm{\infty }$ and zero when $S=+\mathrm{\infty }$.

From state $0$, the first step is a self-loop with probability $r_0$, which is an immediate positive-time return, or a move to $1$ with probability $p_0$. In the latter case, the future path returns to $0$ exactly when it hits $0$ from start $1$; applying [F9] to the bounded event functional ${\mathbf{1}}_{\{T_0<\mathrm{\infty }\}}$ gives ${\mathbb{P}}_0(T_0^{+}<\mathrm{\infty })=r_0+p_0{\mathbb{P}}_1(T_0<\mathrm{\infty })=1-p_0{\mathbb{P}}_1(T_0=\mathrm{\infty })\mathrm{.}$ If $S=+\mathrm{\infty }$, step 5.1 makes this return probability one, so $0$ is recurrent by [F7]. If $S<+\mathrm{\infty }$, step 5.1 gives ${\mathbb{P}}_1(T_0=\mathrm{\infty })=H(1)\mathrm{/}S=1\mathrm{/}S>0$; since $p_0>0$, the return probability is strictly less than one and $0$ is not recurrent. This proves both directions of the stated equivalence.

The state space is the fixed infinite set ${\mathbb{N}}_0$, so empty and one-state spaces do not instantiate the claim. Zero transition weights are exactly the off-neighbor entries and $q_0=0$; zero holding probabilities are allowed. The finite auxiliary chain has absorbing endpoint rows, while the original interior rows have $p_i,q_i>0$. The hitting time $T_0$ includes time zero by [F6], but the escape formula starts at $i\ge 1$; the return time $T_0^{+}$ from $0$ is strictly positive. The scale terms are all positive, $H(1)=1$, and $S\ge 1$, so the finite-denominator branch is defined. AC [A1] is used for canonical chain laws [F1], finite-dimensional laws [F8], bounded future-path conditioning [F9], and the Dirichlet theorem [F13], [F14]; once these Markov facts are available, the finite path, product, and difference calculations are choice-free. Both iff directions are proved in step 6.1.

The enumeration in [F1] makes $E$ countable. For each fixed $z$, [F2] shows that $K(z,\cdot )$ is a probability measure of total mass $p+q=1$; the row evaluation $z\mapsto K(z,A)=p{\mathbf{1}}_A(z+1)+q{\mathbf{1}}_A(z-1)$ is measurable for every $A\subseteq E$, so it is a probability kernel. With ${\delta }_x$ as initial law, [A1] and [F3] give the canonical deterministic-start chain for every $x$. Also $0<r<1$ and $0<p<1$, since $0<q<p$ and $p+q=1$.

Fix integers $a<b$ and put $D=\{a,b\}$. On the finite set $E_{a,b}=\{a,a+1,\dots ,b\}$, define an absorbed kernel $K_{a,b}$ by $K_{a,b}(a,\cdot )={\delta }_a$, $K_{a,b}(b,\cdot )={\delta }_b$, and $K_{a,b}(i,\cdot )=p{\delta }_{i+1}+q{\delta }_{i-1}$ for $a<i<b$. If $b=a+1$, there are no interior states and the endpoint exit is immediate. The same finite-mixture argument as in step 1.1 makes this a probability kernel; take its canonical chain. Let $L=b-a$. Define a measurable future-path event $H$ which is certain from an endpoint and, from each interior $i$, requires the successive right moves $i\to i+1\to \cdots \to b$. Its probability from $i$ is $p^{b-i}\ge p^L$. If $A_k=\{T_D>kL\}$, then $X_{kL}$ is interior on $A_k$. By [F6], conditional on ${\mathcal{F}}_{kL}$ the event $H$ has probability at least $p^L$ on $A_k$; whenever $H$ occurs, $D$ is hit by time $(k+1)L$. Consequently ${\mathbb{P}}_x(T_D>(k+1)L)\le (1-p^L){\mathbb{P}}_x(T_D>kL)$, so ${\mathbb{P}}_x(T_D>kL)\le (1-p^L{)}^k\to 0$ by [F12]. Thus every start in $E_{a,b}$ hits $D$ almost surely, including endpoint starts where $T_D=0$.

The assumptions $p>q>0$ and $p+q=1$ imply $0<r<1$, make every displayed denominator positive, and exclude zero right/left weights, deterministic motion, and the unbiased case $p=q$. By [F4], $P(z,w)=K(z,\{w\})$; since the kernel in [F2] is supported on $\{z-1,z+1\}$, all entries away from those neighbors are zero, as also follows from step 1.1.

Put $\varphi (i)=(1-r^{i-a})\mathrm{/}(1-r^{b-a})$ for $a\le i\le b$. The denominator is positive, $0\le \varphi \le 1$, and $\varphi (a)=0$, $\varphi (b)=1$. For each interior $i$, $\varphi (i+1)-\varphi (i)=((1-r)r^{i-a})\mathrm{/}(1-r^{b-a})=r(\varphi (i)-\varphi (i-1))$. Since $pr=q$, this is equivalent to $p\varphi (i+1)+q\varphi (i-1)=\varphi (i)$. The almost-sure exit in step 2.1 and [F5], applied to boundary payoff $f(b)=1$, $f(a)=0$, identify ${\mathbb{P}}_i(T_b<T_a)=\varphi (i)=(1-r^{i-a})\mathrm{/}(1-r^{b-a})$ for $a<i<b$. The endpoints also have the displayed boundary values by the time-zero hitting convention in [F15].

If $x<y$, choose integers $M$ with $-M<x$ and use step 3.1 on $[-M,y]$; then ${\mathbb{P}}_x(T_y<T_{-M})=(1-r^{x+M})\mathrm{/}(1-r^{y+M})$. As $M$ increases these events increase, and their union is $\{T_y<\mathrm{\infty }\}$: every finite path segment ending at its first visit to $y$ has a finite minimum, so a sufficiently distant lower boundary is not reached first. By [F11] and [F12], the probabilities converge to $1$. If $x>y$, use $[y,M]$ with $M>x$; step 3.1 gives ${\mathbb{P}}_x(T_y<T_M)=1-(1-r^{x-y})\mathrm{/}(1-r^{M-y})=(r^{x-y}-r^{M-y})\mathrm{/}(1-r^{M-y})$. These events increase to $\{T_y<\mathrm{\infty }\}$ because each finite path segment has a finite maximum, and [F11] and [F12] give the limit $r^{x-y}$. When $x=y$, $T_y=0$ and the hitting probability is $1$. Hence ${\mathbb{P}}_x(T_y<\mathrm{\infty })=1$ for $x\le y$ and $r^{x-y}$ for $x>y$.

From $y$, the first step goes to $y+1$ with probability $p$ or to $y-1$ with probability $q$, and there is no holding transition. The bounded future Markov identity [F6], applied to the event of ever hitting $y$ from the shifted path after time one, and the one-time marginal in [F7] together with step 4.1 give ${\rho }_y:={\mathbb{P}}_y(T_y^{+}<\mathrm{\infty })=p{\mathbb{P}}_{y+1}(T_y<\mathrm{\infty })+q{\mathbb{P}}_{y-1}(T_y<\mathrm{\infty })=pr+q=2q$. Since $p>q$ and $p+q=1$, $2q<1$ and $y$ is transient by [F8]. The Green criterion [F9] and [F10] now give $G(y,y)={\sum }_{m\ge 0}{P}^{(m)}(y,y)=1\mathrm{/}(1-2q)=1\mathrm{/}(p-q)<\mathrm{\infty }$.

Fix $x,y$ and put $a_k={\mathbb{P}}_x(T_y=k)$ and $b_m=P^{(m)}(y,y)$. For every $n\ge 0$, the disjoint events $\{T_y=k,X_n=y\}$ for $0\le k\le n$ partition $\{X_n=y\}$, and finite additivity follows from [F16]. The events $\{T_y=k\}$ partition $\{T_y<\mathrm{\infty }\}$, so countable additivity [F16] gives ${\sum }_k{a}_k={\mathbb{P}}_x(T_y<\mathrm{\infty })$. For $m=n-k$, apply [F13] at $T_y$ to the bounded path functional $H_m(\omega )={\mathbf{1}}_{\{{\omega }_m=y\}}$. On $\{T_y=k\}$ the stopped state is $y$, and [F7] identifies the post-hit probability with $b_m$; thus ${\mathbb{P}}_x(T_y=k,X_{k+m}=y)=a_k{b}_m$. Summing the finite partition and then over $n$, [F7] and [F14] give $G(x,y)={\sum }_{n\ge 0}{\mathbb{P}}_x(X_n=y)={\sum }_{k,m\ge 0}{a}_k{b}_m$. The rectangular partial sums factor as $({\sum }_{k\le K}{a}_k)({\sum }_{m\le M}{b}_m)$ and converge to the product of their finite limits: ${\sum }_k{a}_k={\mathbb{P}}_x(T_y<\mathrm{\infty })\le 1$ and ${\sum }_m{b}_m=G(y,y)=1\mathrm{/}(p-q)$ by step 4.1. Therefore $G(x,y)={\mathbb{P}}_x(T_y<\mathrm{\infty })G(y,y)$. Substitution of step 4.1 and the diagonal value from step 5.1 proves the stated two cases. This argument counts the time-zero visit when $x=y$ and uses the nonnegative Green series throughout, so no subtraction of extended values occurs.

The state space is the fixed infinite set $\mathbb{Z}$, so empty and one-state spaces cannot instantiate the Example. In the auxiliary interval $a<b$; if $b=a+1$, both states are absorbing endpoints and there is no interior equation, and step 3.1 uses its formula only when $a<i<b$. Endpoint starts have $T_D=0$ by steps 2.1–3.1, while $T_y=0$ for $x=y$ and $T_y^{+}$ requires a strictly positive return [F15]. Step 6.1 includes the time-zero visit in the Green series.

AC [A1] is used for canonical path laws [F3] and through the conditional Markov, finite-Dirichlet, finite-dimensional-law, recurrence-criterion and strong-Markov results [F5], [F6], [F7], [F9], [F13]; the explicit kernel, interval-path and difference-equation calculations are choice-free. The claim is a formula, not an iff statement.