Tests von Güteeigenschaften

• In der Literatur werden zahlreiche statistische Signifikanztests diskutiert, um Güteeigenschaften von Zufallszahlengeneratoren zu untersuchen, vgl. beispielsweise das Buch von G.S. Fishman (1996) Monte Carlo: Concepts, Algorithms and Applications, Springer-Verlag, New York.

• Wir erinnern hier lediglich an zwei solche Tests, die
  • im Zusammenhang mit der Untersuchung der Güteeigenschaften von linearen Kongruenzgeneratoren (oder von anderen Zufallszahlen-Generatoren) eine Rolle spielen und
  • bereits in der Vorlesung ,,Statistik I'' erwähnt wurden.

• Dabei wird der $\chi ^2$-Anpassungstest von Pearson (vgl. Abschnitt 5.1 der Vorlesung ,,Statistik II'') verwendet, um zu prüfen,
  • ob die erzeugten Pseudozufallszahlen als Realisierungen von gleichverteilten Zufallsvariablen aufgefasst werden können und
  • ob davon ausgegangen werden kann, dass diese Zufallsvariablen unabhängig sind.

• Ein anderes Verfahren zur Erzeugung von Zahlenfolgen $u_1,u_2,\ldots$ mit günstigen Güteeigenschaften
  • beruht auf der Minimierung des Kolmogorov-Abstandes (vgl. Abschnitt 1.5 der Vorlesung ,,Statistik I'')
    $$D_n(u_1,\ldots,u_n)=\sup\limits_{x\in(0,1]}\Bigl\vert\;\frac{1}{n}\; \char93 \bigl\{i:\, 1\le i\le n,\, 0<u_i\le x\bigr\}-x\Bigr\vert$$
    zwischen der empririschen Verteilungsfunktion der ,,Stichprobe'' $u_1,\ldots,u_n$ und der Verteilungsfunktion der $(0,1]$-Gleichverteilung, und zwar für jede natürliche Zahl $n$.
  • Diese Vorgehensweise wird in der Literatur Quasi-Monte-Carlo-Methode genannt, vgl. zum Beispiel das Buch von H. Niederreiter (1992) Random Number Generation and Quasi-Monte-Carlo Methods, SIAM, Philadelphia.

