## A repulsive random walk

Matt Asher posted an R experiment on R-bloggers yesterday simulating the random walk

$x_{t+1} = x_t + \varepsilon_t / x_t$

which has the property of avoiding zero by quickly switching to a large value as soon as $x_t$ is small. He was then wondering about the “convergence” of the random walk given that it moves very little once $x_t$ is large enough. The values he found for various horizons t seemed to indicate a stable regime.

I reran the same experiment as Matt in a Monte Carlo perspective, using the R program

resu=matrix(0,ncol=100,nrow=25)
sampl=rnorm(100)
for (i in 1:25){
for (t in 2^(i-1):2^i) sampl=sampl+rnorm(100)/sampl
resu[i,]=sampl
}
boxplot(as.data.frame(t(abs(resu))),name=as.character(1:25),col="wheat3")

The outcome of this R code plotted above shows that the range and the average of the 100 replications is increasing with t. This behaviour indicates a transient behaviour of the Markov chain, which almost surely goes to infinity and never comes back (because at infinity the variance is zero). Another indication for transience is shown by the fact that $x_t$ comes back to the interval (-1,1) with probability $\Phi(-|x_t|)$, a probability which goes to zero with $x_t$. As suggested to me by Randal Douc, this transience can be established rigorously by considering

$x_{t+1}^2 = x_t^2 + 2\epsilon_t + \epsilon_t^2/x_t^2 > x_t^2 + 2\epsilon_t>2\sum_{i=1}^t \epsilon_t$

which is thus bounded from below by a null recurrent process, which almost surely goes to infinity. Therefore the above Markov chain cannot have a stationary distribution or even a stationary measure: it almost surely goes to (plus or minus) infinity.

### 10 Responses to “A repulsive random walk”

1. sorry, I meant “is not recurrent”

(with a 2-lines rigorous proof)

2. you might be interested to know that an extremely similar ‘repulsive’ walk is recurrent:
http://www.artofproblemsolving.com/Forum/viewtopic.php?uid=96&f=498&t=351254&unwatch=topic

(The one considered in the link is more or less the square of the one considered in this post.)

• Thank you, Alek! The shape is indeed very similar, the main difference being the fact that the noise $\epsilon_k$ is taking only $\pm 1$ values. But the spirit is indeed the same.I have actually wondered more generally about a possible link between recurrence for discrete and continuous random walks…

3. I must say that I was almost convinced – but the fact that the process $X_t$ defined by $dX_t = \frac{dW_T}{X_t}$ always comes back in a neighbourhood of $0$ bothers me a little bit …

• I have no deep intuition about continuous time processes, but the fact is that the discretised versions do not always enjoy the same properties as their continuous relative. Take, e.g., the Langevin diffusion (which is recurrent) and the Langevin “random walk” (which may be transient)…

4. I don’t get the conclusion “Therefore the above Markov chain cannot have a stationary distribution or even a stationary measure: it almost surely goes to (plus or minus) infinity.”

For example $Z_N = \sqrt{|S_N|}$ with $S_N = \epsilon_1 + \ldots+\epsilon_N$ has a square that is bounded below by a null recurrent process, but does not tend to infinity almost surely, isn’t it ?

• Alek: I have had email exchanges with Randal Douc and Arnaud Guillin about this point… My understanding of the behaviour of the null recurrent random walk $S_N = \epsilon_1 + \ldots+\epsilon_N$ is that it visits arbitrarily far regions with a positive probability and that it takes on average an infinite time for the random walk to come back near zero. So it does not almost surely go to infinity (which would violate the null recurrence property). However, if we consider the chain $(x_t)$ itself, its dynamics imply that once it reaches infinity, its variance gets to zero and therefore it remains stuck there. I realise this is not a bullet-proof argument, but it suffices to convince me of the transience of the chain…

5. Ruben Garcia Says:

Hi Xi’an,
thanks a lot for the code.
I’m new to R and these kind of examples are all very enlightening for me.
Regards,
Ruben

6. Ruben Garcia Says:

Hi Xi’an,
I’d like to replicate your results using R 2.11.0 on Leopard but unfortunately the graph doesn’t match: the boxes are much smaller and the X-axis shows V1…V24 instead of just the numbers.
Any idea how I could fix that?
Ruben

• Thanks for the comment: I use
H=25 boxplot(as.data.frame(t(abs(resu))),col="wheat3", names=as.character(1:H),borders=FALSE,outline=FALSE,xlab=expression(log[2](T)),ylab="",ylim=c(0,quantile(resu,.95))
to get a reasonable range for the boxes [ylim] and the numbers at the bottom [names=]

This site uses Akismet to reduce spam. Learn how your comment data is processed.