Anwendungsbeispiele: Monte-Carlo-Simulation

Wie das folgende Beispiel zeigt, kann der $\chi ^2$-Anpassungstest zur Überprüfung der Güte von Zufallszahlengeneratoren bei der Monte-Carlo-Simulation verwendet werden.

Beispiel

$\;$ Test auf Gleichverteilung

• Wir nehmen an, daß die Daten $x_1,\ldots,x_n$ sogenannte Pseudozufallszahlen sind, die von einem Zufallszahlengenerator erzeugt worden sind.
• Dabei wollen wir prüfen, ob die Stichprobe $(x_1,\ldots,x_n)$ als Realisierung von Stichprobenvariablen $X_1,\ldots,X_n$ angesehen werden kann, die gleichverteilt im Intervall $(0,1]$ sind.
• Wir zerlegen das Intervall $(0,1]$ in $r$ gleichlange Teilintervalle $(0,1/r],\ldots,((r-1)/r,1]$ und
• betrachten den $(r-1)$-dimensionalen (hypothetischen) Vektor $p_0=(1/r,\ldots,1/r)$ bzw.
• die Testgröße $T_n:\mathbb{R}^n\to[0,\infty)$ mit
  $$T_n(x_1,\ldots,x_n)=\sum\limits _{j=1}^r\;\frac{(Y_j(x_1,\ldots,x_n)-n/r)^2}{n/r}\;,$$
  wobei $Y_j(x_1,\ldots,x_n)=\char93 \{i:\, 1\le i\le n,\, j-1<rx_i\le j\}$ die Anzahl derjenigen Pseudozufallszahlen $x_1,\ldots,x_n$ bezeichnet, die im Intervall $((j-1)/r,j/r]$ liegen.
• Bei großem $n$ wird die Hypothese $H_0: p=p_0$ abgelehnt, falls $T(x_1,\ldots,x_n)>\chi^2_{r-1,1-\alpha}$.

Für $\alpha=0.05$, $n=100\,000$ und $r=10$ wollen wir nun prüfen, ob

• die Hypothese der Gleichverteilung mit einer (konkreten) Stichprobe $(x_1,\ldots,x_{100\,000})$ von Pseudozufallszahlen vereinbar ist, für die sich der folgende Vektor der Klassenhäufigkeiten $(y_1,\ldots,y_{10})$ ergibt:
  
  
  

  $y_1$	$y_2$	$y_3$	$y_4$	$y_5$	$y_6$	$y_7$	$y_8$	$y_9$	$y_{10}$
  $9\,995$	$10\,045$	$10\,127$	$9\,816$	$10\,130$	$10\,040$	$9\,890$	$9\,858$	$10\,083$	$10\,016$

  
  
  
• In diesem Fall ist $T_{100\,000}(x_1,\ldots,x_{100\,000})=10.99$, und es gilt somit
  $$T_{100\,000}(x_1,\ldots,x_{100\,000})=10.99<\chi^2_{9,0.95}=16.92\,,$$
  wobei das Quantil $\chi^2_{9,0.95}=16.92$ aus Tabelle 2 entnommen wurde.
• Die Hypothese der Gleichverteilung wird also nicht verworfen.

Bei der Überprüfung der Güte von Zufallszahlengeneratoren sind nicht nur Tests auf Gleichverteilung von Interesse. Ein weiteres Gütekriterium besteht darin zu prüfen, ob die von einem Zufallszahlengenerator erzeugten Pseudozufallszahlen $x_1,x_2,\ldots$ als Realisierungen unabhängiger Zufallsvariablen $X_1,X_2,\ldots$ angesehen werden können.

Das folgende Testproblem läßt sich ebenfalls mit Hilfe eines $\chi ^2$-Anpassungstests untersuchen.

Beispiel

$\;$ Test auf Unabhängigkeit (Run-Test)

• Wir wollen nun prüfen, ob die Pseudozufallszahlen $x_1,x_2,\ldots$ als Realisierungen von unabhängigen Zufallsvariablen $X_1,X_2,\ldots$ angesehen werden können, die gleichverteilt im Intervall $(0,1]$ sind.
• Hierfür definieren wir die Zufallsvariablen $U_1,U_2,\ldots$ rekursiv durch

  $$U_{j+1}=\min\{i:\, i>U_j+1, X_i>X_{i+1}\}\,,$$ (71)

  
  
  wobei $U_1=\min\{i:\, i\ge 1, X_i>X_{i+1}\}$.
• Die Zufallsvariablen $V_1,V_2,\ldots$ mit

  $$V_1=U_1\,,\qquad V_{j+1}=U_{j+1}-U_j-1 \mbox{für $j=1,2,\ldots$}$$ (72)

  
  
  werden dann die Runs der Folge $X_1,X_2,\ldots$ genannt.

Der zu konstruierende $\chi ^2$-Anpassungstest beruht auf der folgenden Eigenschaft der Runs.

Theorem 4.8   Die in $(\ref{run1})$ eingeführten Zufallsvariablen $V_1,V_2,\ldots$ sind unabhängig und identisch verteilt mit

$$P(V_j=k)=\frac{k}{(k+1)!}\,,\qquad\forall\, k=1,2,\ldots\,,$$ (73)

falls die Zufallsvariablen $X_1,X_2,\ldots$ unabhängig und (identisch) gleichverteilt im Intervall $(0,1]$ sind.

Beweis

 

• Seien $X_1,X_2,\ldots$ unabhängige und auf $(0,1]$ gleichverteilte Zufallsvariablen.
• Für jedes $n\ge 1$ und für beliebige natürliche Zahlen $k_1,\ldots,k_n\ge 1$ gilt dann
  

  $${ P(V_1=k_1,\ldots,V_n=k_n) = P(U_1=k_1,U_2-U_1-1=k_2,\ldots,U_n-U_{n-1}-1=k_n)}$$

  $$= P\bigl(U_1=k_1,U_2=k_2+k_1+1,\ldots,U_n=k_n+\ldots+k_1+n-1\bigr)$$

  $$= P\bigl(X_i\le X_{i+1},\,\forall\,i=1,\ldots,k_1-1,\,X_{k_1}>X_{k_1+1},$$

  $$\hspace{1cm} X_i\le X_{i+1},\,\forall\,i=k_1+1,\ldots,k_1+k_2-1,\,X_{k_1+k_2}>X_{k_1+k_2+1},\ldots,$$

  $$\hspace{1cm} X_i\le X_{i+1},\,\forall\,i=k_1+\ldots+k_{n-1}+1,\ldots,k_1+\ldots+k_n-1,\, X_{k_1+\ldots+k_n}>X_{k_1+\ldots+k_n+1}\bigr)$$

  $$= P\bigl(X_i\le X_{i+1},\,\forall\,i=1,\ldots,k_1-1,\,X_{k_1}>X_{k_1+1}\bigr)$$

  $$\hspace{1cm} P\bigl(X_i\le X_{i+1},\,\forall\,i=k_1+1,\ldots,k_1+k_2-1,\,X_{k_1+k_2}>X_{k_1+k_2+1}\bigr)$$

  $$\ldots P\bigl(X_i\le X_{i+1},\,\forall\,i=k_1+\ldots+k_{n-1}+1,\ldots,k_1+\ldots+k_n-1,\, X_{k_1+\ldots+k_n}>X_{k_1+\ldots+k_n+1}\bigr)$$

  $$= P\bigl(X_i\le X_{i+1},\,\forall\,i=1,\ldots,k_1-1,\,X_{k_1}>X_{k_1+1}\bigr)$$

  $$\ldots P\bigl(X_i\le X_{i+1},\,\forall\,i=1,\ldots,k_n-1,\, X_{k_n}>X_{k_n+1}\bigr)\,.$$

  
  

• Weil die Zufallsvariablen $X_1,X_2,\ldots$ unabhängig und identisch verteilt sind, folgt hieraus, daß die Runs $V_1,V_2,\ldots$ unabhängig und identisch verteilt sind.
• Außerdem ergibt sich mit vollständiger Induktion, daß für beliebige $k\in\mathbb{R}$ und $t\in(0,1]$

  $$P(X_1\le\ldots\le X_k\le t)=\frac{t^k}{k!}\,.$$ (74)

  
  

• Für $k=1$ ist (74) offenbar richtig, und aus der Formel der totalen Wahrscheinlichkeit ergibt sich, daß
  

  $$P(X_1\le\ldots\le X_{k+1}\le t) = \int\limits_0^1 P(X_1\le\ldots\le X_k\le X_{k+1}\le t\mid X_{k+1}=x)\,P(X_{k+1}\in\, dx)$$

  $$= \int\limits_0^1 P(X_1\le\ldots\le X_k\le x\le t\mid X_{k+1}=x)\,P(X_{k+1}\in\, dx)$$

  $$= \int\limits_0^1 P(X_1\le\ldots\le X_k\le x\le t)\, dx\,,$$

  
  
  wobei sich letzte Gleichheit aus der Unabhängigkeit und U$(0,1]$-Verteiltheit der $X_1,X_2,\ldots$ ergibt.
• Somit gilt
  

  $$P(X_1\le\ldots\le X_{k+1}\le t) = \int\limits_0^t P(X_1\le\ldots\le X_k\le x)\, dx$$

  $$= \int\limits_0^t\;\frac{x^k}{k!}\,dx=\frac{t^{k+1}}{(k+1)!}\;,$$

  
  
  wobei sich die zweite Gleichheit aus der Induktionsannahme ergibt.
• Damit ist (74) bewiesen.
• Aus (74) ergibt sich nun, daß für jedes $k\in\mathbb{N}$
  

  $$P(X_1\le\ldots\le X_k,\,X_k> X_{k+1}) = \int\limits_0^1 P(X_1\le\ldots\le X_k,\,X_k>x)\, dx$$

  $$= \int\limits_0^1 \bigl(P(X_1\le\ldots\le X_k\le 1)- P(X_1\le\ldots\le X_k\le x)\bigr)\, dx$$

  $$= \int\limits_0^1\Bigl(\frac{1}{k!}\;-\;\frac{x^k}{k!}\Bigr)\, dx$$

  $$= \frac{1}{k!}\;-\;\frac{1}{(k+1)!}=\frac{k}{(k+1)!}\;.$$

  
  

• Damit ist auch (73) bewiesen.
  
  $\Box$

Beachte

 

• Es mögen nun hinreichend viele Pseudozufallszahlen $x_1,x_2\ldots$ erzeugt werden, so daß sich aus ihnen gemäß (71) und (72) die $n$ Runs $v_1,\ldots,v_n$ ergeben.
• Wir zerlegen die positive Halbachse in $r$ Intervalle $(a_1,b_1],\ldots,(a_r,b_r]$, so daß
• die Wahrscheinlichkeiten
  $$p_{0,j}=\sum\limits _{k\in\mathbb{N}\cap(a_j,b_j]}\frac{k}{(k+1)!}\,,\qquad j=1,\ldots,r$$
  annähernd gleich sind, und
• für diese Wahrscheinlichkeiten betrachten wir den $(r-1)$-dimensionalen (hypothetischen) Vektor $p_0=(p_{0,1},\ldots,p_{0,r-1})$ bzw.
• die Testgröße $T_n:\mathbb{R}^n\to[0,\infty)$ mit
  $$T_n(v_1,\ldots,v_n)=\sum\limits _{j=1}^r\;\frac{(Y_j(v_1,\ldots,v_n)-np_{0,j})^2}{np_{0,j}}\;,$$
  wobei $Y_j(v_1,\ldots,v_n)=\char93 \{i:\, 1\le i\le n,\, j-1<rv_i\le j\}$ die Anzahl derjenigen Runlängen $v_1,\ldots,v_n$ bezeichnet, die in der $j$-ten Klasse liegen.
• Bei großem $n$, was die Erzeugung entsprechend vieler Pseudozufallszahlen $x_1,x_2,\ldots$ erfordert, wird die Hypothese $H_0: p=p_0$ abgelehnt, falls $T(v_1,\ldots,v_n)>\chi^2_{r-1,1-\alpha}$.