# An “inchworm-like” random walk on an integer interval

Imagine I place $k$ stones on an infinite one-dimensional integer interval $Z$ s.t. no stone is more than some distance $d$ from any other stone. For example, if $d=1$ and $k = 5$, we might place the five stones are positions $(-2,-1,0,1,2)$.

I then proceed to do the following:

For each of some arbitrary number of discrete time steps, I select one of the $k$ stones with uniform probability. I then lift the stone up and uniformly select an unoccupied site to place it back down which satisfies the dual criterion of: (a) being at most a distance $d$ from both of the stone's nearest neighbors, and (b) not disturbing the initial ordering of the stones along the integer interval (note that the stone's original position can be reselected). If $d=1$, no stone can be moved from its original position and the center of mass of the stones/system, $C_m$, will be immobile. However, if $d=2$, starting from the state $(-2,-1,0,1,2)$, the center of mass will move to either the right or left with some per step probability of $\frac{1}{k}$ (until we leave this initial system state).

My question is - provided some number of stones $k$, and some "leashing distance" $d$, how can we characterize the dynamics of the random walk taken by the above system's center of mass, $C_m$? What is the average step time and size, and, in terms of Euclidean distance, what mean square displacement can we expect after some number of steps, $T$?

Update (due to a suggestion by Douglas Zare) - The $k$ stones must be kept in order, and the distance between a stone and its two nearest-neighbors along the interval (or one nearest-neighbor if the stone occupies the left-most or right-most position of the chain) can be at most $d$.

-
If $d=1$ and you start at $(-2,-1,0,1,2)$, why can't you pick up the stone at $-2$ and put it down at $-3$? Are you requiring the stones to stay within $d$ of at least one other stone at all times, or did you mean the new location has to be strictly less than $d$ of the original location? If the former, do you want to keep the stones in order, requiring each stone to be within $d$ of both the previous and next stone? That would resemble a worm to me. –  Douglas Zare May 28 '13 at 1:33
@Douglas Zare Just a minor point, but to clarify my method of counting: picking up a stone at -2 and placing it at -3 would make the distance to the closest stone Abs[(-3) - (-1)] = 2. You can do as you suggest if $d = 2$. I like your suggestion that the stones should be kept in order and I will amend the problem description to include this. –  AmberWave May 28 '13 at 2:28
Yes, the distance between $-3$ and $-1$ is $2$. I pointed out that moving the stone from $-2$ to $-3$ is not prohibited with $d=1$ in the original operation, of selecting an unoccupied site at most a distance $d$ from the stone's original position $-2$. If you meant to rule this out for $d=1$, you needed to add some condition. I also don't know what you mean by "some per step probability of $\frac{1}{k}$. When $k=5$, what is supposed to have probability $\frac{1}{5}$? Suppose there are two legal destinations for a stone. Don't you move to each with probability $\frac{1}{2}$ instead? –  Douglas Zare May 28 '13 at 4:10
Have you figured out what happens for the case $k=2$? It seems simple enough to be tractable... –  j.c. May 29 '13 at 0:13
The case $k=2$ should be solvable (we can even assume the stones alternate), but it misses some of the complexity. Consider the configuration with $d=2$, $k=3$ where the stones are at $0,1,3$. The first and last stones may only move left or stay at the same location. The middle stone may only move right. This means that the center of mass will move left on average. If $k=2$ the center of mass is a martingale. –  Douglas Zare May 29 '13 at 3:06
show 4 more comments

## 3 Answers

This is a particular case of random walks with internal degrees of freedom (aka semi-Markov random walks or covering Markov chains). In the case when the translation group is just $\mathbb Z$ (like in this question) this is a Markov chain on $\mathbb Z \times X$ with translation invariant transition probabilities. In the "inchworm" situation one can take for $X$ the (finite) set of all configurations in which the leftmost stone is at the point $0\in \mathbb Z$. Then states of the worm are described by the pairs $(n,\phi)\in \mathbb Z\times X$, where $n$ is the position of the leftmost stone, and $\phi$ is the shifted configuration. The center of masses will then be within uniformly bounded distance from $n$. It is obvious that in these coordinates the transition probabilities of the chain describing worm's motion are translation invariant, so that this is a random walk with internal degrees of freedom on $\mathbb Z$.

