Detailed mathematical approach

Problem Summary

Problem 84 asks for the long-run popularity of Monopoly squares when the usual two 6-sided dice are replaced by two 4-sided dice. After the game has run for a very long time, some squares are visited more often than others. The required output is the modal string formed by the three most likely square indices, written as two-digit numbers and concatenated in decreasing order of visit probability.

The board has 40 squares, but the motion is not a simple random walk on a 40-cycle. Square 30 sends the token directly to Jail, Community Chest squares can redirect to GO or Jail, Chance squares can redirect to named destinations such as C1, E3, H2, R1, the next railway, or the next utility, and three consecutive doubles also force Jail. Those rules create a biased steady state, so the problem is really about finding the stationary distribution of a finite stochastic system rather than averaging raw dice sums.

Mathematical Approach

The exact method used by the analytical implementation is a Markov chain with memory. The state cannot be only the current square, because the rule about three consecutive doubles depends on what happened on the previous rolls. The correct state is therefore a pair \((p,d)\), where \(p \in \{0,\dots,39\}\) is the current square and \(d \in \{0,1,2\}\) records how many consecutive doubles have already been rolled. This gives \(40 \times 3 = 120\) states.

Why the State Needs a Doubles Counter

If a player is on the same square in two different situations, the next-turn probabilities are not always the same. Being on square 18 after zero consecutive doubles is different from being on square 18 after two consecutive doubles, because one more double would send the token straight to Jail. That is the only memory the exact model needs, so a 120-state chain is sufficient for the stationary calculation.

Resolving the Special Squares

After an ordered dice roll \((d_1,d_2)\), the token first moves by \(d_1+d_2\) squares modulo 40. Then the landing square is resolved. The important board objects are GO \(=0\), Jail \(=10\), Go To Jail \(=30\), Community Chest at \(2,17,33\), Chance at \(7,22,36\), railways at \(5,15,25,35\), and utilities at \(12,28\).

Community Chest contributes only two movement cards: one sends the token to GO and one to Jail. The other 14 cards leave the token where it is. Chance has 10 movement cards out of 16: GO, Jail, C1, E3, H2, R1, next railway twice, next utility, and “go back 3 squares”. The “go back 3 squares” card is the subtle case, because the new square may itself need further resolution. In particular, from Chance at square 36, moving back 3 lands on square 33, which is Community Chest, so that branch splits again.

Building the Transition Matrix

With 4-sided dice there are \(4^2=16\) equally likely ordered outcomes. If \(d_1=d_2\), the doubles counter increases by 1; otherwise it resets to 0. If the counter would become 3, the player is sent immediately to Jail and the counter resets. For every state \((p,d)\), the implementation enumerates all 16 ordered rolls, resolves the landing square completely, and adds the corresponding probabilities to the destination states. This produces a stochastic matrix \(P\) of size \(120 \times 120\), and each row satisfies

$\sum_t P_{(p,d),t}=1.$

The stationary distribution \(\boldsymbol{\pi}\) is defined by

$\boldsymbol{\pi}=\boldsymbol{\pi}P,\qquad \sum_s \pi_s = 1.$

Once \(\boldsymbol{\pi}\) is known, the probability of being on board square \(p\) is obtained by summing over the doubles counter:

$\Pi(p)=\sum_{d=0}^{2}\pi_{(p,d)}.$

The answer is obtained by sorting the 40 values \(\Pi(0),\Pi(1),\dots,\Pi(39)\) and taking the top three indices.

Worked Example: Chance at 36 and the Recursive Branch

Suppose a move lands on square \(36\), the third Chance square. One of the 16 Chance cards says “go back 3 squares”, so that branch first moves to \(33\). But square \(33\) is Community Chest, so the branch is not finished. It must split again into three Community Chest outcomes: GO with probability \(1/16\), Jail with probability \(1/16\), and staying on \(33\) with probability \(14/16\). Therefore the original Chance branch contributes

$\frac{1}{16}\cdot\frac{1}{16}$

to GO, the same amount to Jail, and

$\frac{1}{16}\cdot\frac{14}{16}$

to square \(33\). This is exactly why the implementation resolves special squares as a small probability tree rather than with a single lookup table.

Why Jail and the Railways Become Popular

Jail receives inbound probability from several independent mechanisms: the dedicated Go To Jail square, the Jail card in Community Chest, the Jail card in Chance, and the rule sending the player to Jail after three consecutive doubles. The railways also receive extra inflow because Chance has one card for R1 and two cards sending the player to the next railway. Since doubles occur with probability \(4/16 = 1/4\) on 4-sided dice, the probability of three doubles in succession is \((1/4)^3 = 1/64\), which is much larger than with ordinary dice. That makes Jail especially prominent in the stationary ranking.

The chain is irreducible and aperiodic, so the stationary distribution is unique, and repeated multiplication by \(P\) converges to it. That invariant is the reason the exact implementation can begin from GO and still recover the long-run frequencies.

How the Code Works

The C++, Python, and Java implementations share the same board rules but use two different computational strategies. The C++ implementation builds the full 120-state transition matrix, starts with all probability mass at GO, and applies power iteration for a fixed number of rounds. Because the state space is small and the chain mixes quickly, this converges to the stationary distribution to more than enough accuracy for ranking the most popular squares.

The Python and Java implementations use Monte Carlo simulation instead. They roll two 4-sided dice for many turns, track the current square and the number of consecutive doubles, and update visit counters. Unlike the exact matrix model, they also keep explicit Community Chest and Chance decks that are shuffled once and then consumed cyclically. That means those two programs are simulating a slightly richer stochastic process whose full exact state would have to include deck order and deck position, making an exact matrix treatment much larger than 120 states.

After the visits or stationary masses are accumulated, all implementations sort the 40 square indices by decreasing frequency and concatenate the top three as two-digit numbers. That final formatting step produces the required modal string.

Complexity Analysis

For the exact Markov-chain approach, the state count is fixed at 120. Matrix construction examines 120 states and 16 ordered dice rolls per state, with only constant-size branching when a special square is resolved. Each power-iteration step is a dense matrix-vector multiplication on a \(120 \times 120\) matrix, so 300 iterations cost \(O(120^2 \cdot 300)\), which is tiny in practice. Memory usage is \(O(120^2)\) for the matrix and \(O(120)\) for the probability vectors.

For the Monte Carlo approach, if \(T\) turns are simulated then the running time is \(O(T)\). The auxiliary memory is constant apart from the 40 visit counters and the two 16-card decks. In the supplied simulation implementations, \(T=10^6\), which is enough to stabilize the ranking well even though it estimates frequencies empirically rather than solving the stationary equations exactly.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=84
2. Monopoly board and rules overview: Wikipedia - Monopoly
3. Markov chains: Wikipedia - Markov chain
4. Stationary distributions: Wikipedia - Stationary distribution
5. Power iteration: Wikipedia - Power iteration