# 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})$.

• What do you mean by "there is a drift away from the origin, which tends to zero as ∥s∥ increases"? – Iosif Pinelis Jul 26 '16 at 12:22
• I think in your example $E[X_n]$ should be around $n^{2/3}$, see Theorem 3.12.4 of www.ime.unicamp.br/~popov/book_lyapunov.pdf; in general, this type of question can be investigated with Lyapunov functions. See e.g. Section 2.8, 3.9, 3.10, 3.12 of that book. – Serguei Popov Jul 26 '16 at 12:31
• I took some time searching for Lyapunov functions, but didn't find an appropriate source or paper. I simulated my example, and your right. The growth is indeed $n^{2/3}$. Thank you for this nice reference! @Iosif: I wanted to describe, that the drift decreases, if we go away from the origin. You are right, that I didn't specify it: I think there exists a non-negative function $f: \mathbb{R}_+ \rightarrow \mathbb{R}_+$, with $\lim_{x \rightarrow \infty} f(x) = 0$, such that the drift at state $s$ is upper bounded by $f(\|s\|)$. – Fisher Jul 29 '16 at 8:52

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|$$
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.