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

Dit artikel onderzoekt de lengte van de langste zwak stijgende deelrijen in discrete willekeurige wandelingen met zwaarstaartige incrementen en concludeert dat de gemiddelde lengte schaalt als $\sqrt{n}\log{n}$ bij eindige variantie en als $n^\theta$ (met $\theta > 0,5$) bij oneindige variantie, waarbij de verdeling van de lengte over het algemeen goed benaderd wordt door een lognormale verdeling.

De kern

De Kern van het Onderzoek: Een Wandeltocht door de Willekeur

Stel je voor dat je een wandeling maakt op een oneindig groot rooster (zoals een schaakbord dat zich uitstrekt tot in de verte). Je begint op punt 0. Bij elke stap die je zet, kies je willekeurig een richting: vooruit of achteruit. Maar hier is de twist: de grootte van je stap is niet altijd hetzelfde.

In dit onderzoek kijken de auteurs naar twee soorten wandelaars:

1. De Standaardwandelaar: Deze zet altijd precies één stap vooruit of achteruit (zoals een muntje opgooien: kop of staart).
2. De Zware-Wolk Wandelaar: Deze kan meestal kleine stappen zetten, maar soms, heel zelden, maakt hij een enorme sprong (bijvoorbeeld 100 stappen in één keer). Hoe "zwaar" deze wolk van mogelijke sprongen is, wordt bepaald door een getal dat ze $\alpha$ noemen.

Het doel van het onderzoek is niet om te kijken hoe ver ze komen, maar om te kijken naar het langste stijgende pad dat ze kunnen vinden tijdens hun wandeling.

Het Speelgoed: De "Langste Stijgende Subsequentie" (LIS)

Stel je voor dat je tijdens je wandeling een foto maakt van je positie na elke stap. Je hebt nu een lijst met getallen: 0, 3, 2, 5, 4, 6, 100, 99...

Je wilt nu een zo lang mogelijk rijtje foto's vinden waarbij je positie altijd gelijk blijft of stijgt. Je mag dus over een heuvel klimmen, maar je mag nooit een dal in. Als je een dal ziet, sla je die foto over en zoek je de volgende die hoger is dan de vorige die je hebt gekozen.

• Voorbeeld: In de rij 1, 3, 2, 4 is het langste stijgende pad 1, 3, 4 (lengte 3) of 1, 2, 4 (lengte 3).
• De vraag is: Hoe lang wordt dit pad als je wandeling steeds langer wordt?

Wat Vonden Ze? Twee Werelden

De onderzoekers ontdekten dat het antwoord afhangt van hoe "zwaar" de sprongen zijn (de waarde van $\alpha$).

1. De Rustige Wereld ($\alpha > 2$): De Logaritmische Correctie

Wanneer de wandelaar zelden enorme sprongen maakt (de variantie is eindig), gedraagt het pad zich op een bekende manier, maar dan met een kleine verrassing.

• De Verwachting: Je zou denken dat de lengte van het pad groeit met de wortel van het aantal stappen ($\sqrt{n}$).
• De Werkelijkheid: Het groeit iets sneller dan dat. Het is alsof je een fietspad hebt dat $\sqrt{n}$ lang is, maar er zit een extra, langzame helling op die zorgt dat je net iets verder komt. Deze helling wordt veroorzaakt door een logaritmische factor ($\log n$).
• De Analogie: Stel je voor dat je een ladder beklimt. Bij een simpele wandeling (alleen stappen van 1) kun je op elke tree staan. Omdat je op dezelfde tree mag blijven staan (het pad mag "plat" zijn), kun je meer stappen meenemen dan bij een wandeling waar je altijd hoger moet zijn. Die "platte momenten" (waar je op dezelfde hoogte blijft) geven je een extra boost, wat leidt tot die logaritmische factor.

2. De Chaotische Wereld ($\alpha \le 2$): De Krachtige Kracht

