A repulsive random walk
Matt Asher posted an R experiment on R-bloggers yesterday simulating the random walk
which has the property of avoiding zero by quickly switching to a large value as soon as is small. He was then wondering about the “convergence” of the random walk given that it moves very little once
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
comes back to the interval (-1,1) with probability
, a probability which goes to zero with
. As suggested to me by Randal Douc, this transience can be established rigorously by considering
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.
July 20, 2010 at 4:38 am
sorry, I meant “is not recurrent”
(with a 2-lines rigorous proof)
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.)
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
is taking only
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…
June 2, 2010 at 2:23 pm
I must say that I was almost convinced – but the fact that the process
defined by
always comes back in a neighbourhood of
bothers me a little bit …
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)…
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
with
has a square that is bounded below by a null recurrent process, but does not tend to infinity almost surely, isn’t it ?
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
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
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…
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
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
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=]