For each cycle length \(m\), two walkers move independently on an \(m\)-cycle. In every round each walker chooses one of three actions with equal probability: one step clockwise, no move, or one step counterclockwise. If the chase lasts \(T\) rounds before the walkers meet, the payment for that game is \(T^2\). Let \(E_m\) be the expected payment when the starting positions are chosen uniformly at random, and define
$$G(n)=\sum_{m=2}^{n} E_m.$$
The task is to evaluate this quantity up to \(n=500\). The implementations do not simulate random games. Instead, they solve the exact expectation equations for the relative-separation walk on the cycle.
The key simplification is that absolute positions do not matter. Only the relative separation on the cycle matters, so the original two-walker process becomes a single Markov chain on \(\mathbb{Z}_m\).
Let \(D_t\in\mathbb{Z}_m\) be the directed separation after \(t\) rounds. The chase ends exactly when
$$D_t=0.$$
Each walker contributes an increment from \(\{-1,0,+1\}\) with probability \(1/3\), so the relative increment \(X_t=D_{t+1}-D_t\) has distribution
$$\mathbb{P}(X_t=0)=\frac13,\qquad \mathbb{P}(X_t=\pm1)=\frac29,\qquad \mathbb{P}(X_t=\pm2)=\frac19.$$
Therefore the transition operator acting on a function \(f:\mathbb{Z}_m\to\mathbb{R}\) is
$$ (Pf)(d)=\frac13 f(d)+\frac29\bigl(f(d+1)+f(d-1)\bigr)+\frac19\bigl(f(d+2)+f(d-2)\bigr), $$
where all indices are understood modulo \(m\).
Because the operator is circulant, the discrete Fourier modes
$$u_k(d)=e^{2\pi i k d/m},\qquad k=0,1,\dots,m-1,$$
are eigenvectors of \(P\). Writing
$$\theta_k=\frac{2\pi k}{m},$$
one gets
$$ \lambda_k=\frac13+\frac29\left(e^{i\theta_k}+e^{-i\theta_k}\right)+\frac19\left(e^{2i\theta_k}+e^{-2i\theta_k}\right) =\frac13+\frac49\cos\theta_k+\frac29\cos(2\theta_k). $$
These eigenvalues are exactly the denominators used by the implementation. The mode \(k=0\) has \(\lambda_0=1\), so constants lie in the kernel of \(I-P\); that is why every spectral solve must be written with zero total source.
Let \(T_d\) be the number of rounds until the first meeting when the initial separation is \(d\), and define
$$a_d=\mathbb{E}[T_d],\qquad a_0=0.$$
For every nonzero separation, one round passes and the process restarts from the next state, so
$$a_d=1+(Pa)_d\qquad (d\ne0).$$
To make the equation compatible with Fourier inversion on the whole cycle, rewrite it as the zero-sum Poisson equation
$$ (I-P)a=\mathbf{1}-m e_0, $$
where \(e_0\) is \(1\) at separation \(0\) and \(0\) elsewhere. After removing the zero mode and taking the real part, the first moment becomes
$$ a_d=\sum_{k=1}^{m-1}\frac{1-\cos\left(2\pi k d/m\right)}{1-\lambda_k}. $$
This is the first large spectral sum carried out by the implementations.
Now define the second moment
$$b_d=\mathbb{E}[T_d^2],\qquad b_0=0.$$
Using \(T_d=1+T_{D_1}\) after one round, we get for \(d\ne0\)
$$ b_d=1+2(Pa)_d+(Pb)_d. $$
Since \(a_d=1+(Pa)_d\), this simplifies to
$$ (I-P)b=2a-1 $$
away from the absorbing state. Again we need a zero-sum source, so define
$$ c_d=2a_d-1\quad(d\ne0),\qquad c_0=-\sum_{d=1}^{m-1} c_d. $$
Let \(z\) be the unique zero-mean solution of
$$ (I-P)z=c,\qquad \sum_{d=0}^{m-1} z_d=0. $$
Then \(b_d=z_d-z_0\), which enforces \(b_0=0\). If
$$ \widehat{c}_k=\sum_{d=0}^{m-1} c_d\,e^{-2\pi i k d/m}, $$
then the average payment for a fixed cycle size is
$$ E_m=\frac1m\sum_{d=0}^{m-1} b_d =-z_0 =-\frac1m\sum_{k=1}^{m-1}\frac{\widehat{c}_k}{1-\lambda_k}. $$
That is the second spectral solve implemented in all three languages.
Once \(E_m\) is available for one cycle length, the global function is just
$$G(n)=\sum_{m=2}^{n} E_m.$$
The implementations evaluate this directly for \(m=2,3,\dots,500\) and accumulate the running total.
For \(m=2\), there is only one nontrivial Fourier mode, \(k=1\), with
$$ \lambda_1=\frac13+\frac49\cos\pi+\frac29\cos(2\pi)=\frac19, \qquad 1-\lambda_1=\frac89. $$
The first moment from separation \(1\) is therefore
$$ a_1=\frac{1-\cos\pi}{8/9}=\frac{2}{8/9}=\frac94. $$
Next,
$$ c_1=2a_1-1=\frac72, \qquad c_0=-\frac72, $$
so the nonzero Fourier coefficient is
$$ \widehat{c}_1=c_0-c_1=-7. $$
Hence
$$ E_2=-\frac12\cdot\frac{-7}{8/9}=\frac{63}{16}=3.9375. $$
This is the average of \(T^2\) over the two possible starting separations \(0\) and \(1\). The separation \(0\) contributes \(0\), so the conditional second moment from the nontrivial start is twice as large.
The C++, Python, and Java implementations all follow the same numerical plan. For each cycle length \(m\), they first compute the spectral factors \(1-\lambda_k\) for all nonzero modes. Then they evaluate the first-moment formula by fixing one mode at a time and generating the powers of \(e^{2\pi i k/m}\) incrementally across all separations, which avoids a fresh trigonometric call inside the inner loop.
After that, the implementation builds the balanced source for the second-moment equation, performs a direct discrete Fourier transform of that source, divides each nonzero mode by the same spectral factor, and reads off the average payment from the zero-coordinate of the zero-mean solution. The imaginary parts cancel by conjugate symmetry, so only the real part is kept numerically. Finally, the values for \(m=2\) through \(m=500\) are accumulated and printed in scientific notation.
For one fixed cycle length \(m\), the implementation performs two explicit mode-by-distance sweeps, so the time cost is \(O(m^2)\). The working memory is \(O(m)\), because only a few arrays of length \(m\) are stored at once. Summing over all cycle sizes from \(2\) to \(n\) gives
$$ \sum_{m=2}^{n} O(m^2)=O(n^3), $$
with peak memory \(O(n)\). For the required bound \(n=500\), this direct spectral method is easily practical.
Für jede Zykluslänge \(m\) bewegen sich zwei Läufer unabhängig auf einem \(m\)-Kreis. In jeder Runde wählt jeder mit Wahrscheinlichkeit \(1/3\) genau einen von drei Zügen: einen Schritt im Uhrzeigersinn, keinen Zug oder einen Schritt gegen den Uhrzeigersinn. Dauert die Verfolgung \(T\) Runden bis zum ersten Treffen, dann ist die Auszahlung dieser Partie gleich \(T^2\). Sei \(E_m\) der Erwartungswert dieser Auszahlung bei gleichverteilt gewählten Startpositionen, und definiere
$$G(n)=\sum_{m=2}^{n} E_m.$$
Gesucht ist dieser Wert bis \(n=500\). Die Implementierungen simulieren nicht, sondern lösen die exakten Erwartungsgleichungen der relativen Distanzkette auf dem Kreis.
Der entscheidende Schritt ist die Ausnutzung der Rotationssymmetrie. Die absoluten Positionen sind unwichtig; relevant ist nur die relative Distanz auf dem Kreis. Dadurch wird aus dem ursprünglichen Zwei-Teilchen-Prozess eine einzelne Markov-Kette auf \(\mathbb{Z}_m\).
Sei \(D_t\in\mathbb{Z}_m\) die gerichtete Distanz nach \(t\) Runden. Die Verfolgung endet genau dann, wenn
$$D_t=0.$$
Jeder Läufer trägt einen Inkrementwert aus \(\{-1,0,+1\}\) mit Wahrscheinlichkeit \(1/3\) bei. Daher hat der relative Zuwachs \(X_t=D_{t+1}-D_t\) die Verteilung
$$\mathbb{P}(X_t=0)=\frac13,\qquad \mathbb{P}(X_t=\pm1)=\frac29,\qquad \mathbb{P}(X_t=\pm2)=\frac19.$$
Damit wirkt der Übergangsoperator auf eine Funktion \(f:\mathbb{Z}_m\to\mathbb{R}\) als
$$ (Pf)(d)=\frac13 f(d)+\frac29\bigl(f(d+1)+f(d-1)\bigr)+\frac19\bigl(f(d+2)+f(d-2)\bigr), $$
wobei alle Indizes modulo \(m\) verstanden werden.
Da der Operator zirkulant ist, sind die diskreten Fourier-Moden
$$u_k(d)=e^{2\pi i k d/m},\qquad k=0,1,\dots,m-1,$$
Eigenvektoren von \(P\). Mit
$$\theta_k=\frac{2\pi k}{m}$$
erhält man die Eigenwerte
$$ \lambda_k=\frac13+\frac29\left(e^{i\theta_k}+e^{-i\theta_k}\right)+\frac19\left(e^{2i\theta_k}+e^{-2i\theta_k}\right) =\frac13+\frac49\cos\theta_k+\frac29\cos(2\theta_k). $$
Genau diese Größen stehen in den Nennern der spektralen Formeln. Für \(k=0\) gilt \(\lambda_0=1\), also liegen konstante Funktionen im Kern von \(I-P\). Deshalb muss jede Fourier-Inversion mit einer Quelle von Gesamtsumme \(0\) formuliert werden.
Sei \(T_d\) die Anzahl der Runden bis zum ersten Treffen bei Anfangsdistanz \(d\), und definiere
$$a_d=\mathbb{E}[T_d],\qquad a_0=0.$$
Für jede von Null verschiedene Distanz vergeht zunächst eine Runde, danach startet derselbe Prozess vom Folgezustand. Also
$$a_d=1+(Pa)_d\qquad (d\ne0).$$
Zur Fourier-Lösung auf dem ganzen Kreis schreibt man dies als Poisson-Gleichung mit Nullsumme um:
$$ (I-P)a=\mathbf{1}-m e_0. $$
Nach Entfernung der Nullmode und Bildung des Realteils ergibt sich
$$ a_d=\sum_{k=1}^{m-1}\frac{1-\cos\left(2\pi k d/m\right)}{1-\lambda_k}. $$
Das ist die erste große spektrale Summe der Implementierungen.
Nun definieren wir
$$b_d=\mathbb{E}[T_d^2],\qquad b_0=0.$$
Aus \(T_d=1+T_{D_1}\) nach einer Runde folgt für \(d\ne0\)
$$ b_d=1+2(Pa)_d+(Pb)_d. $$
Wegen \(a_d=1+(Pa)_d\) vereinfacht sich dies zu
$$ (I-P)b=2a-1 $$
abseits des absorbierenden Zustands. Für die spektrale Inversion braucht man wieder eine Quelle mit Gesamtsumme \(0\). Daher setze
$$ c_d=2a_d-1\quad(d\ne0),\qquad c_0=-\sum_{d=1}^{m-1} c_d. $$
Sei \(z\) die eindeutige Lösung mit Mittelwert \(0\) von
$$ (I-P)z=c,\qquad \sum_{d=0}^{m-1} z_d=0. $$
Dann gilt \(b_d=z_d-z_0\), also insbesondere \(b_0=0\). Mit
$$ \widehat{c}_k=\sum_{d=0}^{m-1} c_d\,e^{-2\pi i k d/m} $$
wird der mittlere Auszahlungswert für festen Kreisumfang
$$ E_m=\frac1m\sum_{d=0}^{m-1} b_d =-z_0 =-\frac1m\sum_{k=1}^{m-1}\frac{\widehat{c}_k}{1-\lambda_k}. $$
Genau diese zweite spektrale Lösung wird in allen drei Sprachen durchgeführt.
Sobald \(E_m\) für eine feste Zykluslänge bekannt ist, erhält man global einfach
$$G(n)=\sum_{m=2}^{n} E_m.$$
Die Implementierungen berechnen diese Werte direkt für \(m=2,3,\dots,500\) und akkumulieren die laufende Summe.
Für \(m=2\) gibt es nur eine nichttriviale Fourier-Mode, nämlich \(k=1\), mit
$$ \lambda_1=\frac13+\frac49\cos\pi+\frac29\cos(2\pi)=\frac19, \qquad 1-\lambda_1=\frac89. $$
Der erste Moment aus der Distanz \(1\) ist also
$$ a_1=\frac{1-\cos\pi}{8/9}=\frac{2}{8/9}=\frac94. $$
Als Nächstes gilt
$$ c_1=2a_1-1=\frac72, \qquad c_0=-\frac72, $$
also ist der nichtverschwindende Fourier-Koeffizient
$$ \widehat{c}_1=c_0-c_1=-7. $$
Daraus folgt
$$ E_2=-\frac12\cdot\frac{-7}{8/9}=\frac{63}{16}=3.9375. $$
Das ist der Mittelwert von \(T^2\) über die beiden möglichen Anfangsdistanzen \(0\) und \(1\). Die Distanz \(0\) trägt \(0\) bei; deshalb ist der bedingte zweite Moment für den nichttrivialen Start doppelt so groß.
Die C++-, Python- und Java-Implementierungen folgen derselben numerischen Struktur. Für jede Zykluslänge \(m\) berechnen sie zuerst die spektralen Faktoren \(1-\lambda_k\) für alle nichtverschwindenden Moden. Danach werten sie die Formel für den ersten Moment aus, indem sie jeweils eine Fourier-Mode fixieren und die Potenzen von \(e^{2\pi i k/m}\) über alle Distanzen inkrementell erzeugen. So vermeidet man zusätzliche trigonometrische Auswertungen in der inneren Schleife.
Anschließend baut die Implementierung die ausgeglichene Quelle der zweiten-Moment-Gleichung auf, führt eine direkte diskrete Fourier-Transformation dieser Quelle aus, dividiert jede Nichtnull-Mode durch denselben spektralen Faktor und liest den mittleren Auszahlungswert aus der Nullkoordinate der Lösung mit Mittelwert \(0\) ab. Wegen der konjugierten Symmetrie heben sich die imaginären Teile weg, numerisch bleibt also nur der Realteil. Zum Schluss werden die Beiträge für \(m=2\) bis \(m=500\) aufsummiert und in wissenschaftlicher Notation ausgegeben.
Für eine feste Zykluslänge \(m\) führt die Implementierung zwei explizite Durchläufe über Moden und Distanzen aus. Der Zeitaufwand beträgt daher \(O(m^2)\). Der Speicherbedarf ist \(O(m)\), weil gleichzeitig nur einige wenige Arrays der Länge \(m\) gehalten werden. Über alle Zykluslängen von \(2\) bis \(n\) erhält man
$$ \sum_{m=2}^{n} O(m^2)=O(n^3), $$
bei Spitzenspeicher \(O(n)\). Für die geforderte Grenze \(n=500\) ist dieses direkte spektrale Verfahren problemlos praktikabel.
Her \(m\) çevresi için iki yürüyüşçü \(m\)-çemberi üzerinde birbirinden bağımsız hareket eder. Her turda her biri eşit olasılıkla üç hamleden birini seçer: saat yönünde bir adım, yerinde kalma veya saat yönünün tersine bir adım. Kovalamaca ilk karşılaşmaya kadar \(T\) tur sürüyorsa, o oyunun ödemesi \(T^2\) olur. Başlangıç konumları eşit olasılıkla seçildiğinde beklenen ödeme \(E_m\) olsun ve
$$G(n)=\sum_{m=2}^{n} E_m$$
tanımlansın. Amaç bu toplamı \(n=500\) için hesaplamaktır. Uygulamalar rastgele oyunları simüle etmez; bunun yerine çember üzerindeki bağıl uzaklık zincirinin tam beklenti denklemlerini çözer.
Temel sadeleştirme şudur: mutlak konumlar önemli değildir, sadece çember üzerindeki bağıl ayrım önemlidir. Böylece iki yürüyüşçülü süreç, \(\mathbb{Z}_m\) üzerinde tek bir Markov zincirine indirgenir.
\(t\) turundan sonraki yönlü ayrımı \(D_t\in\mathbb{Z}_m\) ile gösterelim. Oyun tam olarak
$$D_t=0$$
olduğunda biter. Her yürüyüşçü \(\{-1,0,+1\}\) kümesinden \(1/3\) olasılıkla bir artış verdiği için, bağıl artış \(X_t=D_{t+1}-D_t\) şu dağılıma sahiptir:
$$\mathbb{P}(X_t=0)=\frac13,\qquad \mathbb{P}(X_t=\pm1)=\frac29,\qquad \mathbb{P}(X_t=\pm2)=\frac19.$$
Dolayısıyla \(f:\mathbb{Z}_m\to\mathbb{R}\) için geçiş operatörü
$$ (Pf)(d)=\frac13 f(d)+\frac29\bigl(f(d+1)+f(d-1)\bigr)+\frac19\bigl(f(d+2)+f(d-2)\bigr) $$
şeklindedir; tüm indisler mod \(m\) alınır.
Operatör circulant olduğu için ayrık Fourier modları
$$u_k(d)=e^{2\pi i k d/m},\qquad k=0,1,\dots,m-1,$$
\(P\)'nin özvektörleridir. Burada
$$\theta_k=\frac{2\pi k}{m}$$
yazarsak özdeğerler
$$ \lambda_k=\frac13+\frac29\left(e^{i\theta_k}+e^{-i\theta_k}\right)+\frac19\left(e^{2i\theta_k}+e^{-2i\theta_k}\right) =\frac13+\frac49\cos\theta_k+\frac29\cos(2\theta_k) $$
olur. Uygulamanın kullandığı paydalar tam olarak bunlardır. \(k=0\) için \(\lambda_0=1\) olduğundan sabit fonksiyonlar \(I-P\)'nin çekirdeğinde yer alır; bu yüzden spektral tersleme her zaman toplamı sıfır olan bir kaynakla yapılmalıdır.
Başlangıç ayrımı \(d\) iken ilk buluşmaya kadar geçen tur sayısını \(T_d\) ile gösterelim ve
$$a_d=\mathbb{E}[T_d],\qquad a_0=0$$
tanımını yapalım. \(d\ne0\) için önce bir tur geçer, sonra süreç yeni durumdan aynı biçimde devam eder:
$$a_d=1+(Pa)_d\qquad (d\ne0).$$
Bunu tüm çember üzerinde Fourier ile çözebilmek için sıfır toplamlı Poisson denklemine çeviririz:
$$ (I-P)a=\mathbf{1}-m e_0. $$
Sıfır modu çıkarıp reel kısmı aldığımızda
$$ a_d=\sum_{k=1}^{m-1}\frac{1-\cos\left(2\pi k d/m\right)}{1-\lambda_k} $$
elde edilir. Uygulamadaki ilk büyük spektral toplam budur.
Şimdi
$$b_d=\mathbb{E}[T_d^2],\qquad b_0=0$$
olsun. Bir tur sonrası \(T_d=1+T_{D_1}\) bağıntısından \(d\ne0\) için
$$ b_d=1+2(Pa)_d+(Pb)_d $$
çıkar. \(a_d=1+(Pa)_d\) olduğundan bu
$$ (I-P)b=2a-1 $$
biçimine sadeleşir. Yine spektral çözüm için toplamı sıfır olan bir kaynak gerekir. Bu nedenle
$$ c_d=2a_d-1\quad(d\ne0),\qquad c_0=-\sum_{d=1}^{m-1} c_d $$
tanımlanır. Ortalama değeri sıfır olan çözüm \(z\) şu denklemi sağlasın:
$$ (I-P)z=c,\qquad \sum_{d=0}^{m-1} z_d=0. $$
O zaman \(b_d=z_d-z_0\) olur ve özellikle \(b_0=0\) sağlanır. Eğer
$$ \widehat{c}_k=\sum_{d=0}^{m-1} c_d\,e^{-2\pi i k d/m} $$
ise, sabit bir çevre boyu için ortalama ödeme
$$ E_m=\frac1m\sum_{d=0}^{m-1} b_d =-z_0 =-\frac1m\sum_{k=1}^{m-1}\frac{\widehat{c}_k}{1-\lambda_k} $$
şeklindedir. Üç dildeki uygulamanın yaptığı ikinci spektral çözüm tam olarak budur.
\(E_m\) bir kez hesaplandıktan sonra küresel fonksiyon doğrudan
$$G(n)=\sum_{m=2}^{n} E_m$$
olur. Uygulamalar bunu \(m=2,3,\dots,500\) için tek tek hesaplayıp kümülatif toplama ekler.
\(m=2\) için yalnızca bir tane trivial olmayan Fourier modu vardır: \(k=1\). Bu durumda
$$ \lambda_1=\frac13+\frac49\cos\pi+\frac29\cos(2\pi)=\frac19, \qquad 1-\lambda_1=\frac89. $$
Buna göre ayrım \(1\) için birinci moment
$$ a_1=\frac{1-\cos\pi}{8/9}=\frac{2}{8/9}=\frac94 $$
olur. Sonra
$$ c_1=2a_1-1=\frac72, \qquad c_0=-\frac72 $$
ve dolayısıyla sıfır olmayan Fourier katsayısı
$$ \widehat{c}_1=c_0-c_1=-7 $$
elde edilir. O halde
$$ E_2=-\frac12\cdot\frac{-7}{8/9}=\frac{63}{16}=3.9375. $$
Bu değer, başlangıç ayrımları \(0\) ve \(1\) üzerinde \(T^2\)'nin ortalamasıdır. \(0\) ayrımı zaten bitmiş oyunu verdiği için katkısı \(0\)'dır; bu yüzden trivial olmayan başlangıç için koşullu ikinci moment bunun iki katıdır.
C++, Python ve Java uygulamaları aynı sayısal iskeleti izler. Her \(m\) için önce tüm sıfır olmayan modlarda \(1-\lambda_k\) spektral çarpanları hesaplanır. Ardından birinci moment formülü değerlendirilir; bunun için tek bir Fourier modu sabitlenir ve \(e^{2\pi i k/m}\) kuvvetleri uzaklık boyunca artımlı olarak üretilir. Böylece iç döngüde her adım için yeniden trigonometrik çağrı yapılmaz.
Daha sonra uygulama ikinci moment denklemindeki dengeli kaynağı kurar, bu kaynağın doğrudan ayrık Fourier dönüşümünü alır, her sıfır olmayan modu aynı spektral paydaya böler ve ortalama ödemeyi ortalaması sıfır olan çözümün sıfır koordinatından çıkarır. Eşlenik simetri nedeniyle sanal kısımlar birbirini götürür; sayısal olarak yalnızca reel kısım tutulur. Son aşamada \(m=2\) ile \(m=500\) arasındaki tüm katkılar toplanır ve sonuç bilimsel gösterimde yazdırılır.
Sabit bir \(m\) için uygulama modlar ve uzaklıklar üzerinde iki açık tarama yapar; bu nedenle zaman maliyeti \(O(m^2)\) olur. Bellek kullanımı \(O(m)\)'dir; çünkü aynı anda yalnızca uzunluğu \(m\) olan birkaç dizi tutulur. Tüm çevre boyları \(2\)'den \(n\)'e kadar toplandığında
$$ \sum_{m=2}^{n} O(m^2)=O(n^3) $$
elde edilir ve tepe bellek \(O(n)\) olur. Gerekli sınır \(n=500\) için bu doğrudan spektral yöntem rahatlıkla yeterlidir.
Para cada longitud de ciclo \(m\), dos caminantes se mueven de forma independiente sobre un ciclo de \(m\) vértices. En cada ronda, cada uno elige con probabilidad \(1/3\) una de tres acciones: avanzar un paso en sentido horario, quedarse quieto o avanzar un paso en sentido antihorario. Si la persecución dura \(T\) rondas hasta el primer encuentro, el pago de esa partida es \(T^2\). Sea \(E_m\) el pago esperado cuando las posiciones iniciales se eligen uniformemente al azar, y definamos
$$G(n)=\sum_{m=2}^{n} E_m.$$
La meta es evaluar esta suma hasta \(n=500\). Las implementaciones no simulan partidas aleatorias; resuelven exactamente las ecuaciones de esperanza del paseo de separación relativa sobre el ciclo.
La simplificación central es que las posiciones absolutas no importan. Solo importa la separación relativa en el ciclo, de modo que el problema original con dos caminantes se convierte en una sola cadena de Markov sobre \(\mathbb{Z}_m\).
Sea \(D_t\in\mathbb{Z}_m\) la separación dirigida después de \(t\) rondas. La persecución termina exactamente cuando
$$D_t=0.$$
Cada caminante aporta un incremento tomado de \(\{-1,0,+1\}\) con probabilidad \(1/3\). Por tanto, el incremento relativo \(X_t=D_{t+1}-D_t\) tiene distribución
$$\mathbb{P}(X_t=0)=\frac13,\qquad \mathbb{P}(X_t=\pm1)=\frac29,\qquad \mathbb{P}(X_t=\pm2)=\frac19.$$
Entonces el operador de transición sobre una función \(f:\mathbb{Z}_m\to\mathbb{R}\) es
$$ (Pf)(d)=\frac13 f(d)+\frac29\bigl(f(d+1)+f(d-1)\bigr)+\frac19\bigl(f(d+2)+f(d-2)\bigr), $$
donde todos los índices se toman módulo \(m\).
Como el operador es circulante, los modos discretos de Fourier
$$u_k(d)=e^{2\pi i k d/m},\qquad k=0,1,\dots,m-1,$$
son autovectores de \(P\). Si escribimos
$$\theta_k=\frac{2\pi k}{m},$$
los autovalores son
$$ \lambda_k=\frac13+\frac29\left(e^{i\theta_k}+e^{-i\theta_k}\right)+\frac19\left(e^{2i\theta_k}+e^{-2i\theta_k}\right) =\frac13+\frac49\cos\theta_k+\frac29\cos(2\theta_k). $$
Estas cantidades son exactamente los denominadores usados por la implementación. El modo \(k=0\) cumple \(\lambda_0=1\), así que las funciones constantes pertenecen al núcleo de \(I-P\); por eso cada inversión espectral debe escribirse con una fuente de suma total nula.
Sea \(T_d\) el número de rondas hasta el primer encuentro cuando la separación inicial es \(d\), y definamos
$$a_d=\mathbb{E}[T_d],\qquad a_0=0.$$
Para toda separación no nula pasa una ronda y el proceso recomienza desde el nuevo estado, así que
$$a_d=1+(Pa)_d\qquad (d\ne0).$$
Para poder resolver en Fourier sobre todo el ciclo, se reescribe como la ecuación de Poisson de suma nula
$$ (I-P)a=\mathbf{1}-m e_0. $$
Eliminando el modo cero y tomando la parte real, se obtiene
$$ a_d=\sum_{k=1}^{m-1}\frac{1-\cos\left(2\pi k d/m\right)}{1-\lambda_k}. $$
Esta es la primera gran suma espectral realizada por las implementaciones.
Ahora definimos
$$b_d=\mathbb{E}[T_d^2],\qquad b_0=0.$$
Usando \(T_d=1+T_{D_1}\) tras una ronda, para \(d\ne0\) se obtiene
$$ b_d=1+2(Pa)_d+(Pb)_d. $$
Como \(a_d=1+(Pa)_d\), esto se simplifica a
$$ (I-P)b=2a-1 $$
fuera del estado absorbente. De nuevo necesitamos una fuente de suma cero, así que definimos
$$ c_d=2a_d-1\quad(d\ne0),\qquad c_0=-\sum_{d=1}^{m-1} c_d. $$
Sea \(z\) la solución de media cero de
$$ (I-P)z=c,\qquad \sum_{d=0}^{m-1} z_d=0. $$
Entonces \(b_d=z_d-z_0\), lo que impone \(b_0=0\). Si
$$ \widehat{c}_k=\sum_{d=0}^{m-1} c_d\,e^{-2\pi i k d/m}, $$
el pago medio para un ciclo fijo es
$$ E_m=\frac1m\sum_{d=0}^{m-1} b_d =-z_0 =-\frac1m\sum_{k=1}^{m-1}\frac{\widehat{c}_k}{1-\lambda_k}. $$
Ese es exactamente el segundo cálculo espectral que ejecutan las tres implementaciones.
Una vez que se conoce \(E_m\) para una longitud fija, la función global es simplemente
$$G(n)=\sum_{m=2}^{n} E_m.$$
Las implementaciones evalúan esta expresión de manera directa para \(m=2,3,\dots,500\) y acumulan el total parcial.
Para \(m=2\) solo existe un modo de Fourier no trivial, \(k=1\), con
$$ \lambda_1=\frac13+\frac49\cos\pi+\frac29\cos(2\pi)=\frac19, \qquad 1-\lambda_1=\frac89. $$
Por tanto, el primer momento desde la separación \(1\) es
$$ a_1=\frac{1-\cos\pi}{8/9}=\frac{2}{8/9}=\frac94. $$
Luego
$$ c_1=2a_1-1=\frac72, \qquad c_0=-\frac72, $$
y el coeficiente de Fourier no nulo vale
$$ \widehat{c}_1=c_0-c_1=-7. $$
Así,
$$ E_2=-\frac12\cdot\frac{-7}{8/9}=\frac{63}{16}=3.9375. $$
Este valor es el promedio de \(T^2\) sobre las dos separaciones iniciales posibles, \(0\) y \(1\). La separación \(0\) aporta \(0\), así que el segundo momento condicional desde el inicio no trivial es el doble.
Las implementaciones en C++, Python y Java siguen el mismo esquema numérico. Para cada longitud \(m\), primero calculan los factores espectrales \(1-\lambda_k\) para todos los modos no nulos. Después evalúan la fórmula del primer momento fijando un modo cada vez y generando las potencias de \(e^{2\pi i k/m}\) de forma incremental a lo largo de todas las separaciones. De ese modo se evita una llamada trigonométrica nueva dentro del bucle interior.
A continuación, la implementación construye la fuente equilibrada de la ecuación del segundo momento, realiza una transformada discreta de Fourier directa de esa fuente, divide cada modo no nulo por el mismo factor espectral y extrae el pago medio desde la coordenada cero de la solución de media nula. Las partes imaginarias se cancelan por simetría conjugada, así que numéricamente solo se conserva la parte real. Finalmente, se suman las contribuciones para \(m=2\) hasta \(m=500\) y el resultado se muestra en notación científica.
Para una longitud fija \(m\), la implementación realiza dos barridos explícitos sobre modos y separaciones, de modo que el coste temporal es \(O(m^2)\). La memoria de trabajo es \(O(m)\), porque solo se mantienen unos pocos arreglos de longitud \(m\). Sumando todas las longitudes desde \(2\) hasta \(n\), se obtiene
$$ \sum_{m=2}^{n} O(m^2)=O(n^3), $$
con memoria máxima \(O(n)\). Para el límite requerido \(n=500\), este método espectral directo es perfectamente viable.
对于每一个环长 \(m\)，有两个行者在一个 \(m\) 个顶点的环上独立移动。每一轮中，每个行者都以 \(1/3\) 的概率从三种动作中任选一种：顺时针走一步、原地不动、逆时针走一步。如果这场追逐在第一次相遇前持续了 \(T\) 轮，那么该局的支付就是 \(T^2\)。记 \(E_m\) 为起点均匀随机时的期望支付，并定义
$$G(n)=\sum_{m=2}^{n} E_m.$$
题目要求把这个量计算到 \(n=500\)。实现并没有用随机模拟，而是直接求解环上相对位置随机游走所满足的期望方程。
最关键的化简是：绝对位置并不重要，真正决定过程的是两者在环上的相对间距。因此，原来的双行者过程可以压缩成 \(\mathbb{Z}_m\) 上的一个单变量马尔可夫链。
设 \(D_t\in\mathbb{Z}_m\) 表示第 \(t\) 轮结束后的有向相对间距。追逐结束当且仅当
$$D_t=0.$$
每个行者单独贡献一个来自 \(\{-1,0,+1\}\) 的增量，且三者概率都为 \(1/3\)。因此，相对增量 \(X_t=D_{t+1}-D_t\) 的分布为
$$\mathbb{P}(X_t=0)=\frac13,\qquad \mathbb{P}(X_t=\pm1)=\frac29,\qquad \mathbb{P}(X_t=\pm2)=\frac19.$$
于是，作用在函数 \(f:\mathbb{Z}_m\to\mathbb{R}\) 上的转移算子为
$$ (Pf)(d)=\frac13 f(d)+\frac29\bigl(f(d+1)+f(d-1)\bigr)+\frac19\bigl(f(d+2)+f(d-2)\bigr), $$
其中所有下标都按模 \(m\) 理解。
因为这个算子是循环型的，离散傅里叶模态
$$u_k(d)=e^{2\pi i k d/m},\qquad k=0,1,\dots,m-1,$$
正好就是 \(P\) 的特征向量。记
$$\theta_k=\frac{2\pi k}{m},$$
则对应的特征值为
$$ \lambda_k=\frac13+\frac29\left(e^{i\theta_k}+e^{-i\theta_k}\right)+\frac19\left(e^{2i\theta_k}+e^{-2i\theta_k}\right) =\frac13+\frac49\cos\theta_k+\frac29\cos(2\theta_k). $$
实现中反复出现的分母，正是 \(1-\lambda_k\)。其中 \(k=0\) 时有 \(\lambda_0=1\)，说明常数函数落在 \(I-P\) 的核里，所以任何谱反演都必须把右端写成总和为零的形式。
设 \(T_d\) 表示初始间距为 \(d\) 时直到第一次相遇所需的轮数，并定义
$$a_d=\mathbb{E}[T_d],\qquad a_0=0.$$
对于任意非零间距，先走一轮，然后从新状态重新开始，因此
$$a_d=1+(Pa)_d\qquad (d\ne0).$$
为了在整个环上做傅里叶求解，把它改写成零和的泊松方程：
$$ (I-P)a=\mathbf{1}-m e_0. $$
去掉零模并取实部后，得到显式公式
$$ a_d=\sum_{k=1}^{m-1}\frac{1-\cos\left(2\pi k d/m\right)}{1-\lambda_k}. $$
这就是实现中第一组大规模频域求和的数学来源。
接着定义二阶矩
$$b_d=\mathbb{E}[T_d^2],\qquad b_0=0.$$
由一轮后的关系 \(T_d=1+T_{D_1}\) 可得，对 \(d\ne0\)，
$$ b_d=1+2(Pa)_d+(Pb)_d. $$
再利用 \(a_d=1+(Pa)_d\)，可化简为
$$ (I-P)b=2a-1 $$
在吸收态之外成立。为了继续做谱反演，需要把右端调成零和，因此定义
$$ c_d=2a_d-1\quad(d\ne0),\qquad c_0=-\sum_{d=1}^{m-1} c_d. $$
令 \(z\) 为满足
$$ (I-P)z=c,\qquad \sum_{d=0}^{m-1} z_d=0 $$
的零均值解，那么
$$b_d=z_d-z_0,$$
从而自动满足 \(b_0=0\)。如果记
$$ \widehat{c}_k=\sum_{d=0}^{m-1} c_d\,e^{-2\pi i k d/m}, $$
那么固定环长 \(m\) 的平均支付就是
$$ E_m=\frac1m\sum_{d=0}^{m-1} b_d =-z_0 =-\frac1m\sum_{k=1}^{m-1}\frac{\widehat{c}_k}{1-\lambda_k}. $$
这正是三份实现共同执行的第二次频域求解。
一旦某个固定 \(m\) 的 \(E_m\) 计算出来，总函数就只是
$$G(n)=\sum_{m=2}^{n} E_m.$$
实现按 \(m=2,3,\dots,500\) 逐个计算，再把这些值累加起来。
当 \(m=2\) 时，只有一个非平凡傅里叶模，即 \(k=1\)。此时
$$ \lambda_1=\frac13+\frac49\cos\pi+\frac29\cos(2\pi)=\frac19, \qquad 1-\lambda_1=\frac89. $$
所以从间距 \(1\) 出发的一阶矩为
$$ a_1=\frac{1-\cos\pi}{8/9}=\frac{2}{8/9}=\frac94. $$
接着有
$$ c_1=2a_1-1=\frac72, \qquad c_0=-\frac72, $$
因此唯一的非零傅里叶系数是
$$ \widehat{c}_1=c_0-c_1=-7. $$
于是
$$ E_2=-\frac12\cdot\frac{-7}{8/9}=\frac{63}{16}=3.9375. $$
这个值是对两种可能的初始间距 \(0\) 和 \(1\) 的 \(T^2\) 取平均得到的。间距 \(0\) 对应一开始就重合，所以贡献为 \(0\)；因此若条件化到非平凡起点，二阶矩会正好大一倍。
C++、Python 和 Java 三个实现采用的是同一套数值流程。对每个环长 \(m\)，它们先计算所有非零频率的谱因子 \(1-\lambda_k\)。然后逐个固定频率，沿着全部间距递推复数单位根的幂，从而累加出一阶矩所需的频域求和。这样做的好处是内层循环不必重复调用三角函数。
之后，实现构造二阶矩方程对应的平衡源项，对该源项做一次直接离散傅里叶变换，再把每个非零模除以同一个谱因子，并从零均值解的第零坐标读出平均支付。由于共轭对称性，虚部在理论上会相互抵消，所以数值上只保留实部。最后，把 \(m=2\) 到 \(m=500\) 的所有贡献累加，并以科学计数法输出结果。
对固定的 \(m\) 而言，实现要做两次显式的“频率乘以间距”扫描，因此时间复杂度是 \(O(m^2)\)。工作内存是 \(O(m)\)，因为同时只保存少量长度为 \(m\) 的数组。把所有环长从 \(2\) 加到 \(n\) 后，得到
$$ \sum_{m=2}^{n} O(m^2)=O(n^3), $$
峰值内存则是 \(O(n)\)。对于题目要求的 \(n=500\)，这种直接的谱方法完全可行。
Для каждого размера цикла \(m\) два участника независимо движутся по циклу из \(m\) вершин. В каждом раунде каждый из них с вероятностью \(1/3\) выбирает один из трех ходов: шаг по часовой стрелке, остаться на месте или шаг против часовой стрелки. Если погоня длится \(T\) раундов до первой встречи, то выплата за такую игру равна \(T^2\). Обозначим через \(E_m\) математическое ожидание этой выплаты при равномерно случайных начальных позициях и определим
$$G(n)=\sum_{m=2}^{n} E_m.$$
Нужно вычислить эту сумму для \(n=500\). Реализации не моделируют случайные партии, а решают точные уравнения для моментов времени встречи в цепи относительного расстояния на цикле.
Главное упрощение состоит в том, что абсолютные позиции несущественны. Значение имеет только относительное расстояние на цикле, поэтому исходный процесс с двумя участниками превращается в одну цепь Маркова на \(\mathbb{Z}_m\).
Пусть \(D_t\in\mathbb{Z}_m\) обозначает ориентированное расстояние после \(t\) раундов. Погоня заканчивается тогда и только тогда, когда
$$D_t=0.$$
Каждый участник дает приращение из множества \(\{-1,0,+1\}\) с вероятностью \(1/3\). Поэтому относительное приращение \(X_t=D_{t+1}-D_t\) распределено так:
$$\mathbb{P}(X_t=0)=\frac13,\qquad \mathbb{P}(X_t=\pm1)=\frac29,\qquad \mathbb{P}(X_t=\pm2)=\frac19.$$
Следовательно, оператор перехода, действующий на функцию \(f:\mathbb{Z}_m\to\mathbb{R}\), имеет вид
$$ (Pf)(d)=\frac13 f(d)+\frac29\bigl(f(d+1)+f(d-1)\bigr)+\frac19\bigl(f(d+2)+f(d-2)\bigr), $$
где все индексы понимаются по модулю \(m\).
Так как оператор циркулянтный, дискретные моды Фурье
$$u_k(d)=e^{2\pi i k d/m},\qquad k=0,1,\dots,m-1,$$
являются собственными векторами оператора \(P\). Если обозначить
$$\theta_k=\frac{2\pi k}{m},$$
то соответствующие собственные значения равны
$$ \lambda_k=\frac13+\frac29\left(e^{i\theta_k}+e^{-i\theta_k}\right)+\frac19\left(e^{2i\theta_k}+e^{-2i\theta_k}\right) =\frac13+\frac49\cos\theta_k+\frac29\cos(2\theta_k). $$
Именно величины \(1-\lambda_k\) выступают знаменателями во всех спектральных формулах. Для \(k=0\) имеем \(\lambda_0=1\), то есть постоянные функции лежат в ядре \(I-P\). Поэтому каждое спектральное обращение должно использовать правую часть с нулевой суммой.
Пусть \(T_d\) - число раундов до первой встречи при начальном расстоянии \(d\), и определим
$$a_d=\mathbb{E}[T_d],\qquad a_0=0.$$
Для любого ненулевого расстояния сначала проходит один раунд, а затем процесс продолжается из нового состояния, поэтому
$$a_d=1+(Pa)_d\qquad (d\ne0).$$
Чтобы решить это уравнение на всем цикле в базисе Фурье, его переписывают как нулесуммное уравнение Пуассона:
$$ (I-P)a=\mathbf{1}-m e_0. $$
После удаления нулевой моды и взятия действительной части получается формула
$$ a_d=\sum_{k=1}^{m-1}\frac{1-\cos\left(2\pi k d/m\right)}{1-\lambda_k}. $$
Это первая крупная спектральная сумма, которую вычисляют реализации.
Теперь введем второй момент
$$b_d=\mathbb{E}[T_d^2],\qquad b_0=0.$$
Из равенства \(T_d=1+T_{D_1}\) после одного раунда следует, что для \(d\ne0\)
$$ b_d=1+2(Pa)_d+(Pb)_d. $$
Так как \(a_d=1+(Pa)_d\), это упрощается до
$$ (I-P)b=2a-1 $$
вне поглощающего состояния. Для спектрального решения снова нужна правая часть с нулевой суммой, поэтому определим
$$ c_d=2a_d-1\quad(d\ne0),\qquad c_0=-\sum_{d=1}^{m-1} c_d. $$
Пусть \(z\) - единственное решение со средним \(0\) системы
$$ (I-P)z=c,\qquad \sum_{d=0}^{m-1} z_d=0. $$
Тогда \(b_d=z_d-z_0\), и условие \(b_0=0\) выполняется автоматически. Если
$$ \widehat{c}_k=\sum_{d=0}^{m-1} c_d\,e^{-2\pi i k d/m}, $$
то средняя выплата для фиксированного \(m\) равна
$$ E_m=\frac1m\sum_{d=0}^{m-1} b_d =-z_0 =-\frac1m\sum_{k=1}^{m-1}\frac{\widehat{c}_k}{1-\lambda_k}. $$
Это и есть вторая спектральная задача, выполняемая во всех трех реализациях.
Когда \(E_m\) найдено для фиксированного размера цикла, глобальная функция записывается просто как
$$G(n)=\sum_{m=2}^{n} E_m.$$
Реализации непосредственно вычисляют эти значения для \(m=2,3,\dots,500\) и накапливают текущую сумму.
При \(m=2\) существует только одна нетривиальная мода Фурье, \(k=1\), и
$$ \lambda_1=\frac13+\frac49\cos\pi+\frac29\cos(2\pi)=\frac19, \qquad 1-\lambda_1=\frac89. $$
Поэтому первый момент из расстояния \(1\) равен
$$ a_1=\frac{1-\cos\pi}{8/9}=\frac{2}{8/9}=\frac94. $$
Далее
$$ c_1=2a_1-1=\frac72, \qquad c_0=-\frac72, $$
так что единственный ненулевой коэффициент Фурье равен
$$ \widehat{c}_1=c_0-c_1=-7. $$
Следовательно,
$$ E_2=-\frac12\cdot\frac{-7}{8/9}=\frac{63}{16}=3.9375. $$
Это среднее значение \(T^2\) по двум возможным начальным расстояниям \(0\) и \(1\). Состояние \(0\) дает вклад \(0\), потому что погоня уже завершена, поэтому условный второй момент для нетривиального старта вдвое больше.
Реализации на C++, Python и Java используют один и тот же численный план. Для каждого \(m\) сначала вычисляются спектральные множители \(1-\lambda_k\) для всех ненулевых мод. Затем формула для первого момента оценивается по одной моде за раз: степени числа \(e^{2\pi i k/m}\) порождаются последовательно по всем расстояниям, что избавляет от лишних тригонометрических вычислений во внутреннем цикле.
После этого реализация строит сбалансированный источник для уравнения второго момента, выполняет прямое дискретное преобразование Фурье этого источника, делит каждую ненулевую моду на тот же спектральный множитель и извлекает среднюю выплату из нулевой координаты решения со средним ноль. Из-за сопряженной симметрии мнимые части сокращаются, поэтому численно сохраняется только действительная часть. В конце все вклады для \(m=2\) до \(m=500\) суммируются, а ответ выводится в научной записи.
Для фиксированного \(m\) реализация выполняет два явных прохода по модам и расстояниям, так что временная сложность составляет \(O(m^2)\). Рабочая память равна \(O(m)\), потому что одновременно хранятся лишь несколько массивов длины \(m\). При суммировании по всем размерам циклов от \(2\) до \(n\) получаем
$$ \sum_{m=2}^{n} O(m^2)=O(n^3), $$
а пиковое потребление памяти равно \(O(n)\). Для требуемой границы \(n=500\) этот прямой спектральный метод вполне удобен на практике.
لكل طول دورة \(m\)، يتحرك شخصان بشكل مستقل على دورة مكونة من \(m\) مواضع. في كل جولة يختار كل واحد، باحتمال \(1/3\) لكل خيار، إحدى ثلاث حركات: خطوة مع عقارب الساعة، أو البقاء في مكانه، أو خطوة عكس عقارب الساعة. إذا استمرت المطاردة \(T\) جولات حتى أول لقاء، فإن الدفعة لتلك اللعبة تساوي \(T^2\). نرمز إلى متوسط هذه الدفعة عند اختيار موقعي البداية عشوائيًا وبالتساوي بـ \(E_m\)، ثم نعرّف
$$G(n)=\sum_{m=2}^{n} E_m.$$
المطلوب هو حساب هذه الكمية حتى \(n=500\). التنفيذ لا يعتمد على المحاكاة العشوائية، بل يحل معادلات التوقع بدقة لسلسلة المسافة النسبية على الدورة.
الفكرة الجوهرية هي أن المواقع المطلقة لا تهم. ما يحدد العملية فعلًا هو المسافة النسبية على الدورة، ولذلك يمكن اختزال مسألة الشخصين إلى سلسلة ماركوف واحدة على \(\mathbb{Z}_m\).
لتكن \(D_t\in\mathbb{Z}_m\) هي المسافة الموجهة بعد \(t\) جولات. تنتهي المطاردة تمامًا عندما
$$D_t=0.$$
كل لاعب يضيف زيادة من المجموعة \(\{-1,0,+1\}\) باحتمال \(1/3\) لكل عنصر، ولذلك يكون التغير النسبي \(X_t=D_{t+1}-D_t\) موزعًا وفق
$$\mathbb{P}(X_t=0)=\frac13,\qquad \mathbb{P}(X_t=\pm1)=\frac29,\qquad \mathbb{P}(X_t=\pm2)=\frac19.$$
إذًا يعمل مؤثر الانتقال على أي دالة \(f:\mathbb{Z}_m\to\mathbb{R}\) بالشكل
$$ (Pf)(d)=\frac13 f(d)+\frac29\bigl(f(d+1)+f(d-1)\bigr)+\frac19\bigl(f(d+2)+f(d-2)\bigr), $$
مع فهم جميع المؤشرات بترديد \(m\).
بما أن المؤثر دوري من نوع circulant، فإن أنماط فورييه المنفصلة
$$u_k(d)=e^{2\pi i k d/m},\qquad k=0,1,\dots,m-1,$$
هي متجهاته الذاتية. وإذا كتبنا
$$\theta_k=\frac{2\pi k}{m},$$
فإن القيم الذاتية الموافقة هي
$$ \lambda_k=\frac13+\frac29\left(e^{i\theta_k}+e^{-i\theta_k}\right)+\frac19\left(e^{2i\theta_k}+e^{-2i\theta_k}\right) =\frac13+\frac49\cos\theta_k+\frac29\cos(2\theta_k). $$
وهذه هي بالضبط الكميات التي تظهر في المقامات داخل التنفيذ. أما النمط \(k=0\) ففيه \(\lambda_0=1\)، أي إن الدوال الثابتة تقع في نواة \(I-P\)، ولذلك يجب أن تُصاغ كل عملية عكس طيفي بمصدر مجموعُه الكلي يساوي صفرًا.
لتكن \(T_d\) عدد الجولات حتى أول لقاء عندما تكون المسافة الابتدائية \(d\)، ونعرّف
$$a_d=\mathbb{E}[T_d],\qquad a_0=0.$$
عندما تكون المسافة غير صفرية، تمر جولة واحدة ثم تبدأ العملية نفسها من الحالة الجديدة، لذا
$$a_d=1+(Pa)_d\qquad (d\ne0).$$
ولكي نحل هذا على الدورة كلها باستخدام فورييه، نعيد كتابته كمعادلة بواسون ذات مجموع صفري:
$$ (I-P)a=\mathbf{1}-m e_0. $$
بعد حذف النمط الصفري وأخذ الجزء الحقيقي، نحصل على الصيغة
$$ a_d=\sum_{k=1}^{m-1}\frac{1-\cos\left(2\pi k d/m\right)}{1-\lambda_k}. $$
وهذا هو أول مجموع طيفي كبير تحسبه التطبيقات.
الآن نعرّف
$$b_d=\mathbb{E}[T_d^2],\qquad b_0=0.$$
وباستخدام العلاقة \(T_d=1+T_{D_1}\) بعد جولة واحدة، نحصل عندما \(d\ne0\) على
$$ b_d=1+2(Pa)_d+(Pb)_d. $$
ومادام \(a_d=1+(Pa)_d\)، فإن هذا يتبسط إلى
$$ (I-P)b=2a-1 $$
بعيدًا عن الحالة الماصة. ولإجراء الحل الطيفي نحتاج مرة أخرى إلى مصدر مجموعُه صفر، لذلك نضع
$$ c_d=2a_d-1\quad(d\ne0),\qquad c_0=-\sum_{d=1}^{m-1} c_d. $$
ولتكن \(z\) هي الحل وحيد المتوسط الصفري للمعادلة
$$ (I-P)z=c,\qquad \sum_{d=0}^{m-1} z_d=0. $$
عندها يكون
$$b_d=z_d-z_0,$$
ومن ثم يتحقق الشرط \(b_0=0\) تلقائيًا. وإذا كان
$$ \widehat{c}_k=\sum_{d=0}^{m-1} c_d\,e^{-2\pi i k d/m}, $$
فإن متوسط الدفعة لطول دورة ثابت يساوي
$$ E_m=\frac1m\sum_{d=0}^{m-1} b_d =-z_0 =-\frac1m\sum_{k=1}^{m-1}\frac{\widehat{c}_k}{1-\lambda_k}. $$
وهذه بالضبط هي عملية الحل الطيفي الثانية التي تنفذها النسخ الثلاث.
بعد حساب \(E_m\) لطول دورة واحد، تصبح الدالة الكلية ببساطة
$$G(n)=\sum_{m=2}^{n} E_m.$$
وتقوم التطبيقات بحساب هذه القيم مباشرة من \(m=2\) حتى \(m=500\) مع تجميع المجموع التراكمي.
عندما \(m=2\)، لا يوجد إلا نمط فورييه غير تافه واحد وهو \(k=1\)، وفي هذه الحالة
$$ \lambda_1=\frac13+\frac49\cos\pi+\frac29\cos(2\pi)=\frac19, \qquad 1-\lambda_1=\frac89. $$
إذًا يكون العزم الأول عند المسافة \(1\) هو
$$ a_1=\frac{1-\cos\pi}{8/9}=\frac{2}{8/9}=\frac94. $$
ثم نحصل على
$$ c_1=2a_1-1=\frac72, \qquad c_0=-\frac72, $$
ومن ثم يكون معامل فورييه غير الصفري
$$ \widehat{c}_1=c_0-c_1=-7. $$
وبالتالي
$$ E_2=-\frac12\cdot\frac{-7}{8/9}=\frac{63}{16}=3.9375. $$
هذه القيمة هي متوسط \(T^2\) على حالتي البداية الممكنتين \(0\) و\(1\). الحالة \(0\) تعطي مساهمة صفرية لأن المطاردة تكون قد انتهت أصلًا، ولهذا فإن العزم الثاني المشروط على البداية غير التافهة يساوي ضعف هذه القيمة.
تنفذ نسخ C++ وPython وJava الخطة العددية نفسها. فلكل \(m\) تحسب أولًا العوامل الطيفية \(1-\lambda_k\) لكل الأنماط غير الصفرية. بعد ذلك تقيم صيغة العزم الأول بتثبيت نمط واحد في كل مرة وتوليد قوى \(e^{2\pi i k/m}\) تدريجيًا عبر جميع المسافات، وبذلك تتجنب استدعاء الدوال المثلثية من جديد داخل الحلقة الداخلية.
ثم تبني الشفرة المصدر المتوازن لمعادلة العزم الثاني، وتجري له تحويل فورييه منفصلًا مباشرًا، وتقسم كل نمط غير صفري على العامل الطيفي نفسه، ثم تستخرج متوسط الدفعة من الإحداثي الصفري للحل ذي المتوسط الصفري. وبفضل تناظر الأزواج المترافقة، تلغى الأجزاء التخيلية بعضها بعضًا، لذلك يُحتفَظ عدديًا بالجزء الحقيقي فقط. وفي النهاية تُجمع المساهمات من \(m=2\) حتى \(m=500\) ويُطبع الناتج بالصيغة العلمية.
لأي \(m\) ثابت، تجري الشفرة مسحين صريحين عبر الأنماط والمسافات، ولذلك يكون الزمن \(O(m^2)\). أما الذاكرة العاملة فهي \(O(m)\)، لأن ما يُخزَّن في آن واحد هو عدد قليل من المصفوفات بطول \(m\). وعند الجمع على جميع أطوال الدورات من \(2\) إلى \(n\)، نحصل على
$$ \sum_{m=2}^{n} O(m^2)=O(n^3), $$
بينما تكون الذاكرة العظمى \(O(n)\). وبالنسبة إلى الحد المطلوب \(n=500\)، فإن هذه الطريقة الطيفية المباشرة عملية تمامًا.