Markov chain that is "increasing" on average Suppose that $S = \mathbb{Z}_{\geq 0}$ and that $X_n$ is an irreducible, aperiodic Markov chain satisfying that for all $x \in S$ that $E_x[X_n] \geq x$ so that in expectation $X_n$ is not decreasing. Is it true that $X_n$ is not positive recurrent? There are simple examples of such $X_n$ that are transient or null recurrent, but I can't think of any that are positive recurrent.
I tried using the expectation condition to examine the expected return time to say $x = 0$ to try to show the expectation is infinite but did not have any success. Does anyone have any hints or insights?
 A: This summarizes my comments and discusses your last question in the comments.

Indeed we can have an irreducible, aperiodic, positive recurrent DTMC $\{X_n\}_{n=0}^{\infty}$ with state space $S=\{0, 1, 2, ...\}$ and with positive drift in each state.  Design transition probabilities:

*

*$P_{0,0} = 1/2$, $P_{0,1}=1/2$


*For $i \in \{1, 2, 3, ...\}$:

*

*$P_{i,0} = 1/2, P_{i,i+1}=1/4, P_{i,...} = ?$
Any way we fill in the remaining transition probabilities, the DTMC will be irreducible, aperiodic, and positive recurrent.  We can design the missing probabilities to ensure
$$E[X_{n+1}-X_n|X_n=i] \geq 0 \quad \forall i \in \{0, 1, 2, ...\}$$
Indeed, as you suggested in the comments, using $P_{i,4i}=1/4$ for $i \in \{1, 2, 3, ...\}$ accomplishes this.

Fix $k$ as a positive integer and suppose we have a DTMC $\{X_n\}_{n=0}^{\infty}$ on the state space $S=\{0,1,2,...\}$ that satisfies:

*

*$P_{i, i+h}=0$ for all $i \in S$ and all $h\geq k$.  That is, the DTMC can move forward by at most $k$ in one step.


*Nonnegative drift: $E[X_{n+1}-X_n|X_n=i]\geq 0 \quad \forall i \in \{0, 1, 2, ...\}$
Claim: For this DTMC, the expected time to get from state 1 to state 0 is infinity.
Proof: Define a new DTMC $\{Y_n\}_{n=0}^{\infty}$ that is the same except that $0$ is a trapping state (so all transition probabilities out of a state $i \in \{1, 2, 3, ...\}$ are the same, but we redefine $P_{0,0}=1$). The expected time to get from state 1 to state 0 is the same for this new DTMC. Suppose $Y_0=1$ surely. The nonnegative drift condition implies:
$$ E[Y_n]\geq 1 \quad \forall n \in \{0, 1, 2, ...\} \quad (*)$$
Because we can move forward by at most $k$ hops on each step we have:
$$ Y_n \leq (1 + kn)1_{\{Y_n\neq 0\}} \quad \forall n \in \{0, 1, 2, ...\}$$
where $1_{\{Y_n\neq 0\}}$ is an indicator function that is $1$ if $\{Y_n\neq 0\}$ and $0$ else.  Since $1\leq kn$ for all $n \in\{1, 2, 3, ...\}$ we have
$$ Y_n \leq 2kn 1_{\{Y_n\neq 0\}} \quad \forall n \in \{1, 2, 3,  ...\}$$
Taking expectations of both sides gives
$$ E[Y_n] \leq 2knP[Y_n\neq 0] \quad \forall n \in \{1, 2, 3, ...\}$$
Substituting (*) gives $1\leq 2knP[Y_n\neq 0]$ and so
$$ \frac{1}{n} \leq 2kP[Y_n\neq 0] \quad \forall n \in \{1, 2, 3, ...\}$$
Let $T$ be the time to get to 0 (starting from state 1).  Then $P[Y_n\neq 0] = P[T>n]$ and so
$$ \frac{1}{n} \leq 2kP[T>n] \quad \forall n \in \{1, 2, 3, ...\}$$
Summing the above gives
$$\underbrace{\sum_{n=1}^{\infty} \frac{1}{n}}_{\infty} \leq 2k\sum_{n=1}^{\infty}P[T>n] \leq 2kE[T]$$
and so $E[T]=\infty$. $\Box$
