Part II of a probability problem I am working on for a mechanism to move tokens on a chart. Part I was two D4 dice. Part II is much different! [closed]

Question

For Part I of this discussion, see this thread: Probability help on rolling two D4 with all doubles counting as zero except double 4s, which count as 4

That dealt with probabilities using two D4 dice, most of which I could understand.

In Part II I also need to find probabilities, but I have NO IDEA how to calculate them. Hoping someone here can help. I hope I can explain it effectively.

THE SYSTEM: I have a chart on which six individual pieces move. Their respective movement is determined by a set of six disks that move left-to-right on a six-space-track (see inset image) which 'loops' back around to the beginning, forming a continuous circuit. Each of the colored disks match the color and icon on a D6.

Those colors are blue, orange, yellow, green, red and purple. When a color is rolled THAT corresponding disk moves one space to the right on the track. If it reaches the end it loops back to the first space on the far left. This movement inevitably creates "stacks" of various size. Which is the whole point, because the number of tokens in the stack is the number of spaces a colored pawn will move on the chart mechanism.

Example: I roll the D6 and it comes up Green (forest). So I move the green forest token one space to the right where it now sits on top of the red token. This forms a "stack" of two tokens. Since Green was activated it will be the green pawn that will move 2-spaces on the chart.

This process of roll and move goes on indefinitely. The very first move will always result in a 'stack' 2-high, but as you continue rolling the tokens will become dispersed, forming stacks of 1,2,3 and occasionally 4-high. Theoretically stacks could reach 6-high, but 4 is the highest I have seen despite hundreds of test rolls. Logically 1 and 2 stacks should be more frequent and that seems to match my tests, 2-stacks being the most prevalent, though it's not always consistent.

Is there any way to calculate the odds for each 'stack' value: 1, 2, 3, 4, 5, 6?

The colors and icons are irrelevant to my query, so we may convert those to numbers if that helps: Blue=1, Orange=2, Yellow=3, Green=4, Red=5 and Purple=6

WHERE DO I START?

1. Each movement is always exactly 1 space
2. There are exactly 6 tokens
3. There are exactly 6 spaces (but on an infinite loop)
4. Smallest possible 'stack' 1
5. Largest possible 'stack' 6
6. First move always creates a 'stack' of 2

I am particularly curious how 1,2,3,4 compare to those in the D4 system referenced at the at the beginning.

Answer 1

Stationary distributions

You are probably looking for the stationary distribution of a Markov chain. If a unique stationary distribution exists, it represents what happens if you play the game for an infinite amount of time.

Stationary distributions can be found using an eigenvalue decomposition of the game's transition matrix. We'll represent the game state from the perspective of the last token to move, say blue:

• Since the track is circular, if we roll blue on the die, it's the same as everyone else going back one space. So we will do that instead of tracking blue's position explicitly.
• If we roll another color, they go forward one space, wrapping around if necessary.

One script later:

from itertools import combinations_with_replacement
import numpy as np

index_to_state = {}
state_to_index = {}

for i, state in enumerate(combinations_with_replacement(range(6), 5)):
    index_to_state[i] = state
    state_to_index[state] = i

n = len(index_to_state)

# Compute transition matrix.
transition = np.zeros((n, n))
for src in range(n):
    src_state = index_to_state[src]
    # Note that python/numpy indexes start at 0.
    for roll in range(6):
        if roll == 5:
            dst_state = [(x - 1) % 6 for x in src_state]
        else:
            dst_state = [x for x in src_state]
            dst_state[roll] = (dst_state[roll] + 1) % 6
        dst_state = tuple(sorted(dst_state))
        dst = state_to_index[dst_state]
        transition[dst, src] += 1/6

eigenvalues, eigenvectors = np.linalg.eig(transition)

we see that there is indeed a unique eigenvalue of +1. We can compute the stack size as

stationary_eigenvector = np.real(eigenvectors[:, np.argmax(np.real(eigenvalues))]

# The stack size is the number in the same spot as us (0).
stationary_stack_size = np.zeros(6)
for i, p in enumerate(stationary_eigenvector):
    state = index_to_state[i]
    stationary_stack_size[sum(x == 0 for x in state)] += p

print(stationary_stack_size / np.sum(stationary_stack_size))

which gives

[4.01877572e-01 4.01877572e-01 1.60751029e-01 3.21502058e-02
 3.21502058e-03 1.28600823e-04]

which is the same as if you had simply placed the other five tokens on the board uniformly and independently at random.

(This could be proved explicitly from the fact that any game state can be reached from any other game state, therefore the Markov chain is irreducible, therefore it has a unique stationary distribution. Then if you guess a distribution and it turns out to be stationary, that has to be the one. But the numerical approach can also be instructive.)

The mean stack size is then exactly \$11/6 \approx 1.83\$, which is a bit more than the \$1.5\$ of your other post.

The parity effect

However, there is a wrinkle: there is also an eigenvalue of -1, which is due to a parity effect. If you assign the numbers 1-6 to the spaces, and add up the spaces of each of the tokens, the total flips between even and odd on each turn. For example, it is impossible to land a 6-stack when the sum is odd. So the game flips between two disjoint sets of states. The stationary distribution is a half-and-half mix of these two sets.

We can compute the parity effect on stack size in a similar way:

parity_eigenvector = np.real(eigenvectors[:, np.argmin(np.real(eigenvalues))])

parity_stack_size = np.zeros(6)
for i, p in enumerate(parity_eigenvector):
    state = index_to_state[i]
    parity_stack_size[sum(x == 0 for x in state)] += p

print(parity_stack_size / parity_stack_size[-1] * stationary_stack_size[-1])

Result:

[-0.0001286   0.000643   -0.00128601  0.00128601 -0.000643    0.0001286 ]

Here we see turns that land on an even space sum are relatively more likely to land on an even-sized stack, and turns that land on an odd space sum are relatively more likely to land on an odd-sized stack. But in terms of mean stack size it's a wash.

There are also similar periodic effects modulo 3 and 6, with complex eigenvalues corresponding to roots of unity.