2

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.

flag
I would imagine the queueing theory literature must deal with similar problems... – Steve Huntsman Aug 24 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 at 19:03
Have you considered the jump chain? – Steve Huntsman Aug 24 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 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 at 21:42
show 1 more comment

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.