MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

I have a graph $G=(V,E)$ with $|V|=n$ nodes. Define a markov chain matrix P on G (e.g. Metropolis-Hastings). I have $k$ random walkers which are deployed at time $t=0$ on the vertices of $G$ at random based on the stationary distribution of $P$ (for simplicity). If more than one walkers fall in the same node, they are placed in a buffer. At time $t=1$, the top walker in each non-empty node's buffer leaves that node and makes a random transition to a neighbour.

The problem is how to characterize the statistics of the markovian random vector of buffer sizes. This is equivalent to a repeated experiment of throwing k balls in n bins, with probabilities indicated by the stationary distribution of P (at least if $G$ is complete).

Notice that if two walkers at nodes i and j move to the same node r, then in the next step only one of the two can leave r and the other is buffered. Thus the markov chain describing the evolution of the buffer size vector is non-reversible.

share|cite|improve this question
I would imagine the queueing theory literature must deal with similar problems... – Steve Huntsman Aug 24 '12 at 18:32
Yes, there exist something called Closed Jackson's Networks which are a continuous time analog to what I am describing. The difference is there it is assumed that each walker spends some exponentially distributed time at each node before exiting. I am not aware of when a continuous time markov chain is a good (and how good) of an approximation to a discrete one. – konstantinos Aug 24 '12 at 19:03
Have you considered the jump chain? – Steve Huntsman Aug 24 '12 at 19:29
What is the ``Markov chain matrix" $P$? Is there a connection between $P$ and the adjacency matrix of the graph $G$? – Ken W. Smith Aug 25 '12 at 12:44
Yes. P respects the structure of G. $P_{ij}$ is non zero if there is an edge from i to j. – konstantinos Aug 25 '12 at 21:42

Your Answer


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

Browse other questions tagged or ask your own question.