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.

This entry was posted on May 28, 2010 at 11:41 am and is filed under R, Statistics with tags Markov chain, R-bloggers, random walk, recurrence, transience. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

10 Responses to “A repulsive random walk”

Alekk Says:
July 20, 2010 at 4:38 am

sorry, I meant “is not recurrent”

(with a 2-lines rigorous proof)

Reply
Alekk Says:
July 20, 2010 at 4:30 am

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

Reply
- xi'an Says:
  July 20, 2010 at 7:21 am
  
  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…
  
  Reply
Alekk Says:
June 2, 2010 at 2:23 pm

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 …

Reply
- xi'an Says:
  June 2, 2010 at 2:33 pm
  
  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)…
  
  Reply
Alekk Says:
May 31, 2010 at 2:45 pm

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 ?

Reply
- xi'an Says:
  June 1, 2010 at 8:52 am
  
  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…
  
  Reply
Ruben Garcia Says:
May 30, 2010 at 7:23 am

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

Reply
Ruben Garcia Says:
May 29, 2010 at 4:36 am

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?
Many thanks in advance,
Ruben

Reply
- xi'an Says:
  May 29, 2010 at 8:47 am
  
  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=]
  
  Reply