# Markov chains- recurrence and transience

This is an exercise in Durrett's probability book.

$p$ is the transition probability for a markov chain on a countable space. $f$ is said to be superharmonic if $f(x)\geq\sum_y p(x,y)f(y)$, or equivalently $f(X_n)$ is a supermartingale. Suppose $p$ is irreducible. If every nonnegative superharmonic function is constant, show that $p$ is recurrent.

It's not that easy to use the statement "every nonnegative superharmonic function is constant", so I tried 2 ways to reformulate the statement.

1.For all $f\geq 0$ nonconstant, there exists an $x$ s.t. $f(x)<\sum_y p(x,y)f(y)$. Show that $p$ is recurrent.

2.If $p$ is transient, show that there exists a nonnegative superharmonic function which is nonconstant.

But I haven't got a clue about how to prove this.

-

I think the easiest way is through strategy 2). Let $X$ be a transient irreducible Markov Chain. Consider an arbitrary $x_{0}$ and define:

$$\tau = \inf\{n \geq 0: X_{n} = x_{0}\}$$

Define

$$f(x) = P(\tau < \infty|X_{0}=x)$$

By construction, $f(x) \in [0,1]$ and $f(x_{0}) = 1$. Since $X$ is transient, there exists $y$ such that $f(y) < 1$. Finally, by Markovianity, for any $x \neq x_{0}$,

$$f(x) = P(\tau < \infty|X_{0}=x) = \sum_{y}{p(x,y)P(\tau < \infty|X_{1}=y)} = \sum_{y}{p(x,y)f(y)}$$

and

$$f(x_{0}) = 1 \geq \sum_{y}{p(x,y)f(y)}$$

Hence, $f$ is super-harmonic and non-constant.

ps: the condition is actually necessary and sufficient. Can you prove the reverse?

-
Yes the condition is necessary and sufficient. I have proved the reverse and that's why I only asked the first part. In fact, if $p$ is recurrent and let $f$ be a nonnegative superharmonic function, then $f(X_n)$ is a nonnegative supermartingale thus $f(X_n)\rightarrow Y, a.s.$ As $p$ is recurrent, for all $x, P(f(X_n)=f(x), i.o.)=1$, thus $Y=f(x) a.s.$ As this is true for all $x$, $f$ is constant. – Iew Jul 3 '12 at 16:24