Wanneer de wandelaar vaak enorme sprongen maakt (de variantie is oneindig), verandert de natuurw wet.

• Het Resultaat: De lengte van het pad groeit nu als een zuivere macht ($n^\theta$). Er is geen extra logaritmische helling meer.
• De Analogie: Hier is de wandeling zo chaotisch en vol met enorme sprongen dat de "platte momenten" (waar je op dezelfde hoogte blijft) niet meer tellen. De enorme sprongen domineren het spel. De lengte van het pad hangt nu puur af van hoe "zwaar" de sprongen zijn. Hoe chaotischer de wandeling, hoe sneller het langste pad groeit.

De Verrassende Vorm: De Lognormale Verdeling

Naast het kijken naar de lengte, keken ze ook naar de vorm van de verdeling. Als je 10.000 keer dezelfde wandeling doet, krijg je 10.000 verschillende lengtes voor het langste pad.

• De Verrassing: Deze 10.000 lengtes vormen geen normale "klokcurve" (zoals bij de lengte van mensen), maar een lognormale verdeling.
• De Analogie: Denk aan een berg. Een normale verdeling is een symmetrische berg. Een lognormale verdeling is een berg met een steile helling aan de linkerkant en een heel lange, uitlopende staart aan de rechterkant. De meeste wandelaars vinden een pad van gemiddelde lengte, maar er zijn een paar gelukkige wandelaars die door toeval een extreem lang pad vinden. Die "extreme geluksvogels" trekken het gemiddelde omhoog.

Waarom is dit belangrijk?

1. Discreet vs. Continu: Eerdere studies keken naar wandelingen met continue getallen (waar je exact op 1.0001 kunt staan). Dit onderzoek toont aan dat als je werkt met hele getallen (discreet), de wiskunde anders werkt. De "platte momenten" (waar je op hetzelfde getal blijft) zijn cruciaal en zorgen voor die extra logaritmische factor.
2. Voorspellen: Ze hebben een nieuwe manier ontwikkeld om te voorspellen hoe lang zo'n pad wordt, afhankelijk van hoe "zwaar" de sprongen zijn. Dit helpt bij het begrijpen van complexe systemen, van beurskoersen tot netwerkverkeer, waar soms kleine veranderingen zijn en soms enorme schokken.

Samenvatting in één zin

Het onderzoek laat zien dat bij een wandeling met hele getallen, de lengte van het langste stijgende pad groeit als $\sqrt{n} \times \log(n)$ als de sprongen klein zijn, maar als een macht $n^\theta$ als de sprongen enorm groot en chaotisch zijn, waarbij de resultaten altijd een specifieke, scheve vorm hebben die lijkt op een "geluksverdeling".

Technische samenvatting

Titel: Langste zwak stijgende deelrijen van discrete toevalswandelingen op de gehele getallen met zwaarstaartige verdeling van incrementen

Auteurs: José Ricardo G. Mendonça en Marcelo V. Freire (Universiteit van São Paulo, Brazilië)

---

1. Probleemstelling en Context

Het artikel onderzoekt de lengte $L_n$ van de langste zwak stijgende deelrij (weak Longest Increasing Subsequence, weak LIS) van discrete toevalswandelingen op de gehele getallen.

• Achtergrond: De studie van LIS bij willekeurige permutaties (het probleem van Ulam) is goed onderzocht, maar LIS bij toevalswandelingen en andere gecorreleerde tijdsreeksen is minder bestudeerd.
• Specifieke focus: De auteurs richten zich op discrete wandelingen met zwaarstaartige verdelingen van de stapgrootte (increments), in tegenstelling tot de eerder bestudeerde continue verdelingen.
• Het model: Een $n$-staps wandeling $S_i$ wordt gedefinieerd als $S_i = S_{i-1} + X_i$, waarbij de stappen $X_i$ onafhankelijke, identiek verdeelde (i.i.d.) gehele getallen zijn met een symmetrische verdeling met zware staarten (Pareto-achtig of Zipf-achtig). De verdeling wordt gekarakteriseerd door een staartindex $\alpha > 0$, waarbij de waarschijnlijkheidsmassa evenredig is met $|k|^{-1-\alpha}$.
• Kernvraag: Hoe schaalt de verwachte lengte $\langle L_n \rangle$ met de wandelingslengte $n$, en hoe hangt dit af van de staartindex $\alpha$? Er is een fundamenteel verschil tussen wandelingen met eindige variantie ($\alpha > 2$) en oneindige variantie ($\alpha \leq 2$).

