6
$\begingroup$

According to Wikipedia with a little rephrasing:

A state $i$ is transient if and only if $P(T_i < \infty) <1$, recurrent if and only if $P(T_i < \infty) =1$, where $T_i$ is the first hitting time to i, i.e. $T_i=\inf\{n \in \mathbb{N} \cup \{ \infty \}: X_n=i \mid X_0=i \}.$

If I understand correctly, this can be used as the definition of transient/recurrent state.

Usually $P(T_i < \infty)$ is written as a series $\sum_{n \in \mathbb{N}} P(T_i = n)$. But I would like to learn other ways to tell if a state is recurrent/transient, which might be easier in some cases.

  1. For example, can a transient/recurrent state be completely characterized in terms of closed subsets of states (defined similarly as an absorbing state), as follows (my own quote)?

    State $i$ is transient if and only if there exists a closed subset $S$ of states, s.t. $i \notin S$ and there exists $s \in S$ and $n \in \mathbb{N}$ and the $n$-step transition probability $p_{is}^{(n)} > 0$.

    Similarly, State $i$ is recurrent if and only if there does not exist such a closed subset of states as described above?

    Can we also characterize positive/null recurrence in terms of closed subsets of states?

  2. Off the top of your head, what are some other necessary and/or sufficient conditions for recurrent/transient and positive/null recurrent state?

Thanks and regards!

2 Answers 2

8

(0) The definition of $T_i$ on Wikipedia is awful on at least three counts. One should define $T_i=\inf A_i$ with $A_i=\{n\ge1:X_n=i\}\cup\{+\infty\}$ and one should say that $i$ is transient if and only if $P(T_i<+\infty|X_0=i)<1$ and recurrent otherwise.

(1) In some cases there exists no closed subset at all and the existence of closed sets is not related to recurrence or transience.

First example: consider a homogenous random walk on $\mathbb{Z}$. Thus $p_{n,n+1}=a$ and $p_{n,n-1}=1-a$ for every $n$, for a given $a$ in $(0,1)$. Then there exists no closed set except $\mathbb{Z}$ and the chain is recurrent if $a=\frac12$ and transient otherwise.

Second example: consider a homogenous birth-and-death chain such that $0$ is absorbing. Thus $p_{0,0}=1$ and $p_{n,n+1}=a$ and $p_{n,n-1}=1-a$ for every $n\ge1$, for a given $a$ in $(0,1)$. Then the set $S=\{0\}$ is closed and the chain is recurrent if $a\le\frac12$ and transient otherwise.

(2) You could (should?) read the beautiful small book Random Walks and Electric Networks by Peter G. Doyle and J. Laurie Snell, which explains this and a lot of related stuff in a very accessible way.

  • 0
    @Tim: Sorry but the answer is no. All I can suggest is that you read slowly my comment and try to digest it, since I cannot do better than what I wrote. (Or find yourself a good introductory probability book, for example here http://www.math.duke.edu/~rtd/.)2011-03-18
6
  1. Tim's characterization of states in terms of closed sets is correct for finite state space Markov chains. Partition the state space into communicating classes. Every recurrent class is closed, but no transient class is closed (because the chain must eventually get "stuck" in some recurrent class). The part in parentheses is false for infinite state space chains, as Didier's answer shows.

  2. Another well-known characterization is that a state $i$ is transient if and only if $\sum_{n=1}^\infty P(X_n=i | X_0=i)<\infty.$ This criterion is used, for example, to prove Polya's result that the symmetric random walk on $\mathbb{Z}^d$ is recurrent if $d=1,2$, but transient when $d\geq 3$.

  3. Similarly, the probability
    $P(X_n=i\mbox{ for infinitely many } n | X_0=i)$ is equal to zero or one, depending on whether the state $i$ is transient or recurrent.

  • 0
    My bad. Didier's second example is a counterexample to the sufficient statement. I went out for a while before coming back, and I thought I had read his edit but I actually missed that.2011-03-18