Deviations from uniformity in random strings
type: Item
instance of: scholarly article
title: Deviations from uniformity in random strings
zbMATH Open document ID: 0638.68058
DOI: 10.1007/BF00348756
author: Philippe Flajolet
author: Peter Kirschenhofer
author: Robert F. Tichy
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 11K16
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 4041284
zbMATH Keywords: discrepancy
zbMATH Keywords: random infinite strings
zbMATH Keywords: generating function
zbMATH Keywords: normal numbers
MaRDI profile type: Publication
cites work: Q5538132
cites work: Q3469186
cites work: Q3669422
cites work: Maximal Prefix-Synchronized Codes
cites work: Periods in strings
cites work: String overlaps, pattern matching, and nontransitive games
cites work: Q4192121
cites work: Q5585020
cites work: Q5585021
cites work: Q4767350
cites work: Some distribution properties of 0,1-sequences
cites work: Q3333055
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
Recommended article: An excursion to the Kolmogorov random strings
Recommended article: Q5875741
Recommended article: On the complexity of random strings
Recommended article: Block-distribution in random strings
Recommended article: Hitting properties of a random string
Recommended article: Fractal properties of the random string processes
Recommended article: Kolmogorov-Loveland stochasticity for finite strings
Recommended article: Q5528576
description: scientific article; zbMATH DE number 4041284