On a probabilistic extension of the Oldenburger–Kolakoski sequence.

Saved in:

Bibliographic Details
Title:	On a probabilistic extension of the Oldenburger–Kolakoski sequence.
Authors:	Boisson, Chloé¹ (AUTHOR), Jamet, Damien² (AUTHOR) damien.jamet@loria.fr, Marcovici, Irène³ (AUTHOR)
Source:	RAIRO - Theoretical Informatics & Applications. 2024, Vol. 58, p1-14. 14p.
Subjects:	Run-length encoding, Markov processes, Combinatorics, Letter writing, Density
Abstract:	The Oldenburger–Kolakoski sequence is the only infinite sequence over the alphabet {1, 2} that starts with 1 and is its own run-length encoding. In the present work, we take a step back from this largely known and studied sequence by introducing some randomness in the choice of the letters written. This enables us to provide some results on the convergence of the density of 1's in the resulting sequence. When the choice of the letters is given by an infinite sequence of i.i.d. random variables or by a Markov chain, the average densities of letters converge. Moreover, in the case of i.i.d. random variables, we are able to prove that the densities even almost surely converge. [ABSTRACT FROM AUTHOR]
	Copyright of RAIRO - Theoretical Informatics & Applications is the property of EDP Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	The Oldenburger–Kolakoski sequence is the only infinite sequence over the alphabet {1, 2} that starts with 1 and is its own run-length encoding. In the present work, we take a step back from this largely known and studied sequence by introducing some randomness in the choice of the letters written. This enables us to provide some results on the convergence of the density of 1's in the resulting sequence. When the choice of the letters is given by an infinite sequence of i.i.d. random variables or by a Markov chain, the average densities of letters converge. Moreover, in the case of i.i.d. random variables, we are able to prove that the densities even almost surely converge. [ABSTRACT FROM AUTHOR]
ISSN:	28047346
DOI:	10.1051/ita/2024005