Longest weakly increasing subsequences of discrete random walks on the integers with heavy tailed distribution of increments

Diese Studie untersucht die Skalierung und Verteilung der Länge der längsten schwach steigenden Teilfolgen in diskreten Zufallswalks mit schweren Verteilungsschwänzen und stellt fest, dass die durchschnittliche Länge bei endlicher Varianz wie $\sqrt{n}\log{n}$ skaliert, während sie bei unendlicher Varianz einem Potenzgesetz mit einem Exponenten größer als 0,5 folgt, wobei die Verteilung im Kern gut durch ein Lognormalmodell approximiert wird.

Das Wesentliche

Stellen Sie sich vor, Sie beobachten einen etwas chaotischen Spaziergänger auf einer langen, geraden Straße. Dieser Spaziergänger macht zufällige Schritte: manchmal einen Schritt nach vorne, manchmal einen nach hinten, und bei manchen Versionen des Experiments auch riesige Sprünge.

In diesem wissenschaftlichen Papier untersuchen die Autoren genau, wie man die längste mögliche „aufsteigende Kette" in diesem Chaos findet.

Hier ist die Erklärung in einfachen Worten, mit ein paar bildhaften Vergleichen:

1. Das Spiel: Der zufällige Spaziergang

Stellen Sie sich einen Spaziergang vor, bei dem jeder Schritt eine Zahl ist.

• Der normale Spaziergang: Jeder Schritt ist entweder +1 oder -1 (wie beim einfachen Hin-und-Her-Gehen).
• Der „schwere" Spaziergang: Hier gibt es eine Besonderheit. Die Schritte sind nicht immer klein. Manchmal macht der Spaziergänger einen winzigen Schritt, aber sehr selten einen riesigen Sprung (z. B. +100 oder -100). Die Wahrscheinlichkeit für diese riesigen Sprünge folgt einer speziellen Regel, die man „schwere Verteilung" nennt. Je nachdem, wie „schwer" diese Verteilung ist (gesteuert durch einen Parameter $\alpha$), ändert sich das Verhalten des Spaziergängers.

2. Die Aufgabe: Die längste aufsteigende Kette finden

Nehmen wir die Liste aller Schritte des Spaziergängers. Wir wollen nun eine Untergruppe von Schritten finden, die niemals kleiner werden.

• Wenn der Spaziergänger bei Schritt 5 auf Höhe 10 ist, bei Schritt 10 auf Höhe 12 und bei Schritt 20 auf Höhe 15, dann bilden diese drei Punkte eine „aufsteigende Kette".
• Wir suchen die längste mögliche Kette, die wir aus der gesamten Liste herauspicken können. Das nennen die Autoren „LIS" (Longest Increasing Subsequence).

Wichtig: Da es sich um ganze Zahlen handelt (diskret), darf die Kette auch „flache" Stellen haben. Wenn der Spaziergänger zweimal hintereinander auf derselben Höhe ist (z. B. 10, 10), zählt das auch als „nicht kleiner werdend". Das ist wie ein Plateau auf einem Bergpfad, das man mitgehen darf.

3. Die große Entdeckung: Wie wächst die Kette?

Die Forscher haben herausgefunden, dass die Länge dieser längsten Kette von der Art der Schritte abhängt. Es gibt zwei völlig verschiedene Welten:

Welt A: Die „normalen" Schritte (Kleine Varianz, $\alpha > 2$)

Wenn die Schritte meist klein sind und keine extremen Riesen-Sprünge vorkommen (wie beim normalen Zufallsspaziergang), wächst die Länge der längsten Kette ungefähr so:
$$\text{Länge} \approx \sqrt{n} \times \log(n)$$
Die Analogie: Stellen Sie sich vor, Sie laufen durch einen Wald. Die Länge des Pfades, den Sie finden können, wächst mit der Wurzel der Gesamtstrecke, aber es gibt einen kleinen „Bonus" durch das Logarithmus-Wachstum. Das ist wie ein langsames, aber stetiges Wachsen. Bei diskreten Schritten (ganze Zahlen) ist dieser Bonus durch das Logarithmus-Glied besonders wichtig, weil man auf den „Plateaus" (gleiche Höhen) länger verweilen kann.

