Iterationstest auf Zufälligkeit

• In diesem Abschnitt wird nicht vorausgesetzt, dass die Stichprobenvariablen $X_1,\ldots,X_n$ unabhängig sind.
  • Wir nehmen nämlich an, dass $X_1,\ldots,X_n$ nur die Werte 0 oder $1$ annehmen können, wobei $n_1$-mal der Wert 0 und $n_2$-mal der Wert $1$ auftreten möge; $n_2=n-n_1$.
  • Insgesamt gibt es dann ${n\choose n_1}$ mögliche Realisierungen der Zufallsstichprobe $(X_1,\ldots,X_n)$.
  • Dabei soll die Nullhypothese $H_0$ geprüft werden, ob jede dieser ${n\choose n_1}$ Realisierungen die gleiche Wahrscheinlichkeit hat.
  • Mit anderen Worten: Es soll geprüft werden, ob die Lokalisation, d.h. die Reihenfolge ,,rein zufällig'' ist, in der die $n_1$ Einsen bzw. die $n_2$ Nullen angeordnet sind.
• Als Testgröße $T:\Omega\to\{0,1,\ldots\}$ betrachten wir die Anzahl $T(\omega)$ von Iterationen in der (konkreten) Stichprobe $\omega=(x_1,\ldots,x_n)$, d.h. die Anzahl von (Teil-) Folgen aufeinanderfolgender gleicher Zeichen in $\omega=(x_1,\ldots,x_n)$.

Beispiel

 

• Sei $n=20$ mit $n_1=12$ und $n_2=8$. Für

  $$\omega=(1,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,0,1)$$ (2)

  
  
  gilt dann $T(\omega)=7$.
• Wir untersuchen nun die Frage, ob die in (2) gegebenen Daten mit der Hypothese $H_0$ vereinbart sind, dass die Reihenfolge ,,rein zufällig'' ist, oder, ob $H_0$ verworfen wird.
• Hierfür bestimmen wir die Verteilung von $T$, indem wir einen geeignet gewählten Laplaceschen Wahrscheinlichkeitsraum betrachten, vgl. Abschnitt WR-2.4.1.

Theorem 6.1   $\;$ Unter $H_0$ gilt für jedes $i=1,2,\ldots,\min\{n_1,n_2\}$

