How do I show that the mean recurrence time for transient states is infinity?

1k Views Asked by At

The random variable $T_i$, the "Hitting Time of $i$" is defined to be the first $n$ such that $X_n=i$ given that $X_0=i$.

By the mean recurrence time of $T_i$, I mean the expected value of this random variable.

I wish to show that if $i$ is transient, then the expectation does not converge to any finite real number. While this, intuitively makes sense, I do not know how to formally prove this and any help is appreciated.

2

There are 2 best solutions below

3
On

I don't think you have the definition quite right. The first passage time $T_i$ is the minimum $n$ such that $X_n = i$ given $X_0 = i$, and is defined to be $\infty$ if no such $n$ exists.

In that light, we just need to know that a state $i$ is transient if there's some other state $j$ such that $i \rightarrow j$, but $j \not\rightarrow i$. That is, if a (finite-state, discrete-time) Markov chain initialized at state $i$ reaches state $j$ it almost surely never returns to $i$. Because $i \rightarrow j$, this happens with positive probability and thus $T_i = \infty$ with positive probability. (Which implies $\mathbb{E}[T_i] = \infty$).

One reference you may find useful is these lecture notes.

0
On

Note that state $i$ is persistent iff, $$ P(X_n = i \text{ for some } n \geq 1| X_0 = i) = 1$$

Each state is transient or persistent.
The hitting time of state $i$, $T_i$, is a random variable defined as the first time we visit state $i$: $$ T_i = \min \{n | n \geq 1, X_n = i\} $$ where $T_i$ is defined as $\infty$ if this visit never happens.

We now show that $ P(T_i = \infty | X_0 = i) > 0 $ iff state $i$ is transient. Then, the required result on the mean recurrence time follows, because the mean recurrence time $\mu_i$ is defined as: $$\mu_i = E(T_i| X_0 = i) $$

Suppose state $i$ is transient. Then, $$ \begin{align} P(T_i = \infty | X_0 = i) & = P(X_n \neq i \text{ for all } n \geq 1 | X_0 = i) \\ & = 1 - P(X_n = i \text{ for some } n \geq 1 | X_0 = i) \\ & > 1 - 1 = 0. \end{align} $$

Suppose state $i$ is persistent. Then, $$ \begin{align} P(T_i = \infty | X_0 = i) & = P(X_n \neq i \text{ for all } n \geq 1 | X_0 = i) \\ & = 1 - P(X_n = i \text{ for some } n \geq 1 | X_0 = i) \\ & = 1 - 1 = 0. \end{align} $$

This shows both directions, and completes the proof.