Larry and Robin observe the same random sequence of calls from an alphabet of size \(10\). Both memories have capacity \(5\), but they update differently. After \(50\) turns we want the exact value of
$$\mathbb{E}(|L-R|),$$
where \(L\) and \(R\) are the total hit counts of Larry and Robin.
A state is the ordered pair of memories
$$\sigma=(M_L,M_R), \qquad |M_L|,|M_R|\le 5.$$
Both memories keep order from oldest to newest. The update rules are:
Larry. On a hit, the called label is removed from its current position and moved to the back. On a miss, the label is appended, and if the memory is full the oldest label is evicted first.
Robin. On a hit, the score increases but the memory order does not change. On a miss, Robin also appends and evicts the oldest label if necessary.
For one call, the score increment is
$$\Delta=(\text{Larry hit})-(\text{Robin hit})\in\{-1,0,+1\}.$$
The actual digit names do not matter. Only equality relations such as "present in Larry only", "present in both", and relative order inside each memory affect future behavior. Therefore two states that differ only by a permutation of labels have exactly the same transition structure.
The code canonicalizes a state by scanning Larry's memory from left to right, then Robin's memory, and renaming first-seen labels to \(0,1,2,\dots\). For example,
$$M_L=(6,1,8,10,2),\qquad M_R=(2,4,6,8,10)$$
becomes
$$M_L=(0,1,2,3,4),\qquad M_R=(4,5,0,2,3).$$
Any raw state with the same equality pattern collapses to this same canonical representative. This is why the graph stays finite and small.
Suppose a canonical state contains the set \(U\) of labels that currently appear in at least one memory. Calls split into two classes:
Known labels. Every \(x\in U\) is processed individually with weight \(1\).
Unseen labels. Every label outside \(U\) behaves the same up to canonical relabeling, because it is absent from both memories and enters as one fresh symbol. So the code simulates one representative unseen label and assigns it weight
$$10-|U|.$$
After canonicalization, multiple calls may lead to the same \((\sigma',\Delta)\), so their weights are merged. For every state, the outgoing weights sum to the alphabet size \(10\). This is one of the graph-structure checkpoints in the C++ code.
Let \(P_t(\sigma,d)\) be the probability that after \(t\) turns we are in canonical state \(\sigma\) and the hit difference is
$$d=L-R.$$
Initially only the empty state with \(d=0\) has probability \(1\). If a weighted edge \(\sigma\to\sigma'\) has score change \(\Delta\) and weight \(w\), then its probability is \(w/10\), so
$$P_{t+1}(\sigma',d+\Delta)=\sum_{\sigma,d} P_t(\sigma,d)\cdot \frac{w(\sigma\to\sigma',\Delta)}{10}.$$
Since each turn changes the difference by at most \(1\), after \(t\) turns we only need the band
$$-t \le d \le t,$$
which is why the code stores arrays of width \(2T+1\).
At the end, the required expectation is
$$\mathbb{E}(|L-R|)=\sum_{\sigma,d}P_T(\sigma,d)\,|d|.$$
The C++ checkpoint uses the calls
$$1,2,4,6,1,8,10,2,4,1.$$
The cumulative hit counts become
$$L:\ 0,0,0,0,1,1,1,1,1,2,$$
$$R:\ 0,0,0,0,1,1,1,2,3,3.$$
So the final difference is
$$L-R=-1.$$
After the ten calls, the ordered memories are
$$M_L=(8,10,2,4,1),\qquad M_R=(4,6,8,10,1).$$
This example makes the rule difference concrete: Larry keeps refreshing hits, Robin does not.
For the default parameters \((10,5,50)\), the canonical state graph has only
$$439$$
states. The exact expectation is
$$\mathbb{E}(|L-R|)=1.768822942380093\ldots$$
The code also verifies two brute-force cross-checks on smaller instances:
$$\text{alphabet}=3,\ \text{capacity}=2,\ \text{turns}=7 \Rightarrow 0.224965706447188,$$
$$\text{alphabet}=4,\ \text{capacity}=2,\ \text{turns}=8 \Rightarrow 0.259277343750000.$$
These are compared against exhaustive enumeration of all sequences, so they strongly validate the Markov-DP formulation.
build_graph(...) performs a BFS from the empty state, canonicalizes every newly reached state, and stores weighted transitions \((\text{next state},\Delta,\text{weight})\). Then solve_exact(...) runs a probability DP over turns and score differences. The C++ version optionally parallelizes the transition sweep, and then checks that threaded and single-threaded answers agree.
If \(S\) is the number of canonical states, \(B\) the average number of outgoing transitions, and \(T\) the number of turns, then the DP costs about
$$O\!\bigl(T\cdot S\cdot B\cdot (2T+1)\bigr)$$
time and
$$O\!\bigl(S\cdot (2T+1)\bigr)$$
memory. For the actual problem, \(S=439\), so the exact computation is easily manageable and avoids any Monte Carlo error.
Larry und Robin sehen dieselbe zufällige Folge von Aufrufen aus einem Alphabet der Größe \(10\). Beide Speicher haben Kapazität \(5\), werden aber verschieden aktualisiert. Nach \(50\) Schritten ist der gesuchte exakte Wert
$$\mathbb{E}(|L-R|),$$
wobei \(L\) und \(R\) die gesamten Trefferzahlen von Larry bzw. Robin sind.
Ein Zustand ist das geordnete Paar der beiden Speicher
$$\sigma=(M_L,M_R), \qquad |M_L|,|M_R|\le 5.$$
Die Reihenfolge ist jeweils von alt nach neu.
Larry. Bei Treffer wird das aufgerufene Symbol an seine aktuelle Stelle entfernt und ans Ende verschoben. Bei Fehltreffer wird es angehängt; ist der Speicher voll, wird zuvor das älteste Element verworfen.
Robin. Bei Treffer steigt nur der Punktestand; die Reihenfolge ändert sich nicht. Bei Fehltreffer hängt auch Robin an und verwirft gegebenenfalls das älteste Element.
Der Punktezuwachs pro Aufruf ist
$$\Delta=(\text{Larry-Treffer})-(\text{Robin-Treffer})\in\{-1,0,+1\}.$$
Die konkreten Ziffern sind unwichtig. Für die Zukunft zählt nur, welche Gleichheitsbeziehungen existieren, also ob ein Symbol nur bei Larry, nur bei Robin oder bei beiden vorkommt und an welchen Positionen. Deshalb haben zwei Zustände, die sich nur durch eine Permutation der Labels unterscheiden, exakt dieselbe Übergangsstruktur.
Der Code kanonisiert einen Zustand, indem zuerst Larrys Speicher von links nach rechts und danach Robins Speicher durchlaufen wird; jedes erstmals gesehene Label erhält die nächste ID \(0,1,2,\dots\). Beispielsweise wird
$$M_L=(6,1,8,10,2),\qquad M_R=(2,4,6,8,10)$$
zu
$$M_L=(0,1,2,3,4),\qquad M_R=(4,5,0,2,3).$$
Alle rohen Zustände mit demselben Gleichheitsmuster fallen also auf denselben kanonischen Repräsentanten zusammen.
Enthält ein kanonischer Zustand die Menge \(U\) aller aktuell in mindestens einem Speicher vorhandenen Labels, dann zerfallen die Aufrufe in zwei Klassen:
Bekannte Labels. Jedes \(x\in U\) wird einzeln mit Gewicht \(1\) behandelt.
Unbekannte Labels. Jedes Label außerhalb von \(U\) verhält sich bis auf kanonisches Umbenennen identisch, weil es in keinem Speicher vorkommt und als frisches Symbol eintritt. Deshalb simuliert der Code nur ein repräsentatives unbekanntes Label und gibt diesem Übergang das Gewicht
$$10-|U|.$$
Führen mehrere Aufrufe nach der Kanonisierung zum selben Paar \((\sigma',\Delta)\), werden ihre Gewichte addiert. Für jeden Zustand summieren sich die ausgehenden Gewichte zu \(10\); das ist ein eigener Struktur-Checkpoint im C++-Code.
Sei \(P_t(\sigma,d)\) die Wahrscheinlichkeit, nach \(t\) Schritten im kanonischen Zustand \(\sigma\) mit Trefferdifferenz
$$d=L-R$$
zu sein. Anfangs hat nur der leere Zustand mit \(d=0\) Wahrscheinlichkeit \(1\). Hat eine Kante \(\sigma\to\sigma'\) den Differenzbeitrag \(\Delta\) und das Gewicht \(w\), dann ist ihre Wahrscheinlichkeit \(w/10\), also
$$P_{t+1}(\sigma',d+\Delta)=\sum_{\sigma,d} P_t(\sigma,d)\cdot \frac{w(\sigma\to\sigma',\Delta)}{10}.$$
Da sich die Differenz pro Schritt höchstens um \(1\) ändert, reicht nach \(t\) Runden das Band
$$-t \le d \le t,$$
weshalb der Code Felder der Breite \(2T+1\) verwendet. Am Ende gilt
$$\mathbb{E}(|L-R|)=\sum_{\sigma,d}P_T(\sigma,d)\,|d|.$$
Der C++-Checkpoint benutzt die Aufruffolge
$$1,2,4,6,1,8,10,2,4,1.$$
Die kumulativen Trefferzahlen werden zu
$$L:\ 0,0,0,0,1,1,1,1,1,2,$$
$$R:\ 0,0,0,0,1,1,1,2,3,3.$$
Damit ist die Enddifferenz
$$L-R=-1.$$
Nach zehn Aufrufen lauten die geordneten Speicher
$$M_L=(8,10,2,4,1),\qquad M_R=(4,6,8,10,1).$$
Genau daran sieht man den Regelunterschied: Larry aktualisiert Treffer, Robin nicht.
Für die Standardparameter \((10,5,50)\) besitzt der kanonische Zustandsgraph nur
$$439$$
Zustände. Der exakte Erwartungswert ist
$$\mathbb{E}(|L-R|)=1.768822942380093\ldots$$
Außerdem verifiziert der Code zwei Brute-Force-Vergleiche auf kleineren Instanzen:
$$\text{Alphabet}=3,\ \text{Kapazität}=2,\ \text{Runden}=7 \Rightarrow 0.224965706447188,$$
$$\text{Alphabet}=4,\ \text{Kapazität}=2,\ \text{Runden}=8 \Rightarrow 0.259277343750000.$$
Diese Werte werden mit vollständiger Aufzählung aller Folgen verglichen und bestätigen die Markov-DP-Modellierung sehr stark.
build_graph(...) führt eine BFS vom leeren Zustand aus, kanonisiert jeden neu erreichten Zustand und speichert gewichtete Übergänge \((\text{Folgezustand},\Delta,\text{Gewicht})\). Danach führt solve_exact(...) eine Wahrscheinlichkeits-DP über Zeit und Differenz aus. Die C++-Version kann die Übergangsschleife optional parallelisieren und prüft zusätzlich, dass Einzel- und Mehrthread-Ausgabe übereinstimmen.
Mit \(S\) kanonischen Zuständen, \(B\) mittleren Ausgangsübergängen und \(T\) Runden kostet die DP ungefähr
$$O\!\bigl(T\cdot S\cdot B\cdot (2T+1)\bigr)$$
Zeit und
$$O\!\bigl(S\cdot (2T+1)\bigr)$$
Speicher. Für die eigentliche Aufgabe ist \(S=439\), also ist die exakte Rechnung bequem machbar und benötigt keine Monte-Carlo-Schätzung.
Larry ve Robin, \(10\) elemanlı bir alfabe üzerinden gelen aynı rastgele çağrı dizisini izler. İkisinin de belleği \(5\) kapasitelidir ama güncelleme kuralları farklıdır. \(50\) tur sonunda istenen tam değer
$$\mathbb{E}(|L-R|),$$
burada \(L\) ve \(R\), Larry ile Robin'in toplam hit sayılarıdır.
Bir durum, iki belleğin sıralı çifti olarak tutulur:
$$\sigma=(M_L,M_R), \qquad |M_L|,|M_R|\le 5.$$
Sıra her iki bellek için de eskiden yeniye doğrudur.
Larry. Hit olursa çağrılan etiket mevcut yerinden çıkarılır ve sona taşınır. Miss olursa etiket sona eklenir; bellek doluysa önce en eski eleman atılır.
Robin. Hit olursa sadece puan artar; sıralama değişmez. Miss olursa o da sona ekler ve gerekirse en eskiyi atar.
Bir çağrının fark katkısı
$$\Delta=(\text{Larry hit})-(\text{Robin hit})\in\{-1,0,+1\}$$
şeklindedir.
Gerçek rakam isimleri önemsizdir. Geleceği belirleyen şey yalnızca eşitlik deseni, yani hangi etiketin yalnız Larry'de, yalnız Robin'de ya da ikisinde birden bulunduğu ve iki bellekteki göreli sıralamadır. Dolayısıyla sadece etiket isimleri permütasyonuyla farklılaşan iki durumun geçiş yapısı aynıdır.
Kod bir durumu kanonikleştirirken önce Larry'nin belleğini soldan sağa, sonra Robin'inkini tarar ve ilk kez görülen etiketlere sırasıyla \(0,1,2,\dots\) verir. Örneğin
$$M_L=(6,1,8,10,2),\qquad M_R=(2,4,6,8,10)$$
durumu
$$M_L=(0,1,2,3,4),\qquad M_R=(4,5,0,2,3)$$
şeklinde kodlanır. Aynı eşitlik desenine sahip tüm ham durumlar aynı kanonik temsilciye çöker. Bu yüzden durum grafı küçük kalır.
Bir kanonik durumda en az bir bellekte bulunan etiketler kümesine \(U\) diyelim. O zaman çağrılar iki sınıfa ayrılır:
Bilinen etiketler. Her \(x\in U\) tek tek, ağırlık \(1\) ile işlenir.
Görülmemiş etiketler. \(U\) dışında kalan her etiket, kanonik yeniden adlandırmadan sonra aynı davranışı gösterir; çünkü ikisinin de belleğinde yoktur ve sisteme "yeni bir sembol" olarak girer. Bu yüzden kod yalnızca tek bir temsilci görülmemiş etiketi simüle eder ve bu geçişe
$$10-|U|$$
ağırlığını verir.
Kanonikleştirmeden sonra birden çok çağrı aynı \((\sigma',\Delta)\) sonucuna düşebilir; bu durumda ağırlıklar toplanır. Her durum için çıkış ağırlıkları toplamı \(10\)'dur. C++ kodundaki grafik-yapısı checkpoint'lerinden biri tam olarak budur.
\(P_t(\sigma,d)\), \(t\) tur sonunda kanonik durum \(\sigma\)'da ve
$$d=L-R$$
farkında olma olasılığı olsun. Başlangıçta yalnızca boş durum ile \(d=0\) olasılığı \(1\)'dir. \(\sigma\to\sigma'\) kenarının fark katkısı \(\Delta\), ağırlığı \(w\) ise olasılığı \(w/10\)'dur; dolayısıyla
$$P_{t+1}(\sigma',d+\Delta)=\sum_{\sigma,d} P_t(\sigma,d)\cdot \frac{w(\sigma\to\sigma',\Delta)}{10}.$$
Her tur fark en fazla \(1\) değiştiği için \(t\) tur sonunda sadece
$$-t \le d \le t$$
bandı gerekir. Kodun genişliği \(2T+1\) olan diziler kullanmasının sebebi budur. Sonunda beklenen değer
$$\mathbb{E}(|L-R|)=\sum_{\sigma,d}P_T(\sigma,d)\,|d|$$
olarak hesaplanır.
C++ checkpoint'i şu çağrı dizisini kullanır:
$$1,2,4,6,1,8,10,2,4,1.$$
Kümülatif hit sayıları
$$L:\ 0,0,0,0,1,1,1,1,1,2,$$
$$R:\ 0,0,0,0,1,1,1,2,3,3$$
olur. Bu yüzden son fark
$$L-R=-1$$
çıkar. On çağrı sonunda sıralı bellekler
$$M_L=(8,10,2,4,1),\qquad M_R=(4,6,8,10,1)$$
haline gelir. Örnek, Larry'nin hit'lerde yenileme yaptığı, Robin'in ise yapmadığı farkı somut biçimde gösterir.
Varsayılan parametreler \((10,5,50)\) için kanonik durum grafında yalnızca
$$439$$
durum vardır. Tam beklenti değeri ise
$$\mathbb{E}(|L-R|)=1.768822942380093\ldots$$
şeklindedir. Kod ayrıca daha küçük iki örneği brute-force ile çapraz doğrular:
$$\text{alphabet}=3,\ \text{capacity}=2,\ \text{turns}=7 \Rightarrow 0.224965706447188,$$
$$\text{alphabet}=4,\ \text{capacity}=2,\ \text{turns}=8 \Rightarrow 0.259277343750000.$$
Bu değerler tüm olası çağrı dizileri açıkça sayılarak elde edilen sonuçlarla karşılaştırılır; bu da Markov-DP kurulumunun doğru olduğuna güçlü bir kanıttır.
build_graph(...), boş durumdan BFS ile başlayıp erişilen her yeni durumu kanonikleştirir ve ağırlıklı geçişleri \((\text{next state},\Delta,\text{weight})\) biçiminde saklar. Sonra solve_exact(...), tur sayısı ve fark ekseni üzerinde bir olasılık DP'si yürütür. C++ sürümü geçiş taramasını isteğe bağlı çok iş parçacıklı yapabilir ve tek-thread ile aynı cevabı verdiğini ayrıca kontrol eder.
Kanonik durum sayısı \(S\), ortalama çıkış sayısı \(B\), tur sayısı \(T\) ise DP maliyeti yaklaşık
$$O\!\bigl(T\cdot S\cdot B\cdot (2T+1)\bigr)$$
zamandır; bellek ihtiyacı da
$$O\!\bigl(S\cdot (2T+1)\bigr)$$
olur. Gerçek problemde \(S=439\) olduğu için tam hesap oldukça rahattır ve Monte Carlo hatası içermez.
Larry y Robin observan la misma secuencia aleatoria de llamadas de un alfabeto de tamaño \(10\). Ambas memorias tienen capacidad \(5\), pero se actualizan de forma distinta. Tras \(50\) turnos, buscamos el valor exacto de
$$\mathbb{E}(|L-R|),$$
donde \(L\) y \(R\) son los números totales de aciertos de Larry y Robin.
Un estado es el par ordenado de memorias
$$\sigma=(M_L,M_R), \qquad |M_L|,|M_R|\le 5.$$
El orden va de más antiguo a más reciente.
Larry. Si hay acierto, elimina la etiqueta de su posición actual y la mueve al final. Si hay fallo, la añade al final; si la memoria está llena, expulsa antes la más antigua.
Robin. Si hay acierto, el marcador sube pero el orden de memoria no cambia. Si hay fallo, también añade al final y expulsa la más antigua si hace falta.
La contribución de una llamada al diferencial es
$$\Delta=(\text{hit de Larry})-(\text{hit de Robin})\in\{-1,0,+1\}.$$
Los nombres concretos de los dígitos no importan. Lo que afecta al futuro es sólo el patrón de igualdades: qué símbolo aparece sólo en Larry, sólo en Robin o en ambos, y en qué orden relativo aparece en cada memoria. Por ello, dos estados que sólo difieren por una permutación de etiquetas tienen exactamente la misma estructura de transición.
El código canoniza recorriendo primero la memoria de Larry de izquierda a derecha y luego la de Robin, asignando a cada etiqueta nueva los IDs \(0,1,2,\dots\). Por ejemplo,
$$M_L=(6,1,8,10,2),\qquad M_R=(2,4,6,8,10)$$
se transforma en
$$M_L=(0,1,2,3,4),\qquad M_R=(4,5,0,2,3).$$
Cualquier estado bruto con el mismo patrón de igualdad colapsa al mismo representante canónico.
Sea \(U\) el conjunto de etiquetas presentes en al menos una memoria. Entonces las llamadas se dividen en dos clases:
Etiquetas conocidas. Cada \(x\in U\) se procesa individualmente con peso \(1\).
Etiquetas no vistas. Cualquier etiqueta fuera de \(U\) se comporta igual tras canonizar, porque no aparece en ninguna memoria y entra como símbolo fresco. Por eso el código simula una sola etiqueta representativa y le asigna el peso
$$10-|U|.$$
Si varias llamadas terminan en el mismo par \((\sigma',\Delta)\), sus pesos se suman. Para cada estado, la suma de pesos salientes es \(10\); eso mismo se comprueba en el checkpoint estructural del código C++.
Sea \(P_t(\sigma,d)\) la probabilidad de estar tras \(t\) turnos en el estado canónico \(\sigma\) con diferencia
$$d=L-R.$$
Al inicio sólo el estado vacío con \(d=0\) tiene probabilidad \(1\). Si una arista \(\sigma\to\sigma'\) tiene cambio \(\Delta\) y peso \(w\), su probabilidad es \(w/10\), de modo que
$$P_{t+1}(\sigma',d+\Delta)=\sum_{\sigma,d} P_t(\sigma,d)\cdot \frac{w(\sigma\to\sigma',\Delta)}{10}.$$
Como en cada paso la diferencia cambia a lo sumo en \(1\), tras \(t\) turnos basta con la banda
$$-t \le d \le t,$$
y por eso el código usa arrays de anchura \(2T+1\). Al final, el valor pedido es
$$\mathbb{E}(|L-R|)=\sum_{\sigma,d}P_T(\sigma,d)\,|d|.$$
El checkpoint de C++ usa la secuencia
$$1,2,4,6,1,8,10,2,4,1.$$
Las puntuaciones acumuladas quedan
$$L:\ 0,0,0,0,1,1,1,1,1,2,$$
$$R:\ 0,0,0,0,1,1,1,2,3,3.$$
Así, la diferencia final es
$$L-R=-1.$$
Tras las diez llamadas, las memorias ordenadas son
$$M_L=(8,10,2,4,1),\qquad M_R=(4,6,8,10,1).$$
El ejemplo muestra con claridad la diferencia entre “refrescar en hit” y “no refrescar”.
Para los parámetros por defecto \((10,5,50)\), el grafo canónico tiene sólo
$$439$$
estados. La esperanza exacta es
$$\mathbb{E}(|L-R|)=1.768822942380093\ldots$$
Además, el código verifica dos casos pequeños contra fuerza bruta:
$$\text{alphabet}=3,\ \text{capacity}=2,\ \text{turns}=7 \Rightarrow 0.224965706447188,$$
$$\text{alphabet}=4,\ \text{capacity}=2,\ \text{turns}=8 \Rightarrow 0.259277343750000.$$
Ambos se comparan con enumeración exhaustiva de todas las secuencias posibles, así que validan fuertemente la formulación de Markov + DP.
build_graph(...) hace un BFS desde el estado vacío, canoniza cada estado nuevo y guarda las transiciones ponderadas \((\text{next state},\Delta,\text{weight})\). Después solve_exact(...) ejecuta una DP de probabilidades sobre tiempo y diferencia. La versión C++ puede paralelizar el barrido de transiciones y además comprueba que el resultado coincida con la ejecución monohilo.
Si \(S\) es el número de estados canónicos, \(B\) el número medio de transiciones salientes y \(T\) el número de turnos, el coste es aproximadamente
$$O\!\bigl(T\cdot S\cdot B\cdot (2T+1)\bigr)$$
en tiempo y
$$O\!\bigl(S\cdot (2T+1)\bigr)$$
en memoria. En el problema real, \(S=439\), por lo que el cálculo exacto es perfectamente manejable y no sufre error de Monte Carlo.
Larry 与 Robin 看到同一条来自大小为 \(10\) 的字母表的随机调用序列。两人的记忆容量都是 \(5\)，但更新规则不同。经过 \(50\) 轮后，我们要求精确值
$$\mathbb{E}(|L-R|),$$
其中 \(L\) 与 \(R\) 分别是 Larry 和 Robin 的总命中次数。
一个状态就是两份有序记忆的二元组
$$\sigma=(M_L,M_R), \qquad |M_L|,|M_R|\le 5.$$
两份记忆都按“最旧到最新”的顺序存放。
Larry. 命中时，把该标签从当前位置删掉并移到末尾；未命中时，把它追加到末尾，若已满则先淘汰最旧项。
Robin. 命中时只加分，不改变记忆顺序；未命中时同样追加，并在必要时淘汰最旧项。
单次调用带来的分差增量为
$$\Delta=(\text{Larry hit})-(\text{Robin hit})\in\{-1,0,+1\}.$$
真实数字名称本身并不重要。影响未来的只有“相等关系模式”，也就是某个标签只在 Larry 里、只在 Robin 里，还是两边都有，以及它们在两份记忆中的相对顺序。因此，两个只差一个标签置换的状态，其未来转移结构完全相同。
代码的规范化方法是：先从左到右扫描 Larry 的记忆，再扫描 Robin 的记忆，把第一次出现的标签依次重命名为 \(0,1,2,\dots\)。例如
$$M_L=(6,1,8,10,2),\qquad M_R=(2,4,6,8,10)$$
会变成
$$M_L=(0,1,2,3,4),\qquad M_R=(4,5,0,2,3).$$
任何具有相同相等模式的原始状态都会压缩到这个同一个 canonical 代表上。
设 \(U\) 是当前至少出现在一份记忆中的标签集合。调用可分成两类：
已知标签。 对每个 \(x\in U\)，单独模拟一次，权重为 \(1\)。
未见标签。 所有不在 \(U\) 中的标签在 canonical 化之后行为完全相同，因为它们都同时不在两份记忆里，只是作为“一个新符号”进入系统。因此代码只模拟一个代表性的新标签，并赋予权重
$$10-|U|.$$
如果多个调用在规范化之后落到同一个 \((\sigma',\Delta)\)，它们的权重会合并。对每个状态，所有出边权重之和都等于字母表大小 \(10\)。这也是 C++ 代码检查的图结构性质之一。
令 \(P_t(\sigma,d)\) 表示经过 \(t\) 轮后，位于 canonical 状态 \(\sigma\) 且分差
$$d=L-R$$
的概率。初始时只有空状态且 \(d=0\) 的概率为 \(1\)。若一条边 \(\sigma\to\sigma'\) 的分差变化是 \(\Delta\)，权重是 \(w\)，那么它的概率就是 \(w/10\)，因此
$$P_{t+1}(\sigma',d+\Delta)=\sum_{\sigma,d} P_t(\sigma,d)\cdot \frac{w(\sigma\to\sigma',\Delta)}{10}.$$
由于每一步分差最多变化 \(1\)，在第 \(t\) 轮之后只需要范围
$$-t \le d \le t,$$
这就是代码使用宽度 \(2T+1\) 数组的原因。最后要求的期望就是
$$\mathbb{E}(|L-R|)=\sum_{\sigma,d}P_T(\sigma,d)\,|d|.$$
C++ checkpoint 使用的调用序列是
$$1,2,4,6,1,8,10,2,4,1.$$
累计命中次数变为
$$L:\ 0,0,0,0,1,1,1,1,1,2,$$
$$R:\ 0,0,0,0,1,1,1,2,3,3.$$
因此最终分差为
$$L-R=-1.$$
十次调用之后，两份有序记忆分别是
$$M_L=(8,10,2,4,1),\qquad M_R=(4,6,8,10,1).$$
这个例子非常直观地展示了“命中后刷新”和“命中后不刷新”的区别。
在默认参数 \((10,5,50)\) 下，canonical 状态图只有
$$439$$
个状态。精确期望值为
$$\mathbb{E}(|L-R|)=1.768822942380093\ldots$$
代码还对两个小实例做了 brute-force 交叉验证：
$$\text{alphabet}=3,\ \text{capacity}=2,\ \text{turns}=7 \Rightarrow 0.224965706447188,$$
$$\text{alphabet}=4,\ \text{capacity}=2,\ \text{turns}=8 \Rightarrow 0.259277343750000.$$
这两个值都与所有调用序列的完全枚举结果对比，因此对 Markov + DP 建模是很强的验证。
build_graph(...) 从空状态出发做 BFS，对每个新状态做 canonical 化，并存储带权转移 \((\text{next state},\Delta,\text{weight})\)。随后 solve_exact(...) 在“轮数 + 分差”二维上做概率 DP。C++ 版本还支持可选多线程扫描转移，并检查多线程结果与单线程一致。
若 canonical 状态数为 \(S\)，平均出边数为 \(B\)，轮数为 \(T\)，则 DP 大约需要
$$O\!\bigl(T\cdot S\cdot B\cdot (2T+1)\bigr)$$
时间，以及
$$O\!\bigl(S\cdot (2T+1)\bigr)$$
空间。对本题来说 \(S=439\)，所以精确计算完全可行，而且没有 Monte Carlo 误差。
Larry и Robin видят одну и ту же случайную последовательность вызовов из алфавита размера \(10\). Ёмкость обеих памятей равна \(5\), но правила обновления различаются. После \(50\) ходов нужно найти точное значение
$$\mathbb{E}(|L-R|),$$
где \(L\) и \(R\) — общие числа попаданий Larry и Robin.
Состояние — это упорядоченная пара памятей
$$\sigma=(M_L,M_R), \qquad |M_L|,|M_R|\le 5.$$
Порядок в каждой памяти идёт от самого старого к самому новому.
Larry. При попадании вызванная метка удаляется со своего места и переносится в конец. При промахе метка дописывается в конец, а если память заполнена, сначала выбрасывается самый старый элемент.
Robin. При попадании увеличивается только счёт, а порядок памяти не меняется. При промахе Robin тоже дописывает символ в конец и при необходимости выталкивает самый старый.
Вклад одного вызова в разность равен
$$\Delta=(\text{попадание Larry})-(\text{попадание Robin})\in\{-1,0,+1\}.$$
Конкретные названия цифр не важны. На дальнейшую эволюцию влияет только pattern равенств: какой символ есть только у Larry, только у Robin или у обоих, а также их относительный порядок в массивах памяти. Поэтому два состояния, отличающиеся лишь перестановкой меток, имеют полностью одинаковую структуру переходов.
Код канонизирует состояние так: сначала просматривает память Larry слева направо, затем память Robin и присваивает новым меткам номера \(0,1,2,\dots\). Например,
$$M_L=(6,1,8,10,2),\qquad M_R=(2,4,6,8,10)$$
переходит в
$$M_L=(0,1,2,3,4),\qquad M_R=(4,5,0,2,3).$$
Любое исходное состояние с тем же pattern равенств схлопывается в тот же канонический представитель.
Пусть \(U\) — множество меток, присутствующих хотя бы в одной памяти. Тогда вызовы разбиваются на два класса:
Известные метки. Каждая \(x\in U\) рассматривается отдельно с весом \(1\).
Невиданные метки. Любая метка вне \(U\) после канонизации ведёт себя одинаково, потому что отсутствует в обеих памятях и входит как один свежий символ. Поэтому код моделирует только одну representative unseen метку и даёт этому переходу вес
$$10-|U|.$$
Если после канонизации несколько вызовов приводят к одной и той же паре \((\sigma',\Delta)\), их веса складываются. Для каждого состояния сумма исходящих весов равна размеру алфавита \(10\); это отдельно проверяется в C++-коде.
Пусть \(P_t(\sigma,d)\) — вероятность того, что после \(t\) шагов мы находимся в каноническом состоянии \(\sigma\) с разностью
$$d=L-R.$$
Изначально только пустое состояние с \(d=0\) имеет вероятность \(1\). Если ребро \(\sigma\to\sigma'\) имеет изменение \(\Delta\) и вес \(w\), то его вероятность равна \(w/10\), следовательно
$$P_{t+1}(\sigma',d+\Delta)=\sum_{\sigma,d} P_t(\sigma,d)\cdot \frac{w(\sigma\to\sigma',\Delta)}{10}.$$
Поскольку за один ход разность меняется не более чем на \(1\), после \(t\) ходов нужна только полоса
$$-t \le d \le t,$$
поэтому код использует массивы ширины \(2T+1\). В конце требуется
$$\mathbb{E}(|L-R|)=\sum_{\sigma,d}P_T(\sigma,d)\,|d|.$$
В C++-checkpoint берётся последовательность
$$1,2,4,6,1,8,10,2,4,1.$$
Накопленные попадания становятся равны
$$L:\ 0,0,0,0,1,1,1,1,1,2,$$
$$R:\ 0,0,0,0,1,1,1,2,3,3.$$
Следовательно, конечная разность равна
$$L-R=-1.$$
После десяти вызовов упорядоченные памяти имеют вид
$$M_L=(8,10,2,4,1),\qquad M_R=(4,6,8,10,1).$$
Этот пример наглядно показывает разницу между обновлением при попадании и отсутствием такого обновления.
Для стандартных параметров \((10,5,50)\) канонический граф состояний имеет всего
$$439$$
состояний. Точное математическое ожидание равно
$$\mathbb{E}(|L-R|)=1.768822942380093\ldots$$
Кроме того, код проверяет два малых случая через brute force:
$$\text{alphabet}=3,\ \text{capacity}=2,\ \text{turns}=7 \Rightarrow 0.224965706447188,$$
$$\text{alphabet}=4,\ \text{capacity}=2,\ \text{turns}=8 \Rightarrow 0.259277343750000.$$
Они сравниваются с полным перебором всех последовательностей вызовов, что очень убедительно подтверждает корректность модели Маркова и DP.
build_graph(...) выполняет BFS из пустого состояния, канонизирует каждое новое состояние и сохраняет взвешенные переходы \((\text{next state},\Delta,\text{weight})\). Затем solve_exact(...) запускает вероятностное DP по шагам и разности очков. Версия на C++ может по желанию распараллеливать проход по переходам и дополнительно проверяет совпадение многопоточного и однопоточного результата.
Если \(S\) — число канонических состояний, \(B\) — среднее число исходящих переходов, а \(T\) — число ходов, то трудоёмкость составляет примерно
$$O\!\bigl(T\cdot S\cdot B\cdot (2T+1)\bigr)$$
по времени и
$$O\!\bigl(S\cdot (2T+1)\bigr)$$
по памяти. В реальной задаче \(S=439\), так что точный расчёт легко выполним и не содержит ошибки Монте-Карло.
يراقب Larry وRobin نفس السلسلة العشوائية من النداءات القادمة من أبجدية حجمها \(10\). سعة ذاكرة كل منهما \(5\)، لكن قاعدة التحديث مختلفة. بعد \(50\) خطوة نريد القيمة الدقيقة
$$\mathbb{E}(|L-R|),$$
حيث \(L\) و\(R\) هما مجموع عدد الإصابات لكل من Larry وRobin.
الحالة هي الزوج المرتب للذاكرتين
$$\sigma=(M_L,M_R), \qquad |M_L|,|M_R|\le 5.$$
والترتيب في كل ذاكرة من الأقدم إلى الأحدث.
Larry. عند الإصابة، يُزال الرمز من موضعه الحالي ويُنقل إلى آخر الذاكرة. وعند الفشل، يُضاف في النهاية، وإذا كانت الذاكرة ممتلئة يُطرَد أقدم عنصر أولًا.
Robin. عند الإصابة يزداد الرصيد لكن ترتيب الذاكرة لا يتغير. وعند الفشل، يضيف أيضًا في النهاية ويطرد الأقدم إذا لزم الأمر.
مساهمة نداء واحد في فرق النقاط هي
$$\Delta=(\text{إصابة Larry})-(\text{إصابة Robin})\in\{-1,0,+1\}.$$
أسماء الأرقام نفسها لا تهم. ما يحدد المستقبل هو نمط التساوي فقط: هل الرمز موجود عند Larry فقط، أو عند Robin فقط، أو عند الاثنين، وما ترتيبه النسبي داخل كل ذاكرة. لذلك فإن حالتين تختلفان فقط بتبديل أسماء الرموز تملكان البنية نفسها تمامًا من حيث الانتقالات.
يقوم الكود بعمل canonicalization عبر المرور أولًا على ذاكرة Larry من اليسار إلى اليمين ثم على ذاكرة Robin، وإعطاء أول رمز جديد المعرف \(0\)، والثاني \(1\)، وهكذا. مثلًا
$$M_L=(6,1,8,10,2),\qquad M_R=(2,4,6,8,10)$$
تتحول إلى
$$M_L=(0,1,2,3,4),\qquad M_R=(4,5,0,2,3).$$
أي حالة خام لها نفس نمط المساواة ستنهار إلى هذا الممثل المعياري نفسه، ولهذا يبقى مخطط الحالات صغيرًا.
لتكن \(U\) مجموعة الرموز الموجودة حاليًا في واحدة على الأقل من الذاكرتين. عندئذ تنقسم النداءات إلى فئتين:
الرموز المعروفة. كل \(x\in U\) يعالج منفردًا بوزن \(1\).
الرموز غير المرئية. كل رمز خارج \(U\) يتصرف بالطريقة نفسها بعد canonicalization، لأنه غير موجود في الذاكرتين ويدخل بوصفه رمزًا جديدًا. لذلك يحاكي الكود رمزًا ممثلًا واحدًا فقط ويعطي هذا الانتقال الوزن
$$10-|U|.$$
إذا أدت عدة نداءات بعد canonicalization إلى الزوج نفسه \((\sigma',\Delta)\)، فإن الأوزان تُجمع. ولكل حالة، مجموع أوزان الانتقالات الخارجة يساوي \(10\). وهذا أحد اختبارات البنية في كود ++C.
لتكن \(P_t(\sigma,d)\) احتمال أن نكون بعد \(t\) خطوة في الحالة المعيارية \(\sigma\) ومع فرق النقاط
$$d=L-R.$$
في البداية، الحالة الفارغة مع \(d=0\) وحدها احتمالها \(1\). إذا كانت الحافة \(\sigma\to\sigma'\) تملك تغيرًا \(\Delta\) ووزنًا \(w\)، فإن احتمالها هو \(w/10\)، ولذلك
$$P_{t+1}(\sigma',d+\Delta)=\sum_{\sigma,d} P_t(\sigma,d)\cdot \frac{w(\sigma\to\sigma',\Delta)}{10}.$$
ولأن الفرق يتغير في كل خطوة بمقدار لا يتجاوز \(1\)، فنحن بعد \(t\) خطوة لا نحتاج إلا إلى المجال
$$-t \le d \le t,$$
ولهذا يستخدم الكود مصفوفات بعرض \(2T+1\). وفي النهاية نحسب
$$\mathbb{E}(|L-R|)=\sum_{\sigma,d}P_T(\sigma,d)\,|d|.$$
يستخدم اختبار ++C تسلسل النداءات
$$1,2,4,6,1,8,10,2,4,1.$$
فتصبح أعداد الإصابات التراكمية
$$L:\ 0,0,0,0,1,1,1,1,1,2,$$
$$R:\ 0,0,0,0,1,1,1,2,3,3.$$
ومن ثم يكون الفرق النهائي
$$L-R=-1.$$
وبعد عشرة نداءات تصبح الذاكرتان المرتبتان
$$M_L=(8,10,2,4,1),\qquad M_R=(4,6,8,10,1).$$
هذا المثال يوضح عمليًا الفرق بين “تحديث الذاكرة عند الإصابة” و“عدم التحديث عند الإصابة”.
للمعاملات الافتراضية \((10,5,50)\)، لا يحتوي الرسم البياني للحالات المعيارية إلا على
$$439$$
حالة فقط. والقيمة الدقيقة للتوقع هي
$$\mathbb{E}(|L-R|)=1.768822942380093\ldots$$
كما يتحقق الكود من حالتين صغيرتين بالمقارنة مع brute force:
$$\text{alphabet}=3,\ \text{capacity}=2,\ \text{turns}=7 \Rightarrow 0.224965706447188,$$
$$\text{alphabet}=4,\ \text{capacity}=2,\ \text{turns}=8 \Rightarrow 0.259277343750000.$$
تُقارن هاتان القيمتان مع تعداد كامل لكل السلاسل الممكنة، ولذلك فهما تحققان بقوة صحة نموذج ماركوف مع البرمجة الديناميكية.
تقوم الدالة build_graph(...) بعمل BFS بدءًا من الحالة الفارغة، وتحوّل كل حالة جديدة إلى صورتها المعيارية، ثم تخزن الانتقالات الموزونة على الصورة \((\text{next state},\Delta,\text{weight})\). بعد ذلك تشغل solve_exact(...) برمجة ديناميكية احتمالية على عدد الخطوات وفرق النقاط. نسخة ++C تستطيع توزيع المرور على الانتقالات على أكثر من خيط، وتتحقق أيضًا من أن الناتج يطابق التنفيذ أحادي الخيط.
إذا كان \(S\) عدد الحالات المعيارية، و\(B\) متوسط عدد الانتقالات الخارجة، و\(T\) عدد الخطوات، فإن كلفة البرمجة الديناميكية تقارب
$$O\!\bigl(T\cdot S\cdot B\cdot (2T+1)\bigr)$$
زمنًا، و
$$O\!\bigl(S\cdot (2T+1)\bigr)$$
ذاكرةً. وفي المسألة الحقيقية \(S=439\)، ولذلك يكون الحساب الدقيق سهلًا عمليًا ولا يتضمن أي خطأ من نوع Monte Carlo.