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

  • $\begingroup$ What do you mean by "there is a drift away from the origin, which tends to zero as ∥s∥ increases"? $\endgroup$ Jul 26, 2016 at 12:22
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 26, 2016 at 12:31
  • $\begingroup$ 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\|)$. $\endgroup$
    – Fisher
    Jul 29, 2016 at 8:52

2 Answers 2


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.