0

I have found the following theorem in a book:

Let $s \in S$ be any state of an irreducible Markov chain on state space $S=\{0,1,2,...\}$. The chain is recurrent if there exists a solution $\{ y_j : j \not= s \}$ to the inequalities $$ y_i \geq \sum_{j: j \not=s} p_{ij} y_j, \quad i \not=s,$$ such that $y_i \rightarrow \infty$ as $i \rightarrow \infty$.

Now my professor said that I can't use it if $S$ is finite. I have to give an additional condition in that case, because $i$ is in the sense of a state and not an integer number. Is he right?

I think he is wrong, since one can see in the following example I figured out. Am I right?

Example: Let $S=\{0,1,2 \}$ with transition matrix $$P=\begin{pmatrix} 2/3 & 1/3 & 0 \\ 2/3 & 0 & 1/3 \\ 0 & 2/3 & 1/3 \end{pmatrix}$$.

I take $s=0$ and claim that $\{ y_j=j : j > 0 \}$ is a solution to the inequalities above. Indeed: $$i=1 : \ y_1=1 \geq p_{11}y_1 + p_{12}y_2=2/3.$$ $$i=2 : \ y_2=2 \geq p_{21}y_1 + p_{22}y_2=4/3.$$ And for $i>2$, we have that $i \geq 0$ always. Further $y_i \rightarrow \infty$ as $i \rightarrow \infty$.

mr_T
  • 303

1 Answers1

1

As stated, the theorem explicitly requires S to be an infinite set.

However, it is also true for finite sets (trivially): Every finite irreducible Markov chain is recurrent. This follows from the pigeon hole principle: if there are finitely many states, then over infinitely many time steps, some state must be visited infinitely many times. Then using irreducibility, every state must be visited infinitely many times.

Nate Eldredge
  • 97,710