Deviations from uniformity in random strings (Q1099625)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Deviations from uniformity in random strings |
scientific article |
Statements
Deviations from uniformity in random strings (English)
0 references
1988
0 references
We show that almost all binary strings of length n contain all blocks of size \((1-\epsilon)\log _ 2 n\) a close to uniform number of times. From this, we derive tight bounds on the discrepancy of random infinite strings. Our results are obtained through explicit generating function expressions and contour integration estimates.
0 references
discrepancy
0 references
random infinite strings
0 references
generating function
0 references
normal numbers
0 references
