Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Completely uniformly distributed sequences based on de Bruijn sequences


Authors: Emilio Almansi and Verónica Becher
Journal: Math. Comp. 89 (2020), 2537-2551
MSC (2010): Primary 11-04, 11K36; Secondary 68-04
DOI: https://doi.org/10.1090/mcom/3534
Published electronically: April 6, 2020
MathSciNet review: 4109577
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We study a construction published by Donald Knuth in 1965 yielding a completely uniformly distributed sequence of real numbers. Knuth's work is based on de Bruijn sequences of increasing orders and alphabet sizes, which grow exponentially in each of the successive segments composing the generated sequence. In this work we present a similar, albeit simpler, construction using linearly increasing alphabet sizes, and we give an elementary proof showing that the generated sequence is also completely uniformly distributed. In addition, we present an alternative proof of the same result based on Weyl's criterion.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11-04, 11K36, 68-04

Retrieve articles in all journals with MSC (2010): 11-04, 11K36, 68-04


Additional Information

Emilio Almansi
Affiliation: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Email: ealmansi@gmail.com

Verónica Becher
Affiliation: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & ICC CONICET, Argentina
Email: vbecher@dc.uba.ar

DOI: https://doi.org/10.1090/mcom/3534
Keywords: Completely uniformly distributed sequences, algorithms
Received by editor(s): September 24, 2019
Received by editor(s) in revised form: December 29, 2019, and January 4, 2020
Published electronically: April 6, 2020
Additional Notes: Supported by Universidad de Buenos Aires and CONICET, Argentina
Article copyright: © Copyright 2020 American Mathematical Society