Satz von Baik Deift Johansson Der ist ein mathematisches Resultat aus der Kombinatorik Er beschäftigt sich mit den Teilf

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

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.

Einzelnachweise Bearbeiten

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

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: Dezember 02, 2023, 11:39 am

Der Satz von Baik Deift Johansson ist ein mathematisches Resultat aus der Kombinatorik Er beschaftigt sich mit den Teilfolgen einer zufallig gezogenen Permutation aus der Menge 1 2 N displaystyle 1 2 dots N Zufallig heisst alle Permutationen besitzen dieselbe Wahrscheinlichkeit gezogen zu werden Das Theorem macht eine Aussage uber die Verteilung der Lange der langsten aufsteigenden Teilfolge im Grenzwert Angenommen man zieht aus der Menge 1 2 6 displaystyle 1 2 dots 6 die Permutation p 6 2 5 1 3 4 6 displaystyle pi 6 2 5 1 3 4 6 dann sind die langsten aufsteigenden Teilfolgen 2 3 4 6 displaystyle 2 3 4 6 und 1 3 4 6 displaystyle 1 3 4 6 Sei L p 6 6 displaystyle L pi 6 6 die Lange von p 6 displaystyle pi 6 und l p 6 4 displaystyle l pi 6 4 die Lange der langsten aufsteigenden Teilfolge Betrachtet man allgemein 1 2 N displaystyle 1 2 dots N dann charakterisiert das Baik Deift Johansson Theorem die Verteilung von l p N displaystyle l pi N wenn N displaystyle N nach Unendlich strebt 1 Das Theorem wurde von Jinho Baik Percy Deift und Kurt Johansson gezeigt Inhaltsverzeichnis 1 Satz von Baik Deift Johansson 1 1 Ulams Problem 1 2 Satz von Baik Deift Johansson 1 3 KPZ Universalitat 2 EinzelnachweiseSatz von Baik Deift Johansson BearbeitenUlams Problem Bearbeiten Mit S N displaystyle S N nbsp bezeichnen wir die symmetrische Gruppe Sei p N S N displaystyle pi N in S N nbsp eine Permutation dann nennen wir p k j p i 1 p i k displaystyle pi k j pi i 1 cdots pi i k nbsp eine aufsteigende Teilfolge der Lange L p k j k displaystyle L pi k j k nbsp falls i 1 lt lt i k displaystyle i 1 lt dots lt i k nbsp und p N i 1 lt lt p N i k displaystyle pi N i 1 lt cdots lt pi N i k nbsp Mit l p N displaystyle l pi N nbsp bezeichnen wir die Lange der langsten aufsteigenden Teilfolge von p N displaystyle pi N nbsp l p N max 1 k N k L p k j p k j ist eine aufsteigende Teilfolge von p 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 nbsp Angenommen wir ziehen eine Permutation p N displaystyle pi N nbsp aus S N displaystyle S N nbsp unter der Gleichverteilung was konnen wir uber die Wahrscheinlichkeitsverteilung von l p N displaystyle l pi N nbsp insbesondere P l p N t displaystyle mathbb P l pi N leq t nbsp sagen Dieses Problem ist auch unter dem Namen Ulams Problem bekannt Satz von Baik Deift Johansson Bearbeiten Fur jedes N 1 displaystyle N geq 1 nbsp sei p N displaystyle pi N nbsp eine unter der Gleichverteilung gezogene Permutation der Lange N displaystyle N nbsp Dann gilt fur jedes x R displaystyle x in mathbb R nbsp P l p N 2 N N 1 6 x F 2 x wenn N 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 nbsp wobei F 2 x displaystyle F 2 x nbsp die Tracy Widom Verteilung des gaussschen unitaren Ensembles GUE bezeichnet KPZ Universalitat Bearbeiten Hauptartikel KPZ Fixpunkt Das Theorem sagt dass sich das asymptotische Verhalten der Verteilung der Lange l p N displaystyle l pi N nbsp unter entsprechender Skalierung gleich verhalt wie das asymptotische Verhalten der Eigenwerte einer gaussschen hermiteschen Zufallsmatrix Das asymptotische Verhalten von l p N displaystyle l pi N nbsp unterliegt der sogenannten KPZ Universalitatsklasse 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 Grenzflachenwachstumsmodell englisch stochastic interface growth model formulieren dem sogenannten polynuklearen Wachstumsmodell englisch polynuclear growth model kurz PNG Modell 2 Einzelnachweise Bearbeiten 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 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 Abgerufen von https de wikipedia org w index php title Satz von Baik Deift Johansson amp oldid 233479441