Take the 2-minute tour ×

Imagine a discrete random walk on an infinite one-dimensional lattice where, for every unit interval of time, $(t_1, t_2, ...)$, the walker takes a step with uniform probability to its left or right.

We add the constraint that each time the walker visits a vertex, the vertex is transiently "blocked", and cannot be revisited by the walker until it is "unblocked", which has a constant probability $p$ of occurring during every unit interval of time $t_i$ prior to the walker taking a step. In other words, every time the walker visits a vertex, the vertex is assigned an exponentially distributed random variable $X$ (always with the same rate parameter $\lambda = p$) that determines the number of time intervals that need to pass (counting from the interval in which the site is "blocked") before it can be reoccupied by the walker. If the vertex to the right or left of a walker is blocked during some time interval, it will move to the left or right, respectively. In the situation where sites to the left and right of the random walker are "blocked", the walker will remain in place for that unit interval of time.

To provide the extremal examples, if $p = 1$, sites are immediately unblocked prior to the walker taking its next step, and one will have a vanilla one-dimensional random walk with a Gaussian probability distribution. If, however, we set $p = 0$, sites will never "unblock" and the walk will become fully self-avoiding and, with a direction chosen with uniform probability, continuously move to the right or left without ever revisiting the origin.

As a function of $p$, what is the probability distribution for this walker? How does this walk generalize to higher dimensions, specifically $D = 2$? Is there a "magic term" for this sort of walk, and are there any good literature references?

As a sort of cute extension, provided some $p$ can we predict the mean distance the walker will travel returning to its point of origin?

Note - I would be happy to accept the simplification where, instead of assigning vertices an exponentially distributed random variable, $X$ can adopt an alternative probability distribution.

Note 2 - I suppose one could say that this system is similar to a persistant or correlated random walk with a memory for each step that lasts according to the chosen probability distribution. My impression is that the literature mostly refers to vertex reinforced random walks as situations where repeated traversal of "blocked" vertices increases or otherwise alters the barrier to revisiting a particular vertex, with no alternative mechanism for a decrease or change in these barriers over time.

share|improve this question
On the note: Doesn't blocking visited vertices for a fixed positive time in 1-d imply that the walker never visits the same vertex twice? The more general question seems to be related to the theory of reinforced random walks (or even once reinforced random walks). There may be methods in that literature that would be useful to you. –  Stephen Shea Sep 15 '12 at 11:59
@Stephen Shea Good point, I've edited the question to say that I would be open to $X$ adopting a different probability distribution. –  T.R. Sep 15 '12 at 15:47

2 Answers 2

At the intuitive level, it would seem that the process should behave as if it had finite memory, and be diffusive in the long term: as soon as $p>0$ I would expect a central limit theorem. Of course the variance of the limit should depend on the value of $p$ and be smaller and smaller as $p\to0$. Now proving that is another story, and questions of that kind tend to be very tricky indeed.

One case where everything works out well: assume, in one dimension (but that is not essential here), that the lifetime of a block is always bounded by some fixed number $A$, and that there is a positive probability $\eta$ that it is $0$ (meaning that the backtracking probability is positive). Then you cannot be ballistic forever, because at some point you will jump $A$ times in the same direction while putting traps with no lifetime. The probability of that happening at time $t$ is bounded below by $(\eta/2)^A$. After such a stretch, the world is completely fresh because all traps have expired. This is called a regeneration time, and the existence of such a time implies central limit theorems and convergence to Brownian motion in the scaling limit. It even gives a (ludicrously bad) bound on the variance of the limit, as a function of $\eta$ and $A$, if you really need one.

The other easy case is the one when a blockage has lifetime bounded below, then there is never a way to backtrack and you go to infinity linearly in a randomly chosen direction.

I would think that the regeneration time argument will apply in most cases under similar hypotheses (say, any dimension and positive probability to be zero), as soon as the tail behavior of the trap lifetimes is small enough, but obviously that would need to be checked more carefully.

share|improve this answer
@Vincent Beffara, I agree with what you say. I'm certainly seeing long-term diffusive behavior for values of $p$ ranging from $p = 0.01$ to $0.99$. Also, and I didn't properly specify this, I'm allowing for an unblocking event, with non-zero probability in the same time interval that a site is blocked, so we are guaranteed reversals. –  T.R. Sep 16 '12 at 10:48

Not an answer, just illustrations from some quick simulations. Immediately below, the previous position of the walker is blocked with probability $\frac{1}{2}$, and blocked for just one time step:
         Walk Barrier 100 steps
Below, again blocked with probability $\frac{1}{2}$, but now blocked for two time steps:
         Walk Barrier 100 steps
And now three time steps:
         Walk Barrier 100 steps
Of course, in this model, it is quite possible to get "stuck," if the barriers last long enough (4 or more time steps in my simulation).

share|improve this answer

Your Answer


