# Nonhomogeneous random walk with increasing probability of staying still

Let $$\alpha \geq 1$$ and $$X_n$$ be independent random variables such that $$P(X_n=2)=P(X_n=-2)=\frac 1{2n^\alpha}$$ and $$P(X_n=0)=1-\frac 1{n^\alpha}$$. Let $$S_n=\sum_{k=1}^n X_k$$.

Depending on the value of $$\alpha$$, what are the properties of $$S_n$$ (convergence, asymptotic behaviour)?

$$S_n$$ is clearly a Markov chain on the even integers. Note that it is not time-homogeneous or stationary.

Since $$E(X_n)=0$$ and $$V(X_n)=\frac 4{n^\alpha}$$, we have $$V(S_n)=4\sum_{k=1}^n \frac{1}{k^\alpha}$$.

Whether $$\alpha=1$$ or $$\alpha >1$$, we have respectively $$V(S_n)=O(\log n)$$ and $$V(S_n)=O(1)$$. In both cases, by Markov's bound, for any $$\epsilon >0$$ and $$\delta >0$$, $$P(\frac{|S_n|}{ n^{1/2+\epsilon}}\geq\delta) = P(|S_n|\geq n^{1/2+\epsilon}\delta)=O\left( \frac{\log n}{n^{1+2\epsilon}}\right)$$ and since $$\sum_n \frac{\log n}{n^{1+2\epsilon}} < \infty$$, we get $$S_n = o\left(n^{1/2+\epsilon} \right)$$ a.s.

As noticed by Olivier in the comments, if $$\alpha>1$$, $$\sum_n P(X_n\neq 0) = \sum_n \frac{1}{n^\alpha}<\infty$$ thus by Borel-Cantelli lemma, $$P(\limsup_n (X_n\neq 0)) = 0$$, i.e. $$P(\liminf_n (X_n= 0)) = 1$$ Hence almost surely, $$S_n$$ becomes constant.

Olivier also noticed that $$S_n$$ is a martingale, and for $$\alpha>1$$, $$E(S_n^2) = V(S_n)=O(1)$$. A result from the theory of martingales implies that $$S_n$$ converges almost surely and also converges in $$L^2$$.

The characteristic function of $$S_n$$ is $$\prod_{k=1}^n \frac 1{2k^\alpha} e^{2it} + \frac 1{2k^\alpha} e^{-2it} + 1-\frac 1{k^\alpha} = \prod_{k=1}^n \left(1-\frac{1-\cos(2t)}{k^\alpha}\right)$$ When $$\alpha=1$$, this converges pointwise to $$t\mapsto 1_{\pi \mathbb Z}(t)$$ This limit is not a continuous function, so Lévy's continuity theorem does not apply. This rather indicates that $$S_n$$ does not converge in distribution when $$\alpha=1$$.

• Hi Gabriel. One idea for intuition - and perhaps eventually for proof (?) : in continuous time, continuous martingales may be time changed into browian motions; the situation is quite similar here; the process at time $n$ should be close to a simple random walk at time $4 \log(n)$. I'll think of references to push this approach (check perhaps Lawler Limic). – Olivier Sep 12 at 21:44
• About cvg in probability/a.s. convergence : as soon as $\alpha>1$, Borel-Cantelli gives you almost sure convergence of the $X_n$ towards 0, meaning the process $S_n$ converges (=is ultimately constant here). Also, the process $S_n$ is a martingale and under the same condition $\alpha>1$, estimation on the variance ensures the process is bounded in $L^2$, leading to the same conclusion plus the fact that the limit is in $L^2$; beware there is a typo in the calculation of the variance of $S_n$ in your post, you have sumed the tails, this invalidates your first paragraph. – Olivier Sep 13 at 14:40
• @Olivier Thanks for your nice response and sorry for the non-sense. I'm wondering what more can be said about the a.s limit when $\alpha >1$ ? I've updated my post to show that $S_n = o\left(n^{1/2+\epsilon} \right)$ a.s. (for $\alpha \geq 1$). I'd be interested in sharper estimates. Also, for $\alpha>1$, it'd be interesting to say something about $\tau$ the random time after which the walk becomes constant. E.g. does $\tau$ have an expectation ? – Gabriel Romon Sep 13 at 15:20
• By the application of the Kolmogorov's Three-Series Theorem, we know that $(S_n)_{n\geq 1}$ converges almost surely if and only if $\alpha > 1$. Moreover, it is well-known that an independent sum converges almost surely if and only if it converges in distribution. So this completely addresses the question of convergence of $S_n$ with probability one, in probability, and in distribution. – Sangchul Lee Sep 13 at 16:45
• Also, for $\alpha \in (0, 1]$, Lindeberg condition is satisfied, and so, $S_n/s_n\to\mathcal{N}(0,1)$ in distribution as $n\to\infty$, where $s_n:=\sqrt{\mathbf{Var}(S_n)}$. And as Olivier pointed out, I suspect that $S_n$ would behave like a random walk at time $s_n^2$. For instance, the Martingale FCLT tells that the linear interpolation of points $\{(s_k^2/s_n^2,S_k/s_n)\}_{k=0}^{n}$ converges weakly to the law of the Weiner process $\{W_t\}_{0\leq t\leq1}$. And I suspect that $S_n$ satisfies a form of Law of Iterated Logarithm, although I have no proof yet. – Sangchul Lee Sep 14 at 0:01