$$\mathbb{P}(T=k)=\left\{\begin{array}{ll}\frac{ \displaystyle 2{n_... ... i}}{\displaystyle {n\choose n_1}} \;,&\mbox{wenn $k=2i+1$.} \end{array}\right.$$ (3)

Außerdem gilt

$${\mathbb{E} }T= 1+\frac{2n_1n_2}{n} \qquad{\rm Var } T=\frac{2n_1n_2(2n_1n_2-n)}{n^2(n-1)}\;.$$ (4)

Beweis

 

• Wir zeigen die Gültigkeit von (3) nur für den Fall $k=2i$, denn der Beweis für den Fall $k=2i+1$ verläuft analog.
  • Sei also $k=2i$. Dann gibt es je $i$ Iterationen, die aus Einsen bzw. aus Nullen bestehen.
  • Für die Zerlegung der $n_1$ Nullen in $i$ Teilmengen gibt es ${n_1-1\choose i-1}$ Möglichkeiten.
  • Für jede dieser Zerlegungen gibt es ${n_2-1\choose i-1}$ Möglichkeiten, die $n_2$ Einsen in $i$ Teilmengen zu zerlegen.
  • Wenn nun noch beachtet wird, dass die Stichprobe $\omega=(x_1,\ldots,x_n)$ entweder mit $x_1=0$ oder mit $x_1=1$ beginnen kann, dann ergeben sich insgesamt $2{n_1-1\choose i-1}{n_2-1\choose i-1}$ Zerlegungsmöglichkeiten.
  • Damit ist (3) für den Fall $k=2i$ bewiesen.
• Bei der Bestimmung des Erwartungswertes ${\mathbb{E} }T$ nutzen wir die folgende Überlegung.
  • Für jedes $j=2,\ldots,n$ betrachten wir die Indikatorvariable $Y_j:\Omega\to\{0,1\}$ mit
    $$Y_j= \left\{\begin{array}{ll} 1 , & \mbox{wenn an der $j$-ten Stelle eine Iteration beginnt,}\\ 0 , & \mbox{sonst.} \end{array}\right.$$

  • Dann gilt $\{\omega\in\Omega: Y_j(\omega)=1\}=\{\omega\in\Omega: X_{j-1}(\omega)\not= X_j(\omega)\}$, d.h., es gibt $2 {n-2\choose n_i-1}$ Möglichkeiten, dass an der $j$-ten Stelle eine Iteration beginnt.
  • Somit gilt
    $${\mathbb{E} }Y_j \;=\;\mathbb{P}(Y_j=1)\;=\;2\;\frac{ \displayst... ...2)! (n-n_1)! n_1!}{(n-n_1-1)!(n_1-1)!n!}\;=\;2\;\frac{n_1(n-n_1)}{n(n-1)}\;.$$

  • Hieraus und aus der Identität

    $$T=1+\sum_{j=2}^n Y_j$$ (5)

    
    
    ergibt sich, dass
    $${\mathbb{E} }T\;=\;1+\sum\limits_{j=2}^n{\mathbb{E} } Y_j\;=\;1+2\;\frac{n_1(n-n_1)}{n}\;.$$

• Die Varianzformel in (4) lässt sich auf ähnliche Weise beweisen, denn aus (5) ergibt sich, dass
  

  $${\rm Var }T = {\mathbb{E} }\Bigl(\sum\limits_{j=2}^n{\mathbb{E} } Y_j\Bigr)^2-\Bigl(\sum\limits_{j=2}^n{\mathbb{E} }Y_j\Bigr)^2$$

  $$= \sum\limits_{j=2}^n{\mathbb{E} }Y^2_j\;+\;\sum\limits_{2\le j_1,... ...gl(Y_{j_1}Y_{j_2}\bigr)\;-\; \Bigl(\sum\limits_{j=2}^n{\mathbb{E} }Y_j\Bigr)^2$$

  $$= \sum\limits_{j=2}^n{\mathbb{E} }Y_j\;+\;\sum\limits_{2\le j_1,j_... ...Y_{j_1}Y_{j_2}\bigr)\;-\; \Bigl(\sum\limits_{j=2}^n{\mathbb{E} }Y_j\Bigr)^2 ,$$

  
  
  so dass lediglich noch die Momente ${\mathbb{E} } \bigl(Y_{j_1}Y_{j_2}\bigr)$ zu bestimmen sind.
  
  $\Box$

Beachte

 

• Eine mögliche Alternative zu der Nullhypothese $H_0$ der ,,rein zufälligen'' Lokalisation der Nullen und Einsen ist die Tendenz zur Klumpen- bzw. Clusterbildung.
• Als Ablehnungsbereich von $H_0$ wird dann das linke Ende der Verteilung von $T$ gewählt.
• Mit anderen Worten: $H_0$ wird abgelehnt, wenn $T\le r_\alpha(n_1;n_2)$, wobei
  $$r_\alpha(n_1;n_2)=\max\Bigl\{r\in\{1,2,\ldots\}: \mathbb{P}(T\le r)\le\alpha\Bigr\}$$
  das $\alpha$-Quantil der Verteilung der Testgröße $T$ ist.
• Die Quantile $r_\alpha(n_1;n_2)$ können mit Hilfe der in Theorem 6.1 gegebenen Formeln für die Wahrscheinlichkeiten $\mathbb{P}(T=k)$ berechnet werden. Sie können aus Tafeln entnommen werden, die in der Literatur gegeben sind.

Beispiel

$\;$ (Fortsetzung)$\;$ Für $\alpha=0.1$ und $n_1=12$, $n_2=8$ ergibt sich, dass $r_{0.1}(12;8)=7$. Andererseits gilt für die in (2) betrachtete Stichprobe

$$T(\omega)=7 \;\;\Bigl(\le r_{0.1}(12;8)\Bigr) ,$$

d.h., $H_0$ wird abgelehnt.

Wenn die (Teil-) Stichprobenumfänge $n_1$ und $n_2$ groß sind, dann ist die Bestimmung der Quantile $r_\alpha(n_1;n_2)$ von $T=T_{n_1,n_2}$ mit erheblichem Rechenaufwand verbunden. Einen Ausweg bietet dann der folgenden zentrale Grenzwertsatz, den wir hier ohne Beweis angeben.

Theorem 6.2   $\;$ Wenn $n_1, n_2\to\infty$, so dass $n_1/(n_1+n_2)\to p\;$ bzw. $\;n_2/(n_1+n_2)\to 1-p$ für ein $p\in(0,1)$, dann gilt

$$\lim\limits_{n_1,n_2\to\infty}\;\frac{1}{n_1+n_2}\;{\mathbb{E} }T_{n_1,n_2} =\;2p(1-p) \qquad \lim\limits_{n_1,n_2\to\infty}\;\frac{1}{n_1+n_2}\;{\rm Var } T_{n_1,n_2}=\;4p^2(1-p)^2$$ (6)

sowie

$$\lim\limits_{n_1,n_2\to\infty} \mathbb{P}\Bigl( \frac{T_{n_1,n_2... ...\sqrt{n_1+n_2} p(1-p)} \;\le\; x\Bigr)=\Phi(x)\qquad\forall x\in\mathbb{R} ,$$ (7)

wobei $\Phi:\mathbb{R}\to[0,1]$ die Verteilungsfunktion der N$(0,1)$-Verteilung ist.

Beachte

$\;$ Wegen Theorem 6.2 wird $H_0$ für große $n_1,n_2$ abgelehnt, wenn

$$\frac{T_{n_1,n_2}-2n_1n_2/(n_1+n_2)}{2n_1n_2/(n_1+n_2)^{3/2}} \;\le\; z_\alpha ,$$ (8)

wobei $z_\alpha$ das $\alpha$-Quantil der N$(0,1)$-Verteilung ist.