Satz von Baik-Deift-Johansson

Der Satz von Baik-Deift-Johansson ist ein mathematisches Resultat aus der Kombinatorik. Er beschäftigt sich mit den Teilfolgen einer zufällig gezogenen Permutation aus der Menge ${\displaystyle \{1,2,\dots ,N\}}$. Zufällig heißt, alle Permutationen besitzen dieselbe Wahrscheinlichkeit gezogen zu werden. Das Theorem macht eine Aussage über die Verteilung der Länge der längsten, aufsteigenden Teilfolge im Grenzwert.

Angenommen, man zieht aus der Menge ${\displaystyle \{1,2,\dots ,6\}}$ die Permutation ${\displaystyle \pi _{6}=(2,5,1,3,4,6)}$, dann sind die längsten, aufsteigenden Teilfolgen ${\displaystyle (2,3,4,6)}$ und ${\displaystyle (1,3,4,6)}$. Sei ${\displaystyle L(\pi _{6})=6}$ die Länge von ${\displaystyle \pi _{6}}$ und ${\displaystyle l(\pi _{6})=4}$ die Länge der längsten, aufsteigenden Teilfolge. Betrachtet man allgemein ${\displaystyle \{1,2,\dots ,N\}}$, dann charakterisiert das Baik-Deift-Johansson-Theorem die Verteilung von ${\displaystyle l(\pi _{N})}$ wenn ${\displaystyle N}$ nach Unendlich strebt.^[1]

Das Theorem wurde von Jinho Baik, Percy Deift und Kurt Johansson gezeigt.

Mit ${\displaystyle S_{N}}$ bezeichnen wir die symmetrische Gruppe. Sei ${\displaystyle \pi _{N}\in S_{N}}$ eine Permutation, dann nennen wir ${\displaystyle \pi _{k,j}=(\pi (i_{1}),\cdots ,\pi (i_{k}))}$ eine aufsteigende Teilfolge der Länge ${\displaystyle L(\pi _{k,j})=k}$, falls ${\displaystyle i_{1}<\dots <i_{k}}$ und ${\displaystyle \pi _{N}(i_{1})<\cdots <\pi _{N}(i_{k})}$.

Mit ${\displaystyle l(\pi _{N})}$ bezeichnen wir die Länge der längsten, aufsteigenden Teilfolge von ${\displaystyle \pi _{N}}$

${\displaystyle l(\pi _{N}):=\operatorname {max} \{1\leq k\leq N:k=L(\pi _{k,j}),\pi _{k,j}{\text{ ist eine aufsteigende Teilfolge von }}\pi _{N}\}.}$

Angenommen, wir ziehen eine Permutation ${\displaystyle \pi _{N}}$ aus ${\displaystyle S_{N}}$ unter der Gleichverteilung, was können wir über die Wahrscheinlichkeitsverteilung von ${\displaystyle l(\pi _{N})}$ insbesondere ${\displaystyle \mathbb {P} (l(\pi _{N})\leq t)}$ sagen? Dieses Problem ist auch unter dem Namen Ulams Problem bekannt.

Für jedes ${\displaystyle N\geq 1}$ sei ${\displaystyle \pi _{N}}$ eine unter der Gleichverteilung gezogene Permutation der Länge ${\displaystyle N}$. Dann gilt für jedes ${\displaystyle x\in \mathbb {R} }$

${\displaystyle \mathbb {P} \left({\frac {l(\pi _{N})-2{\sqrt {N}}}{N^{1/6}}}\leq x\right)\to F_{2}(x)\quad {\text{wenn }}N\to \infty }$

wobei ${\displaystyle F_{2}(x)}$ die Tracy-Widom-Verteilung des gaußschen unitären Ensembles (GUE) bezeichnet.

Das Theorem sagt, dass sich das asymptotische Verhalten der Verteilung der Länge ${\displaystyle l(\pi _{N})}$ unter entsprechender Skalierung gleich verhält wie das asymptotische Verhalten der Eigenwerte einer gaußschen hermiteschen Zufallsmatrix. Das asymptotische Verhalten von ${\displaystyle l(\pi _{N})}$ unterliegt der sogenannten KPZ-Universalitätsklasse der Kardar-Parisi-Zhang-Gleichung, einer nicht-linearen stochastischen partiellen Differentialgleichung. Alle Modelle in der Klasse fluktuieren ab einer gewissen Zeit wie die KPZ-Gleichung. Man kann Ulams Problem auch als stochastisches Grenzflächenwachstumsmodell (englisch stochastic interface growth model) formulieren, dem sogenannten polynuklearen Wachstumsmodell (englisch polynuclear growth model) kurz PNG-Modell.^[2]

1. ↑ Jinho Baik, Percy Deift und Kurt Johansson: On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations. Hrsg.: arXiv. 1998, doi:10.48550/ARXIV.MATH/9810105, arxiv:math/9810105. 
2. ↑ Ivan Corwin: Comments on David Aldous and Persi Diaconis' "Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem". Hrsg.: arXiv. 2018, doi:10.48550/ARXIV.1806.10542, arxiv:1806.10542 [abs].