next up previous contents
Nächste Seite: Rotationen und Operatordiskrepanz Aufwärts: Diskrepanzen auf der Kugel Vorherige Seite: Diskrepanzen   Inhalt

Kugelkappendiskrepanz, Methode von Beck

Auf der $S^{d-1}$ sei eine n-elementige Punktmenge $\{P_1,..,P_n\}$ gegeben. ${\mathbf{\mathit C}} = {\mathbf{\mathit C}}({\mathbf v},t):=
\{{\mathbf y} \in S^{d-1}: {\mathbf v} \cdot {\mathbf y} \leq t \}$ sei eine Kugelkappe.
In dieser Definition bezeichnet ${\mathbf v}$ allerdings nicht den Scheitelpunkt der Kappe, sondern dessen Antipode; und auch der Normalabstand t der Kappe vom Mittelpunkt der Kugel wird in der von der Kappe wegweisenden Richtung gemessen. Daher ist für eine Kappe im üblichen Sinn der Wert von t stets negativ.
Wir können nun auf der Sphäre in natürlicher Weise folgende Maße einführen:
(i) das Zählmaß $Z_0({\mathbf{\mathit C}}):= \char93  \{P_i: P_i \in {\mathbf{\mathit C}}\} = \char93  \{P_1,..,P_n \} \cap {\mathbf{\mathit C}}$ und
(ii) das ''Oberflächenmaß'' $\omega_0({\mathbf{\mathit C}}):= n \cdot \omega^*({\mathbf{\mathit C}}):= n \cdot \omega({\mathbf{\mathit C}})/\omega(S^{d-1})$
Mit $\omega^*$ wollen wir im weiteren stets das normierte Oberflächenmaß $\omega/\omega_{d-1}$ bezeichnen.
Durch diese beiden Maße erhalten wir, analog zu (1.2) eine Diskrepanz $B_N({\mathbf{\mathit C}}):= Z_0({\mathbf{\mathit C}}) -
\omega_0({\mathbf{\ma...
...{P_i : P_i \in {\mathbf{\mathit C}}\} - n \cdot \omega^* ({\mathbf{\mathit C}})$, die '' Kugelkappendiskrepanz'' heißt [3]. Für den Betrag dieser Diskrepanz wollen wir nun obere und untere Schranken berechen.
Dazu sei ${\huge 1}_r({\mathbf x})$ die charakteristische Funktion einer Vollkugel mit Radius r und Mittelpunkt ${\mathbf x}$. Unter ${\mathit f} \ast {\mathit g}$ verstehen wir das Faltungsprodukt auf $R^d$, das so definiert ist:

\begin{displaymath}
({\mathit f} \ast {\mathit g})({\mathbf x}):=
\int_{{\rm...
... a})
\cdot {\mathit g}({\mathbf a}){\mathit d}{\mathbf a}.
\end{displaymath}

Weiters brauchen wir im folgenden stets die Funktion $F_r$:

\begin{displaymath}
F_r({\mathbf x}):= ({\huge 1}_r \ast (dZ_0\ -d\sigma_0 ))({...
...})-{\mathit d}\omega_0({\mathbf a})){\mathit d}{\mathbf a} =
\end{displaymath}


\begin{displaymath}
= \char93  \{P_i: P_i \in B^d({\mathbf x},r)\}-n \cdot \omega^* (B^d({\mathbf x},r) \cap S^{d-1}) =
\end{displaymath}


\begin{displaymath}
= \char93  \{P_i: P_i \in (B^d({\mathbf x},r) \cap S^{d-1} )\}-n \cdot
\omega^* (B^d({\mathbf x},r) \cap S^{d-1}) =
\end{displaymath}


\begin{displaymath}
= B^d (B_N({\mathbf x},r) \cap S^{d-1})
\end{displaymath} (2.6)

Um Aussagen über die Diskrepanz treffen zu können, geht man so vor, daß man das Integral $\int_1^2 \int_{{\rm I\mkern-3mu R}^d} \vert F_r({\mathbf x})\vert^2 {\mathit d}{\mathbf x}{\mathit d}r$ abschätzt und anschließend durch das zugehörige Maximum ersetzt.
$B^d({\mathbf x},r)$ schneidet aus der Sphäre $S^{d-1}$ eine Kugelkappe ${\mathbf{\mathit C}}({\mathbf v},t)$ heraus. Bezeichnen wir mit x den Betrag von ${\mathbf x}$, so sind die Kappenparameter: ${\mathbf v} = -{\mathbf x}/x$ und $t = (r^2-1-x^2)/(2 \cdot x)$.
Diese Parameterwerte erhält man aus folgender Überlegung:
${\mathbf v}$ ist der von ${\mathbf x}$ wegweisende Schnittpunkt der Sphäre mit der Geraden ${\mathcal G}$, die ${\mathbf x}$ mit dem Ursprung (das sei der Mittelpunkt der Sphäre) verbindet.
Für t benötigen wir folgende Überlegung: Es sei ${\mathbf y} \in B^d({\mathbf x},r) \cap S^{d-1}$ und ${\mathit l}$ sei der Lotpunkt von ${\mathbf y}$ auf ${\mathcal G}$. Dann sind die Winkel $\angle({\mathit o},{\mathit l},{\mathbf y})$ und $\angle({\mathbf x},{\mathit l},{\mathbf y})$ rechte Winkel. Auf die beiden rechtwinkeligen Dreiecke $\Delta({\mathit o},{\mathit l},{\mathbf y})$ und $\Delta({\mathbf x},{\mathit l},{\mathbf y})$ wenden wir nun den Satz von Pythagoras an und beachten, daß gilt: $\vert {\mathit o},{\mathit l} \vert = t$, $\vert {\mathit o},{\mathbf y} \vert = 1$, $\vert {\mathbf x},{\mathit l} \vert = x$ und $\vert {\mathbf x},{\mathbf y} \vert = r$.
Wir erhalten das Ergebnis: $1-t^2 = \vert {\mathbf y},{\mathit l} \vert^2 = r^2-(x+t)^2$, aus dem die Formel für t folgt.
Nun betrachten wir zwei Sonderfälle:
Für $1 + r < x$ liegt die Kugel $B^d({\mathbf x},r)$ vollständig im Komplement von $S^{d-1}$. Das heißt, daß der Schnitt leer ist und daß daher $F_r({\mathbf x}) \equiv 0$ für $\vert{\mathbf x}\vert > r + 1$ ist.
Ist umgekehrt $r > x + 1$, so ist $S^{d-1}$ vollständig in $B^d({\mathbf x},r)$ enthalten. Dann ist $B^d({\mathbf x},r) \in S^{d-1} = S^{d-1}$ und es gilt:

\begin{displaymath}
Z_0(B^d({\mathbf x},r)\cap S^{d-1})= Z_0(S^{d-1}) = \char93  \{P_i: P_i \in S^{d-1} \} = n
\end{displaymath}

und

\begin{displaymath}
\omega_0(B^d({\mathbf x},r)\cap S^{d-1}) = n \cdot \omega^* (S^{d-1}) = n \cdot 1 = n.
\end{displaymath}

Daher ist $F_r({\mathbf x})$ auch für $\vert {\mathbf x} \vert < r - 1$ ident Null.
Die soeben durchgeführten Überlegungen wenden wir nun auf $B_N(B^d({\mathbf x},r) \cap S^{d-1})$ an und erhalten: $\int_1^d \int_{{\rm I\mkern-3mu R}^d} \vert F_r({\mathbf x}) \vert ^2 {\mathit d}{\mathbf x} {\mathit d}r = $

\begin{displaymath}
= \int_1^2 \int_{{\rm I\mkern-3mu R}^d} \vert \char93  \{P_...
...\cap S^{d-1} )\vert^2
{\mathit d}{\mathbf x}{\mathit d}r =
\end{displaymath}


\begin{displaymath}
\int_1^2 \int_{{\rm I\mkern-3mu R}^d} \vert \char93  \{P_i ...
...mathbf x},r)) \vert^2
{\mathit d}{\mathbf x}{\mathit d}r =
\end{displaymath}


\begin{displaymath}
\int_1^2 \int_{r-1}^{r+1} \int_{{\rm I\mkern-3mu R}^d} =
...
...^2
{\mathit d}\frac{{\mathbf x}}{x}{\mathit d}x{\mathit d}r
\end{displaymath}


Da ${\mathbf v}$ nur von ${\mathbf x}$ abhängt und sich auf ganz $S^{d-1}$ bewegt, ist ${\mathit d}({\mathbf x}/x) = {\mathit d}\omega({\mathbf v})/\omega_d$. Weiters ist t nur abhängig von $x =\vert {\mathbf x}\vert$ und r.
Daher ist das bisherige Integral gleich:

\begin{displaymath}
\int_1^2 \int_{r-1}^{r+1} \frac{1}{\omega_d} \cdot
\int_...
...
{\mathit d}\omega({\mathbf v})
{\mathit d}x {\mathit d}r.
\end{displaymath}

Betrachtet man $t = t(x,r)$ nur als Funktion von x [= $t_r(x)$], so kann man folgende Transformation durchführen :

\begin{displaymath}
\int_1^2 \int_{r-1}^{r+1} \frac{1}{\omega_d} \cdot
\int_...
...{\mathit d}\omega({\mathbf v})
{\mathit d}x {\mathit d}r =
\end{displaymath}


\begin{displaymath}
\int_1^2 \int_{r-1}^{r+1} \frac{1}{\omega_d} \cdot
\int_...
... {\mathit d}\omega({\mathbf v})
{\mathit d}x {\mathit d}r =
\end{displaymath}


\begin{displaymath}
\int_1^2 \max \vert \frac{1}{t'_r(x)} \vert \cdot
\int_...
...{\mathit d}\omega({\mathbf v})
{\mathit d}t_r {\mathit d}r,
\end{displaymath}

da wegen $2x \cdot t = r^2 -1-x^2$ gilt: $x = r \pm 1 \Leftrightarrow t = \mp 1.$ Dieses Integral ist ( wegen $\int_a^b f \leq (b-a) \cdot \max \vert f \vert$ ) kleiner gleich:

\begin{displaymath}
(2-1) \cdot \max_{1 < r < 2 \atop r-1 < x < r+1}
\vert ...
...},t) \vert ^2
{\mathit d}\omega({\mathbf v}){\mathit d}t =
\end{displaymath}


\begin{displaymath}
\vert \frac{1}{ \inf_{1 < r < 2 \atop r-1 < x < r+1} (\par...
...) \vert ^2
{\mathit d}\omega({\mathbf v}){\mathit d}t \leq
\end{displaymath}


\begin{displaymath}
Konst \cdot
\int_{-1}^{+1} \frac{1}{\omega_d} \cdot \Big...
...v},t) )
{\mathit d}\omega({\mathbf v}) \Bigr) {\mathit d}t,
\end{displaymath}

da das angegebene Infimum stets $\geq Konst > 0$ ist [3].
Wir führen nun für zwei Funktionen f und g das Symbol $\ll$ ein:
\begin{displaymath}
{\mathit f} \ll {\mathit g} \Leftrightarrow E Konstante c >0 mit
\vert {\mathit f} \vert \leq c \cdot {\mathit g}
\end{displaymath} (2.7)

Damit können wir die bisherigen Rechnungen zusammenfassen in:

\begin{displaymath}
\int_1^2 \int_{{\rm I\mkern-3mu R}^d} \vert F_r({\mathbf x}...
...bf v},t)) {\mathit d}\omega({\mathbf v}) \Bigr) {\mathit d}t,
\end{displaymath}


Mit Hilfe von Fouriertransformierten kann man zeigen [2],[3], daß gilt:

\begin{displaymath}
\int_1^2 \int_{{\rm I\mkern-3mu R}^d} \vert F_r({\mathbf x}...
...t ^2 {\mathit d}{\mathbf x} {\mathit d} r \gg
n^{1-1/(d-1)}
\end{displaymath}

Daher können wir die Diskrepanz abschätzen durch:

\begin{displaymath}
n^{1-1/(d-1)} \ll
\int_{-1}^{+1} \frac{1}{\omega_d} \cdot...
...bf v},t)) {\mathit d}\omega({\mathbf v}) \Bigr) {\mathit d}t,
\end{displaymath}