The paper "Random walks with internal degrees of freedom. I. Local limit theorems" of Krámli and Szász (MR0699788) describes the asymptotic behaviour of such chains in terms of the properties of the quotient chain on $X$. In particular, there is an explicit formula for the non-zero variance of the displacement in terms of the stationary distribution on $X$ (which in our case should also be quite explicit - it's a nice exercise).

-
Yes, of course. However, the devil here is in the computation of correlations between steps. Even the asymptotic regime doesn't look trivial to me :(. –  fedja May 30 '13 at 2:35
Don't see any problem here. Look at Pre-theorem 2.1 from the paper I quote, condition (iii). The only difficulty might be in finding the stationary measure - is this what you mean? –  R W May 30 '13 at 11:15
Nope. The stationary measure us trivial: the uniform distribution on all configurations. What I mean is that I have no idea how to find what they call $\sigma^2$ with any decent precision for this huge chain in terms of $k$ and $d$. –  fedja May 30 '13 at 17:29
add comment

Example. $k=5$, $d=3$, $100$ (substantive) iterations; center of mass pink, time growing downward:

It appears the center of mass performs a scaled random walk, scaled as a function of $k$ and $d$. Perhaps scaled by about $(d/2)/k$...?

-
add comment

I wanted this to be a comment since I don't know enough probability to finish the argument but it was a bit too long:

You can transform the positions of the stones into the following data - one number telling us the position of the center of mass of the inchworm, and a $(k-1)$-tuple of positive integers $\vec{a}=(a_1,\dots,a_{k-1})$ living in the hypercube $C$ defined by the inequalities $1\leq a_i\leq d$. The components of $\vec{a}$ are the distances between each pair of neighboring stones and I think of $C$ as the space of configurations of the inchworm.

Each step of your process is a trial move of some random stone either left or right. This corresponds to some trial move of $\vec{a}$, where some component(s) will be incremented or decremented by one. I tried to define $C$ so that your conditions (a) and (b) precisely correspond to $\vec{a}$ staying within a "configuration space" $C$ of the body of the inchworm. Provided $\vec{a}$ does not attempt to leave $C$, the center of mass of the inchworm will move a distance of $1/k$ either left or right.

Thus the problem boils down to understanding how $\vec{a}$ moves around $C$ and in particular how often it attempts to leave $C$. In particular a good bound on this event will tell us how often the center of mass pauses from its default simple random walk behavior.

You can construct a graph $G_C$ whose vertices are the points of $C$ and whose edges are precisely the possible transitions of the body of the inchworm from one state to another. Note that the vertices at the boundary of $C$ have loops attached which correspond to trial moves that fail. In particular the degree of every vertex is $2k$. The change of the body shape of the inchworm is a simple random walk on $G_C$ and I think you can show from this that every shape is visited equally often.

I wrote some Mathematica code for playing around with this model. It's at the end of this answer.

Here is a picture of a run for the case $k=3$, $d=2$ as described in Douglas Zare's comment above. The different colors correspond to different stones.

While it is true that in the first step the center of mass will tend to move left there isn't any particular propensity for the worm to move left or right in the long run.

The configuration space for a worm with $k=3$ is a $d$ by $d$ square. Here's a histogram of the time spent at each point from a run of $10^5$ steps with $k=3$ and $d=10$. It seems that the inchworm spends an equal amount of time in each possible configuration. This should follow from basic results on random walks on finite graphs but I don't know them.

It seems that the amount of time that the center of mass is "stuck" because $\vec{a}$ attempts to leave $C$ is proportional to $1/d$ which intuitively seems to come from dividing the area of $C$ by its volume. An analysis of the walk on $G_C$ should make this more clear...

n = 100000;
a0 = {0, 1, 3};
a = a0;
k = Length[a];
inputrand =
Table[{RandomChoice[{-1, 1}],
RandomChoice[Table[i, {i, k}]]}, {n}];
d = 2;
happening =
Table[j = inputrand[[t, 2]];
anew = a + Table[If[ind == j, inputrand[[t, 1]], 0], {ind, k}];
If[(j ==
1 || (anew[[j]] > anew[[j - 1]] &&
anew[[j]] - anew[[j - 1]] <= d)) && (j ==
k || (anew[[j + 1]] > anew[[j]] &&
anew[[j + 1]] - anew[[j]] <= d)), a = anew];
a, {t, n}];
happening = Join[{a0}, happening];
ListPlot[Table[happening[[All, i]], {i, k}], Joined -> True]
ListPlot[Table[Mean[happening[[t, All]]], {t, n + 1}], Joined -> True]

-
add comment