TITLE: An "inchworm-like" random walk on an integer interval
QUESTION [12 upvotes]: 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$.

REPLY [7 votes]: 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).
{"set_name": "stack_exchange", "score": 12, "question_id": 132066}