Suppose we have a circular arrangement (periodic boundaries) with $M$ sites and we want to distribute $N$ particles over these sites such that there are occupation numbers $n_m$ that respect $\sum_m n_m = N$. Now in each step every single particle stays with probability $p$ and a jumps with probability $q$ to the left or to the right (only to the neighbors). Therefore we have $p+2q=1$.

Now given the sets of occupation numbers $\{n_m\}$ and $\{n'_m\}$ of two consecutive steps, what is the transition probability between these two sets of numbers?

The challenge in this question arises because the "macro" combinatorics has to be worked out starting from the "micro" combinatorics for each particle, such that one has to consider several micro-configurations that give rise to the same macro-configuration though each of them has a different probability.

Maybe there is a nice reformulation of this combinatorics problem or an approach with stronger theoretical input, since basic counting has not gotten me past the micro <-> macro issue.

  • $\begingroup$ It would help to add clarity. I would prefer a vector of length m or a labeling of the sites in M so that I know to which site the index $m$ refers. Your use of the term sets suggests that you don't care about labelling, you just care about the resulting set of numbers, so that e.g. {2,3,4} could refer to any vector of 2's 3's and 4's that had the dot product with the length m vector $(1,...,1)$ . Labels, or not? Gerhard "Inquiring Minds Want More Clarity" Paseman, 2011.07.27 $\endgroup$ – Gerhard Paseman Jul 27 '11 at 21:14
  • $\begingroup$ Sorry, I meant to say "Had the right dot product", meaning that the occupation numbers added up to $N$. Gerhard "Ask Me About System Design" Paseman, 2011.07.27 $\endgroup$ – Gerhard Paseman Jul 27 '11 at 21:15
  • $\begingroup$ Let $n = (n_1,\dots,n_M)$ denote a standard multi-index. Now the nontrivial transition probabilities are $P_{n,n-e_j+e_{j \pm 1}} = q$ (here $j$-indices are taken mod $M$) and $P_{n,n} = 1-2q$. The corresponding invariant distribution is the left eigenvector $p = pP$ with nonnegative entries summing to unity. This calculation is not trivial, but I can't really tell what you're asking for. $\endgroup$ – Steve Huntsman Jul 28 '11 at 0:12
  • $\begingroup$ I think what madison64 is saying is that, for example, it's not obvious how to write the transition probability from $(100,100,100,100,100)$ to $(110,90,100,100,100)$ without an horrendous sum. The global component is that one of the summations is over elements of $H_1$ (or more properly an $H_1$-torsor) indicating the net clockwise drift. $\endgroup$ – Douglas Zare Jul 28 '11 at 5:37

there doesn't seem to be a nice closed formula.

for each edge of the cycle, let $u_i,v_i$ be the number of particles that cross it in the two directions. in terms of these, the probability is a product of multinomial coefficients. $u_i-v_i$ is determined by the two vectors up to an additive constant, but that still leaves a large set of terms to be added up.

in many cases, the additive constant will be determined by the two configurations as well. this happens whenever it is forced tat some $u_i=v_j=0$.


Your Answer

