Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index $1$ or $2$. There are $4$ of them on the lattice, $A_1$, $A_2$, $B_1$ and $B_2$. (Note that $A$'s are distinguishable from $B$'s).

The system evolves stochastically for a span of time $t$, where each particle is allowed to make a random jump at each step (i.e. $1$ particle jumping per step), within the lattice. The type $1$ particles have a different discrete jump compared to type $2$ ones, namely for the former the jumps can only be diagonal (i.e. both coordinates change by same amount $\Delta_1=(\pm \alpha,\pm \alpha)$) and for the latter they are lateral (i.e. only one coordinate can change for each jump, $\Delta_2=(\pm \beta, 0)$ or $(0, \pm \beta)$). No two particles can occupy the same point.

  • Given that we have 4 particles, the states are given by vectors of $n^2$ components (Initial state: $I_0=(A_1, A_2, B_1, B_2, \cdots)$) and $T$ is an $n$ by $n$ matrix. A specific example one could consider $n=4,$ $\alpha=1$ and $\beta=2$ (if the general case is difficult to discuss about).

Given only the above (type of lattice, particles and types, size ...), what extent of the transition matrix $T$ of this random walk of 4-particles can already be written down in order to study its emergent properties?


Since the particles interact with each other (they cannot jump simultaneously to the same point or to a point occupied by another particle), I think you cannot construct the global transition matrix from the transition matrix of a single particle taken in isolation.

By the way, aren't $4$ components enough to describe the position of the $4$ particles (since you labelled the lattice points from $1$ to $n^2$)? Why should a state of your particle system be described by a vector of $n^2$ components? Furthermore, are you sure the transition matrix of your particle system would be only $n \times n$? Usually the dynamics of a Markov chain (in particular random walks) is given by a matrix whose dimension is given by the state space cardinality. In your case, I guess that the state space will have $n^2( n^2-1)(n^2-2)(n^2-3)$ states, since I understand from your description that all particles are distinguishable.

There are many properties of RWs that you can study and analyze even without having to work with the full transition matrix.

  • $\begingroup$ Well, that's basically the entire literature on RWs, there are plenty of lecture notes and books (google can help you). As far as the dimensions of state vector and transition matrix are concerned, it depends on whether you want to study how the distribution of the 4 particles $S$ evolves over time (then you need a vector of the size $|S|$) or whether you want to study the sample paths of the process (and then a 4-dim vector is enough, but then no transition matrix, you have to work only with transition probabilities). You seem quite confused on the topic, I suggest you read a bit about RWs. $\endgroup$
    – alezok
    Nov 6 '15 at 17:20
  • $\begingroup$ hi, very interesting discussions, glad I came across this post. I was wondering, if one is e.g. interested in figuring out the stationary case (i.e. the frequency of visits of the lattice sites in the long time limit, specially given that we have a finite system), would one have to absolutely go through the transition matrix? For the sake of discussion, say for two similar random walkers on a square lattice, where like this question, disallowed to occupy same site simultaneously. $\endgroup$
    – user88381
    Nov 16 '16 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy