15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Minisymposium Zahlentheoretische Algorithmen und ihre Anwendungen
Dienstag, 18. September 2001, 16.40, Audimax der Universität Wien

 

Über die Abhängigkeit der Diskrepanz von der Dimension

Stefan Heinrich, Kaiserslautern

 

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 $n_\infty^* (d, \varepsilon)$ die Zahl der mindestens erforderlichen Punkte, mit denen man eine Sterndiskrepanz kleiner als $\varepsilon$ in Dimension $d$ erreichen kann. Dann gilt für fixiertes $\varepsilon$ mit $0<\varepsilon \le 1/64$, daß $n_\infty^* (d, \varepsilon)$ von der Ordnung $d$ 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 $d$ 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 $n_\infty^* (d, \varepsilon)$ als Funktion beider Variablen $d$ and $\varepsilon$ 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

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden