Punktemengen mit niedriger Diskrepanz spielen eine wichtige Rolle bei der Lösung hochdimensionaler Integrationsprobleme, wie sie zum Beispiel beim Strahlungstransport und in der Finanzmathematik vorkommen. Wir untersuchen verschiedene Typen von Diskrepanzen in hohen Dimensionen. Im Gegensatz zu früheren Zugängen streben wir ein Verständnis der Abhängigkeit nicht (oder nicht nur) von der Zahl der Punkte an, sondern (auch) von der Dimension. Unlängst wurde in [1] folgendes Resultat erzielt: Sei die Zahl der mindestens erforderlichen Punkte, mit denen man eine Sterndiskrepanz kleiner als in Dimension erreichen kann. Dann gilt für fixiertes mit , daß von der Ordnung ist. Dieses scheint das erste Resultat zu sein, das eine scharfe Ordnung der Dimensionsabhängigkeit enthält. Von Bedeutung für hochdimensionale Anwendungen ist es, daß die Abhängigkeit von polynomial (sogar linear) ist. Damit wurden frühere Vermutungen über ein exponentielles Wachstum widerlegt.
Der Beweis der oberen Schranke basiert auf der Theorie der empirischen Prozesse und dem Konzept der Vapnik-Cervonenkis Dimension. Die Techniken sind probabilistisch und zeigen, daß das Resultat für zufällig gewählte Punktmengen gilt, wobei die Fehlerwahrscheinlichkeit exponentiell abklingt. Die Beweistechnik für die untere Schranke stützt sich auf Entropieabschätzungen und ist ebenfalls probabilistisch.
Im Vortrag werden grundlegende Elemente dieser Techniken beschrieben und Verallgemeinerungen auf eine Reihe von geometrischen Diskrepanzen angesprochen. Wir geben auch verschiedene (nicht scharfe) obere und untere Abschätzungen für als Funktion beider Variablen and an und diskutieren diesbezügliche offene Probleme.
[1] | S. Heinrich, E. Novak, G. W. Wasilkowski, H. Wozniakowski, The inverse of the star-discrepancy depends linearly on the dimension, to appear in Acta Arithmetica, 2001 |