3
$\begingroup$

This is a problem given by a professor that has been perplexing me.


Suppose a particle takes a random walk on a $100 \times 100$ checkerboard in the following way. After an exponential time with rate 1, it attempts to move up, down, left, or right -- each with probability 1/4. If the attempted move would take the particle off the board, it stays put instead. Then, after an exponential time with rate 1, it tries to move again, and on and on. What is the stationary distribution of the particle's position.

Now suppose there are 1278 such particles on the board moving independently, and multiple particles can occupy the same squares. What is the stationary distribution for the number of particles on each square? You might want to think of your state space as consisting of all the $100 \times 100$ arrays, where the number in the $(i, j)$ position in the array corresponds to the number of particles there.

Finally answer the previous question when the 1278 particles are only allowed to move to empty squares. That is, each square can only accomodate one particle. Now the state space would be all the $100 \times 100$ arrays of 1s and 0s with exactly 1278 1s.


Now, I'm certain that if I understand how to solve the first part (the first paragraph that is, then I'll be able to use similar logic to solve the latter paragraphs. I believe that the principle I need to use because this process is clearly time reversible is $$P_i^A = \frac{P_i}{\sum_{j \in A}P_j}$$ where $A$ is a truncated state space of the whole CTMC. I can envision truncating the space to just the neighboring checkerboard squares, but I'm still uncertain of what to even do with that information.

$\endgroup$
4
  • $\begingroup$ The truncation method can only work when you specify the original Markov chain that you are truncating. Also, you likely meant the denominator to sum, rather than to multiply. Since you are (correctly) guessing reversibility, it would be better to verify that the detail equations $\pi_i q_{ij} = \pi_j q_{ji}$ hold for all $i,j$ for a particular guess on the steady state $\pi_i$, relating it to the degree $d_i$ of each location. $\endgroup$
    – Michael
    Commented Apr 6, 2018 at 3:22
  • $\begingroup$ I did, and I fixed it. I feel like the stationary distribution is just going to be a slowly diminishing probability as one approaches the minimum, but I'm still uncertain exactly how to write that. It's become more clear the more I type about it though. $\endgroup$
    – Ryan Honea
    Commented Apr 6, 2018 at 3:35
  • $\begingroup$ What does "I did" refer to, and what does "the minimum" refer to? The stationary distribution is not complicated. You should compute the transition rates $q_{ij}$ between locations. $\endgroup$
    – Michael
    Commented Apr 6, 2018 at 4:01
  • $\begingroup$ Sorry about that. My mind might be a little confused. I was initially imagining that it would be on the outward cells the longest, and that as it approaches the middle of the board that it would diminish. But I went ahead and simulated it to see what would happen, and things are definitely starting to make more sense. That is, the stationary distribution is definitely not that crazy! $\endgroup$
    – Ryan Honea
    Commented Apr 6, 2018 at 4:21

1 Answer 1

1
$\begingroup$

A clever approach for the first part is to consider an infinite board ruled off in $100 \times 100$ sections. When the particle moves off the edge of your board, it moves to a space of the same type (corner or edge) of a neighboring board, but on the infinite grid all the cells are equivalent as there are no reflections. This shows the chance of the particle being on any given cell on your board is the same. For the second part, you have $1278$ particles each with a chance of $10^{-4}$ to be in your given cell.

$\endgroup$
2
  • $\begingroup$ Thanks! That works great and it does indeed satisfy the time reversibility equations. In the case of 1278 particles each moving but not being able to enter occupied spaces, I'm thinking that maybe this doesn't actually change the stationary distribution. For example, moving from a corner space to an edge space occurs with rate $2/4$ (as two corners can move into an edge) times the probability that it isn't occupied. Similarly, it moves out of a corner into an edge space with rate $1/2$ times the probability that the edges aren't occupied. Is this accurate? $\endgroup$
    – Ryan Honea
    Commented Apr 6, 2018 at 5:36
  • $\begingroup$ @RyanHonea : The third part, where we cannot move in an already-occupied spot, is the only place you need the truncation theorem. The three parts of the problem are aligned in a correct order for solvability. $\endgroup$
    – Michael
    Commented Apr 6, 2018 at 20:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .