Stay or jump...this shouldn't be complicated!

I've been trying to think of a way of modifying the standard transition matrix method to describe a process where you have many "particles," but they may only switch states in some fixed number higher than 1. For example, assuming the particles may only hop between states in pairs, but are otherwise independent, is there a simple way to predict the system's development over many time steps?

Here is the standard approach. Removing the "must hop in pairs" constraint, the transition matrix is a simple way of analyzing many time steps for a single particle. Suppose there are two states a particle may be in, state 1 and state 2 (denoted by s₁ and s₂). During each time step, a particle in state 1 has probability a₁₁ of remaining in state 1, and probability a₂₁ of switching to state 2. A particle in state 2 has probability a₂₂ of remaining in state 2, and probability a₁₂ of switching to state 1. The transition matrix, A, is

A =	a11 a12 a21 a22

The probability of finding the particle in each state after t time steps is found from A^t. If we're given its initial location, then

s1(t) s2(t)

=

a11 a12 a21 a22

t

s1(0) s2(0)

The components of the final state vector, s(t), are mutually exclusive: either the particle has found its way to state 1 or state 2. So the total probability of the particle being somewhere is just their sum (which is, of course, 1). To calculate the statistics for N independent particles, this sum is raised to the N power. For 1 time step, if the particle starts in state 1, this is a simple binomial:

Q = (a₁₁ + a₂₁)^N

Q, the sum over all available system states, is the partition function. For multiple time steps, Q is calculated as

Q = ([1 1]A^ts(0))^N

where [1 1] just "flattens" the final state vector into a sum, so the multiparticle expansion is all-to-all, as required. This is mathematically convenient in this case, but it's worth noting that the final state may be kept in vector form: we can still do an all-to-all multiplication by convoluting the vector with itself (which is, in an unfortunate convention, denoted by *),

A^ts(0) * A^ts(0) * · · · * A^ts(0)

Writing the multiparticle expansion as a convolution seems like a pointless complication, since we're going to ultimately flatten the vector to calculate Q. However, keeping the vector's structure intact has the advantage of being able to keep track of pairs of particles switching states, because that information has not been flattened out. This is most clearly seen by writing the convolution in matrix form. The convolution matrix, C, will have the state vector as its first row, and a "shifted" state vector as its second row. (A matrix created using this rule is called a "circulant matrix.") After 1 time step,

C =	a11 a21 a21 a11

This circulant matrix is handy because it lets us calculate convolutions by doing ordinary matrix multiplication. The total expansion for a two-particle system (N = 2) is:

C2 =	a112 + a212 2a11a21 2a11a21 a112 + a212

The internal structure of the circulant stores even powers of the hop probability a₂₁, corresponding to pairs of particles switching states, on its diagonal, and odd powers on its anti-diagonal. To see this more clearly, look at the circulant for a four-particle system,

C4 =	a114 + 6a112a212 + a214 4a113a21 + 4a11a213 4a113a21 + 4a11a213 a114 + 6a112a212 + a214

So the partition function for 1 time step for pairs of particles can be calculated as 1/2 of the trace of the circulant raised to the number of particles! Alternately, to store every third power of the hop probability on its diagonal (a "three particles must jump simultaneously" rule), a 3x3 circulant matrix may be used:

C =	a11 a21 0 0 a11 a21 a21 0 a11

and so on, for every fourth (4x4), fifth (5x5), etc. power.

This is not that useful as-is, because it's only for a single time-step, where it is not difficult to brute-force calculate every possible trajectory by hand. It would be very nice to be able to do this for multiple time steps: in effect, combining the transition matrix and circulant matrix to allow you to easily develop a multiparticle system for many time steps, while keeping the allowed trajectories separated from the forbidden trajectories inside the circulant's structure. This is a bit frustrating, because I think there should be a simple way to do this, but for some reason I just can't see what it is...