Satz von Baik-Deift-Johansson

mathematisches Resultat aus der Kombinatorik
(Weitergeleitet von Baik-Deift-Johansson-Theorem)

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 . 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 die Permutation , dann sind die längsten, aufsteigenden Teilfolgen und . Sei die Länge von und die Länge der längsten, aufsteigenden Teilfolge. Betrachtet man allgemein , dann charakterisiert das Baik-Deift-Johansson-Theorem die Verteilung von wenn nach Unendlich strebt.[1]

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

Satz von Baik-Deift-Johansson

Bearbeiten

Ulams Problem

Bearbeiten

Mit   bezeichnen wir die symmetrische Gruppe. Sei   eine Permutation, dann nennen wir   eine aufsteigende Teilfolge der Länge  , falls   und  .

Mit   bezeichnen wir die Länge der längsten, aufsteigenden Teilfolge von  

 

Angenommen, wir ziehen eine Permutation   aus   unter der Gleichverteilung, was können wir über die Wahrscheinlichkeitsverteilung von   insbesondere   sagen? Dieses Problem ist auch unter dem Namen Ulams Problem bekannt.

Satz von Baik-Deift-Johansson

Bearbeiten

Für jedes   sei   eine unter der Gleichverteilung gezogene Permutation der Länge  . Dann gilt für jedes  

 

wobei   die Tracy-Widom-Verteilung des gaußschen unitären Ensembles (GUE) bezeichnet.

KPZ-Universalität

Bearbeiten

Das Theorem sagt, dass sich das asymptotische Verhalten der Verteilung der Länge   unter entsprechender Skalierung gleich verhält wie das asymptotische Verhalten der Eigenwerte einer gaußschen hermiteschen Zufallsmatrix. Das asymptotische Verhalten von   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]

Einzelnachweise

Bearbeiten
  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].