Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us consider the state space being $0,1,\dots,M$ for some $M\in \mathbb N$ and put there $N$ walkers: $$ X = (X_1,\dots,X_N). $$ Each of the walkers move independently, they can be in the same points of the state space at the same time and they reflect from the boundaries. More precisely, $$ X_i(n+1) = \begin{cases} 1,&\text{ if }X_1(n) \leq 0 \\ M-1,&\text{ if }X_i(n) \geq M \\ X_i(n)+\xi_i(n),&\text{ otherwise.} \end{cases} $$

Here $\xi_i(n)$ takes value $-1$ and $1$ with probability $\frac12$ and are all independent. I was asked to help to write an algorithm for Monte-Carlo simulation for this problem, which is quite an easy task and didn't take much time.

On the other hand I realized that these people are trying to simulate quantities which can be found analytically in a more handy way: namely as expectations with respect to the invariant distribution. I think that will make their life much easier, especially if the explicit formula is available.

The problem is that the correspondent Markov Chain has $(M+1)^N$ states and is irreducible: e.g. if $N=M=2$ and all the walkers start at $0$ then it is not possible that in some moment of time one of them will be at $0$ and one of them at $1$ because the sum of their states if always even.

Still the problem has a very simple description so I have a hope that a analytic characterization of irreducible classes as well as invariant distribution for each of them are already known.

I also wonder if for the case $\xi$ taking values $-1,0,1$ with probability $\frac13$ (which leads to the irreducible Markov Chain with $(M+1)^N$ states) the invariant distribution is known.

share|cite|improve this question
It actually has $(M+1)^N$ states. – Henry Dec 23 '11 at 17:31
@Henry: thanks for fixing – Ilya Dec 23 '11 at 17:49

For one walker in your second case, it is fairly clear that $p(x)=\frac{1}{M}$ for $0 \lt x \lt M$ and $p(0)=p(M)=\frac{1}{2M}$ is invariant, since you typically have

  • $p(x)=\frac{1}{3}p(x-1)+\frac{1}{3}p(x)+\frac{1}{3}p(x+1)$

but special cases such as

  • $p(1)=\frac{2}{3}p(0)+\frac{1}{3}p(1)+\frac{1}{3}p(2)$ and
  • $p(0)=\frac{1}{3}p(0)+\frac{1}{3}p(1)$

and similarly at the other end. In a handwaving sense this distribution might also be thought to be invariant for your first case, though with the problems you point out.

So in general for your $N$ walkers and $(M+1)^N$ states the invariant distribution has a probability of each state of $\dfrac{1}{2^L M^N}$ where $L$ is the number of walkers at the extremes of $0$ and $M$.

share|cite|improve this answer
Thank you, I guess for the example with 1 walker you assumed that he can stay at the boundary point with a probability $\frac13$ which is not crucial though. Could you explain please formula for the general case? Is it for the general case for the random walk with $\xi = -1,1$ or $\xi = -1,0,1$? And what does $L$ mean - the characterization of the irreducible class? – Ilya Dec 24 '11 at 11:13
It is to say that a position at the edge is half as likely as a position not at the edge for a particular walker. With $N$ walkers, a position will have somewhere between $0$ and $N$ walkers at the edge, so you need a factor which halves the probability for each walker at the edge and that is what the $2^L$ element does. – Henry Dec 24 '11 at 12:38
The general $\frac{1}{2^L M^N}$ is invariant both for the $-1,1$ and the $-1,0,1$ cases (in the latter where there is a $\frac{1}{3}$ probability of staying at the edge). One way to see this makes sense is to imagine the walkers are on an $M$ point circle identifying positions $0$ and $M$ as a single point. – Henry Dec 24 '11 at 12:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.