×

zbMATH — the first resource for mathematics

Deviations from uniformity in random strings. (English) Zbl 0638.68058
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.
Reviewer: P.Flajolet

MSC:
68R99 Discrete mathematics in relation to computer science
11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.
65C10 Random number generation in numerical analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Feller, W.: An introduction to probability theory and its applications, 3rd edn. Wiley 1968 · Zbl 0155.23101
[2] Flajolet, P., Kirschenhofer, P., Tichy, R.: Discrepancy of sequences infinite strings. In: Coll. Math.; Janos Bolyai Soc., Proc. 1986 Conf. on Irregularities of partitions, to appear · Zbl 0694.10046
[3] Goulden, I., Jackson, D.: Combinatorial enumerations. New York: Wiley 1983 · Zbl 0519.05001
[4] Guibas, L.J., Odlyzko, A.M.: Maximal prefix-synchronized codes. SIAM J. Appl. Math. 35, 401-418 (1978) · Zbl 0394.94024 · doi:10.1137/0135034
[5] Guibas, L.J., Odlyzko, A.M.: Periods in strings. J. Comb. Th. (A) 30, 19-42 (1981) · Zbl 0464.68070 · doi:10.1016/0097-3165(81)90038-8
[6] Guibas, L.J., Odlyzko, A.M.: Strings overlaps, pattern matching and nontransitive games. J. Comb. Theory, Ser. A 30, 183-208 (1981) · Zbl 0454.68109 · doi:10.1016/0097-3165(81)90005-4
[7] Hlawka, E.: Theorie der Gleichverteilung. Mannheim Wien Zürich: Bibliographisches Institut 1969 · Zbl 0406.10001
[8] Knuth, D.E.: The art of computer programming, vol. 1: Fundamental algorithms, Reading Mass: Addison-Wesley 1968 · Zbl 0191.17903
[9] Knuth, D.E.: The art of computer programming, vol. 2: Semi-numerical algorithms, Reading Mass: Addison-Wesley 1969 · Zbl 0191.18001
[10] Kuipers, L., Niederreiter, H.: Uniform distriubution of sequences. New York: Wiley 1974 · Zbl 0281.10001
[11] Kirschenhofer, P., Tichy, R.: Some distribution properties of 0-1 sequences, Manuscr. Math. 54, 205-219 (1985) · Zbl 0599.10045 · doi:10.1007/BF01171708
[12] Odlyzko, A.M.: Enumeration of strings. In: Apostolicao, A., Galil, Z. (eds.) Combinatorial algorithms on words. NATO ASI Series F12, Berlin Heidelberg New York: Springer 1984 · Zbl 0544.05020
[13] Révész, P.: Strong theorems in coin tossing. Proc. 1978 Int. Congress of Mathematicians, Helsinki 1980
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.