2. Methodologie

De auteurs hebben een uitgebreide numerieke studie uitgevoerd met de volgende methoden:

• Data Generatie:
  • Er zijn 10.000 toevalswandelingen gegenereerd voor 13 verschillende wandelingslengtes ($n$ variërend van $10^4$ tot $10^8$).
  • De staartindex $\alpha$ varieerde van $0.5$ tot $10$, inclusief de simpele toevalswandeling (SRW, stappen $\pm 1$).
  • De stappen werden gegenereerd via inversie van een uniforme verdeling, met een teken dat willekeurig wordt gekozen ($\pm 1$) om symmetrie te garanderen.
• Berekening van de LIS: De lengte van de weak LIS werd berekend met het "patience sorting" algoritme (dynamisch programmeren met binaire zoekopdracht) in $O(n \log n)$ tijd.
• Statistische Analyse en Modelselectie:
  • Exploratieve analyse: Berekening van effectieve exponenten ($\theta_{eff}$) om lokale schaalgedrag te inspecteren.
  • Modelvergelijking: Twee modellen werden getest:
    • Model I: Een universeel model $f(n) = n^\theta(a + b \log n)$ voor alle $\alpha$.
    • Model II: Gescheiden modellen: een zuivere machtswet $a n^\theta$ voor $\alpha < 2$ en een logaritmisch gecorrigeerde vorm $\sqrt{n}(a + b \log n)$ voor $\alpha \geq 2$.
  • Gewogen niet-lineaire kleinste-kwadraten (Weighted NLS): Om rekening te houden met de variatie in de steekproefverdeling, werd een NLS-fit uitgevoerd op individuele waarden (in plaats van alleen gemiddelden), gewogen met de inverse variantie.
  • ANOVA en F-tests: Gebruikt om geneste modellen te vergelijken (bijv. test op $b=0$ voor logaritmische correctie, of $\delta=0$ voor de exponent).
  • Verdelingsdiagnostiek: Analyse van de verdeling van $L_n$ zelf, specifiek getoetst op lognormaliteit via Q-Q-plots, scheefheid (skewness) en excess kurtosis.

3. Belangrijkste Resultaten

A. Schaalgedrag van de verwachte lengte $\langle L_n \rangle$

De resultaten tonen een duidelijk onderscheid op basis van de staartindex $\alpha$:

1. Oneindige variantie ($\alpha \leq 2$):

   • De lengte volgt een zuivere machtswet: $\langle L_n \rangle \sim a n^\theta$.
   • De exponent $\theta$ is groter dan $0.5$ en neemt toe naarmate $\alpha$ afneemt (zwaardere staarten).
   • Voor $\alpha = 1/2$ is $\theta \approx 0.73$ (met voorzichtigheid vanwege afwijkend gedrag bij zeer grote $n$).
   • Voor $\alpha = 1$ is $\theta \approx 0.685$.
   • Voor $\alpha = 1.5$ is $\theta \approx 0.64$.
   • Bij $\alpha = 3/2$ wordt een overgangsregime waargenomen waar een kleine logaritmische correctie al detecteerbaar is.