Welt B: Die „schweren" Schritte (Große Varianz, $\alpha \le 2$)

Wenn die Schritte sehr unvorhersehbar sind und riesige Sprünge möglich sind (die Verteilung hat einen „schweren Schweif"), ändert sich das Gesetz komplett. Die Länge wächst jetzt wie eine reine Potenz:
$$\text{Länge} \approx n^{\theta}$$
Die Analogie: Hier ist der Spaziergänger so chaotisch, dass er riesige Sprünge macht. Dadurch kann man viel längere Ketten finden als im normalen Fall. Der Exponent $\theta$ ist hier größer als 0,5 (also schneller als die Wurzel). Je „schwerer" die Verteilung (je öfter die riesigen Sprünge vorkommen), desto größer wird dieser Exponent $\theta$. Es ist, als würde der Spaziergänger plötzlich durch einen Trichter fallen, der ihn schneller nach oben drückt.

4. Der Übergang und die Überraschung

Die Forscher haben genau untersucht, wo der Übergang zwischen diesen beiden Welten liegt.

• Der Wendepunkt: Er liegt bei $\alpha = 2$.
• Die Überraschung: Bei den „schweren" Schritten (Welt B) gibt es kein Logarithmus-Glied mehr. Es ist eine reine Potenzfunktion. Bei den „leichten" Schritten (Welt A) ist das Logarithmus-Glied jedoch entscheidend.
• Warum? Bei ganzen Zahlen (diskret) gibt es oft „Pausen" (gleiche Zahlen). Diese Pausen helfen, die Kette länger zu machen. Bei echten, kontinuierlichen Zahlen (wie bei einem Wasserfall, der nie genau auf derselben Höhe bleibt) gibt es diese Pausen nicht. Die Autoren vermuten, dass das Logarithmus-Glied in früheren Studien bei kontinuierlichen Zahlen vielleicht nur ein Rechenfehler der Computer war, weil Computer Zahlen auch nur diskret speichern. Bei echten ganzen Zahlen ist es aber ein echtes, physikalisches Phänomen.

5. Die Form der Verteilung: Ein Glockenkurven-Verwandter

Neben der Länge haben die Autoren auch geschaut, wie die Ergebnisse verteilt sind.
Sie haben festgestellt, dass die Verteilung der Kettenlängen sehr gut durch eine Lognormal-Verteilung beschrieben werden kann.
Die Analogie: Stellen Sie sich vor, Sie werfen 10.000 Mal einen Würfel und notieren die Ergebnisse. Die meisten Ergebnisse liegen in der Mitte, aber es gibt einen langen „Schweif" nach rechts (ein paar sehr große Werte). Das sieht aus wie eine Glocke, die nach rechts verzerrt ist. Die Daten der Forscher passten perfekt auf diese Form.

Zusammenfassung für den Alltag

Stellen Sie sich vor, Sie sammeln Münzen auf einem langen Spaziergang.

• Wenn Sie nur kleine Münzen finden (normale Schritte), wächst Ihre Sammlung langsam, aber mit einem kleinen Bonus, weil Sie manchmal an der gleichen Stelle stehen bleiben dürfen.
• Wenn Sie ab und zu riesige Goldbarren finden (schwere Schritte), wächst Ihre Sammlung plötzlich viel schneller und folgt einem anderen, einfacheren Gesetz.

Die Autoren haben mit Hilfe von Millionen von Computer-Simulationen genau herausgefunden, wann welcher Fall eintritt und wie man die Mathematik dahinter am besten beschreibt. Sie haben bewiesen, dass die Art der Schritte (klein und regelmäßig vs. groß und chaotisch) das fundamentale Wachstumsgesetz der längsten Kette verändert.

Technische Zusammenfassung

Titel: Längste schwach wachsende Teilfolgen diskreter Zufallswege mit schwerem Verteilungsschwanz

Autoren: José Ricardo G. Mendonça und Marcelo V. Freire (Universität São Paulo, Brasilien)

---

1. Problemstellung und Motivation

Die Untersuchung der längsten wachsenden Teilfolgen (Longest Increasing Subsequence, LIS) ist ein klassisches Problem der Kombinatorik und Wahrscheinlichkeitstheorie (bekannt als Ulams Problem). Während das Verhalten der LIS für zufällige Permutationen und Zufallswege mit kontinuierlichen Inkrementen gut untersucht ist, bleibt das Verhalten für diskrete Zufallswege mit schweren Verteilungsschwänzen (heavy-tailed distributions) weitgehend unerforscht.

Der Fokus dieser Arbeit liegt auf der Analyse der Länge $L_n$ der längsten schwach wachsenden Teilfolge (weak LIS, d.h. $S_{i_1} \le \dots \le S_{i_L}$) von $n$-stufigen Zufallswegen auf den ganzen Zahlen. Die Inkrementverteilung folgt einer symmetrischen Pareto-ähnlichen (Zipf-)Verteilung mit dem Schwanzindex $\alpha > 0$:
$$\mathbb{P}(X=k) \propto |k|^{-1-\alpha}$$
Das Ziel ist es, das Skalierungsverhalten von $\langle L_n \rangle$ in Abhängigkeit von $\alpha$ zu bestimmen und zu klären, ob sich diskrete Wege mit unendlicher Varianz ($\alpha \le 2$) fundamental von denen mit endlicher Varianz ($\alpha > 2$) sowie vom einfachen Zufallsweg (SRW, Schritte $\pm 1$) unterscheiden.

2. Methodik

Die Autoren führten umfangreiche numerische Simulationen durch:

• Datengenerierung: Für 13 verschiedene Weglängen ($10^4 \le n \le 10^8$) und Schwanzindizes ($0.5 \le \alpha \le 10$) wurden jeweils 10.000 Zufallswege simuliert.
• Algorithmus: Die Länge der weak LIS wurde mit dem "Patience Sorting"-Algorithmus berechnet ($O(n \log n)$ Zeitkomplexität).
• Statistische Analyse:
  • Explorative Anpassungen: Analyse des effektiven Exponenten $\theta_{\text{eff}}(n)$.
  • Modellvergleich: Zwei konkurrierende Skalierungsmodelle wurden getestet:
    • Modell I: Ein universelles Potenzgesetz mit logarithmischem Korrekturterm: $f(n) = n^\theta(a + b \log n)$.
    • Modell II: Ein regimespezifischer Ansatz: Reines Potenzgesetz $a n^\theta$ für $\alpha < 2$ und $\sqrt{n}(a + b \log n)$ für $\alpha \ge 2$.
  • Gewichtete nichtlineare Kleinste-Quadrate (NLS): Eine robuste Anpassung an die einzelnen Datenpunkte unter Berücksichtigung der Varianz (Inverse-Variance-Weighting).
  • ANOVA-Tests: Statistische Hypothesentests (F-Tests) zur Unterscheidung zwischen den Modellen.
  • Verteilungsdiagnostik: Analyse der Verteilung von $L_n$ selbst mittels Q-Q-Plots, Schiefe und Exzess-Kurtosis.

3. Wichtige Ergebnisse

A. Skalierungsverhalten von $\langle L_n \rangle$

Die Studie identifiziert einen kritischen Übergang bei $\alpha = 2$ (dem Punkt, an dem die Varianz der Inkremente divergiert):

1. Schwere Schwänze ($\alpha \le 2$):

   • Das Verhalten folgt einem reinen Potenzgesetz: $\langle L_n \rangle \sim a n^\theta$.
   • Der Exponent $\theta$ ist größer als $0.5$ und hängt von $\alpha$ ab.
   • Für $\alpha = 0.5$ (sehr schwere Schwänze) wurde $\theta \approx 0.73$ gefunden.
   • Für $\alpha = 1$ beträgt $\theta \approx 0.685$.
   • Für $\alpha = 1.5$ liegt $\theta \approx 0.64$.
   • Der Fall $\alpha = 0.5$ zeigt bei den größten $n$ Anomalien, was darauf hindeutet, dass der asymptotische Bereich möglicherweise noch nicht vollständig erreicht ist.

2. Endliche Varianz ($\alpha \ge 2$) und Einfacher Zufallsweg (SRW):

   • Das Verhalten folgt dem Gesetz: $\langle L_n \rangle \sim \sqrt{n}(a + b \log n)$.
   • Der führende Exponent ist exakt $\theta = 0.5$.
   • Der logarithmische Term ($\log n$) ist signifikant und dominiert das Verhalten für große $n$.
   • Die Koeffizienten $a$ und $b$ unterscheiden sich stark von denen bei kontinuierlichen Verteilungen (wo $a \approx b \approx 0.36$). Hier sind $b$ deutlich größer (bis zu 1.5), was auf die diskrete Natur der Wege zurückzuführen ist.

B. Rolle der Diskretisierung und Plateaus

Ein zentrales Ergebnis ist die Erklärung des logarithmischen Faktors. Bei diskreten Wegen mit ganzzahligen Schritten treten häufig "Plateaus" auf (wiederholte Besuche desselben Wertes). Da die schwache LIS Gleichheit erlaubt ($S_i \le S_j$), können diese Plateaus genutzt werden, um die Länge der Teilfolge zu verlängern. Dies führt zu einer stärkeren logarithmischen Korrektur als bei kontinuierlichen Wegen, wo Gleichheit mit Wahrscheinlichkeit null auftritt. Die Autoren argumentieren, dass der logarithmische Term in früheren Studien zu kontinuierlichen Wegen möglicherweise ein Artefakt der diskreten Floating-point-Repräsentation in Simulationen war.

C. Verteilung von $L_n$

Die Verteilung der Längen $L_n$ selbst wird durch ein Lognormal-Modell sehr gut approximiert.

• Die logarithmierten Werte $\log L_n$ sind annähernd normalverteilt.
• Die Verteilung zeigt eine leichte negative Schiefe und negative Exzess-Kurtosis (leichtere Schwänze als die Normalverteilung), was auf eine schneller abklingende Verteilung in den Extremen hindeutet.
• Für $\alpha \ge 1$ ist die Lognormal-Approximation sehr gut; für $\alpha = 0.5$ bei sehr großen $n$ treten Abweichungen auf.

4. Signifikanz und Beiträge

1. Auflösung offener Fragen: Die Arbeit klärt den langjährigen Streit um die Skalierungsexponenten für diskrete Zufallswege und zeigt objektiv durch ANOVA-Tests und Stabilitätsanalysen, dass die scheinbaren Abweichungen von $\theta=0.5$ bei $\alpha \ge 2$ durch den logarithmischen Korrekturterm verursacht werden.
2. Diskret vs. Kontinuierlich: Es wird ein fundamentaler Unterschied zwischen diskreten und kontinuierlichen Zufallswegen bezüglich der weak LIS herausgearbeitet. Die Diskretisierung führt zu Plateaus, die die Kombinatorik der Teilfolgen verändern und den logarithmischen Faktor verstärken.
3. Methodischer Fortschritt: Die Kombination aus explorativen Fits, gewichteter NLS und formaler Hypothesentests bietet einen robusten Rahmen für die Analyse von Skalierungsverhalten in der statistischen Physik, der über die rein explorativen Methoden früherer Arbeiten hinausgeht.
4. Neue Vermutung: Die Autoren stellen die Vermutung auf, dass die Verteilung der weak LIS für eine breite Klasse von Zufallswegen (nicht nur für diese spezifischen) durch eine Lognormalverteilung beschrieben werden kann, was theoretisch noch nicht hergeleitet wurde.

Fazit

Die Studie liefert eine umfassende Charakterisierung der längsten schwach wachsenden Teilfolgen in diskreten Zufallswegen. Sie bestätigt, dass für schwere Schwänze ($\alpha \le 2$) ein Potenzgesetz mit variablem Exponenten gilt, während für $\alpha \ge 2$ (einschließlich des einfachen Zufallswegs) ein $\sqrt{n} \log n$-Verhalten vorliegt. Die Ergebnisse unterstreichen die kritische Rolle der Diskretisierung und der Plateaus für das Skalierungsverhalten und bieten neue empirische Evidenz für die Lognormalität der Fluktuationen.