Combinatorics: Stochastics on a circular arrangement

AI Thread Summary
The discussion revolves around a combinatorial problem involving the distribution of N tokens across M spots in a circular arrangement, incorporating stochastic dynamics where tokens can stay or jump to neighboring spots. The challenge lies in determining the transition probabilities between sets of token numbers over time, requiring a balance between local and macro perspectives. Participants clarify that "token numbers" refer to the quantity of tokens at each spot, and the sets of token numbers should be treated as vectors. The conversation suggests that a transition matrix may be necessary to approach the problem as a Markov process. Overall, the problem is recognized as complex and non-standard, inviting further exploration and reformulation.
madison54
Messages
3
Reaction score
0
I am dealing with the following interesting combinatorics problem, several reformulations of which haven't help me solve the problem:

Suppose we have a circular arrangement with M spots and we want to distribute N tokens over these spots such that there are token numbers n_m that respect \sum_{m}n_m = N. Now we want to impose a discrete time stochastic dynamics such that in each time step every single token stays with probability p and a "goes" with probability q for jumps to the left and to the right (only to the neighbors). Therefore we have p+2q=1.
Now given the sets of token numbers \{n_m\} and \{n_{m}'\} of two consecutive time 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 token, such that one has to consider several micro-configurations, each having a different probability, that give rise to the same macro-configuration.
With simple counting techniques, one gets pretty quickly stuck with this problem: on the one hand it has to be a local approach, taking into account 3 spots in a row (since tokens can stay or jump to the neighbors), on the other hand, all of the spots influence each other such also a macro-view has to be incorporated. I therefore think that a little more elaborated theory is needed.

Maybe one has seen an equivalent problem or has a fresh idea of reformulation.

I think it's a challenging, non-standard combinatorics problem, which makes it pretty interesting :-)
 
Physics news on Phys.org
The first insurmountable difficulty in the problem is understanding what you mean by a "token number". Is it something stamped on each token? Or is it stamped on the "spots"?
 
Stephen Tashi said:
The first insurmountable difficulty in the problem is understanding what you mean by a "token number". Is it something stamped on each token? Or is it stamped on the "spots"?
He means the number of tokens at the spot.
 
pmsrw3 said:
He means the number of tokens at the spot.

Then are the "sets" of token numbers actually vectors of token numbers?
 
Stephen Tashi said:
Then are the "sets" of token numbers actually vectors of token numbers?
Umm, good point. Yeah, I guess they would have to be. Either that, or I have completely misunderstood the problem.
 
Yes, all pmsrw3 has said is the way I meant it: Instead of a set you can take it as a vector and ask for the transition probability between the two "state-vectors". Though I doubt that linear algebra is going to help, since formulating as this language we need something like a transition matrix which leads us to another Markov process. Determining the transition probabilities of this process is the actual combinatorial task.

If you want a more physical language for "tokens" and "spots", call it "particles" that hop on the one dimensional ring.
 
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top