2. Eindige variantie ($\alpha \geq 2$) en Simpele Toevalswandeling (SRW):

   • De lengte volgt een schaalwet met een logaritmische correctie: $\langle L_n \rangle \sim \sqrt{n}(a + b \log n)$.
   • De leidende exponent is exact $\theta = 0.5$.
   • De coëfficiënten $a$ en $b$ zijn significant anders dan bij continue verdelingen (waar $a \approx b \approx 0.36$). Hier zijn $b$ veel groter en $a$ negatief, wat wijst op een sterkere rol van de logaritmische term in discrete systemen.
   • De ANOVA-tests bevestigen dat voor $\alpha \geq 2$ de exponent $\theta$ statistisch significant afwijkt van $0.5$ in eindige steekproeven (door het "opzuigen" van de log-term), maar dat dit een eindgrootte-effect is dat convergeert naar $0.5$.

B. Verdelingskarakteristieken

• De verdeling van $L_n$ wordt zeer goed benaderd door een lognormale verdeling voor alle onderzochte $\alpha$ en $n$.
• De verdeling van $\log L_n$ is ongeveer normaal, maar vertoont systematische afwijkingen in de staarten:
  • De staarten zijn lichter dan een normale verdeling (negatieve excess kurtosis).
  • Er is een lichte negatieve scheefheid (linksstaartend) voor $\alpha \geq 1$.
• Voor $\alpha = 0.5$ bij zeer grote $n$ neemt de variabiliteit toe en verschuift de verdeling, wat suggereert dat het asymptotische regime nog niet volledig is bereikt.

4. Bijdragen en Innovatie

• Discriminatie van schaalvormen: De auteurs ontwikkelen een robuust statistisch raamwerk (gewichting, ANOVA, stabiliteitsanalyse) dat in staat is om objectief te onderscheiden tussen een zuivere machtswet ($n^\theta$) en een logaritmisch gecorrigeerde vorm ($\sqrt{n} \log n$), een probleem dat in eerdere werken onopgelost bleef.
• Discrete vs. Continue: Het artikel levert direct bewijs dat de logaritmische correctie in de schaalwet voor $\alpha \geq 2$ een intrinsiek kenmerk is van discrete wandelingen. Dit verklaart de verwarring in eerdere studies over continue wandelingen, waar de log-term mogelijk een artefact was van de discretisatie in numerieke simulaties.
• Overgangsregime: Het artikel identificeert $\alpha = 3/2$ als een kritiek overgangsgebied tussen de machtswet-regime en het logaritmisch gecorrigeerde regime.
• Lognormaliteit: Het biedt sterke empirische ondersteuning voor de hypothese dat de verdeling van de LIS van zwaarstaartige wandelingen lognormaal is, hoewel een theoretische afleiding nog ontbreekt.

5. Betekenis en Conclusie

Dit onderzoek vult een belangrijke lacune in de literatuur over de statistische mechanica van niet-evenwichtssystemen en combinatorische probabiliteit.

• Het bevestigt dat de aard van de stapverdeling (discreet vs. continu) fundamenteel invloed heeft op de combinatorische structuur van de LIS, voornamelijk door de aanwezigheid van "plateaus" (gelijkwaardige waarden) in discrete wandelingen die zwak stijgende deelrijen kunnen benutten.
• De bevindingen ondersteunen eerdere numerische conjecturen en bieden een gedetailleerd beeld van hoe de exponent $\theta$ varieert met de "zwaarte" van de staart.
• De conclusie dat $L_n$ lognormaal verdeeld is, heeft implicaties voor het modelleren van fluctuaties in dergelijke systemen en suggereert dat er mogelijk een onderliggende multiplicatieve structuur of een decompositie in het "patience sorting" tableau bestaat die nog moet worden ontdekt.

Kortom, het artikel levert een grondige kwantitatieve analyse van het schaalgedrag en de verdelingsstatistiek van de langste stijgende deelrijen in discrete toevalswandelingen, met een scherp inzicht in de rol van zware staarten en discretisatie.