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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 604 other followers