Is there an irreducible Markov chain admitting a non-constant bounded harmonic function? I am asked the following question: Does there exist an irreducible Markov chain which admits a non-constant bounded harmonic function? Either give an example or prove that such examples do not exist.
So far I showed that an irreducible recurrent Markov $(X_n)_{n \in \mathbb{N}}$ does not admit such a function. Namely, suppose $\varphi$ is such a function. Define for $y$ in the state space $\tau_y := inf\{n \geq 1 \mid X_n = y\}$. Then by recurrence $\tau_y$ is finite a.s. and by optional stopping time theorem it follows that $(\varphi(X_{n \wedge \tau_y}))_{n \in \mathbb{N}}$ is a martingale. Therefore for $X_0 = x$ we have
\begin{align*}
\varphi(x) = \varphi(X_0) = \mathbb{E}_x[\varphi(X_{n \wedge \tau_y})] \rightarrow \mathbb{E}_x[\varphi(X_{\tau_y})] = \varphi(y)
\end{align*}
which shows that $\varphi$ must be constant. 
How about the transient case?
 A: A typical argument for proving that harmonic functions are constant is to consider the state with the maximum value of the function, and argue from there that adjacent states must also have same value, and so forth.
This fails for infinite Markov chains, because then the maximum value may never be achieved. So that gives us a place to go with finding an example: we want an infinite state space and a bounded harmonic function on that space that approaches but does not reach its minimum or maximum.
So let's suppose that the state space of our Markov chain is $\mathbb Z$, and the function $\varphi$ is something without a minimum or maximum. (Let's assume it's strictly increasing; for the natural "shape" of a random walk on $\mathbb Z$, local minima or maxima would be just as tricky as global ones.) $\varphi(n) = \frac{2^n}{2^n+1}$ and $\varphi(n) = \arctan(n)$ are two easy-to-define examples of this form.
We can make this harmonic by defining our random walk appropriately. For each $n$, define $p_{n,n+1} = \frac{\varphi(n) - \varphi(n-1)}{\varphi(n+1) - \varphi(n-1)}$ and $p_{n,n-1} = \frac{\varphi(n+1) - \varphi(n)}{\varphi(n+1) - \varphi(n-1)}$. This will produce valid transition probabilities whenever $\varphi$ is strictly increasing. For $\varphi(n) = \frac{2^n}{2^n+1}$, it actually gives relatively nice formulas: $p_{n,n+1} = \frac23 (\frac{2^{n+1}+1}{2^{n+1}+2})$ and $p_{n,n-1} = \frac13(\frac{2^n+2}{2^n+1})$.
As a result:

*

*$\varphi$ is harmonic because $p_{n,n+1} \varphi(n+1) + p_{n,n-1} \varphi(n-1)$ simplifies to $\varphi(n)$.

*The random walk is irreducible because $p_{n,n+1}$ and $p_{n,n-1}$ are strictly positive for all $n$.

