Symbolic representation of piecewise linear functions on the unit interval and application to discrepancy
type: Item
instance of: scholarly article
title: Symbolic representation of piecewise linear functions on the unit interval and application to discrepancy
zbMATH Open document ID: 0813.11045
DOI: 10.1016/0304-3975(94)90069-8
published in: Theoretical Computer Science
publication date: 1994-09-28T00:00:00Z
review text: Let \(D_ N^*(U)\) denote the star-discrepancy of a sequence \(U\) in the unit interval. ``Self-similar sequences'' \(U\) are known for having a small discrepancy, i.e. \(L(U) : = \lim \sup ND_ N^*(U)/ \log N\) is finite, under some additional assumptions. In this paper the author applies techniques concerning substitutions on finite alphabets and automata to prove upper bounds for \(L(U)\), in a special case of such sequences. In an appendix (by H. Faure) the best possible values for the discrepancy of van der Corput and \((n \alpha)\)-sequences are given.
Mathematics Subject Classification ID: 11K38
Mathematics Subject Classification ID: 11B85
zbMATH DE Number: 501208
zbMATH Keywords: selfsimilar sequences
zbMATH Keywords: van der Corput sequences
zbMATH Keywords: star-discrepancy
zbMATH Keywords: small discrepancy
zbMATH Keywords: substitutions on finite alphabets
zbMATH Keywords: automata
author: Jean-Pierre Borel
reviewed by: Robert F. Tichy
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)90069-8
OpenAlex ID: W2021778966
cites work: Minoration de la discrépance à l'origine d'une suite quelconque
cites work: Self-similar measures and sequences
cites work: Discrepancy of the sequence \(\Big(\Big\{n{1+\sqrt{5}\over 2}\Big\}\Big)\)
cites work: Q4079524
cites work: Discrépances de suites associées à un système de numération (en dimension un)
cites work: Etude des restes pour les suites de van der Corput generalisees
cites work: Good permutations for extreme discrepancy
cites work: On a sequence of points of interest for numerical quadrature
cites work: On intrinsic ergodicity of piecewise monotonic transformations with positive entropy
cites work: The Maximal Measure for Linear Mod One Transformations
cites work: The structure of piecewise monotonic transformations
cites work: Q4767350
cites work: Q3814426
cites work: Substitution dynamical systems - spectral analysis
cites work: On the discrepancy of the sequence formed by the multiples of an irrational number
cites work: Irregularities of distribution, VII
cites work: Isomorphisms of \(\beta\)-automorphisms to Markov automorphisms
cites work: Q5762265
cites work: Q5342712
description: scientific article; zbMATH DE number 501208