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.
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.
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.
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.
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.
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.
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.
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.
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.
Bei Problem 84 sollen die langfristigen Besuchswahrscheinlichkeiten der Monopoly-Felder bestimmt werden, wenn statt der üblichen zwei 6-seitigen Würfel zwei 4-seitige Würfel verwendet werden. Gesucht ist die sogenannte modale Zeichenkette: die Indizes der drei wahrscheinlichsten Felder, jeweils zweistellig geschrieben und in absteigender Reihenfolge der Wahrscheinlichkeit aneinandergehängt.
Die Bewegung auf dem Brett ist kein einfacher Zufallsgang auf 40 Positionen. Feld 30 schickt den Spieler direkt ins Gefängnis, die Gemeinschaftsfelder können nach GO oder ins Gefängnis weiterleiten, die Ereignisfelder können zu mehreren festen Zielen springen, und drei aufeinanderfolgende Pasche führen ebenfalls ins Gefängnis. Deshalb muss man keine reine Würfelsummenverteilung, sondern die stationäre Verteilung eines endlichen stochastischen Systems bestimmen.
Der exakte Ansatz der analytischen Implementierung ist eine Markov-Kette mit Gedächtnis. Der Zustand kann nicht nur aus dem aktuellen Feld bestehen, denn die Regel mit den drei aufeinanderfolgenden Paschen hängt von der Vorgeschichte ab. Der passende Zustand ist also \((p,d)\), wobei \(p \in \{0,\dots,39\}\) das aktuelle Feld und \(d \in \{0,1,2\}\) die Anzahl bereits aufgetretener aufeinanderfolgender Pasche bezeichnet. Damit erhält man \(40 \times 3 = 120\) Zustände.
Dasselbe Brettfeld kann unterschiedliche Zukunftswahrscheinlichkeiten haben. Wer auf Feld 18 mit bereits zwei Paschen in Folge steht, befindet sich nicht in derselben Situation wie jemand auf Feld 18 ohne vorherige Pasche, denn ein weiterer Pasch würde sofort Gefängnis bedeuten. Genau diese kurze Erinnerung wird durch die drei Werte \(d=0,1,2\) erfasst.
Nach einem geordneten Würfelwurf \((d_1,d_2)\) bewegt sich die Figur zunächst um \(d_1+d_2\) Felder modulo 40. Danach wird das Zielfeld ausgewertet. Die wichtigen Brettobjekte sind GO \(=0\), Gefängnis \(=10\), „Gehe ins Gefängnis“ \(=30\), Gemeinschaftsfelder bei \(2,17,33\), Ereignisfelder bei \(7,22,36\), Bahnhöfe bei \(5,15,25,35\) und Versorgungswerke bei \(12,28\).
Bei Gemeinschaftsfeldern gibt es genau zwei Bewegungskarten: eine führt zu GO, eine ins Gefängnis, die übrigen 14 lassen die Figur stehen. Bei Ereignisfeldern gibt es 10 Bewegungskarten unter 16: GO, Gefängnis, C1, E3, H2, R1, zweimal der nächste Bahnhof, das nächste Versorgungswerk und „3 Felder zurück“. Gerade diese letzte Karte ist mathematisch wichtig, weil das neue Feld selbst wieder ein Sonderfeld sein kann. Von Feld 36 aus führt „3 Felder zurück“ nämlich auf 33, also auf ein Gemeinschaftsfeld, das erneut aufgelöst werden muss.
Mit 4-seitigen Würfeln gibt es \(4^2=16\) gleich wahrscheinliche geordnete Würfelresultate. Gilt \(d_1=d_2\), so erhöht sich der Paschzähler um 1, andernfalls wird er auf 0 zurückgesetzt. Würde er 3 erreichen, so wird der eigentliche Zug verworfen und die Figur direkt ins Gefängnis geschickt. Für jeden Zustand \((p,d)\) zählt die Implementierung alle 16 Würfelergebnisse durch, löst das Zielfeld vollständig auf und verteilt die Wahrscheinlichkeitsmasse auf die Folgezustände. So entsteht eine stochastische Matrix \(P\) der Größe \(120 \times 120\) mit
$$\sum_t P_{(p,d),t}=1.$$
Die stationäre Verteilung \(\boldsymbol{\pi}\) erfüllt
$$\boldsymbol{\pi}=\boldsymbol{\pi}P,\qquad \sum_s \pi_s = 1.$$
Die reine Brettverteilung erhält man durch Marginalisierung über den Paschzähler:
$$\Pi(p)=\sum_{d=0}^{2}\pi_{(p,d)}.$$
Die drei größten Werte von \(\Pi(p)\) liefern direkt die gesuchte Zeichenkette.
Angenommen, ein Zug landet auf Feld \(36\), also auf dem dritten Ereignisfeld. Eine der 16 Ereigniskarten lautet „3 Felder zurück“, daher geht dieser Ast zunächst auf \(33\). Feld \(33\) ist aber ein Gemeinschaftsfeld, also ist der Ast noch nicht abgeschlossen. Er zerfällt erneut in GO mit Wahrscheinlichkeit \(1/16\), Gefängnis mit Wahrscheinlichkeit \(1/16\) und Verbleib auf \(33\) mit Wahrscheinlichkeit \(14/16\). Somit trägt der ursprüngliche Ereignisast
$$\frac{1}{16}\cdot\frac{1}{16}$$
zu GO, denselben Wert zu Gefängnis und
$$\frac{1}{16}\cdot\frac{14}{16}$$
zu Feld \(33\) bei. Genau deshalb modelliert die exakte Lösung Sonderfelder als kleinen Wahrscheinlichkeitsbaum und nicht als bloße Einzelsprung-Tabelle.
Das Gefängnis erhält Zufluss aus mehreren unabhängigen Quellen: vom Feld „Gehe ins Gefängnis“, von der entsprechenden Gemeinschaftskarte, von der entsprechenden Ereigniskarte und von der Regel mit den drei Paschen in Folge. Auch die Bahnhöfe werden bevorzugt, weil die Ereigniskarten einmal direkt nach R1 und zweimal zum nächsten Bahnhof schicken. Da ein Pasch mit 4-seitigen Würfeln die Wahrscheinlichkeit \(4/16 = 1/4\) hat, tritt die Folge von drei Paschen mit Wahrscheinlichkeit \((1/4)^3 = 1/64\) auf und damit deutlich häufiger als bei gewöhnlichen Würfeln. Dadurch wird insbesondere die Gefängnisregion im Langzeitverhalten verstärkt.
Die Kette ist irreduzibel und aperiodisch, daher besitzt sie genau eine stationäre Verteilung. Deshalb konvergiert die Potenziteration unabhängig vom Startzustand auf dieselben langfristigen Feldwahrscheinlichkeiten.
Die C++-, Python- und Java-Implementierungen benutzen dieselben Spielregeln, aber zwei verschiedene Rechenwege. Die C++-Implementierung baut die komplette 120-Zustands-Übergangsmatrix auf, startet die Wahrscheinlichkeitsmasse auf GO und wendet dann wiederholt Potenziteration an. Wegen des kleinen Zustandsraums und der schnellen Durchmischung genügt das bequem, um die drei beliebtesten Felder sicher zu ordnen.
Die Python- und Java-Implementierungen arbeiten dagegen per Monte-Carlo-Simulation. Sie würfeln viele Züge lang mit zwei 4-seitigen Würfeln, verfolgen Position und Paschzähler und zählen Besuche mit. Im Unterschied zum exakten Matrixmodell führen sie die Gemeinschafts- und Ereigniskarten als explizit gemischte Decks, die zyklisch verbraucht werden. Eine exakte Markov-Kette für dieses reichere Modell müsste also zusätzlich die Deckreihenfolge und die aktuelle Deckposition speichern und wäre deshalb wesentlich größer als 120 Zustände.
Am Ende werden in allen drei Sprachen die 40 Feldindizes nach absteigender Häufigkeit sortiert, und die ersten drei werden zweistellig zusammengefügt. Daraus entsteht die geforderte modale Zeichenkette.
Beim exakten Markov-Ansatz ist die Zustandszahl fest gleich 120. Der Aufbau der Matrix betrachtet 120 Zustände und pro Zustand 16 geordnete Würfe; die zusätzliche Verzweigung an Sonderfeldern bleibt konstant klein. Jeder Schritt der Potenziteration ist eine Matrix-Vektor-Multiplikation auf einer \(120 \times 120\)-Matrix, sodass 300 Iterationen in der Praxis sehr klein sind. Der Speicherbedarf beträgt \(O(120^2)\) für die Matrix und \(O(120)\) für die Zustandsvektoren.
Beim Monte-Carlo-Ansatz kostet eine Simulation von \(T\) Zügen Zeit \(O(T)\). Der Zusatzspeicher bleibt konstant bis auf die 40 Besuchszähler und die beiden Decks mit je 16 Karten. In den gelieferten Simulationen ist \(T=10^6\); das reicht gut für eine stabile Rangfolge, auch wenn keine exakte stationäre Verteilung berechnet wird.
84. problem, standart iki 6 yüzlü zar yerine iki 4 yüzlü zar kullanıldığında Monopoly tahtasındaki karelerin uzun vadede ne sıklıkla ziyaret edildiğini sorar. İstenen çıktı, ziyaret olasılığı en büyük üç karenin indekslerini ikişer basamaklı yazarak birleştiren modal dizgedir.
Tahta üzerinde hareket, 40 elemanlı basit bir çember yürüyüşü değildir. 30. kare doğrudan hapse yollar, Topluluk Sandığı kareleri GO veya hapishaneye ışınlayabilir, Şans kareleri birkaç sabit hedefe yönlendirebilir ve art arda üç çift gelmesi de hapse gönderir. Bu nedenle asıl matematik, çıplak zar toplamlarını saymak değil, sonlu bir stokastik sistemin durağan dağılımını bulmaktır.
Analitik uygulamanın kullandığı kesin yöntem, hafızalı bir Markov zinciridir. Durumu yalnızca mevcut kare ile temsil etmek yeterli değildir; çünkü “üst üste üç çift” kuralı önceki atışlara bağlıdır. Bu yüzden doğru durum \((p,d)\) çiftidir. Burada \(p \in \{0,\dots,39\}\) geçerli kareyi, \(d \in \{0,1,2\}\) ise bir sonraki atıştan önce elde bulunan ardışık çift sayısını gösterir. Böylece toplam \(40 \times 3 = 120\) durum elde edilir.
Aynı karede bulunmak her zaman aynı gelecek dağılımını vermez. Örneğin 18. karede iki ardışık çift sonrasında olmak ile hiç çift geçmişi olmadan olmak aynı durum değildir; bir sonraki atışta çift gelirse ilk oyuncu doğrudan hapse gider. Zincirin taşıması gereken ek hafıza tam olarak budur ve üç seviyeli sayaç bu bilgiyi eksiksiz tutar.
Sıralı bir zar sonucu \((d_1,d_2)\) geldikten sonra taş önce \(d_1+d_2\) kadar ilerler ve sonuç 40'a göre mod alınır. Sonra iniş yapılan kare çözülür. Kullanılan temel tahta nesneleri şunlardır: GO \(=0\), Hapishane \(=10\), Hapise Git \(=30\), Topluluk Sandığı kareleri \(2,17,33\), Şans kareleri \(7,22,36\), demiryolları \(5,15,25,35\) ve şirket kareleri \(12,28\).
Topluluk Sandığı için 16 kartın yalnızca ikisi hareket üretir: biri GO'ya, biri hapishaneye yollar, kalan 14 kart oyuncuyu bulunduğu karede bırakır. Şans için 16 kartın 10'u hareket ettiricidir: GO, Hapishane, C1, E3, H2, R1, iki kez sonraki demiryolu, sonraki şirket ve “3 kare geri git”. Özellikle “3 kare geri git” kartı önemlidir; çünkü gidilen yeni kare de tekrar çözülmek zorunda olabilir. Örneğin 36. karedeki Şans’tan 3 kare geri gidildiğinde 33. kareye, yani Topluluk Sandığına gelinir ve olasılık ağacı bir kat daha dallanır.
4 yüzlü zarlarla \(4^2=16\) eş olasılıklı sıralı sonuç vardır. Eğer \(d_1=d_2\) ise çift sayacı 1 artar, değilse 0'a sıfırlanır. Sayaç 3'e ulaşacaksa normal hareket iptal edilir ve oyuncu doğrudan hapse gönderilir. Uygulama her \((p,d)\) durumu için 16 zar sonucunun tamamını dolaşır, iniş karesini tüm yan etkileriyle çözer ve oluşan olasılık kütlesini hedef durumlara ekler. Böylece boyutu \(120 \times 120\) olan stokastik geçiş matrisi \(P\) elde edilir ve her satır için
$$\sum_t P_{(p,d),t}=1$$
eşitliği sağlanır. Durağan dağılım \(\boldsymbol{\pi}\),
$$\boldsymbol{\pi}=\boldsymbol{\pi}P,\qquad \sum_s \pi_s = 1$$
koşullarını sağlar. Tahta üzerindeki saf kare olasılıkları ise çift sayaçları üzerinden marjinalleştirilerek bulunur:
$$\Pi(p)=\sum_{d=0}^{2}\pi_{(p,d)}.$$
Son adımda \(\Pi(p)\) değerleri sıralanır ve en büyük üç indeks modal dizgeyi verir.
Diyelim ki bir hamle 36. kareye, yani üçüncü Şans karesine indi. 16 Şans kartından biri “3 kare geri git” dediği için bu dal önce 33. kareye gider. Fakat 33. kare Topluluk Sandığıdır; dolayısıyla süreç bitmez ve dal yeniden üçe ayrılır: \(1/16\) olasılıkla GO, \(1/16\) olasılıkla Hapishane, \(14/16\) olasılıkla 33. karede kalış. Bu nedenle başlangıçtaki Şans dalı
$$\frac{1}{16}\cdot\frac{1}{16}$$
olasılığını GO’ya, aynı miktarı Hapishaneye ve
$$\frac{1}{16}\cdot\frac{14}{16}$$
olasılığını 33. kareye taşır. Uygulamadaki küçük özyineli çözümün arkasındaki matematik tam olarak budur.
Hapishane birden fazla bağımsız kaynaktan beslenir: Hapise Git karesi, Topluluk Sandığındaki hapis kartı, Şans’taki hapis kartı ve art arda üç çift kuralı. Demiryolları da Şans kartları yüzünden fazladan akış alır; çünkü bir kart doğrudan R1’e, iki kart ise “sonraki demiryolu”na yollar. 4 yüzlü zarlarla çift gelme olasılığı \(4/16 = 1/4\) olduğundan, art arda üç çiftin olasılığı \((1/4)^3 = 1/64\) olur. Bu değer standart zarlara göre daha büyüktür ve özellikle Hapishane çevresinin durağan dağılımda yukarı çıkmasına yol açar.
Zincir indirgenemez ve aperiyodiktir; bu yüzden durağan dağılım tektir. Güç yinelemesinin sabit bir vektöre oturmasının nedeni de bu yapısal özelliktir.
C++, Python ve Java uygulamaları aynı oyun kurallarını uygular, fakat iki farklı hesaplama yaklaşımı kullanır. C++ uygulaması tam 120 durumlu geçiş matrisini kurar, başlangıçta tüm olasılığı GO karesine koyar ve ardından sabit sayıda güç yinelemesi yapar. Durum uzayı küçük olduğu için bu yöntem durağan dağılımı ilk üç kareyi sıralamaya fazlasıyla yetecek doğrulukta verir.
Python ve Java uygulamaları ise Monte Carlo simülasyonu yapar. Çok sayıda tur boyunca iki 4 yüzlü zar atılır, mevcut kare ile ardışık çift sayısı izlenir ve ziyaret sayıları artırılır. Bu iki sürüm ayrıca Topluluk Sandığı ve Şans destelerini açıkça karıştırıp döngüsel biçimde tüketir. Dolayısıyla onların simüle ettiği süreç, tam analitik modelden biraz daha zengindir; bunu tam Markov zinciri olarak yazmak istesek deste sırası ve destedeki konumu da duruma eklemek gerekir.
Son aşamada bütün uygulamalar kareleri frekanslarına göre sıralar ve ilk üç indeksi ikişer basamaklı biçimde birleştirir. Böylece sorunun istediği modal dizge üretilir.
Kesin Markov-zinciri yaklaşımında durum sayısı sabit olarak 120'dir. Matris kurulumunda 120 durum ve her durum için 16 sıralı zar sonucu incelenir; özel kare dallanmaları sabit boyutlu kaldığı için bu kısım pratikte sabit maliyetlidir. Her güç yinelemesi adımı \(120 \times 120\) yoğun bir matris ile vektör çarpımıdır; 300 yineleme de gerçek çalışma süresi açısından çok küçüktür. Bellek kullanımı matris için \(O(120^2)\), olasılık vektörleri için \(O(120)\) olur.
Monte Carlo yaklaşımında \(T\) tur simüle edilirse zaman maliyeti \(O(T)\) olur. Yardımcı bellek, 40 ziyaret sayacı ve iki adet 16 kartlık deste dışında sabittir. Verilen simülasyonlarda \(T=10^6\) kullanılır; bu, frekansları tam çözmez ama sıralamayı güvenilir biçimde sabitlemek için yeterlidir.
El problema 84 pide estudiar qué casillas de Monopoly se visitan con mayor frecuencia cuando los dos dados habituales de 6 caras se sustituyen por dos dados de 4 caras. La salida buscada es la cadena modal formada por los índices de las tres casillas más probables, escritos con dos dígitos y concatenados en orden decreciente de probabilidad.
El movimiento no es un paseo aleatorio simple sobre un ciclo de 40 posiciones. La casilla 30 envía directamente a la cárcel, las casillas de Community Chest pueden redirigir a GO o a Jail, las casillas de Chance pueden mover la ficha a varios destinos concretos, y además tres dobles consecutivos también mandan a la cárcel. Por eso el problema consiste en hallar la distribución estacionaria de un sistema estocástico finito, no en promediar solo sumas de dados.
El método exacto usado por la implementación analítica es una cadena de Markov con memoria. El estado no puede ser solamente la casilla actual, porque la regla de los tres dobles consecutivos depende de lo ocurrido en tiradas anteriores. El estado correcto es entonces \((p,d)\), donde \(p \in \{0,\dots,39\}\) es la casilla actual y \(d \in \{0,1,2\}\) indica cuántos dobles consecutivos lleva acumulados el jugador. Eso produce \(40 \times 3 = 120\) estados.
Estar en la misma casilla no siempre significa tener las mismas probabilidades para el siguiente turno. Si una ficha está en la casilla 18 con dos dobles consecutivos previos, otro doble la enviará inmediatamente a la cárcel; si está en la misma casilla sin historial de dobles, eso no ocurre. Esa memoria mínima es exactamente la que representa el contador \(d\).
Tras una tirada ordenada \((d_1,d_2)\), la ficha avanza \(d_1+d_2\) posiciones módulo 40. Después se resuelve la casilla de llegada. Los objetos importantes del tablero son GO \(=0\), Jail \(=10\), Go To Jail \(=30\), Community Chest en \(2,17,33\), Chance en \(7,22,36\), los ferrocarriles en \(5,15,25,35\) y las utilities en \(12,28\).
Community Chest tiene solo dos cartas de movimiento: una manda a GO y otra a Jail; las otras 14 no cambian la posición. Chance tiene 10 cartas de movimiento entre 16: GO, Jail, C1, E3, H2, R1, dos veces el siguiente ferrocarril, la siguiente utility y “retrocede 3 casillas”. Esta última carta es la más delicada, porque la nueva casilla puede requerir otra resolución. En particular, desde Chance en la casilla 36, retroceder 3 casillas lleva a 33, que es Community Chest, así que la probabilidad vuelve a ramificarse.
Con dados de 4 caras hay \(4^2=16\) resultados ordenados equiprobables. Si \(d_1=d_2\), el contador de dobles aumenta en 1; en otro caso se reinicia a 0. Si el contador alcanzaría 3, el movimiento normal se reemplaza por una transición directa a Jail. Para cada estado \((p,d)\), la implementación recorre las 16 tiradas, resuelve por completo la casilla final y acumula probabilidad en los estados de destino. Así se obtiene una matriz estocástica \(P\) de tamaño \(120 \times 120\) que cumple
$$\sum_t P_{(p,d),t}=1.$$
La distribución estacionaria \(\boldsymbol{\pi}\) satisface
$$\boldsymbol{\pi}=\boldsymbol{\pi}P,\qquad \sum_s \pi_s = 1.$$
Luego se elimina el contador de dobles sumando sobre sus tres valores:
$$\Pi(p)=\sum_{d=0}^{2}\pi_{(p,d)}.$$
Las tres mayores cantidades \(\Pi(p)\) determinan directamente la cadena modal pedida.
Supongamos que una jugada termina en la casilla \(36\), la tercera casilla de Chance. Una de las 16 cartas dice “retrocede 3 casillas”, de modo que esa rama pasa primero a \(33\). Pero la casilla \(33\) es Community Chest, así que la historia no termina ahí. Ahora la rama se divide otra vez: GO con probabilidad \(1/16\), Jail con probabilidad \(1/16\) y permanencia en \(33\) con probabilidad \(14/16\). Por tanto, la rama inicial de Chance aporta
$$\frac{1}{16}\cdot\frac{1}{16}$$
a GO, la misma cantidad a Jail, y
$$\frac{1}{16}\cdot\frac{14}{16}$$
a la casilla \(33\). Este ejemplo muestra por qué la resolución exacta se implementa como un pequeño árbol de probabilidades.
La cárcel recibe probabilidad de varias fuentes independientes: la casilla Go To Jail, la carta de Jail en Community Chest, la carta de Jail en Chance y la regla de los tres dobles consecutivos. Los ferrocarriles también reciben flujo extra porque Chance tiene una carta para R1 y dos cartas que envían al siguiente ferrocarril. Como con dados de 4 caras la probabilidad de dobles es \(4/16 = 1/4\), la probabilidad de tres dobles seguidos es \((1/4)^3 = 1/64\), bastante mayor que con los dados normales. Eso eleva notablemente la importancia de Jail en la distribución estacionaria.
La cadena es irreducible y aperiódica, así que posee una única distribución estacionaria. Esa es la base teórica que justifica la convergencia de la iteración de potencia.
Las implementaciones en C++, Python y Java comparten las reglas del tablero, pero usan dos estrategias distintas. La implementación en C++ construye la matriz completa de 120 estados, concentra inicialmente toda la masa en GO y aplica iteración de potencia durante un número fijo de pasos. Como el espacio de estados es pequeño, esa aproximación converge con margen suficiente para ordenar sin ambigüedad las casillas más visitadas.
Las implementaciones en Python y Java usan simulación Monte Carlo. Ejecutan una gran cantidad de turnos, tiran dos dados de 4 caras, mantienen la posición actual y el contador de dobles, y acumulan visitas por casilla. Además, esas dos versiones representan Community Chest y Chance como barajas explícitas que se barajan una vez y luego se recorren de forma cíclica. Por tanto, el proceso exacto que están simulando incluye también el orden de las barajas y su posición actual, lo que haría mucho más grande una cadena de Markov exacta para ese modelo.
Al final, todas las implementaciones ordenan los 40 índices por frecuencia descendente y concatenan los tres primeros como números de dos dígitos. Así se construye la respuesta final.
En el enfoque exacto de cadena de Markov, el número de estados es fijo e igual a 120. La construcción de la matriz examina 120 estados y 16 tiradas ordenadas por estado, con una ramificación de tamaño constante al resolver casillas especiales. Cada paso de iteración de potencia es una multiplicación matriz-vector sobre una matriz \(120 \times 120\); con 300 iteraciones, el coste práctico sigue siendo muy pequeño. La memoria usada es \(O(120^2)\) para la matriz y \(O(120)\) para los vectores de probabilidad.
En el enfoque Monte Carlo, si se simulan \(T\) turnos, el tiempo es \(O(T)\). La memoria auxiliar es constante salvo por los 40 contadores de visitas y las dos barajas de 16 cartas. En las simulaciones incluidas se usa \(T=10^6\), suficiente para estabilizar bien el orden de las casillas aunque no produzca una distribución estacionaria exacta.
第 84 题要求分析这样一个 Monopoly 过程：把通常的两个 6 面骰子换成两个 4 面骰子以后，棋盘上 40 个格子的长期访问频率会怎样变化。题目要输出的是 modal string，也就是把稳态下访问概率最大的三个格子编号按概率从大到小排列，并各自写成两位数后拼接起来。
这不是一个单纯的“在 40 个位置上按骰子和前进”的循环随机游走。30 号格会直接送进监狱，Community Chest 可能把玩家送到 GO 或 Jail，Chance 可能把玩家送到若干固定目标，连续三次掷出 doubles 也会立刻入狱。于是问题的本质不是普通的掷骰统计，而是求一个有限随机系统的平稳分布。
解析实现采用的是带记忆的马尔可夫链。状态不能只记录当前位置，因为“三次连续 doubles 进监狱”这一规则依赖前两次掷骰结果。合适的状态写成 \((p,d)\)，其中 \(p \in \{0,\dots,39\}\) 表示当前所在格子，\(d \in \{0,1,2\}\) 表示在这一回合开始前已经累计了多少次连续 doubles。这样总状态数就是 \(40 \times 3 = 120\)。
同一个格子在不同 doubles 历史下，对下一步的转移概率并不相同。比如都站在 18 号格，如果此前已经连续掷出了两次 doubles，那么下一次再出 doubles 就要直接进监狱；如果此前没有 doubles 历史，则不会发生这件事。也就是说，位置之外还必须保留一个长度为 3 的“连续 doubles 计数器”，这正是 120 状态模型的来源。
一次有序掷骰结果 \((d_1,d_2)\) 先让棋子前进 \(d_1+d_2\) 格，对 40 取模，然后再解析落点。代码中真正起作用的对象包括：GO \(=0\)、Jail \(=10\)、Go To Jail \(=30\)、Community Chest \(2,17,33\)、Chance \(7,22,36\)、铁路 \(5,15,25,35\)、公用事业 \(12,28\)。
Community Chest 的 16 张牌里，只有两张会移动棋子：一张去 GO，一张去 Jail，其余 14 张保持不动。Chance 的 16 张牌里有 10 张会移动棋子，分别去 GO、Jail、C1、E3、H2、R1、下一条铁路两次、下一个公用事业一次，以及“后退 3 格”。最后这一张最关键，因为后退后的新格子可能还要继续解析。例如从 36 号 Chance 格后退 3 格会到 33 号，而 33 号本身又是 Community Chest，所以这一分支会继续拆开。
两个 4 面骰子共有 \(4^2=16\) 个等概率的有序结果。如果 \(d_1=d_2\)，连续 doubles 计数加 1；否则清零。如果计数本该变成 3，那么正常移动直接取消，转而立刻去 Jail。实现对每个状态 \((p,d)\) 都枚举全部 16 个掷骰结果，完整解析落点及其连锁效果，再把概率质量累加到目标状态上，于是得到一个 \(120 \times 120\) 的随机矩阵 \(P\)，满足
$$\sum_t P_{(p,d),t}=1.$$
平稳分布 \(\boldsymbol{\pi}\) 定义为
$$\boldsymbol{\pi}=\boldsymbol{\pi}P,\qquad \sum_s \pi_s = 1.$$
如果只关心棋盘格子而不关心 doubles 计数，就把三个 doubles 状态相加：
$$\Pi(p)=\sum_{d=0}^{2}\pi_{(p,d)}.$$
然后把 40 个 \(\Pi(p)\) 排序，取前三个编号，就得到题目要求的 modal string。
假设某一步恰好落在 \(36\) 号格，也就是第三个 Chance。16 张 Chance 牌里有一张是“后退 3 格”，所以这条分支先走到 \(33\) 号格。但 \(33\) 号格是 Community Chest，这条分支并没有结束，它还要继续按 Community Chest 规则分成三部分：以 \(1/16\) 的概率去 GO，以 \(1/16\) 的概率去 Jail，以 \(14/16\) 的概率停在 \(33\) 号格。因此，最初那张 Chance 牌对 GO 的贡献是
$$\frac{1}{16}\cdot\frac{1}{16},$$
对 Jail 的贡献相同，而对 \(33\) 号格的贡献是
$$\frac{1}{16}\cdot\frac{14}{16}.$$
这正说明为什么实现里要把特殊格子的处理写成一个很小的概率树，而不是一张单层查表。
Jail 会从多个独立来源吸收概率质量：30 号 Go To Jail、Community Chest 中的去 Jail 卡、Chance 中的去 Jail 卡，以及连续三次 doubles 的强制入狱规则。铁路也会得到额外流入，因为 Chance 里既有直接去 R1 的卡，也有两张“去下一条铁路”的卡。对于 4 面骰子，掷出 doubles 的概率是 \(4/16 = 1/4\)，因此三次连续 doubles 的概率是 \((1/4)^3 = 1/64\)，比普通 6 面骰子下要大得多，所以 Jail 在稳态分布中尤其突出。
这个链是不可约且非周期的，因此平稳分布唯一存在。也正因为如此，从任何初始状态出发做幂迭代，最终都会收敛到同一个长期分布。
C++、Python 和 Java 三种实现遵循同一套棋盘规则，但采用了两种不同的计算路线。C++ 实现显式构造 120 状态转移矩阵，把初始全部概率放在 GO，然后反复做矩阵乘向量的幂迭代。由于状态空间很小，这种做法足以精确恢复最常访问格子的排名。
Python 和 Java 实现则走 Monte Carlo 路线。它们模拟大量回合，每回合掷两个 4 面骰子，维护当前位置和连续 doubles 计数，并把每次落点记入访问次数。与解析矩阵模型不同，这两个实现还显式维护洗过一次牌后循环使用的 Community Chest 和 Chance 牌堆。于是它们真正模拟的是一个更丰富的随机过程；如果要把这个过程完整写成精确马尔可夫链，就必须把牌堆顺序和当前抽到哪里也纳入状态，规模会远大于 120。
最后，三种实现都会把 40 个格子的频率按降序排列，取前三个编号，并以两位数字的形式拼接起来。这样就得到题目所要求的输出格式。
在精确马尔可夫链方法中，状态数固定为 120。构造矩阵时要查看 120 个状态以及每个状态的 16 个有序掷骰结果，特殊格子的分支规模又是常数，所以这一步在实际中非常小。每一次幂迭代都是一次 \(120 \times 120\) 的矩阵向量乘法；做 300 次迭代的总成本依然很低。内存方面，矩阵占 \(O(120^2)\)，概率向量占 \(O(120)\)。
在 Monte Carlo 方法中，如果总共模拟 \(T\) 回合，时间复杂度就是 \(O(T)\)。额外空间除 40 个访问计数和两副各 16 张的牌堆之外几乎是常数。给出的模拟实现取 \(T=10^6\)，这虽然不是精确求解平稳分布，但已经足以让热门格子的排序稳定下来。
В задаче 84 нужно выяснить, какие клетки Monopoly посещаются чаще всего в долгосрочном режиме, если вместо двух стандартных шестигранных кубиков использовать два четырехгранных. Ответом служит модальная строка: индексы трех наиболее вероятных клеток записываются как двузначные числа и конкатенируются в порядке убывания вероятности.
Это не простой случайный обход 40-клеточного цикла. Клетка 30 немедленно отправляет в тюрьму, клетки Community Chest могут перенаправить на GO или в Jail, клетки Chance могут отправлять на несколько фиксированных позиций, а три последовательных дубля тоже ведут в тюрьму. Поэтому задача сводится к нахождению стационарного распределения конечной стохастической системы.
Точный аналитический метод в реализации основан на цепи Маркова с памятью. Нельзя хранить только текущую клетку, потому что правило трех последовательных дублей зависит от предыдущих бросков. Поэтому естественное состояние имеет вид \((p,d)\), где \(p \in \{0,\dots,39\}\) обозначает текущую клетку, а \(d \in \{0,1,2\}\) показывает, сколько последовательных дублей уже накоплено. Всего получается \(40 \times 3 = 120\) состояний.
Одна и та же клетка не всегда означает одинаковое распределение следующего хода. Если игрок находится на клетке 18 после двух последовательных дублей, то еще один дубль отправит его прямо в тюрьму. Если же тот же игрок находится на клетке 18 без такой истории, картина переходов будет другой. Именно поэтому в состоянии нужен дополнительный счетчик из трех возможных значений.
После упорядоченного броска \((d_1,d_2)\) фишка сначала перемещается на \(d_1+d_2\) клеток по модулю 40, а затем применяется правило для клетки приземления. Существенные объекты доски таковы: GO \(=0\), Jail \(=10\), Go To Jail \(=30\), Community Chest на \(2,17,33\), Chance на \(7,22,36\), железные дороги на \(5,15,25,35\) и utilities на \(12,28\).
Для Community Chest из 16 карт только две меняют положение: одна отправляет на GO, одна в Jail, остальные 14 оставляют игрока на месте. Для Chance из 16 карт 10 являются движущими: GO, Jail, C1, E3, H2, R1, два раза следующая железная дорога, следующее utility и «назад на 3 клетки». Последняя карта особенно важна, потому что новая клетка сама может оказаться специальной. Например, с клетки 36 переход назад на 3 клетки ведет на 33, а это снова Community Chest, значит ветвление вероятностей продолжается.
Для двух четырехгранных кубиков есть \(4^2=16\) равновероятных упорядоченных исходов. Если \(d_1=d_2\), счетчик дублей увеличивается на 1, иначе сбрасывается в 0. Если он должен стать равным 3, обычный ход отменяется, и игрок сразу отправляется в Jail. Для каждого состояния \((p,d)\) реализация перебирает все 16 бросков, полностью разрешает конечную клетку и распределяет вероятность по состояниям назначения. Так возникает стохастическая матрица \(P\) размера \(120 \times 120\), для которой выполняется
$$\sum_t P_{(p,d),t}=1.$$
Стационарное распределение \(\boldsymbol{\pi}\) определяется условиями
$$\boldsymbol{\pi}=\boldsymbol{\pi}P,\qquad \sum_s \pi_s = 1.$$
Вероятности только по клеткам доски получаются суммированием по трем значениям счетчика дублей:
$$\Pi(p)=\sum_{d=0}^{2}\pi_{(p,d)}.$$
Три наибольших значения \(\Pi(p)\) и дают искомую модальную строку.
Пусть ход заканчивается на клетке \(36\), то есть на третьей клетке Chance. Одна из 16 карт Chance говорит «назад на 3 клетки», поэтому соответствующая ветвь сначала попадает на \(33\). Но клетка \(33\) является Community Chest, так что на этом процесс не заканчивается. Ветвь снова распадается: GO с вероятностью \(1/16\), Jail с вероятностью \(1/16\), и остаться на \(33\) с вероятностью \(14/16\). Значит, исходная ветвь Chance вносит
$$\frac{1}{16}\cdot\frac{1}{16}$$
в GO, столько же в Jail, и
$$\frac{1}{16}\cdot\frac{14}{16}$$
в клетку \(33\). Именно этот пример показывает, почему в точной модели специальные клетки обрабатываются как маленькое дерево вероятностей.
В Jail вероятность поступает из нескольких независимых источников: клетка Go To Jail, карта Jail из Community Chest, карта Jail из Chance и правило трех последовательных дублей. Железные дороги тоже получают дополнительный поток, потому что Chance содержит одну карту для R1 и две карты вида «идти на следующую железную дорогу». Так как на четырехгранных кубиках дубль выпадает с вероятностью \(4/16 = 1/4\), вероятность трех дублей подряд равна \((1/4)^3 = 1/64\), что заметно выше, чем при обычных кубиках. Поэтому область Jail особенно выделяется в стационарном распределении.
Цепь неприводима и апериодична, следовательно, стационарное распределение единственно. Это и гарантирует сходимость степенной итерации к правильным долгосрочным частотам.
Реализации на C++, Python и Java используют одни и те же правила доски, но опираются на две разные вычислительные идеи. Реализация на C++ строит полную матрицу переходов для 120 состояний, начинает со всей вероятностной массы в GO и затем многократно умножает текущий вектор на матрицу. Поскольку пространство состояний мало, такой способ быстро дает стационарное распределение с запасом по точности для ранжирования клеток.
Реализации на Python и Java выбирают путь Монте-Карло. Они моделируют большое число ходов, каждый раз бросают два четырехгранных кубика, отслеживают текущую позицию и число последовательных дублей и накапливают счетчики посещений. В отличие от точной матричной модели, эти две версии также явно хранят колоды Community Chest и Chance, перемешанные один раз и затем проходящиеся циклически. Поэтому точная цепь Маркова для их процесса должна была бы включать еще и порядок карт, и текущий индекс внутри колоды, что делает точную модель намного крупнее 120 состояний.
После накопления вероятностей или посещений все реализации сортируют 40 индексов по убыванию частоты и склеивают первые три как двузначные числа. Так формируется окончательный ответ.
В точном марковском подходе число состояний фиксировано и равно 120. Построение матрицы требует рассмотреть 120 состояний и по 16 упорядоченных бросков для каждого, а размер ветвления при обработке специальных клеток остается постоянным. Каждый шаг степенной итерации представляет собой умножение матрицы \(120 \times 120\) на вектор; даже 300 таких шагов стоят очень мало. Память составляет \(O(120^2)\) для матрицы и \(O(120)\) для векторов вероятностей.
В подходе Монте-Карло, если моделируется \(T\) ходов, время работы равно \(O(T)\). Дополнительная память постоянна, если не считать 40 счетчиков посещений и двух колод по 16 карт. В предоставленных симуляциях берется \(T=10^6\), чего достаточно для устойчивого порядка лидирующих клеток, хотя это и не точное решение стационарной задачи.
تطلب المسألة 84 تحديد المربعات الأكثر زيارة على لوحة Monopoly عندما نستبدل النردين القياسيين ذوي الستة أوجه بنردين ذوي أربعة أوجه. المطلوب في النهاية هو تكوين السلسلة النمطية، أي أخذ أرقام المربعات الثلاثة الأعلى احتمالًا في الحالة المستقرة، وكتابتها بصيغة رقمين لكل مربع ثم وصلها بترتيب تنازلي حسب الاحتمال.
الحركة هنا ليست مجرد مشي عشوائي بسيط على دورة طولها 40. فالمربع 30 يرسل اللاعب مباشرة إلى السجن، ومربعات Community Chest قد تنقله إلى GO أو Jail، ومربعات Chance قد تقفز به إلى وجهات محددة، كما أن ثلاث مرات doubles متتالية ترسله أيضًا إلى السجن. لذلك فجوهر المسألة هو إيجاد التوزيع الثابت لنظام احتمالي منتهٍ، لا مجرد حساب متوسط مجموع النرد.
الطريقة الدقيقة في التنفيذ التحليلي تعتمد على سلسلة ماركوف لها ذاكرة قصيرة. لا يكفي أن نمثل الحالة بالمربع الحالي فقط، لأن قاعدة “ثلاث doubles متتالية” تعتمد على ما حدث في الرميات السابقة. لذلك تُكتب الحالة على صورة \((p,d)\)، حيث \(p \in \{0,\dots,39\}\) هو المربع الحالي، و\(d \in \{0,1,2\}\) هو عدد doubles المتتالية المتراكمة قبل الرمية التالية. وهكذا نحصل على \(40 \times 3 = 120\) حالة.
الوجود على نفس المربع لا يعني دائمًا نفس احتمالات الحركة التالية. إذا كان اللاعب على المربع 18 بعد doubles متتاليتين، فإن double ثالثة سترسله فورًا إلى السجن. أما إذا كان على المربع نفسه من دون هذا التاريخ، فالسلوك مختلف. إذن لا بد من حفظ عداد صغير يمثل هذه الذاكرة، وهذا هو سبب وجود ثلاثة مستويات إضافية لكل مربع.
بعد رمية مرتبة \((d_1,d_2)\)، تتحرك القطعة أولًا بمقدار \(d_1+d_2\) مربعًا بتعديل 40، ثم تُحل القاعدة الخاصة بالمربع الذي وصلت إليه. الكائنات المهمة على اللوحة هي: GO \(=0\)، Jail \(=10\)، Go To Jail \(=30\)، ومربعات Community Chest عند \(2,17,33\)، ومربعات Chance عند \(7,22,36\)، والسكك الحديدية عند \(5,15,25,35\)، والخدمات عند \(12,28\).
في Community Chest توجد بطاقتان فقط تغيران الموضع: بطاقة إلى GO وبطاقة إلى Jail، أما البطاقات الأربع عشرة الأخرى فتبقي اللاعب في مكانه. وفي Chance توجد 10 بطاقات حركة من أصل 16: إلى GO، إلى Jail، إلى C1، إلى E3، إلى H2، إلى R1، وإلى السكة الحديدية التالية مرتين، وإلى الخدمة التالية مرة واحدة، وبطاقة “ارجع 3 مربعات”. هذه البطاقة الأخيرة مهمة جدًا لأن المربع الجديد قد يحتاج إلى حل إضافي. فإذا خرجت من Chance عند 36 وعدت 3 مربعات، فإنك تصل إلى 33، وهو Community Chest، فتتفرع الاحتمالات من جديد.
مع نردين رباعيي الأوجه توجد \(4^2=16\) نتيجة مرتبة متساوية الاحتمال. إذا كان \(d_1=d_2\) يزداد عداد doubles بمقدار 1، وإلا يعود إلى الصفر. وإذا كان العداد سيصبح 3، تُلغى الحركة العادية ويُنقل اللاعب مباشرة إلى Jail. يقوم التنفيذ، لكل حالة \((p,d)\)، بتعداد جميع الرميات الست عشرة، ثم يحل مربع الهبوط بالكامل ويضيف الكتلة الاحتمالية إلى حالات الوصول. بهذه الطريقة نحصل على مصفوفة انتقال احتمالية \(P\) بحجم \(120 \times 120\)، ويحقق كل صف فيها العلاقة
$$\sum_t P_{(p,d),t}=1.$$
أما التوزيع الثابت \(\boldsymbol{\pi}\) فيحقق
$$\boldsymbol{\pi}=\boldsymbol{\pi}P,\qquad \sum_s \pi_s = 1.$$
وللحصول على احتمال الوجود على المربع \(p\) بصرف النظر عن عداد doubles، نجمع على الحالات الثلاث الموافقة له:
$$\Pi(p)=\sum_{d=0}^{2}\pi_{(p,d)}.$$
بعد ذلك يكفي ترتيب القيم الأربعين \(\Pi(p)\) وأخذ أكبر ثلاث قيم مع فهارسها لبناء السلسلة النمطية.
افترض أن حركة ما انتهت عند المربع \(36\)، أي عند ثالث مربعات Chance. إحدى بطاقات Chance الست عشرة تقول “ارجع 3 مربعات”، لذلك تنتقل هذه الشعبة أولًا إلى \(33\). لكن \(33\) هو مربع Community Chest، ولذلك لا ينتهي الأمر هنا. بل تنقسم الشعبة مرة أخرى إلى ثلاث نتائج: GO باحتمال \(1/16\)، وJail باحتمال \(1/16\)، والبقاء على \(33\) باحتمال \(14/16\). لهذا تسهم شعبة Chance الأصلية بمقدار
$$\frac{1}{16}\cdot\frac{1}{16}$$
في GO، وبالمقدار نفسه في Jail، وبمقدار
$$\frac{1}{16}\cdot\frac{14}{16}$$
في المربع \(33\). هذا المثال يوضح لماذا تُنفذ معالجة المربعات الخاصة على هيئة شجرة احتمالات صغيرة لا كجدول قفزة واحد فقط.
السجن يستقبل كتلة احتمالية من عدة مصادر مستقلة: مربع Go To Jail، وبطاقة Jail في Community Chest، وبطاقة Jail في Chance، وقاعدة الثلاث doubles المتتالية. كما تحصل السكك الحديدية على تدفق إضافي لأن Chance تحتوي على بطاقة تنقل مباشرة إلى R1 وبطاقتين تنقلان إلى السكة الحديدية التالية. وبما أن احتمال ظهور doubles مع نردين رباعيي الأوجه هو \(4/16 = 1/4\)، فإن احتمال ثلاث doubles متتالية يساوي \((1/4)^3 = 1/64\)، وهو أكبر مما يكون عليه مع النرد القياسي. لذلك تزداد شعبية Jail بوضوح في التوزيع الثابت.
السلسلة هنا غير قابلة للاختزال وغير دورية، ولهذا يوجد توزيع ثابت وحيد. وهذه الحقيقة هي التي تبرر تقارب تكرار القدرة إلى نفس المتجه النهائي بغض النظر عن حالة البداية.
تنفيذات C++ وPython وJava تشترك في قواعد اللوحة نفسها، لكنها تستخدم مسارين مختلفين للحساب. تنفيذ C++ يبني مصفوفة الانتقال الكاملة ذات 120 حالة، ويبدأ بوضع كل الكتلة الاحتمالية عند GO، ثم يطبق تكرار القدرة عددًا ثابتًا من المرات. وبما أن فضاء الحالات صغير، فإن هذا يكفي لاستخراج ترتيب المربعات الأكثر زيارة بدقة مريحة.
أما تنفيذات Python وJava فتستخدم محاكاة Monte Carlo. فهي تجري عددًا كبيرًا من الأدوار، وترمي نردين رباعيي الأوجه، وتتابع الموضع الحالي وعدد doubles المتتالية، ثم تزيد عدادات الزيارة. كذلك تحتفظ هاتان النسختان برزمتي Community Chest وChance بعد خلطهما مرة واحدة ثم استهلاكهما دوريًا. وهذا يعني أن العملية التي تحاكيانها أغنى قليلًا من نموذج المصفوفة الدقيقة؛ فلو أردنا تمثيلها بدقة كسلسلة ماركوف، لوجب إضافة ترتيب البطاقات وموضع السحب الحالي إلى الحالة.
في النهاية ترتب جميع التنفيذات المربعات الأربعين حسب التكرار التنازلي، وتأخذ الفهارس الثلاثة الأولى، وتكتبها بصيغة رقمين ثم تصلها. بذلك تتكون الإجابة النهائية التي تطلبها المسألة.
في منهج سلسلة ماركوف الدقيقة، عدد الحالات ثابت ويساوي 120. بناء المصفوفة يتطلب فحص 120 حالة و16 رمية مرتبة لكل حالة، بينما يبقى عدد التفرعات الناتج عن حل المربعات الخاصة ثابتًا وصغيرًا. كل خطوة من تكرار القدرة هي ضرب مصفوفة \(120 \times 120\) في متجه، وحتى 300 خطوة تبقى زهيدة جدًا في التطبيق العملي. استهلاك الذاكرة هو \(O(120^2)\) للمصفوفة و\(O(120)\) لمتجهات الاحتمال.
في منهج Monte Carlo، إذا حاكينا \(T\) دورات فزمن التنفيذ هو \(O(T)\). والذاكرة الإضافية ثابتة تقريبًا باستثناء 40 عدادًا للزيارات ورزمتين من 16 بطاقة. في التنفيذات المرفقة استُخدم \(T=10^6\)، وهو كافٍ لتثبيت ترتيب المربعات الأعلى رغم أنه لا يحل معادلات التوزيع الثابت حلًا تحليليًا مباشرًا.