Da man ein Mittel nach oben stets durch das zugehörige Maximum abschätzen kann, folgt der Satz:
Es gibt zu jeder Menge $\{{\mathit P}_1,..,{\mathit P}_n \}$ von n Punkten auf der Kugel eine sphärische Kappe ${\mathbf{\mathit C}}({\mathbf v},t)$, für die gilt: $\vert B_N({\mathbf{\mathit C}}({\mathbf v},t))\vert $ =
\begin{displaymath}
\vert \char93  \{P_i \in {\mathbf{\mathit C}}({\mathbf v},t...
...athit C}}({\mathbf v},t) \vert
> c(d) \cdot n^{1/2-1/(2d-1)}
\end{displaymath} (2.8)

[Tatsächlich ist $\omega^*$ nur abhängig von t, da nur dieser Parameter Einfluß auf die Oberfläche der Kappe hat. Beck notiert deswegen anstelle von $\omega^*({\mathbf{\mathit C}}({\mathbf v},t))$ stets $\omega^*(t)$.]
Um $\vert B_N\vert$ in die andere Richtung abschätzen zu können, führte Beck in [3] eine wichtige wahrscheinlichkeitstheoretische Methode ein, die nun erläutert werden soll.
Dazu führen wir Polarkoordinaten ein, zum Beispiel so: Bezeichnet $(x_1,...,x_d)$ einen Punkt der $S^{d-1}$, so setzen wir:

\begin{displaymath}
x_1 = \cos \theta_1 ,
x_2 = \sin \theta_1 \cdot \cos \the...
..... ,
x_d = \sin \theta_1 \cdot ... \cdot \sin \theta_{d-1},
\end{displaymath}

Dabei bewegen sich Polarkoordinaten zwischen :
$0 \leq \theta_{\mu} \leq \pi$ für $\mu = 1,..,d-2$ und $0 \leq \theta_{d-1} \leq 2\pi$
Als nächstes zerlegen wir die $S^{d-1}$ in n Koordinatenkästchen der Form $Q_l = \{(\theta_1,..,\theta_{d-1} )\}$. Man kann [3] die Kästchen so wählen, daß gilt:

\begin{displaymath}
S^{d-1} = Q_1 \cup ... \cup Q_n
\end{displaymath}


\begin{displaymath}
\omega(Q_l) = \omega ( S^{d-1} )/n = \omega_d/n
\end{displaymath}


\begin{displaymath}
diam Q_l = \sup_{{\mathbf x},{\mathbf y} \in Q_l} \vert {\mathbf x} - {\mathbf y}\vert \ll n^{-1/(d-1)}
\end{displaymath} (2.9)

[Unter diam Q ist der Durchmesser von Q zu verstehen.]
Aus jedem Bereich $Q_l$ wählen wir gleichmäßig und unabhängig voneinander einen Zufallspunkt ${\mathit p}_l$ aus. Das bedeutet, daß die unabhängige Auswahl so erfolgt, daß für jede meßbare Menge ${\mathbf{\mathit H}} \subseteq S^{d-1}$ gilt:

\begin{displaymath}
{\huge W}({\mathit p}_l \in {\mathbf{\mathit H}} =
\omega({\mathbf{\mathit H}} \ Q_l )/\omega(Q_l).
\end{displaymath}

Auf diese Weise erhalten wir eine Menge ${\mathcal P}$ von n Punkten auf der Kugel, deren Diskrepanz $B_N$ wir nun berechnen.
[ $\overline{{\mathbf{\mathit C}}} = {\mathbf{\mathit C}}({\mathbf v},t)$ sei eine beliebige aber feste Kappe und unter ${\mathbf{\mathit C}} = \bigcup \{ Q_l:Q_l \subset {\mathbf{\mathit C}} \}$ verstehen wir die Vereinigung aller Kästchen, die in ${\mathbf{\mathit C}}$ liegen. $\overline{{\mathbf{\mathit C}}}$ enthält genau so viele Zufallspunkte, wie der Erwartungswert angibt. D.h. es ist $B_N(\overline{{\mathbf{\mathit C}}}) = \char93  \{ {\mathit p}_l :{\mathit p}_l...
...}}} \} -
n \cdot \omega^* (\overline{{\mathbf{\mathit C}}})/\omega_{d-1} = 0$. Weiters sei ${\mathcal L}({\mathbf{\mathit C}})$ die Menge der Indizes jener Bereiche $Q_l$ die am Rand von ${\mathbf{\mathit C}}$ zu liegen kommen, dh. jener Kästchen, die sowohl mit ${\mathbf{\mathit C}}$ als auch mit $S^{d-1} \backslash {\mathbf{\mathit C}}$ innere Punkte gemeinsam haben. Klarerweise liegen in ${\mathbf{\mathit C}} \\ \overline{{\mathbf{\mathit C}}}$ genau $\char93 {\mathcal L}({\mathbf{\mathit C}})$ Kästchen und es ist:

\begin{displaymath}
{\mathbf{\mathit C}} \backslash \overline{{\mathbf{\mathit ...
...\bigcup \{ Q_l : l \in {\mathcal L}({\mathbf{\mathit C}}) \}.
\end{displaymath}

Da der Durchmesser eines jeden Kästchens $ \ll n^{-1/(d-1)}$ ist, können auf einem ''Breitenkreis'' höchstens ''Kreisumfang''/ ''Kästchendurchmesser'' Kästchen liegen. Aus dieser Überlegung folgt, daß $ \char93  {\mathcal L}({\mathbf{\mathit C}}) \ll n^{1-1/(d-1)}$ sein muß [3].
Für die Randmenge ${\mathbf{\mathit C}} \backslash \overline{ {\mathbf{\mathit C}} }$ definieren wir eine Zufallsvariable $\xi_l$:
$\xi_l = 1$ für ${\mathit p}_l \in {\mathbf{\mathit C}} \cap Q_l$ und $\xi_l = 0$ sonst.
Mit dieser Zufallsvariablen können wir die folgenden Umformungen vornehmen. Dabei beachten wir, daß gilt:

\begin{displaymath}
B_N(\overline{{\mathbf{\mathit C}}}) = 0
\end{displaymath}


\begin{displaymath}
\char93 \{{\mathit p}_l : {\mathit p}_l \in {\mathbf{\mathit C}} \} =
\sum_{{\mathbf{\mathit C}}} 1
\end{displaymath}


\begin{displaymath}
l \in {\mathcal L}({\mathbf{\mathit C}}) \Leftrightarrow {...
...athbf{\mathit C}} \backslash \overline{{\mathbf{\mathit C}}}.
\end{displaymath}

Es gilt also:

\begin{displaymath}
B_N({\mathbf{\mathit C}}) = \char93  \{{\mathit p}_l:{\math...
...thbf{\mathit C}}\}-n \cdot \omega^* ({\mathbf{\mathit C}}) =
\end{displaymath}


\begin{displaymath}
= \char93  \{ {\mathit p}_l : {\mathit p}_l \in \overline{{...
...} \backslash \overline{{\mathbf{\mathit C}}} )/\omega_{d-1} =
\end{displaymath}


\begin{displaymath}
= \char93  \{{\mathit p}_l : {\mathit p}_l \in {\mathbf{\ma...
...} \backslash \overline{{\mathbf{\mathit C}}} )/\omega_{d-1} =
\end{displaymath}


\begin{displaymath}
= \char93  \{{\mathit p}_l : {\mathit p}_l \in {\mathbf{\ma...
...h (\overline{{\mathbf{\mathit C}}} \cap Q_l) )/\omega_{d-1} =
\end{displaymath}


\begin{displaymath}
= \sum_{l \in {\mathcal L}({\mathbf{\mathit C}})} \xi_l -
...
...athcal L}({\mathbf{\mathit C}})}( \xi_l - {\huge E}(\xi_l) ).
\end{displaymath}

Zusammenfassend ergibt sich:
\begin{displaymath}
B_N({\mathbf{\mathit C}}) = \char93  \{ {\mathit p}_l : {\m...
...athcal L}({\mathbf{\mathit C}})}( \xi_l - {\huge E}(\xi_l) ).
\end{displaymath} (2.10)

Mit der Abkürzung $\eta_l :=\xi_l-{\huge E}(\xi_l)$ schreibt sich diese Gleichung an als $B_N({\mathbf{\mathit C}}) = \sum_l \eta_l$, wobei über ${\mathcal L}({\mathbf{\mathit C}})$ zu summieren ist.
Da die Auswahl der ${\mathit p}_l$ unabhängig voneinander erfolgte, sind auch $\xi_l$ und $\eta_l$ unabhängige Zufallsvariablen. Daher gilt

\begin{displaymath}
{\huge E}(\sum_l \eta_l )^2 =
{\huge E}((\sum_{l1} \eta_...
...sum_{l1} \sum_{l2} {\huge E}(\eta_{l_1} \cdot \eta_{l_2} ) =
\end{displaymath}


\begin{displaymath}
= \sum_{l1} \sum_{l2} {\huge E}(\eta_{l_1}) \cdot {\huge E}...
... L}({\mathbf{\mathit C}})}{\huge E}(\xi_l -{\huge E}(\xi_l)).
\end{displaymath}

Daraus erhält man:

\begin{displaymath}
{\huge E}(\char93 \{{\mathit p}_l:{\mathit p}_l \in {\mathb...
...cal L}({\mathbf{\mathit C}})}(\xi_l -{\huge E}(\xi_l)) ) \leq
\end{displaymath}


\begin{displaymath}
\sum_{l \in {\mathcal L}({\mathbf{\mathit C}})}{\huge E}(\...
...\char93  {\mathcal L}({\mathbf{\mathit C}}) \ll n^{1-1/(d-1)}
\end{displaymath}

Damit ist:
\begin{displaymath}
{\huge E} \Bigl(
\int_{-1}^{+1} \frac{1}{\omega_d} \cdot \...
...ga({\mathbf v}) \Bigr) {\mathit d}t
\Bigr) \ll n^{1-1/(d-1)}
\end{displaymath} (2.11)

Da der Erwartungswert als ein gewichtetes Mittel aufgefaßt werden kann, daher folgt aus (8) unmittelbar die Existenz einer Kappe ${\mathbf{\mathit C}}$, die diese Abschätzung erfüllt.
Auf ${\huge E}(\sum_l \eta_l)^2$ können wir aber auch folgendes Lemma [eine Bernstein-Chernoff-Ungleichung] anwenden [3]:
Es seien $X_1,...,X_m$ unabhängige Zufallsvariablen mit Betrag $\leq 1$ und es sei $\beta = \sum_{i=1}^m {\huge E}(X_i -{\huge E}(X_i))^2$. Dann ist:
\begin{displaymath}
{\Huge W}\Bigl( \vert
\sum_{i=1}^m {\huge E}(X_i -{\huge ...
...ad f\uml {u}r \; \gamma \; \leq \beta
\end{array}
\right.
\end{displaymath} (2.12)

Daraus erhält man den folgenden Satz ([3], Theorem 24D) ( vgl. mit (5) ):
Für jede Menge $\{P_1,...,P_n\}$ von n Punkten auf der $S^{d-1}$ gibt es eine sphärische Kappe ${\mathbf{\mathit C}}$ und eine Konstante $C > 0$ sodaß gilt:
\begin{displaymath}
\vert B_N({\mathbf{\mathit C}}) \vert =
\vert \char93  \...
...C}}) \vert
< C \cdot n^{1/2-1/(2d-2)} \cdot (\log n)^{1/2}
\end{displaymath} (2.13)

Mit der Kugelkappendiskrepanz verwandt ist die Spaltendiskrepanz. Sie verwendet an der Stelle von Kugelkappen Spalten (slices), das sind Schnitte zweier Großkreisbögen, also Kugelzweiecke. Der Autor in [7] beweist, daß diese Diskrepanz durch die Kugelkappendiskrepanz abgeschätzt werden kann, und daß daher dieselben Abschätzungen wie bei dieser gelten.
next up previous contents
Nächste Seite: Rotationen und Operatordiskrepanz Aufwärts: Diskrepanzen auf der Kugel Vorherige Seite: Diskrepanzen   Inhalt

2004-03-25