1. $\chi ^2$-Anpassungstests auf Gleichverteilung

   Wir betrachten zunächst den folgenden Test, um zu prüfen, ob die Pseudozufallszahlen $u_1,\ldots,u_n$

   • als Realisierungen von unabhängigen Stichprobenvariablen $U_1,\ldots,U_n$ angesehen werden können, die gleichverteilt im Intervall $(0,1]$ sind.
   • Hierfür zerlegen wir das Intervall $(0,1]$ in $r$ gleichlange Teilintervalle $(0,1/r],\ldots,((r-1)/r,1]$ und
     • betrachten den $(r-1)$-dimensionalen (hypothetischen) Parametervektor ${\mathbf{p}}_0=(1/r,\ldots,1/r)$ bzw.
     • die Testgröße $T_n:\mathbb{R}^n\to[0,\infty)$ mit
       $$T_n(u_1,\ldots,u_n)=\sum\limits _{j=1}^r\;\frac{(Z_j(u_1,\ldots,u_n)-n/r)^2}{n/r}\;,$$
       wobei $Z_j(u_1,\ldots,u_n)=\char93 \{i:\, 1\le i\le n,\, j-1<ru_i\le j\}$ die Anzahl derjenigen Pseudozufallszahlen $u_1,\ldots,u_n$ bezeichnet, die im Intervall $((j-1)/r,j/r]$ liegen.
   • Weil die Testgröße $T_n$ asymptotisch $\chi^2_{r-1}$-verteilt ist,
     • falls die Stichprobenvariablen $U_1,\ldots,U_n$ unabhängig und im Intervall $(0,1]$ gleichverteilt sind (vgl. Theorem 5.1 des Vorlesungsskriptes ,,Statistik II''),
     • wird bei hinreichend großem $n$ die Hypothese $H_0:{\mathbf{p}}={\mathbf{p}}_0$ abgelehnt, falls
       $$T_n(u_1,\ldots,u_n)>\chi^2_{r-1,1-\alpha}\,,$$
       wobei $\chi^2_{r-1,1-\alpha}$ das $(1-\alpha)$-Quantil der $\chi ^2$-Verteilung mit $r-1$ Freiheitsgraden bezeichnet.
   • Wir illustrieren dies mit Hilfe des folgenden Zahlenbeispiels. Für $\alpha=0.05$, $n=100\,000$ und $r=10$ soll geprüft werden, ob
     • die Hypothese der Gleichverteilung mit einer (konkreten) Stichprobe $(u_1,\ldots,u_{100\,000})$ von Pseudozufallszahlen vereinbar ist, für die sich der folgende Vektor der Klassenhäufigkeiten $(z_1,\ldots,z_{10})$ ergibt:

       
       
       

       $z_1$	$z_2$	$z_3$	$z_4$	$z_5$	$z_6$	$z_7$	$z_8$	$z_9$	$z_{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}(u_1,\ldots,u_{100\,000})=10.99$, und es gilt somit
       $$T_{100\,000}(u_1,\ldots,u_{100\,000})=10.99<\chi^2_{9,0.95}=16.92\,.$$

     • Die Hypothese der $(0,1]$-Gleichverteilung wird also nicht verworfen.

   Beachte

    

   • In Verallgemeinerung des bisher betrachteten $\chi ^2$-Tests auf Gleichverteilung kann man auch prüfen,
     • ob für eine vorgegebene natürliche Zahl $d\ge 1$ (beispielsweise $d=2$ oder $d=3$) die Pseudozufallsvektoren $(u_1,\ldots,u_d),\ldots,(u_{(n-1)d+1},\ldots,u_{nd})$
     • als Realisierungen von unabhängigen Zufallsvektoren $(U_1,\ldots,U_d),\ldots,(U_{(n-1)d+1},\ldots,U_{nd})$ angesehen werden können, die gleichverteilt in $(0,1]^d$ sind.
   • Hierfür wird der Einheitswürfel $(0,1]^d$
     • in $r^d$ gleichgroße Teilwürfel $B_j$ vom Typ $((i_1-1)/r,i_1/r]\times\ldots\times((i_d-1)/r,i_d/r]$ zerlegt und
     • der $(r^d-1)$-dimensionale (hypothetische) Parametervektor ${\mathbf{p}}_0=(1/r^d,\ldots,1/r^d)$ bzw.
     • die Testgröße $T_n:\mathbb{R}^{nd}\to[0,\infty)$ mit
       $$T_n({\mathbf{u}}_1,\ldots,{\mathbf{u}}_n)=\sum\limits _{j=1}^{r^d}\;\frac{(Z_j({\mathbf{u}}_1,\ldots,{\mathbf{u}}_n)-n/r^d)^2}{n/r^d}$$
       betrachtet, wobei ${\mathbf{u}}_i=(u_{(i-1)d+1},\ldots,u_{id})$ und $Z_j({\mathbf{u}}_1,\ldots,{\mathbf{u}}_n)=\char93 \{i:\, 1\le i\le n,\, {\mathbf{u}}_i\in B_j\}$ die Anzahl derjenigen Pseudozufallsvektoren ${\mathbf{u}}_1,\ldots,{\mathbf{u}}_n$ bezeichnet, die in $W_j$ liegen.

   
   

2. Run-Test

   Zur Überprüfung der Güte von Zufallszahlengeneratoren gibt es noch weitere statistische Signifikanztests, durch die verifiziert werden kann,

   • ob die erzeugten Pseudozufallszahlen $u_1,\ldots,u_n$ als Realisierungen von unabhängigen Zufallsvariablen $U_1,\ldots,U_n$ mit einer bestimmten Verteilung (im vorliegenden Fall die $(0,1]$-Gleichverteilung) angesehen werden können.
   • Bei dem folgenden Run-Test wird insbesondere geprüft,
     • ob auch die Modellannahme der Unabhängigkeit der Stichprobenvariablen $U_1,\ldots,U_n$ hinreichend gut durch die Pseudozufallszahlen $u_1,\ldots,u_n$ widergespiegelt wird,
     • indem die Längen monoton wachsender Teilfolgen, sogenannte Runs, innerhalb der Folge der Pseudozufallszahlen $u_1,u_2,\ldots$ untersucht werden.
   • Hierfür definieren wir zunächst die Zufallsvariablen $V_1,V_2,\ldots$ rekursiv durch

     $$V_{j+1}=\min\{i:\, i>V_j+1, U_i>U_{i+1}\}\,,\qquad\forall\, j=1,2,\ldots\,,$$ (5)

     
     
     wobei $V_1=\min\{i:\, i\ge 1, U_i>U_{i+1}\}$.
   • Die Zufallsvariablen $W_1,W_2,\ldots$ mit

     $$W_1=V_1 \qquad W_{j+1}=V_{j+1}-(V_j+1) \mbox{für $j=1,2,\ldots$}$$ (6)

     
     
     werden dann die Runs der Folge $U_1,U_2,\ldots$ genannt.

   
   Der zu konstruierende Signifikanztest beruht auf der folgenden Eigenschaft der Runs $W_1,W_2,\ldots$.

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

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

   
   

   falls die Zufallsvariablen $U_1,U_2,\ldots$ unabhängig und gleichverteilt im Intervall $(0,1]$ sind.

   Beweis

    

   • Seien $U_1,U_2,\ldots$ unabhängige und in $(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(W_1=k_1,\ldots,W_n=k_n) = P(V_1=k_1,V_2-V_1-1=k_2,\ldots,V_n-V_{n-1}-1=k_n)}$$

       $$= P\bigl(V_1=k_1,V_2=k_2+k_1+1,\ldots,V_n=k_n+\ldots+k_1+n-1\bigr)$$

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

       $$U_i\le U_{i+1},\,\forall\,i=k_1+2,\ldots,k_1+1+k_2-1,\,U_{k_1+1+k_2}>U_{k_1+1+k_2+1},\ldots,$$

       $$U_i\le U_{i+1},\,\forall\,i=k_1+1+\ldots+k_{n-1}+2,\ldots,k_1+1+\ldots+k_{n-1}+1+k_n-1,\,$$

       $$\hspace{3cm} U_{k_1+1+\ldots+k_{n-1}+1+k_n}>U_{k_1+1+\ldots+k_{n-1}+1+k_n+1}\bigr)$$

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

       $$P\bigl(U_i\le U_{i+1},\,\forall\,i=k_1+2,\ldots,k_1+1+k_2-1,\,U_{k_1+1+k_2}>U_{k_1+1+k_2+1}\bigr)$$

       $$\ldots P\bigl(U_i\le U_{i+1},\,\forall\,i=k_1+1+\ldots+k_{n-1}+2,\ldots,k_1+1+\ldots+k_{n-1}+1+k_n-1,\,$$

       $$\hspace{3cm} U_{k_1+1+\ldots+k_{n-1}+1+k_n}>U_{k_1+1+\ldots+k_{n-1}+1+k_n+1}\bigr)$$

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

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

       
       

     • Hieraus folgt, dass die Runs $W_1,W_2,\ldots$ unabhängig und identisch verteilt sind.
   • Außerdem ergibt sich mit vollständiger Induktion, dass für beliebige $k\in\mathbb{R}$ und $t\in(0,1]$

     $$P(U_1\le\ldots\le U_k\le t)=\frac{t^k}{k!}\,.$$ (8)

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

       $$P(U_1\le\ldots\le U_{k+1}\le t) = \int\limits_0^1 P(U_1\le\ldots\le U_k\le U_{k+1}\le t\mid U_{k+1}=x)\,P(U_{k+1}\in\, dx)$$

       $$= \int\limits_0^1 P(U_1\le\ldots\le U_k\le x\le t\mid U_{k+1}=x)\,P(U_{k+1}\in\, dx)$$

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

       
       
       wobei sich letzte Gleichheit aus der Unabhängigkeit und $(0,1]$-Gleichverteiltheit der $U_1,U_2,\ldots$ ergibt.
     • Es gelte nun (8) für ein gewisses $k\ge 1$. Dann gilt auch
       

       $$P(U_1\le\ldots\le U_{k+1}\le t) = \int\limits_0^t P(U_1\le\ldots\le U_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 die Gültigkeit von (8) für jedes $k\ge 1$ bewiesen.
   • Aus (8) ergibt sich nun darüber hinaus, dass für jedes $k\in\mathbb{N}$
     

     $$P(U_1\le\ldots\le U_k,\,U_k> U_{k+1}) = \int\limits_0^1 P(U_1\le\ldots\le U_k,\,U_k>x)\, dx$$

     $$= \int\limits_0^1 \Bigl(P(U_1\le\ldots\le U_k\le 1)- P(U_1\le\ldots\le U_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)!}\;.$$

     
     
     
      
       $\Box$
     
     
     

   Beachte

    

   • Es mögen nun hinreichend viele Pseudozufallszahlen $u_1,u_2\ldots$ erzeugt werden, so dass sich aus ihnen gemäß (5) und (6) die $n$ Runs $w_1,\ldots,w_n$ ergeben.
   • Wir zerlegen die positive Halbachse in $r$ Intervalle $(a_1,b_1],\ldots,(a_r,b_r]$, so dass
     • 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 ${\mathbf{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(w_1,\ldots,w_n)=\sum\limits _{j=1}^r\;\frac{(Y_j(w_1,\ldots,w_n)-np_{0,j})^2}{np_{0,j}}\;,$$
       wobei $Y_j(w_1,\ldots,w_n)=\char93 \{i:\, 1\le i\le n,\, a_j<w_i\le b_j\}$ die Anzahl derjenigen Runlängen $w_1,\ldots,w_n$ bezeichnet, die in der $j$-ten Klasse liegen.
   • Gemäß Theorem 3.3 wird nun bei großem $n$, was die Erzeugung entsprechend vieler Pseudozufallszahlen $u_1,u_2,\ldots$ erfordert, die Hypothese $H_0:{\mathbf{p}}={\mathbf{p}}_0$ abgelehnt, falls $T(w_1,\ldots,w_n)>\chi^2_{r-1,1-\alpha}$.