Satz von Ajtai Komlós Tusnády Der auch AKT optimal matching theorem ist ein Satz aus der probabilistischen Kombinatorik

Satz von Ajtai-Komlós-Tusnády

Der Satz von Ajtai-Komlós-Tusnády (auch AKT optimal matching theorem) ist ein Satz aus der probabilistischen Kombinatorik. Gegeben sind zwei zufällige, verschiedene Mengen von Punkten und im Einheitsquadrat . Dann macht der Satz eine Aussage über die obere und untere Schranke der kleinsten Summe der Distanzen der Punkte.

Der Satz wurde 1984 von den ungarischen Mathematikern Miklós Ajtai, János Komlós und Gábor Tusnády bewiesen.

Aussage Bearbeiten

Seien und zwei unabhängige Zufallsvektoren, welche der Gleichverteilung auf folgen (d. h. .) Sei die symmetrische Gruppe und die euklidische Norm in .

Dann gilt

wobei reelle Konstanten sind.

Erläuterungen Bearbeiten

bedeutet

Der Satz sagt, dass

mit hoher Wahrscheinlichkeit.

Literatur Bearbeiten

Sergey Bobkov und Michel Ledoux: A simple Fourier analytic proof of the AKT optimal matching theorem. 2019 (englisch).
Ajtai, M., Komlos, Janos und Tusnády, G.: On optimal matchings. In: Combinatorica. Band 4, 1984, S. 259–264, doi:10.1007/BF02579135 (englisch).
Michel Talagrand: Matching theorems and empirical discrepancy computations using majorizing measures. In: Journal of the American Mathematical Society. Band 7, 1994, S. 455–537, doi:10.1090/S0894-0347-1994-1227476-X (englisch).

Einzelnachweise Bearbeiten

Ajtai, M., Komlos, Janos und Tusnády, G.: On optimal matchings. In: Combinatorica. Band 4, 1984, S. 259–264, doi:10.1007/BF02579135.

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, 23:05 pm

Der Satz von Ajtai Komlos Tusnady auch AKT optimal matching theorem ist ein Satz aus der probabilistischen Kombinatorik Gegeben sind zwei zufallige verschiedene Mengen von Punkten X X 1 X k displaystyle X X 1 dots X k und Y Y 1 Y k displaystyle Y Y 1 dots Y k im Einheitsquadrat 0 1 2 displaystyle 0 1 2 Dann macht der Satz eine Aussage uber die obere und untere Schranke der kleinsten Summe der Distanzen der Punkte Der Satz wurde 1984 von den ungarischen Mathematikern Miklos Ajtai Janos Komlos und Gabor Tusnady bewiesen 1 Inhaltsverzeichnis 1 Aussage 1 1 Erlauterungen 2 Literatur 3 EinzelnachweiseAussage BearbeitenSeien X 1 X k displaystyle X 1 dots X k nbsp und Y 1 Y k displaystyle Y 1 dots Y k nbsp zwei unabhangige Zufallsvektoren welche der Gleichverteilung auf 0 1 2 displaystyle 0 1 2 nbsp folgen d h X i 0 1 2 displaystyle X i in 0 1 2 nbsp Sei S n displaystyle S n nbsp die symmetrische Gruppe und displaystyle cdot nbsp die euklidische Norm in R 2 displaystyle mathbb R 2 nbsp Dann gilt P C 1 n log n lt inf s S n k 1 n X k Y s k lt C 2 n log n 1 o 1 displaystyle mathbb P left C 1 sqrt n log n lt inf limits sigma in S n sum limits k 1 n X k Y sigma k lt C 2 sqrt n log n right 1 o 1 nbsp wobei C 1 C 2 displaystyle C 1 C 2 nbsp reelle Konstanten sind Erlauterungen Bearbeiten o 1 displaystyle o 1 nbsp bedeutetf n o 1 lim n f n 0 displaystyle f n in o 1 iff lim limits n to infty f n 0 nbsp siehe Landau Symbole dd Der Satz sagt dassinf s S n 1 n k 1 n X k Y s k log n n displaystyle inf limits sigma in S n frac 1 n sum limits k 1 n X k Y sigma k sim sqrt frac log n n nbsp dd mit hoher Wahrscheinlichkeit Literatur BearbeitenSergey Bobkov und Michel Ledoux A simple Fourier analytic proof of the AKT optimal matching theorem 2019 englisch Ajtai M Komlos Janos und Tusnady G On optimal matchings In Combinatorica Band 4 1984 S 259 264 doi 10 1007 BF02579135 englisch Michel Talagrand Matching theorems and empirical discrepancy computations using majorizing measures In Journal of the American Mathematical Society Band 7 1994 S 455 537 doi 10 1090 S0894 0347 1994 1227476 X englisch Einzelnachweise Bearbeiten Ajtai M Komlos Janos und Tusnady G On optimal matchings In Combinatorica Band 4 1984 S 259 264 doi 10 1007 BF02579135 Abgerufen von https de wikipedia org w index php title Satz von Ajtai Komlos Tusnady amp oldid 233479543