Asymptotic Growth of Markov Chain I asked the following question one week ago at math.stackexchange but didn't receive a response, so I want to give it here another try:
I'm interested in the following problem: We have got a time-discrete Markov chain $(X_n)$ with state space $S=\mathbb{R}^d_+$. The transition kernel is discrete in the sense, that for each $s \in S$ there is a finite subset $S′ \subset S$, such that $P[X_{n+1} \in S′|X_n=s]=1$. Furthermore, we can assume that there exists a constant $c$, such that for all $n$ we have $\|X_{n+1}−X_n\|≤c$. We also know, that there is a drift away from the origin, which tends to zero as $\|s\|$ increases.
I want to show, that $E[\|X_n\|]$ is in $o(n)$ (i.e., it behaves in a sublinear way). Could you give me some ideas how to show this statement?
To illustrate the question I give a concrete example: Assume $X_0=0$
and $X_{n+1}=\max(0,X_n+\frac{2}{\sqrt{X_n}}+Y_{n+1})$, where the $Y_i$ are i.i.d. with probability distribution $P[Y_i=−1]=P[Y_i=1]=1/2$. This Markov chain behaves like a classical random walk if $X_n$ is very large, so $E[X_n]$ should behave like $O(\sqrt{n})$.
 A: One way to do it is by first proving it for an appropriate "comparison" chain just  on $\mathbb R_+$, and then showing that there is a measure preserving map $\pi$ from the path space of the comparison chain to the path space of the original chain such that 
$$
\mathop{dist} ((\pi\mathbf x)_t,(\pi\mathbf x)_0) \le |\mathbf x_t - \mathbf x_0|
$$
A: My approach would be to write your problem as a stochastic approximation algorithm. 
Let $f$ denote your drift:
$$ f(x) := E[X_{n+1}-X_n | X_n=x]$$ and let $U_{n+1} = X_{n+1}-X_n-f(X_n)$. As $||X_{n+1}-X_k||$ is bounded, the variance of $U_{n+1}$ is finite. Moreover, $U_{n+1}$ is a martingale difference sequence (i.e. $E[U_{n+1}| F_n]=0)$. By the martingale central limit theorem, this implies that $\sum_{n=1}^n U_n$ is $O(\sqrt{n})$ for $n$ large. 
Now, you have $X_{n+1} = X_n + f(X_n) + U_n$. Developing this recurrence, you have: 
$$ X_{n+1} = X_0 + \sum_{k=1}^n f(X_k) + O(\sqrt{n})$$
If the drift $f(x)$ tends to sufficiently fast, this sum cannot grow linearly. 
