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.
Best Answer
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?