\documentclass[a4paper,12pt]{article}
\usepackage{german}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{ulem}
\pagestyle{headings}
\begin{document}
\title{Verwendung von Fourier-Koeffizienten zum Testen auf Gleichverteilung}
\author{Jan Behrens}
\date{\small 1. Juni 2008 \linebreak Erg\"anzung/\"Uberarbeitung vom 9. August 2009}
\maketitle

Ziel soll es sein, zu einer Stichprobe von Zufallszahlen im Bereich von $0$ bis $1$ den eindeutig definierten Wert $g(h)$ zu berechnen, der als Ma{\ss} f\"ur das Abweichen dieser Stichprobe von einer Gleichverteilung dient. $g(h)$ nimmt ebenfalls Werte zwischen $0$ und $1$ an, wobei kleine Werte eine hohe Abweichung von der Gleichverteilung bedeuten, w\"ahrend Werte gegen $1$ f\"ur eine gute \"Ubereinstimmung der Stichprobe mit einer Gleichverteilung stehen. Die Gr\"o{\ss}e $g(h)$ soll au{\ss}erdem mit dem Signifikanzniveau \"ubereinstimmen; d.h. bei einer Stichprobe, die einer Gleichverteilung entstammt, soll die Wahrscheinlichkeit, dass $g(h)$ einen Wert $x$ unterschreitet genau $x$ sein.

Hierzu wird die Summe $h$ der Quadrate von Fourier-Koeffizienten (unter Auslassung des Koeffizienten f\"ur den Gleichanteil) gebildet, da diese bei einer konstanten Funktion (entsprechend einer Gleichverteilung) gleich $0$ ist. Konvergenz wird dadurch gew\"ahrleistet, dass mit zunehmendem Index $n$ die Quadrate der Fourier-Koeffizienten schw\"acher gewichtet werden, n\"amlich mit $\frac{1}{n^2}$. Zur Berechnung der Gr\"o{\ss}e $g(h)$ aus der Summe $h$ wird diese Summe f\"ur den Fall einer zugrundeliegenden Gleichverteilung ($h_{gleich}$) zun\"achst mit Hilfe des Zentralen Grenzwertsatzes von {\sc Lindeberg-Levy} durch eine unendliche Summe von gewichteten, quadrierten normalverteilten Zufallsgr\"o{\ss}en angen\"ahert. Die der unendlichen Summe dieser Zufallsgr\"o{\ss}en entsprechenden unendlichen Faltungen der Wahrscheinlichkeitsdichten werden anschlie{\ss}end berechnet, um die Wahrscheinlichkeitsdichte $f(x)$ von $h_{gleich}$ zu ermitteln. Aus dieser Wahrscheinlichkeitsdichte wird anschlie{\ss}end durch Integration die kumulative Verteilungsfunktion $F(x)$ und daraus dann eine Formel f\"ur die gesuchte Gr\"o{\ss}e $g(h)$ gebildet.

Es wird weiterhin eine M\"oglichkeit erw\"ahnt, wie durch eine einfache Transformation der Stichprobe anstelle des Testens auf Gleichverteilung auf jede andere Wahrscheinlichkeitsverteilung mit gegebenen Parametern gepr\"uft werden kann.

Da die Signifikanz bei Erh\"ohung des Stichproblenumfanges von einer nicht exakt gleichverteilten Zufallsgr\"o{\ss}e beliebig steigt, und $g(h)$ entsprechend gegen $0$ strebt, wird zum Abschluss noch eine weitere Gr\"o{\ss}e $k$ untersucht, die ebenfalls ein Ma{\ss} f\"ur die Ungleichverteilung ist, die sich jedoch bei einer Erh\"ohung des Stichproblemumfanges einem Grenzwert ann\"ahert, der die Abweichung zwischen der zugrundeliegenden Verteilung und einer Gleichverteilung wiederspiegelt.

\vfill

Gegeben sei eine Folge $a$ von $M$ reellen Zahlen, die im Intervall $[0;1]$ liegen. Durch Berechnung von
$$
h := \frac{1}{M} \cdot \sum_{n=1}^\infty \left[
  \frac{1}{n^2} \cdot \left(
    \left( \sum_{m=1}^M \cos(2\pi \cdot n \cdot a_m) \right)^2 +
    \left( \sum_{m=1}^M \sin(2\pi \cdot n \cdot a_m) \right)^2
  \right)
\right]
$$
erhalten wir eine Zahl, die umso gr\"o{\ss}er wird, desto ungleich-verteilter die Zahlen der Folge $a$ im Intervall $[0;1]$ sind, da bei einer Gleichverteilung sich die positiven und negative Werte des Sinus und Cosinus in den (inneren) Summen aufheben.

Sind die Zahlen der Folge $a$ zuf\"allig und gen\"ugen einer Gleichverteilung, dann weisen die Zufallsgr\"o{\ss}en
$$
U_{n,m} := \cos(2\pi \cdot n \cdot a_m)
$$
folgenden Mittelwert $\mu$ und folgende Varianz $\sigma^2$ auf:
$$
\mu =
  \frac{1}{1-0} \cdot
  \int\limits_{\Theta=0}^1 \cos(2\pi n \Theta) \;d\Theta = 0
$$$$
\sigma^2 =
  \frac{1}{1-0} \cdot
  \int\limits_{\Theta=0}^1 \cos^2 (2\pi n \Theta) \;d\Theta = \frac{1}{2}
$$

Wir bilden nun die Zufallsgr\"o{\ss}e:
$$
V_n := \frac{\sum_{m=1}^M U_{n,m}}{\sqrt{M}}
= \sum_{m=1}^M \frac{\cos(2\pi \cdot n \cdot a_m)}{\sqrt{M}}
$$

\pagebreak

$V_n$ n\"ahert sich f\"ur $M \to \infty$ gem\"a{\ss} dem Grenzwertsatz von {\sc Lindeberg-Levy} einer Normalverteilung mit dem Mittelwert $\mu = 0$ und der Varianz $\sigma^2 = \frac{1}{2}$ an. F\"ur $M>30$ erhalten wir mit der Normalverteilung bereits eine hinreichend gute N\"aherung. Seien $X_n$ und $Y_n$ (0,1)-normalverteilte Zufallsgr\"o{\ss}en, dann l\"a{\ss}t sich $V_n$ (n\"aherungsweise) auch darstellen als:
$$
V_n = \mu + \sigma X_n = \sqrt{\frac{1}{2}} \cdot X_n
$$

Die Zufallsgr\"o{\ss}en
$$
W_n := \frac{1}{n^2} \cdot \left(
    \left( \sum_{m=1}^M \frac{\cos(2\pi \cdot n \cdot a_m)}{\sqrt{M}} \right)^2
  + \left( \sum_{m=1}^M \frac{\sin(2\pi \cdot n \cdot a_m)}{\sqrt{M}} \right)^2
\right)
$$
$$
= \frac{1}{M} \cdot \frac{1}{n^2} \cdot \left(
    \left( \sum_{m=1}^M \cos(2\pi \cdot n \cdot a_m) \right)^2
  + \left( \sum_{m=1}^M \sin(2\pi \cdot n \cdot a_m) \right)^2
\right)
$$
ergeben sich entsprechend zu:
$$
W_n = \frac{1}{n^2} \cdot \left(
    \left( \sqrt{\frac{1}{2}} \cdot X_n \right)^2
  + \left( \sqrt{\frac{1}{2}} \cdot Y_n \right)^2
\right)
= \frac{1}{n^2} \cdot \frac{X_n^2 + Y_n^2}{2}
$$


$h$ l\"asst sich somit bei gleichverteilt-zuf\"alligen $a_m$ als unendliche Summe von gewichteten, quadrierten (0,1)-normalverteilten Zufallsgr\"o{\ss}en $X_n$ und $Y_n$ darstellen:

$$
h_{gleich} = \sum_{n=1}^\infty W_n
= \sum_{n=1}^\infty \frac{1}{n^2} \cdot \frac{X_n^2 + Y_n^2}{2}
$$

Die Zufallsgr\"o{\ss}e $X_n^2 + Y_n^2$ gen\"ugt einer $\chi^2$-Verteilung mit 2 Freiheitsgraden, welche die Wahrscheinlichkeitsdichte $\frac{1}{2} \cdot \mathrm{e}^{-\frac{1}{2} \cdot x}$ aufweist. Multipliziert man eine Zufallsgr\"o{\ss}e mit einem Faktor, so bedeutet dies f\"ur die Wahrscheinlichkeitsdichte eine entsprechende Streckung in $x$-Richtung sowie eine Stauchung in $y$-Richtung. Demnach entsprechen die einzelnen Summanden
$$
\frac{1}{n^2} \cdot \frac{X_n^2 + Y_n^2}{2}
$$
von $h_{gleich}$ den folgenden Wahrscheinlichkeitsdichtefunktionen:
$$
n^2 \cdot \mathrm{e}^{-n^2 \cdot x}
$$

\pagebreak

Ein Addieren von Zufallsgr\"o{\ss}en entspricht der Faltung ($*$) ihrer Wahrscheinlichkeitsdichten. Bezeichnen wir mit $f(x)$ die Wahrscheinlichkeitsdichte der Zufallsgr\"o{\ss}e $h_{gleich}$ an der Stelle $x$, so ist:

$$
f(x) =
  (\mathrm{e}^{-x}) *
  (2^2 \cdot \mathrm{e}^{-2^2 \cdot x}) *
  (3^2 \cdot \mathrm{e}^{-3^2 \cdot x}) *
  (4^2 \cdot \mathrm{e}^{-4^2 \cdot x}) * \ldots
$$

mit
$$
r(x) * s(x) = \int\limits_{\Theta=0}^x r(x-\Theta) \cdot s(\Theta) \;d\Theta
$$

Wir berechnen zun\"achst die Faltung von zwei unterschiedlichen Exponentialfunktionen ($\alpha\not=\beta$):

$$
(A \cdot \mathrm{e}^{-\alpha x}) * (B \cdot \mathrm{e}^{-\beta x})
= \int\limits_{\Theta=0}^x
    A \cdot \mathrm{e}^{-\alpha (x-\Theta)} \cdot
    B \cdot \mathrm{e}^{-\beta \Theta} \; d\Theta
$$$$
= AB \cdot \int\limits_{\Theta=0}^x
    \mathrm{e}^{- \alpha x + \alpha \Theta - \beta \Theta} \; d\Theta
= AB \cdot \mathrm{e}^{-\alpha x} \cdot \int\limits_{\Theta=0}^x
    \mathrm{e}^{(\alpha-\beta) \cdot \Theta} \; d\Theta
$$$$
= AB \cdot \mathrm{e}^{-\alpha x} \cdot \frac{1}{\alpha-\beta} \cdot
  \left(
    \mathrm{e}^{(\alpha-\beta) \cdot x} - \mathrm{e}^{(\alpha-\beta) \cdot 0}
  \right)
= \frac{AB}{\alpha-\beta} \cdot \left( \mathrm{e}^{-\beta x} - \mathrm{e}^{-\alpha x} \right)
$$

Wir stellen fest, dass die Faltung zweier Exponentialfunktionen mit unterschiedlich skaliertem Exponenten eine Linearkombination dieser Exponentialfunktionen ergibt.

Faltet man eine Summe von Exponentialfunktionen mit einer weiteren Exponentialfunktion $A \cdot \mathrm{e}^{-\alpha x}$, so ist der Koeffizient $B$ eines Summanden \linebreak $B \cdot \mathrm{e}^{-\beta x}$ im Ergebnis mit $\frac{A}{\alpha - \beta}$ zu multiplizieren. Aus diesem Grunde l\"asst sich $f(x)$ f\"ur $x > 0$ darstellen als:

$$
f(x) = \sum_{n=1}^\infty \underbrace{ \left( \prod_{m \in \mathbb{N} \setminus \{n\}} \frac{m^2}{m^2 - n^2} \right) }_{=: \; p(n)} \left( n^2 \cdot \mathrm{e}^{-n^2 \cdot x} \right)
$$

\pagebreak

Zur Berechnung des unendlichen Produktes $p(n)$ spalten wir dieses zun\"achst in drei getrennte Produkte $p_1(n)$, $p_2(n)$ und $p_3(n)$ auf:

$$
p(n) = \prod_{m \in \mathbb{N} \setminus \{n\}} \frac{m^2}{m^2 - n^2}
= \underbrace{ \prod_{m=1}^{n-1} \frac{m^2}{m^2-n^2} }_{=: \; p_1(n)} \cdot
  \underbrace{ \prod_{m=n+1}^{2n} \frac{m^2}{m^2-n^2} }_{=: \; p_2(n)} \cdot
  \underbrace{ \prod_{m>2n} \frac{m^2}{m^2-n^2} }_{=: \; p_3(n)}
$$

Umformung von $p_1(n)$ ergibt:

$$
p_1(n) = \prod_{m=1}^{n-1} \frac{m^2}{m^2-n^2}
= \prod_{m=1}^{n-1} \left( (-1) \cdot \frac{m^2}{n^2-m^2} \right)
$$$$
= (-1)^{n-1} \cdot \prod_{m=1}^{n-1} \frac{m^2}{(n-m)(n+m)}
= (-1)^{n-1} \cdot \prod_{m=1}^{n-1} \frac{1}{n-m} \cdot \prod_{m=1}^{n-1} \frac{m^2}{n+m}
$$$$
= (-1)^{n-1} \cdot \prod_{m=1}^{n-1} \frac{1}{m} \cdot \prod_{m=1}^{n-1} \frac{m^2}{n+m}
= (-1)^{n-1} \cdot \prod_{m=1}^{n-1} \frac{m}{m+n}
$$

Umformung von $p_2(n)$ ergibt:

$$
p_2(n) = \prod_{m=n+1}^{2n} \frac{m^2}{m^2-n^2}
= \prod_{m=n+1}^{2n} \frac{m^2}{(m-n)(m+n)}
= \prod_{m=1}^n \frac{(m+n)^2}{m(m+2n)}
$$

Und eine Umformung des unendlichen Produktes $p_3(n)$ ergibt:

$$
p_3(n) = \prod_{m>2n} \frac{m^2}{m^2-n^2}
= \prod_{m>2n} \left( \frac{m}{m-n} \cdot \frac{m}{m+n} \right)
$$$$
= \prod_{m>0} \left( \frac{m+2n}{m+n} \cdot \frac{m+2n}{m+3n} \right)
= \prod_{m=1}^n \frac{m+2n}{m+n} \cdot
  \prod_{m>n} \frac{m+2n}{m+n} \cdot
  \prod_{m>0} \frac{m+2n}{m+3n}
$$$$
= \prod_{m=1}^n \frac{m+2n}{m+n} \cdot
  \underbrace{
    \prod_{m>0} \frac{m+3n}{m+2n} \cdot
    \prod_{m>0} \frac{m+2n}{m+3n}
  }_{=1}
= \prod_{m=1}^n \frac{m+2n}{m+n}
$$

\pagebreak

Das Gesamtprodukt $p(n)$ ist somit:

$$
p(n) =
  \overbrace{ (-1)^{n-1} \cdot \prod_{m=1}^{n-1} \frac{m}{m+n} }^{p_1(n)} \cdot
  \overbrace{ \prod_{m=1}^n \frac{(m+n)^2}{m(m+2n)} }^{p_2(n)} \cdot
  \overbrace{ \prod_{m=1}^n \frac{m+2n}{m+n} }^{p_3(n)}
$$$$
= (-1)^{n-1} \cdot \prod_{m=1}^{n-1} \left(
    \underbrace{
      \frac{m}{m+n} \cdot
      \frac{(m+n)^2}{m(m+2n)} \cdot
      \frac{m+2n}{m+n}
    }_{=1}
  \right) \cdot
  \underbrace{
    \frac{(n+n)^2}{n(n+2n)} \cdot \frac{n+2n}{n+n}
  }_{=2}
$$
\smallskip
$$
\uuline{ = (-1)^{n-1} \cdot 2 }
$$

Setzen wir dieses Ergebnis in die Gleichung f\"ur $f(x)$ ein, so erhalten wir ($x>0$ vorausgesetzt):

$$
f(x)
= \sum_{n=1}^\infty p(n) \cdot \left (n^2 \cdot \mathrm{e}^{-n^2 \cdot x} \right)
$$$$
= \sum_{n=1}^\infty \left( (-1)^{n-1} \cdot 2 \right) \left (n^2 \cdot \mathrm{e}^{-n^2 \cdot x} \right)
= 2 \cdot \sum_{n=1}^\infty (-1)^{n-1} \cdot n^2 \cdot \mathrm{e}^{-n^2 \cdot x}
$$

Aus der Dichteverteilung $f$ l\"asst sich die kumulative Verteilungsfunktion $F$ durch Integration berechnen:

$$
F(x) = \int\limits_{t=0}^x f(t) \;dt = \left\{
  \begin{array}{l@{\quad\mbox{f\"ur}\quad}l}
    0 & x \le 0 \\
    1 - 2 \cdot \sum\limits_{n=1}^\infty (-1)^{n-1} \cdot \mathrm{e}^{-n^2 \cdot x} & x > 0
  \end{array}
\right.
$$

Mit der gegebenen Verteilungsfunktion $F$ l\"asst sich nun leicht die Wahrscheinlichkeit $g(x)$ berechnen mit der die Gr\"o{\ss}e $h$ f\"ur den Fall, dass die Zahlen der Folge $a$ die Stichprobe einer gleichverteilten Zufallsgr\"o{\ss}e sind, einen gegebenen Wert $x$ \"uberschreitet:

$$
g(x) = \mathbb{P}(h_{gleich}>x) = 1 - F(x) = \left\{
  \begin{array}{l@{\quad\mbox{f\"ur}\quad}l}
    1 & x \le 0 \\
    2 \cdot \sum\limits_{n=1}^\infty (-1)^{n-1} \cdot \mathrm{e}^{-n^2 \cdot x} & x > 0
  \end{array}
\right.
$$

\pagebreak

Ist $g(h) < 5\%$, dann weicht die Stichprobe signifikant von einer Gleichverteilung ab, d.h. die Wahrscheinlichkeit betr\"agt nur 5\%, dass im Falle des Zugrundeliegens einer Gleichverteilung $h$ zuf\"allig so gro{\ss} bzw. $g(h)$ zuf\"allig so klein ist.

Das beschriebene Verfahren kann nicht nur zur Pr\"ufung einer Stichprobe auf Gleichverteilung, sondern ebenso zur Pr\"ufung einer Stichprobe $a'$ auf jede beliebige Verteilung (mit gegebenen Parametern) angewendet werden. Hierzu ist die Stichprobe vorher mit Hilfe der entsprechenden kumulativen Verteilungsfunktion $\Psi$ auf die gepr\"uft werden soll zu transformieren:

$$
a_m = \Psi(a'_m)
$$

M\"ochte man z.B. auf eine Normalverteilung mit dem Mittelwert $\mu$ und der Standardabweichung $\sigma$ pr\"ufen, dann ist:

$$
a_m = \Psi(a'_m) = \Phi_{\mu,\sigma}(a'_m) = \frac{1}{2} \cdot \left(
  1 + \mathrm{erf} \left(
    \frac{a'_m-\mu}{\sigma \cdot \sqrt{2}}
  \right)
\right)
$$

$h$ bzw. $g(h)$ eignen sich, um festzustellen wie signifikant eine Stichprobe von einer Gleichverteilung abweicht. Da, falls die Stichprobe keiner Gleichverteilung folgt, die Signifikanz bei Erh\"ohung des Stichprobenumfangs beliebig steigt, definieren wir noch ein Ma{\ss} $k \in [0,1]$ f\"ur den Grad der Abweichung von einer Gleichverteilung, welches sich bei Erh\"ohung des Stichprobenumfanges einem Grenzwert ann\"ahert:

$$
k := \sqrt{
  \frac{6}{\pi^2 M^2} \cdot \sum_{n=1}^\infty \left[
    \frac{1}{n^2} \cdot \left(
      \left( \sum_{m=1}^M \cos(2\pi \cdot n \cdot a_m) \right)^2 +
      \left( \sum_{m=1}^M \sin(2\pi \cdot n \cdot a_m) \right)^2
    \right)
  \right]
}
$$

Insbesondere wirkt sich ein Duplizieren der Stichprobe nicht auf die neu definierte Gr\"o{\ss}e $k$ aus, d.h. f\"ur $a_{m+M_0} = a_m$ und $N \in \mathbb{N}$ gilt $k|_{M = N \cdot M_0} = k|_{M = M_0}$. Falls eine Stichprobe mit $M$ optimal gleichverteilten Werten vorliegt ($a_m = \frac{m}{M} + d$ mit $d \in [0,\frac{m}{M}]$), ist die Gr\"o{\ss}e $k = \frac{1}{M}$. Dies l\"asst sich wie folgt beweisen:

$$
k|_{a_m = \frac{m}{M} + d} = \sqrt {
  \frac{6}{\pi^2 M^2} \cdot \sum_{n=1}^\infty \left(
    \frac{1}{n^2} \cdot k_m
  \right)
}
$$$$
k_m := \left( \sum_{m=1}^M \cos \left( 2\pi n (\frac{m}{M} + d) \right) \right)^2 +
       \left( \sum_{m=1}^M \sin \left( 2\pi n (\frac{m}{M} + d) \right) \right)^2
$$
Man formt den Term $k_m$ mittels Ausmultiplizieren und Additionstheoremen um:
$$
k_m = \sum_{m=1}^M \sum_{m'=1}^M
  \cos \left( 2\pi n (\frac{m}{M} + d) \right) \cdot
  \cos \left( 2\pi n (\frac{m'}{M} + d) \right)
+ \sum_{m=1}^M \sum_{m'=1}^M
  \sin \left( ... \right) \cdot \sin \left( ... \right)
$$$$
= \sum_{m=1}^M \sum_{m'=1}^M \left[
    \cos \left( 2\pi n (\frac{m}{M} + d) \right) \cdot
    \cos \left( 2\pi n (\frac{m'}{M} + d) \right)
    +
    \sin \left( ... \right) \cdot \sin \left( ... \right)
  \right]
$$$$
= \sum_{m=1}^M \sum_{m'=1}^M \cos \left( 2\pi n (\frac{m}{M} + d) - 2\pi n (\frac{m'}{M} + d) \right)
$$
Dann l\"asst sich die Variable $d$ entfernen:
$$
k_m = \sum_{m=1}^M \sum_{m'=1}^M \cos \left( 2\pi n \frac{m}{M} - 2\pi n \frac{m'}{M} \right)
$$
Anschlie{\ss}end wird der Term zur\"uck transformiert:
$$
k_m = \sum_{m=1}^M \sum_{m'=1}^M \left[
  \cos \left( 2\pi n \frac{m}{M} \right) \cdot
  \cos \left( 2\pi n \frac{m'}{M} \right)
  +
  \sin \left( ... \right) \cdot \sin \left( ... \right)
\right]
$$$$
= \sum_{m=1}^M \sum_{m'=1}^M
    \cos \left( 2\pi n \frac{m}{M} \right) \cdot
    \cos \left( 2\pi n \frac{m'}{M} \right)
+ \sum_{m=1}^M \sum_{m'=1}^M
    \sin \left( ... \right) \cdot \sin \left( ... \right)
$$$$
= \left( \sum_{m=1}^M \cos \left( 2\pi n \frac{m}{M} \right) \right)^2 +
  \left( \sum_{m=1}^M \sin \left( 2\pi n \frac{m}{M} \right) \right)^2
$$
Falls $n$ ein Vielfaches von $M$ ist, ist $k_m = M^2$, ansonsten sind beide Summen $0$ und damit auch $k_m = 0$. Beschreiben wir die Vielfachen von $M$ mit $i \cdot M$, dann ergibt sich f\"ur $k|_{a_m = \frac{m}{M} + d}$:
$$
k|_{a_m = \frac{m}{M} + d} = \sqrt{
  \frac{6}{\pi^2 M^2} \cdot \sum_{i=1}^\infty \left( \frac{1}{(i \cdot M)^2} \cdot M^2 \right)
}
$$$$
= \sqrt{
  \frac{6}{\pi^2 M^2} \cdot \sum_{i=1}^\infty \frac{1}{i^2}
}
= \sqrt{
  \frac{6}{\pi^2 M^2} \cdot \frac{\pi^2}{6}
}
= \frac{1}{M}
$$
Dieses entspricht genau der oben aufgestellten Behauptung.

\pagebreak

Folgendes Haskell-Programm kann die oben definierten Gr\"o{\ss}en berechnen: 

\begin{verbatim}

inhomoSum :: RealFloat a => [a] -> a
inhomoSum xs
  =  sum [ ((s1 n)**2 + (s2 n)**2) / n**2
         | i <- [1..huge], n <- [fromIntegral i] ]
  where
    s1 n    =  sum [ cos (2 * pi * n * x) | x <- xs ]
    s2 n    =  sum [ sin (2 * pi * n * x) | x <- xs ]
    huge    =  1000

inhomoSignificance :: RealFloat a => [a] -> a
inhomoSignificance xs  =  prob (inhomoSum xs / count)
  where
    count   =  fromIntegral (length xs)
    prob x  =  (min 1 . max 0) (
                 sum [ (if i < huge then 2 else 1) *
                       (-1)**(n-1) * exp (-n**2 * x)
                     | i <- [1..huge], n <- [fromIntegral i] ]
               )
    huge    =  1000

inhomogeneity :: RealFloat a => [a] -> a
inhomogeneity xs  =  sqrt (6 / pi**2 / count**2 * inhomoSum xs)
  where
    count  =  fromIntegral (length xs)


\end{verbatim}

\pagebreak

Hinweise zum Programm: {\tt fromIntegral} dient nur der Typ-Konvertierung von ganzzahligen Zahlen in Gleitkommazahlen und hat nichts mit der Berechnung von mathematischen Integralen zu tun. Die Variablen {\tt i} und {\tt n} stellen beide die gleiche Zahl dar, jedoch unterschiedlichen Typs: {\tt i} ist vom Typ {\tt Integer}, w\"ahrend {\tt n} einen Typ der Klasse {\tt RealFloat} aufweist. Die Fallunterscheidung {\tt if i < huge then 2 else 1} dient der Vermeidung von Berechnungsfehlern f\"ur {\tt x} gleich oder nahe $0$, indem das letzte Glied der (eigentlich unendlichen) Summe nur halb angerechnet wird.

{\tt inhomoSum} ist eine Hilfsfunktion. Die Funktion {\tt inhomoSignificance} berechnet die Gr\"o{\ss}e $g(h)$ f\"ur eine gegebene Zahlenfolge, d.h. wenn das Ergebnis kleiner als $0.05$ ist, dann liegt eine signifikante Abweichung von der Gleichverteilung vor. Die Funktion {\tt inhomogeneity} berechnet die Gr\"o{\ss}e $k$, wobei $1$ f\"ur maximale Ungleichverteilung steht (nur ein Wert kommt in der Zahlenfolge vor) und ein Wert nahe $0$ gute Gleichverteilung angibt.

\vfill

Es wird unentgeltlich jeder Person das Recht einger\"aumt, Kopien dieses Dokumentes und des dazugeh\"origen Haskell-Programmes zu benutzen, zu kopieren, zu modifizieren, mit anderen Werken zu kombinieren, zu ver\"offentlichen, zu verbreiten, unterzulizensieren, zu verkaufen und/oder weiteren Personen diese Rechte einzur\"aumen, soweit in allen Kopien oder wesentlichen Teilen davon der Autor genannt wird und dieser Hinweistext enthalten bleibt. Fehlerfreiheit und Funktionsf\"ahigkeit werden nicht zugesichert; Benutzung erfolgt auf eigenes Risiko.

\end{document}