The quantity of interest is the skewness of a random walk defined by the signed Fibonacci-type recurrence
$$X_0=0,\qquad X_1=1,\qquad X_n=X_{n-1}+\varepsilon_n X_{n-2}\quad(n\ge 2),$$
where each \(\varepsilon_n\) is independently chosen from \(\{-1,+1\}\) with probability \(1/2\). The task is to evaluate the skewness of \(X_{50}\).
A brute-force distribution build would branch over \(2^{49}\) sign histories, which is unnecessary. The implementations avoid enumeration entirely by tracking only the moments that the skewness formula needs.
The key simplification is that skewness depends on the mean, variance, and third central moment. For this walk, those quantities can be extracted from two short linear recurrences.
At every step \(n\ge 2\), the process adds or subtracts the previous-but-one value. This is why the walk is Fibonacci-shaped but random: the deterministic recurrence \(x_n=x_{n-1}+x_{n-2}\) is replaced by a random sign in front of \(x_{n-2}\).
Define the raw moments
$$a_n=\mathbb{E}[X_n^2],\qquad c_n=\mathbb{E}[X_n^3].$$
Once these are known, the skewness follows from standard moment identities.
Because \(\varepsilon_n\) is independent of the past and has mean \(0\),
$$\mathbb{E}[X_n]=\mathbb{E}[X_{n-1}]+\mathbb{E}[\varepsilon_n]\mathbb{E}[X_{n-2}]=\mathbb{E}[X_{n-1}].$$
Starting from \(\mathbb{E}[X_1]=1\), this gives
$$\mathbb{E}[X_n]=1\qquad\text{for all }n\ge 1.$$
This invariant is what turns the variance and the third central moment into the simple expressions
$$\operatorname{Var}(X_n)=a_n-1,\qquad \mu_{3,n}=c_n-3a_n+2.$$
Expand the square:
$$X_n^2=X_{n-1}^2+2\varepsilon_n X_{n-1}X_{n-2}+X_{n-2}^2.$$
Taking expectations kills the mixed term, again because \(\mathbb{E}[\varepsilon_n]=0\). Therefore
$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 2),$$
with initial values
$$a_0=0,\qquad a_1=1.$$
So the second moments are exactly the Fibonacci numbers in the convention \(F_0=0\), \(F_1=1\):
$$a_n=F_n.$$
In particular, the variance is simply \(F_n-1\).
Cubing the step relation gives
$$X_n^3=X_{n-1}^3+3\varepsilon_n X_{n-1}^2X_{n-2}+3X_{n-1}X_{n-2}^2+\varepsilon_n X_{n-2}^3.$$
After taking expectations, the terms with an odd factor of \(\varepsilon_n\) vanish, so
$$c_n=c_{n-1}+3\,\mathbb{E}[X_{n-1}X_{n-2}^2].$$
The remaining mixed moment collapses one step further. Since
$$X_{n-1}=X_{n-2}+\varepsilon_{n-1}X_{n-3},$$
we have
$$\mathbb{E}[X_{n-1}X_{n-2}^2]=\mathbb{E}[X_{n-2}^3]+\mathbb{E}[\varepsilon_{n-1}X_{n-3}X_{n-2}^2]=c_{n-2}.$$
Hence the third raw moment satisfies
$$c_n=c_{n-1}+3c_{n-2}\qquad(n\ge 2),$$
with
$$c_0=0,\qquad c_1=1.$$
The first values are
$$0,1,1,4,7,19,\dots,$$
which already show that the third moment grows faster than the second.
For \(n=5\) there are \(2^3=8\) equally likely sign patterns, because the random choices start at \(n=3\). Enumerating those eight paths gives
$$X_5\in\{5,3,1,1,1,-1,-1,-1\}.$$
From this list,
$$\mathbb{E}[X_5]=1,\qquad \mathbb{E}[X_5^2]=\frac{25+9+1+1+1+1+1+1}{8}=5,$$
and
$$\mathbb{E}[X_5^3]=\frac{125+27+1+1+1-1-1-1}{8}=19.$$
Therefore
$$\operatorname{Var}(X_5)=5-1=4,\qquad \mu_{3,5}=19-3\cdot 5+2=6,$$
so the skewness is
$$\gamma_5=\frac{6}{4^{3/2}}=\frac{6}{8}=0.75.$$
This matches the validation values embedded in the implementations and is a concrete check that the recurrence derivation is correct.
Once \(a_n\) and \(c_n\) are known, the skewness is
$$\gamma_n=\frac{\mu_{3,n}}{\operatorname{Var}(X_n)^{3/2}}=\frac{c_n-3a_n+2}{(a_n-1)^{3/2}}.$$
So the whole problem is reduced to iterating two scalar recurrences up to \(n=50\). No probability table, no path enumeration, and no symbolic distribution are required.
The C++, Python, and Java implementations store only the last two values of the second-moment recurrence and the last two values of the third-moment recurrence. Starting from \((a_0,a_1)=(0,1)\) and \((c_0,c_1)=(0,1)\), each loop step advances both sequences by
$$a_n=a_{n-1}+a_{n-2},\qquad c_n=c_{n-1}+3c_{n-2}.$$
After the loop reaches \(n=50\), the implementation converts the final moment values into the variance \(a_{50}-1\) and the third central moment \(c_{50}-3a_{50}+2\). It then computes \(\sigma=\sqrt{\operatorname{Var}(X_{50})}\) and returns
$$\gamma_{50}=\frac{\mu_{3,50}}{\sigma^3}.$$
There is also a small safety guard: if the variance is non-positive, the result is reported as \(0\). For the actual target \(n=50\), the variance is positive, so the normal skewness formula is used.
The running time is \(O(n)\), because the implementation performs one constant-cost recurrence update for each \(n\) from 2 through 50. The memory usage is \(O(1)\), because only a fixed number of scalar values are stored.
This is dramatically smaller than building the full distribution, which would branch into \(2^{n-2}\) equally likely sign histories. The moment method succeeds because skewness depends on only a few aggregated statistics, and those statistics obey closed recurrences.
Gesucht ist die Schiefe eines Zufallswegs, der durch die vorzeichenbehaftete Fibonacci-Rekursion
$$X_0=0,\qquad X_1=1,\qquad X_n=X_{n-1}+\varepsilon_n X_{n-2}\quad(n\ge 2)$$
definiert ist. Dabei wird jedes \(\varepsilon_n\) unabhängig mit Wahrscheinlichkeit \(1/2\) als \(-1\) oder \(+1\) gewählt. Bestimmt werden soll die Schiefe von \(X_{50}\).
Ein direkter Aufbau der Verteilung würde \(2^{49}\) verschiedene Vorzeichenfolgen verzweigen und ist unnötig teuer. Die Implementierungen berechnen stattdessen nur die Momente, die in der Schiefeformel tatsächlich vorkommen.
Der entscheidende Punkt ist, dass Schiefe nur vom Erwartungswert, von der Varianz und vom dritten zentralen Moment abhängt. Für diesen Zufallsweg lassen sich genau diese Größen durch zwei kurze lineare Rekurrenzen erfassen.
Ab Schritt \(n\ge 2\) wird entweder \(X_{n-2}\) addiert oder subtrahiert. Dadurch bleibt die Fibonacci-Struktur erhalten, aber jede neue Stufe enthält eine zufällige Richtungsentscheidung.
Wir definieren die rohen Momente durch
$$a_n=\mathbb{E}[X_n^2],\qquad c_n=\mathbb{E}[X_n^3].$$
Sobald diese beiden Folgen bekannt sind, lässt sich die Schiefe direkt berechnen.
Da \(\varepsilon_n\) vom bisherigen Verlauf unabhängig ist und Mittelwert \(0\) hat, gilt
$$\mathbb{E}[X_n]=\mathbb{E}[X_{n-1}]+\mathbb{E}[\varepsilon_n]\mathbb{E}[X_{n-2}]=\mathbb{E}[X_{n-1}].$$
Mit \(\mathbb{E}[X_1]=1\) folgt induktiv
$$\mathbb{E}[X_n]=1\qquad\text{für alle }n\ge 1.$$
Damit werden Varianz und drittes zentrales Moment zu
$$\operatorname{Var}(X_n)=a_n-1,\qquad \mu_{3,n}=c_n-3a_n+2.$$
Quadriert man die Schrittgleichung, so erhält man
$$X_n^2=X_{n-1}^2+2\varepsilon_n X_{n-1}X_{n-2}+X_{n-2}^2.$$
Beim Erwartungswert verschwindet der gemischte Term, weil \(\mathbb{E}[\varepsilon_n]=0\). Also gilt
$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 2),$$
mit Anfangswerten
$$a_0=0,\qquad a_1=1.$$
Die Folge der zweiten Momente ist damit genau die Fibonacci-Folge in der Konvention \(F_0=0\), \(F_1=1\):
$$a_n=F_n.$$
Insbesondere ist die Varianz gleich \(F_n-1\).
Aus der Kubikentwicklung folgt
$$X_n^3=X_{n-1}^3+3\varepsilon_n X_{n-1}^2X_{n-2}+3X_{n-1}X_{n-2}^2+\varepsilon_n X_{n-2}^3.$$
Nach dem Mitteln bleiben nur die Terme ohne ungerade Potenzen von \(\varepsilon_n\):
$$c_n=c_{n-1}+3\,\mathbb{E}[X_{n-1}X_{n-2}^2].$$
Der verbleibende Mischterm reduziert sich noch einmal, denn aus
$$X_{n-1}=X_{n-2}+\varepsilon_{n-1}X_{n-3}$$
folgt
$$\mathbb{E}[X_{n-1}X_{n-2}^2]=\mathbb{E}[X_{n-2}^3]+\mathbb{E}[\varepsilon_{n-1}X_{n-3}X_{n-2}^2]=c_{n-2}.$$
Damit erhält man
$$c_n=c_{n-1}+3c_{n-2}\qquad(n\ge 2),$$
mit
$$c_0=0,\qquad c_1=1.$$
Die ersten Werte sind
$$0,1,1,4,7,19,\dots,$$
also wächst der dritte Moment deutlich schneller als der zweite.
Für \(n=5\) gibt es \(2^3=8\) gleich wahrscheinliche Vorzeichenmuster, weil die Zufallsentscheidungen erst bei \(n=3\) beginnen. Die acht Pfade liefern
$$X_5\in\{5,3,1,1,1,-1,-1,-1\}.$$
Daraus folgt
$$\mathbb{E}[X_5]=1,\qquad \mathbb{E}[X_5^2]=\frac{25+9+1+1+1+1+1+1}{8}=5,$$
und
$$\mathbb{E}[X_5^3]=\frac{125+27+1+1+1-1-1-1}{8}=19.$$
Somit gilt
$$\operatorname{Var}(X_5)=5-1=4,\qquad \mu_{3,5}=19-3\cdot 5+2=6,$$
also
$$\gamma_5=\frac{6}{4^{3/2}}=\frac{6}{8}=0.75.$$
Genau diese Werte werden auch in den eingebauten Prüfungen der Implementierungen verwendet.
Sobald \(a_n\) und \(c_n\) bekannt sind, ist die Schiefe
$$\gamma_n=\frac{\mu_{3,n}}{\operatorname{Var}(X_n)^{3/2}}=\frac{c_n-3a_n+2}{(a_n-1)^{3/2}}.$$
Das gesamte Problem reduziert sich also auf zwei skalare Rekurrenzen bis \(n=50\). Weder eine vollständige Verteilung noch eine Pfadaufzählung ist nötig.
Die C++-, Python- und Java-Implementierungen speichern nur die letzten zwei Werte der Rekurrenz für den zweiten Moment und die letzten zwei Werte der Rekurrenz für den dritten Moment. Ausgehend von \((a_0,a_1)=(0,1)\) und \((c_0,c_1)=(0,1)\) wird in jedem Schleifendurchlauf mit
$$a_n=a_{n-1}+a_{n-2},\qquad c_n=c_{n-1}+3c_{n-2}$$
auf den nächsten Zustand fortgeschrieben.
Nach Erreichen von \(n=50\) formt die Implementierung die Endwerte in die Varianz \(a_{50}-1\) und in das dritte zentrale Moment \(c_{50}-3a_{50}+2\) um. Anschließend wird \(\sigma=\sqrt{\operatorname{Var}(X_{50})}\) berechnet und
$$\gamma_{50}=\frac{\mu_{3,50}}{\sigma^3}$$
ausgegeben. Zusätzlich gibt es eine kleine Schutzabfrage: Falls die Varianz nicht positiv ist, wird \(0\) zurückgegeben. Für das eigentliche Ziel \(n=50\) tritt dieser Sonderfall nicht ein.
Die Laufzeit ist \(O(n)\), weil für jedes \(n\) von 2 bis 50 genau ein Rekurrenzschritt mit konstantem Aufwand ausgeführt wird. Der Speicherverbrauch ist \(O(1)\), denn es werden nur wenige skalare Werte gehalten.
Das ist wesentlich kleiner als ein expliziter Verteilungsaufbau mit \(2^{n-2}\) möglichen Vorzeichenfolgen. Die Momentenmethode funktioniert hier deshalb so gut, weil die Schiefe nur von einigen aggregierten Größen abhängt und diese Größen selbst wieder lineare Rekurrenzen erfüllen.
İlgilenilen nicelik, şu işaretli Fibonacci tipi yürüyüşün çarpıklığıdır:
$$X_0=0,\qquad X_1=1,\qquad X_n=X_{n-1}+\varepsilon_n X_{n-2}\quad(n\ge 2).$$
Burada her \(\varepsilon_n\), \(\{-1,+1\}\) kümesinden bağımsız ve eşit olasılıkla seçilir. İstenen değer \(X_{50}\)'nin çarpıklığıdır.
Dağılımı doğrudan kurmaya çalışmak \(2^{49}\) farklı işaret geçmişini dallandırmak demektir. Uygulamalar bunu yapmaz; yalnızca çarpıklık formülü için gerçekten gereken momentleri izler.
Temel fikir şu: çarpıklık yalnızca ortalama, varyans ve üçüncü merkezî momentten oluşur. Bu yürüyüş için bu nicelikler iki kısa lineer bağıntıdan çıkarılabilir.
\(n\ge 2\) adımlarında süreç, iki adım önceki değeri ya ekler ya çıkarır. Bu yüzden yapı Fibonacci benzeridir; fakat her adımda yeni bir rastgele yön seçimi bulunduğu için tam deterministik değildir.
Ham momentleri
$$a_n=\mathbb{E}[X_n^2],\qquad c_n=\mathbb{E}[X_n^3]$$
şeklinde tanımlayalım. Bu iki dizi bilindiğinde çarpıklık doğrudan elde edilir.
\(\varepsilon_n\) geçmişten bağımsızdır ve ortalaması \(0\)'dır. Dolayısıyla
$$\mathbb{E}[X_n]=\mathbb{E}[X_{n-1}]+\mathbb{E}[\varepsilon_n]\mathbb{E}[X_{n-2}]=\mathbb{E}[X_{n-1}].$$
\(\mathbb{E}[X_1]=1\) olduğundan
$$\mathbb{E}[X_n]=1\qquad\text{tüm }n\ge 1\text{ için}$$
sonucuna ulaşılır. Bu değişmez, varyans ve üçüncü merkezî momenti
$$\operatorname{Var}(X_n)=a_n-1,\qquad \mu_{3,n}=c_n-3a_n+2$$
biçimine indirger.
Kare açılımı
$$X_n^2=X_{n-1}^2+2\varepsilon_n X_{n-1}X_{n-2}+X_{n-2}^2$$
şeklindedir. Beklenti alınca orta terim \(\mathbb{E}[\varepsilon_n]=0\) nedeniyle yok olur. Böylece
$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 2)$$
elde edilir; başlangıç değerleri de
$$a_0=0,\qquad a_1=1$$
olur. Demek ki ikinci momentler, \(F_0=0\), \(F_1=1\) konvansiyonundaki Fibonacci sayılarıdır:
$$a_n=F_n.$$
Dolayısıyla varyans yalnızca \(F_n-1\)'dir.
Küp açılımı bize
$$X_n^3=X_{n-1}^3+3\varepsilon_n X_{n-1}^2X_{n-2}+3X_{n-1}X_{n-2}^2+\varepsilon_n X_{n-2}^3$$
ifadesini verir. Beklenti alınca \(\varepsilon_n\)'nin tek kuvvetli olduğu terimler yok olur ve
$$c_n=c_{n-1}+3\,\mathbb{E}[X_{n-1}X_{n-2}^2]$$
kalır. Karışık moment bir adım daha sadeleşir; çünkü
$$X_{n-1}=X_{n-2}+\varepsilon_{n-1}X_{n-3}$$
olduğundan
$$\mathbb{E}[X_{n-1}X_{n-2}^2]=\mathbb{E}[X_{n-2}^3]+\mathbb{E}[\varepsilon_{n-1}X_{n-3}X_{n-2}^2]=c_{n-2}.$$
Sonuç olarak
$$c_n=c_{n-1}+3c_{n-2}\qquad(n\ge 2)$$
ve başlangıç koşulları
$$c_0=0,\qquad c_1=1$$
olur. İlk birkaç değer
$$0,1,1,4,7,19,\dots$$
şeklindedir; yani üçüncü moment ikinci momentten daha hızlı büyür.
\(n=5\) için rastgele seçimler \(n=3\)'te başladığından \(2^3=8\) eş olasılıklı işaret dizisi vardır. Bu sekiz yolun sonunda
$$X_5\in\{5,3,1,1,1,-1,-1,-1\}$$
elde edilir. Buradan
$$\mathbb{E}[X_5]=1,\qquad \mathbb{E}[X_5^2]=\frac{25+9+1+1+1+1+1+1}{8}=5,$$
ve
$$\mathbb{E}[X_5^3]=\frac{125+27+1+1+1-1-1-1}{8}=19$$
hesaplanır. O halde
$$\operatorname{Var}(X_5)=5-1=4,\qquad \mu_{3,5}=19-3\cdot 5+2=6,$$
dolayısıyla çarpıklık
$$\gamma_5=\frac{6}{4^{3/2}}=\frac{6}{8}=0.75$$
olur. Bu örnek, uygulamalardaki doğrulama değerleriyle birebir uyumludur.
\(a_n\) ve \(c_n\) bilindiğinde çarpıklık
$$\gamma_n=\frac{\mu_{3,n}}{\operatorname{Var}(X_n)^{3/2}}=\frac{c_n-3a_n+2}{(a_n-1)^{3/2}}$$
formülüyle bulunur. Böylece bütün problem, \(n=50\)'ye kadar iki skaler bağıntıyı yürütmeye indirgenir; tam dağılımı kurmaya gerek yoktur.
C++, Python ve Java uygulamaları ikinci moment bağıntısının son iki terimini ve üçüncü moment bağıntısının son iki terimini tutar. \((a_0,a_1)=(0,1)\) ve \((c_0,c_1)=(0,1)\) başlangıçlarından sonra her döngü adımı
$$a_n=a_{n-1}+a_{n-2},\qquad c_n=c_{n-1}+3c_{n-2}$$
güncellemesini yapar.
Döngü \(n=50\)'ye ulaştığında son değerler, varyans \(a_{50}-1\) ve üçüncü merkezî moment \(c_{50}-3a_{50}+2\) biçimine çevrilir. Sonra \(\sigma=\sqrt{\operatorname{Var}(X_{50})}\) hesaplanır ve
$$\gamma_{50}=\frac{\mu_{3,50}}{\sigma^3}$$
üretilir. Ek olarak küçük bir koruma vardır: varyans pozitif değilse çıktı \(0\) yapılır. Gerçek hedef olan \(n=50\) için bu durum oluşmaz.
Çalışma süresi \(O(n)\)'dir; çünkü 2'den 50'ye kadar her adımda sabit maliyetli tek bir güncelleme yapılır. Bellek kullanımı \(O(1)\)'dir; çünkü yalnızca sabit sayıda skaler saklanır.
Bu yaklaşım, \(2^{n-2}\) olası işaret geçmişini açan doğrudan dağılım yönteminden çok daha küçüktür. Moment yaklaşımı burada etkilidir; çünkü çarpıklık yalnızca birkaç özet niceliğe bağlıdır ve bu niceliklerin her biri kapalı bir rekürans taşır.
La cantidad buscada es la asimetría de una caminata aleatoria definida por la recurrencia de tipo Fibonacci con signo
$$X_0=0,\qquad X_1=1,\qquad X_n=X_{n-1}+\varepsilon_n X_{n-2}\quad(n\ge 2),$$
donde cada \(\varepsilon_n\) se elige de forma independiente en \(\{-1,+1\}\) con probabilidad \(1/2\). El objetivo es hallar la asimetría de \(X_{50}\).
Construir la distribución completa por fuerza bruta implicaría ramificar \(2^{49}\) historias de signos distintas. Las implementaciones evitan esa explosión y siguen únicamente los momentos necesarios para la fórmula de skewness.
La simplificación central es que la asimetría depende solo de la media, la varianza y el tercer momento central. Para esta caminata, esas cantidades salen de dos recurrencias lineales muy cortas.
En cada paso \(n\ge 2\), el proceso suma o resta el valor de dos pasos atrás. Por eso la forma básica sigue siendo Fibonacci, pero cada nivel incorpora una decisión aleatoria de dirección.
Definimos los momentos brutos
$$a_n=\mathbb{E}[X_n^2],\qquad c_n=\mathbb{E}[X_n^3].$$
Una vez conocidos, la asimetría sale directamente.
Como \(\varepsilon_n\) es independiente del pasado y tiene media \(0\),
$$\mathbb{E}[X_n]=\mathbb{E}[X_{n-1}]+\mathbb{E}[\varepsilon_n]\mathbb{E}[X_{n-2}]=\mathbb{E}[X_{n-1}].$$
Puesto que \(\mathbb{E}[X_1]=1\), se obtiene
$$\mathbb{E}[X_n]=1\qquad\text{para todo }n\ge 1.$$
Ese invariante convierte la varianza y el tercer momento central en
$$\operatorname{Var}(X_n)=a_n-1,\qquad \mu_{3,n}=c_n-3a_n+2.$$
Al expandir el cuadrado aparece
$$X_n^2=X_{n-1}^2+2\varepsilon_n X_{n-1}X_{n-2}+X_{n-2}^2.$$
Al tomar esperanza, el término mixto desaparece porque \(\mathbb{E}[\varepsilon_n]=0\). Por tanto
$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 2),$$
con condiciones iniciales
$$a_0=0,\qquad a_1=1.$$
Así, los segundos momentos coinciden exactamente con los números de Fibonacci en la convención \(F_0=0\), \(F_1=1\):
$$a_n=F_n.$$
En particular, la varianza es simplemente \(F_n-1\).
La expansión cúbica da
$$X_n^3=X_{n-1}^3+3\varepsilon_n X_{n-1}^2X_{n-2}+3X_{n-1}X_{n-2}^2+\varepsilon_n X_{n-2}^3.$$
Al promediar, los términos con una potencia impar de \(\varepsilon_n\) se anulan y queda
$$c_n=c_{n-1}+3\,\mathbb{E}[X_{n-1}X_{n-2}^2].$$
Ese momento mixto se reduce un paso más. Como
$$X_{n-1}=X_{n-2}+\varepsilon_{n-1}X_{n-3},$$
tenemos
$$\mathbb{E}[X_{n-1}X_{n-2}^2]=\mathbb{E}[X_{n-2}^3]+\mathbb{E}[\varepsilon_{n-1}X_{n-3}X_{n-2}^2]=c_{n-2}.$$
Por eso
$$c_n=c_{n-1}+3c_{n-2}\qquad(n\ge 2),$$
con
$$c_0=0,\qquad c_1=1.$$
Los primeros términos son
$$0,1,1,4,7,19,\dots,$$
lo que muestra que el tercer momento crece más deprisa que el segundo.
Para \(n=5\) hay \(2^3=8\) patrones de signos equiprobables, porque las elecciones aleatorias empiezan en \(n=3\). Al enumerarlos se obtiene
$$X_5\in\{5,3,1,1,1,-1,-1,-1\}.$$
Entonces
$$\mathbb{E}[X_5]=1,\qquad \mathbb{E}[X_5^2]=\frac{25+9+1+1+1+1+1+1}{8}=5,$$
y
$$\mathbb{E}[X_5^3]=\frac{125+27+1+1+1-1-1-1}{8}=19.$$
Por consiguiente,
$$\operatorname{Var}(X_5)=5-1=4,\qquad \mu_{3,5}=19-3\cdot 5+2=6,$$
de modo que
$$\gamma_5=\frac{6}{4^{3/2}}=\frac{6}{8}=0.75.$$
Ese ejemplo coincide con las comprobaciones de validación incluidas en las implementaciones.
Una vez conocidos \(a_n\) y \(c_n\), la asimetría es
$$\gamma_n=\frac{\mu_{3,n}}{\operatorname{Var}(X_n)^{3/2}}=\frac{c_n-3a_n+2}{(a_n-1)^{3/2}}.$$
Así, todo el problema queda reducido a iterar dos recurrencias escalares hasta \(n=50\). No hace falta construir la distribución completa ni recorrer todos los caminos.
Las implementaciones en C++, Python y Java guardan solo los dos últimos valores de la recurrencia del segundo momento y los dos últimos valores de la recurrencia del tercer momento. Partiendo de \((a_0,a_1)=(0,1)\) y \((c_0,c_1)=(0,1)\), cada iteración actualiza ambas secuencias con
$$a_n=a_{n-1}+a_{n-2},\qquad c_n=c_{n-1}+3c_{n-2}.$$
Al terminar el bucle en \(n=50\), la implementación transforma esos valores en la varianza \(a_{50}-1\) y el tercer momento central \(c_{50}-3a_{50}+2\). Luego calcula \(\sigma=\sqrt{\operatorname{Var}(X_{50})}\) y devuelve
$$\gamma_{50}=\frac{\mu_{3,50}}{\sigma^3}.$$
También hay una protección pequeña: si la varianza no es positiva, el resultado se fija en \(0\). Para el caso real \(n=50\), la varianza sí es positiva.
El tiempo de ejecución es \(O(n)\), porque desde 2 hasta 50 solo se hace una actualización de costo constante por paso. El uso de memoria es \(O(1)\), ya que únicamente se mantienen unos pocos escalares.
Esto es muchísimo menor que construir la distribución completa, lo cual ramificaría \(2^{n-2}\) historias de signos equiprobables. El método de momentos funciona porque la asimetría depende solo de unas pocas estadísticas agregadas y esas estadísticas obedecen recurrencias cerradas.
题目关注的是下面这个随机游走在第 \(50\) 步时的偏度：
$$X_0=0,\qquad X_1=1,\qquad X_n=X_{n-1}+\varepsilon_n X_{n-2}\quad(n\ge 2),$$
其中每个 \(\varepsilon_n\) 都独立地以概率 \(1/2\) 取 \(-1\) 或 \(+1\)。也就是说，每一步都会把前两步中的较早那一项随机地加上去或减掉。要求的是 \(X_{50}\) 的 skewness，也就是偏度。
如果直接枚举分布，那么从 \(n=2\) 到 \(n=50\) 一共会出现 \(2^{49}\) 条符号路径，规模完全没有必要。三个实现都没有展开整张概率表，而是只追踪偏度公式真正需要的矩。
偏度只依赖于均值、方差和三阶中心矩。对这个带随机符号的 Fibonacci 型游走来说，这些量并不需要通过完整分布得到，而是可以从两个很短的线性递推直接推出。
普通 Fibonacci 递推是 \(x_n=x_{n-1}+x_{n-2}\)。这里的区别在于，\(x_{n-2}\) 前面的符号每一步都随机变化，所以过程既保留了 Fibonacci 的结构，又带有真正的随机性。
记二阶和三阶原始矩为
$$a_n=\mathbb{E}[X_n^2],\qquad c_n=\mathbb{E}[X_n^3].$$
只要把这两个序列算出来，偏度就能直接写出。
由于 \(\varepsilon_n\) 与过去独立，并且 \(\mathbb{E}[\varepsilon_n]=0\)，所以
$$\mathbb{E}[X_n]=\mathbb{E}[X_{n-1}]+\mathbb{E}[\varepsilon_n]\mathbb{E}[X_{n-2}]=\mathbb{E}[X_{n-1}].$$
而初值满足 \(\mathbb{E}[X_1]=1\)，因此对所有 \(n\ge 1\) 都有
$$\mathbb{E}[X_n]=1.$$
这个不变量非常关键，因为它立刻把方差和三阶中心矩化成
$$\operatorname{Var}(X_n)=a_n-1,\qquad \mu_{3,n}=c_n-3a_n+2.$$
换句话说，只要知道二阶原始矩和三阶原始矩，就已经足够了。
把递推式平方：
$$X_n^2=X_{n-1}^2+2\varepsilon_n X_{n-1}X_{n-2}+X_{n-2}^2.$$
取期望以后，中间项会消失，因为 \(\varepsilon_n\) 的均值为 \(0\)。于是得到
$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 2),$$
初值为
$$a_0=0,\qquad a_1=1.$$
这说明 \(a_n\) 正好就是 Fibonacci 数列：
$$a_n=F_n\qquad(F_0=0,\;F_1=1).$$
因此方差的表达式非常干净：
$$\operatorname{Var}(X_n)=F_n-1.$$
把同一个递推式立方，可以得到
$$X_n^3=X_{n-1}^3+3\varepsilon_n X_{n-1}^2X_{n-2}+3X_{n-1}X_{n-2}^2+\varepsilon_n X_{n-2}^3.$$
对两边取期望后，所有带有 \(\varepsilon_n\) 奇次幂的项都会消失，所以
$$c_n=c_{n-1}+3\,\mathbb{E}[X_{n-1}X_{n-2}^2].$$
现在真正的关键点在于，这个混合项还能继续塌缩。因为
$$X_{n-1}=X_{n-2}+\varepsilon_{n-1}X_{n-3},$$
于是
$$\mathbb{E}[X_{n-1}X_{n-2}^2]=\mathbb{E}[X_{n-2}^3]+\mathbb{E}[\varepsilon_{n-1}X_{n-3}X_{n-2}^2]=c_{n-2}.$$
因此三阶原始矩满足
$$c_n=c_{n-1}+3c_{n-2}\qquad(n\ge 2),$$
并且
$$c_0=0,\qquad c_1=1.$$
前几项是
$$0,1,1,4,7,19,\dots,$$
可以看出它的增长比二阶矩更快，这也是偏度在后面会明显变大的根源。
当 \(n=5\) 时，随机选择只发生在 \(n=3,4,5\) 三个位置，所以一共有 \(2^3=8\) 条等概率路径。把这八种情况全部列出来，最终值恰好是
$$X_5\in\{5,3,1,1,1,-1,-1,-1\}.$$
于是均值为
$$\mathbb{E}[X_5]=1,$$
二阶矩为
$$\mathbb{E}[X_5^2]=\frac{25+9+1+1+1+1+1+1}{8}=5,$$
三阶矩为
$$\mathbb{E}[X_5^3]=\frac{125+27+1+1+1-1-1-1}{8}=19.$$
所以
$$\operatorname{Var}(X_5)=5-1=4,\qquad \mu_{3,5}=19-3\cdot 5+2=6,$$
最后得到
$$\gamma_5=\frac{6}{4^{3/2}}=\frac{6}{8}=0.75.$$
这个例子一方面说明了递推公式确实正确，另一方面也和实现中的校验数值完全一致。
一旦 \(a_n\) 与 \(c_n\) 算出，偏度就由
$$\gamma_n=\frac{\mu_{3,n}}{\operatorname{Var}(X_n)^{3/2}}=\frac{c_n-3a_n+2}{(a_n-1)^{3/2}}$$
直接给出。因此整道题最终只剩下“把两个递推做 \(50\) 步”这一件事，不需要维护任何完整分布。
C++、Python 和 Java 三个实现都只保存二阶矩递推的最后两项，以及三阶矩递推的最后两项。初值是 \((a_0,a_1)=(0,1)\) 和 \((c_0,c_1)=(0,1)\)，之后每次循环同时更新
$$a_n=a_{n-1}+a_{n-2},\qquad c_n=c_{n-1}+3c_{n-2}.$$
当循环推进到 \(n=50\) 时，实现把最终矩转换成方差 \(a_{50}-1\) 和三阶中心矩 \(c_{50}-3a_{50}+2\)，再计算 \(\sigma=\sqrt{\operatorname{Var}(X_{50})}\)，输出
$$\gamma_{50}=\frac{\mu_{3,50}}{\sigma^3}.$$
代码里还带有一个很小的保护分支：如果方差不是正数，就直接返回 \(0\)。这只会影响最早的退化步数，对真正要求的 \(n=50\) 没有影响。
时间复杂度是 \(O(n)\)，因为从 2 到 50 每一步只做常数次整数更新和最后一次平方根计算。空间复杂度是 \(O(1)\)，因为始终只保留固定数量的标量。
相比之下，如果显式枚举全部分布，就会出现 \(2^{n-2}\) 条等概率符号路径。矩递推方法之所以高效，是因为偏度只依赖少数聚合统计量，而这些统计量本身又满足封闭的线性递推。
Нужно найти коэффициент асимметрии для случайного блуждания, заданного рекуррентным соотношением типа Фибоначчи с случайным знаком:
$$X_0=0,\qquad X_1=1,\qquad X_n=X_{n-1}+\varepsilon_n X_{n-2}\quad(n\ge 2),$$
где каждое \(\varepsilon_n\) независимо принимает значения \(-1\) и \(+1\) с вероятностью \(1/2\). Требуется асимметрия величины \(X_{50}\).
Если строить полное распределение напрямую, пришлось бы рассматривать \(2^{49}\) различных последовательностей знаков. Реальные реализации этого не делают: они отслеживают только те моменты, которые действительно входят в формулу skewness.
Коэффициент асимметрии зависит только от математического ожидания, дисперсии и третьего центрального момента. Для данного процесса все эти величины можно получить из двух коротких линейных рекуррентных соотношений.
На каждом шаге \(n\ge 2\) к предыдущему значению либо прибавляется, либо вычитается значение двухшаговой давности. Поэтому форма рекурсии остается фибоначчиевой, но каждое новое состояние зависит от случайного выбора направления.
Обозначим сырые моменты через
$$a_n=\mathbb{E}[X_n^2],\qquad c_n=\mathbb{E}[X_n^3].$$
Как только эти две последовательности найдены, асимметрия получается напрямую.
Так как \(\varepsilon_n\) независимо от прошлого и \(\mathbb{E}[\varepsilon_n]=0\), имеем
$$\mathbb{E}[X_n]=\mathbb{E}[X_{n-1}]+\mathbb{E}[\varepsilon_n]\mathbb{E}[X_{n-2}]=\mathbb{E}[X_{n-1}].$$
Поскольку \(\mathbb{E}[X_1]=1\), отсюда следует
$$\mathbb{E}[X_n]=1\qquad\text{для всех }n\ge 1.$$
Этот инвариант сразу упрощает формулы для дисперсии и третьего центрального момента:
$$\operatorname{Var}(X_n)=a_n-1,\qquad \mu_{3,n}=c_n-3a_n+2.$$
Квадрат шага раскладывается так:
$$X_n^2=X_{n-1}^2+2\varepsilon_n X_{n-1}X_{n-2}+X_{n-2}^2.$$
После взятия ожидания смешанный член исчезает, потому что \(\mathbb{E}[\varepsilon_n]=0\). Значит,
$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 2),$$
при начальных значениях
$$a_0=0,\qquad a_1=1.$$
Итак, второй момент совпадает с числами Фибоначчи в нормировке \(F_0=0\), \(F_1=1\):
$$a_n=F_n.$$
Следовательно, дисперсия равна \(F_n-1\).
Кубическая формула имеет вид
$$X_n^3=X_{n-1}^3+3\varepsilon_n X_{n-1}^2X_{n-2}+3X_{n-1}X_{n-2}^2+\varepsilon_n X_{n-2}^3.$$
После усреднения все члены с нечетной степенью \(\varepsilon_n\) пропадают, и остается
$$c_n=c_{n-1}+3\,\mathbb{E}[X_{n-1}X_{n-2}^2].$$
Здесь важен следующий шаг. Из равенства
$$X_{n-1}=X_{n-2}+\varepsilon_{n-1}X_{n-3}$$
получаем
$$\mathbb{E}[X_{n-1}X_{n-2}^2]=\mathbb{E}[X_{n-2}^3]+\mathbb{E}[\varepsilon_{n-1}X_{n-3}X_{n-2}^2]=c_{n-2}.$$
Значит, третий сырой момент удовлетворяет рекурсии
$$c_n=c_{n-1}+3c_{n-2}\qquad(n\ge 2),$$
с начальными условиями
$$c_0=0,\qquad c_1=1.$$
Первые значения равны
$$0,1,1,4,7,19,\dots,$$
и уже видно, что рост здесь быстрее, чем у второго момента.
При \(n=5\) случайные выборы происходят на шагах \(3,4,5\), поэтому всего существует \(2^3=8\) равновероятных траекторий. Полный перебор дает набор значений
$$X_5\in\{5,3,1,1,1,-1,-1,-1\}.$$
Отсюда
$$\mathbb{E}[X_5]=1,\qquad \mathbb{E}[X_5^2]=\frac{25+9+1+1+1+1+1+1}{8}=5,$$
и
$$\mathbb{E}[X_5^3]=\frac{125+27+1+1+1-1-1-1}{8}=19.$$
Следовательно,
$$\operatorname{Var}(X_5)=5-1=4,\qquad \mu_{3,5}=19-3\cdot 5+2=6,$$
а значит
$$\gamma_5=\frac{6}{4^{3/2}}=\frac{6}{8}=0.75.$$
Именно эти значения используются как контрольная проверка внутри реализаций.
Как только найдены \(a_n\) и \(c_n\), коэффициент асимметрии равен
$$\gamma_n=\frac{\mu_{3,n}}{\operatorname{Var}(X_n)^{3/2}}=\frac{c_n-3a_n+2}{(a_n-1)^{3/2}}.$$
Значит, вся задача сводится к вычислению двух скалярных рекуррентных последовательностей до \(n=50\). Никакого хранения полного распределения не требуется.
Реализации на C++, Python и Java хранят только последние два значения рекурсии для второго момента и последние два значения рекурсии для третьего момента. Начиная с \((a_0,a_1)=(0,1)\) и \((c_0,c_1)=(0,1)\), каждый шаг цикла выполняет обновления
$$a_n=a_{n-1}+a_{n-2},\qquad c_n=c_{n-1}+3c_{n-2}.$$
После достижения \(n=50\) программа преобразует полученные моменты в дисперсию \(a_{50}-1\) и третий центральный момент \(c_{50}-3a_{50}+2\). Затем вычисляется \(\sigma=\sqrt{\operatorname{Var}(X_{50})}\) и возвращается
$$\gamma_{50}=\frac{\mu_{3,50}}{\sigma^3}.$$
Также предусмотрена небольшая защита: если дисперсия не положительна, результатом становится \(0\). Для нужного значения \(n=50\) этот вырожденный случай не возникает.
Временная сложность равна \(O(n)\), потому что от 2 до 50 выполняется по одному обновлению постоянной стоимости на шаг. Память равна \(O(1)\), поскольку сохраняется только фиксированное число скаляров.
Это несравнимо дешевле, чем явный перебор полного распределения с \(2^{n-2}\) равновероятными последовательностями знаков. Метод моментов работает эффективно именно потому, что коэффициент асимметрии зависит лишь от немногих агрегированных величин, а сами эти величины удовлетворяют замкнутым рекуррентным формулам.
الكمية المطلوبة هي معامل الالتواء لمسير عشوائي يُعطى بالعلاقة الشبيهة بفيبوناتشي ذات الإشارة العشوائية
$$X_0=0,\qquad X_1=1,\qquad X_n=X_{n-1}+\varepsilon_n X_{n-2}\quad(n\ge 2),$$
حيث إن كل \(\varepsilon_n\) يُختار مستقلًا من \(\{-1,+1\}\) باحتمال \(1/2\) لكل قيمة. المطلوب هو حساب التواء \(X_{50}\).
بناء التوزيع كاملًا بطريقة مباشرة يعني تتبّع \(2^{49}\) تاريخًا مختلفًا للإشارات، وهذا غير ضروري. التنفيذات الثلاثة تتجنب ذلك تمامًا، وتكتفي بمتابعة العزوم التي تدخل فعلًا في صيغة الالتواء.
الفكرة الأساسية هي أن الالتواء يعتمد فقط على المتوسط والتباين والعزم المركزي الثالث. وفي هذا المسير يمكن استخراج هذه الكميات من علاقتين عوديتين قصيرتين.
في كل خطوة \(n\ge 2\) نأخذ قيمة الخطوة السابقة ثم نضيف أو نطرح قيمة الخطوة التي قبلها بخطوتين. لذلك تبقى البنية من نوع فيبوناتشي، لكن كل مستوى يحمل قرارًا عشوائيًا جديدًا في الإشارة.
لنعرّف العزمين الخامين
$$a_n=\mathbb{E}[X_n^2],\qquad c_n=\mathbb{E}[X_n^3].$$
بمجرد معرفة هاتين السلسلتين يصبح حساب الالتواء مباشرًا.
لأن \(\varepsilon_n\) مستقل عن الماضي ومتوسطه يساوي \(0\)، فإن
$$\mathbb{E}[X_n]=\mathbb{E}[X_{n-1}]+\mathbb{E}[\varepsilon_n]\mathbb{E}[X_{n-2}]=\mathbb{E}[X_{n-1}].$$
ومع \(\mathbb{E}[X_1]=1\) نحصل على
$$\mathbb{E}[X_n]=1\qquad(n\ge 1).$$
هذا الثابت هو ما يجعل صيغتي التباين والعزم المركزي الثالث في غاية البساطة:
$$\operatorname{Var}(X_n)=a_n-1,\qquad \mu_{3,n}=c_n-3a_n+2.$$
بتربيع علاقة الانتقال نحصل على
$$X_n^2=X_{n-1}^2+2\varepsilon_n X_{n-1}X_{n-2}+X_{n-2}^2.$$
وعند أخذ التوقع يختفي الحد المختلط لأن \(\mathbb{E}[\varepsilon_n]=0\). لذلك
$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 2),$$
مع القيم الابتدائية
$$a_0=0,\qquad a_1=1.$$
إذن العزم الثاني يطابق أعداد فيبوناتشي تمامًا وفق الاصطلاح \(F_0=0\)، \(F_1=1\):
$$a_n=F_n.$$
ومن ثم يكون التباين ببساطة
$$\operatorname{Var}(X_n)=F_n-1.$$
أما التكعيب فيعطي
$$X_n^3=X_{n-1}^3+3\varepsilon_n X_{n-1}^2X_{n-2}+3X_{n-1}X_{n-2}^2+\varepsilon_n X_{n-2}^3.$$
بعد أخذ التوقع تسقط الحدود التي تحتوي على قوة فردية من \(\varepsilon_n\)، فنحصل على
$$c_n=c_{n-1}+3\,\mathbb{E}[X_{n-1}X_{n-2}^2].$$
وهنا تظهر الخطوة الحاسمة. بما أن
$$X_{n-1}=X_{n-2}+\varepsilon_{n-1}X_{n-3},$$
فإن
$$\mathbb{E}[X_{n-1}X_{n-2}^2]=\mathbb{E}[X_{n-2}^3]+\mathbb{E}[\varepsilon_{n-1}X_{n-3}X_{n-2}^2]=c_{n-2}.$$
وبالتالي
$$c_n=c_{n-1}+3c_{n-2}\qquad(n\ge 2),$$
مع
$$c_0=0,\qquad c_1=1.$$
وأول القيم هي
$$0,1,1,4,7,19,\dots,$$
وهذا يوضح أن نمو العزم الثالث أسرع من نمو العزم الثاني.
عند \(n=5\) تبدأ الاختيارات العشوائية من الخطوات \(3,4,5\)، ولذلك توجد \(2^3=8\) مسارات متساوية الاحتمال. إذا عُدِّدت هذه الحالات كلها نحصل على
$$X_5\in\{5,3,1,1,1,-1,-1,-1\}.$$
ومن ثم
$$\mathbb{E}[X_5]=1,\qquad \mathbb{E}[X_5^2]=\frac{25+9+1+1+1+1+1+1}{8}=5,$$
وكذلك
$$\mathbb{E}[X_5^3]=\frac{125+27+1+1+1-1-1-1}{8}=19.$$
إذًا
$$\operatorname{Var}(X_5)=5-1=4,\qquad \mu_{3,5}=19-3\cdot 5+2=6,$$
ومن هنا يكون معامل الالتواء
$$\gamma_5=\frac{6}{4^{3/2}}=\frac{6}{8}=0.75.$$
هذا المثال يطابق قيم التحقق الموجودة داخل التنفيذات، ولذلك فهو اختبار عملي جيد لصحة الاشتقاق.
بعد الحصول على \(a_n\) و\(c_n\)، يصبح الالتواء
$$\gamma_n=\frac{\mu_{3,n}}{\operatorname{Var}(X_n)^{3/2}}=\frac{c_n-3a_n+2}{(a_n-1)^{3/2}}.$$
وهكذا تنحصر المسألة كلها في تشغيل علاقتين عوديتين عدديتين حتى \(n=50\)، من دون بناء التوزيع الكامل أو تعداد جميع المسارات.
تنفيذات C++ وPython وJava تحفظ فقط آخر قيمتين من علاقة العزم الثاني وآخر قيمتين من علاقة العزم الثالث. نبدأ من \((a_0,a_1)=(0,1)\) و\((c_0,c_1)=(0,1)\)، ثم تُحدَّث السلسلتان في كل دورة بواسطة
$$a_n=a_{n-1}+a_{n-2},\qquad c_n=c_{n-1}+3c_{n-2}.$$
بعد الوصول إلى \(n=50\)، تحوِّل الشيفرة القيم النهائية إلى التباين \(a_{50}-1\) والعزم المركزي الثالث \(c_{50}-3a_{50}+2\). ثم تحسب \(\sigma=\sqrt{\operatorname{Var}(X_{50})}\) وتعيد
$$\gamma_{50}=\frac{\mu_{3,50}}{\sigma^3}.$$
هناك أيضًا شرط حماية صغير: إذا كان التباين غير موجب فالناتج يكون \(0\). هذا لا يؤثر في الحالة المطلوبة فعلًا، لأن التباين عند \(n=50\) موجب بوضوح.
زمن التنفيذ هو \(O(n)\)، لأن الشيفرة تنفذ تحديثًا ثابت الكلفة لكل خطوة من 2 إلى 50. أما الذاكرة فهي \(O(1)\)، لأن عدد القيم المخزنة ثابت طوال الوقت.
وهذا أصغر بكثير من بناء التوزيع الصريح الذي كان سيتفرع إلى \(2^{n-2}\) مسارًا متساوي الاحتمال. تنجح طريقة العزوم هنا لأن الالتواء يعتمد على عدد قليل من الإحصاءات المجمعة، وهذه الإحصاءات نفسها تحقق علاقات عودية مغلقة.