Beispiel 3: Gleichverteilung/Maßtheorie

Definition. Sei x̄ = (x_{1}, x_{2}, …) eine {0, …, 9}- Folge. x̄ heißt gleichverteilt, wenn für alle w ∈ {0, …, 9} gilt:

lim_{N→∞} \frac{#\{i < N : a_{i} = w\}}{N} = \frac{1}{10}

Die Diskrepanz oder Abweichung von der Gleichverteilung wird durch

D(x̄, N) = 10· max_{w∈\{0,... ,9\}} |\frac{#\{i < N : a_{i} = w\}}{N} −\frac{1}{10} |

definiert.

Sei k eine natürliche Zahl. Für jede natuerliche Zahl N mißt die k-Diskrepanz D_{k}(x̄, N) =

max_{w:{1,... ,k}→{0,... ,9}}

|\frac{#\{i < N : (a_{i+1} , …, a_{i+k} ) = (w(1), …, w(k))\}}{N} − \frac{1}{10^{k}} |·10^{k}

wie gut die 10^{k} vielen {0, …, 9}-Worte der Länge k in den ersten N + k Elementen von x̄ gleichverteilt sind.