License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.1
URN: urn:nbn:de:0030-drops-160879
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16087/
Akhavi, Ali ;
Paccaut, Fréderic ;
Vallée, Brigitte
Building Sources of Zero Entropy: Rescaling and Inserting Delays (Invited Talk)
Abstract
Most of the natural sources that intervene in Information Theory have a positive entropy. They are well studied. The paper aims in building, in an explicit way, natural instances of sources with zero entropy. Such instances are obtained by slowing down sources of positive entropy, with processes which rescale sources or insert delays. These two processes - rescaling or inserting delays - are essentially the same; they do not change the fundamental intervals of the source, but only the "depth" at which they will be used, or the "speed" at which they are divided. However, they modify the entropy and lead to sources with zero entropy. The paper begins with a "starting" source of positive entropy, and uses a natural class of rescalings of sublinear type. In this way, it builds a class of sources of zero entropy that will be further analysed. As the starting sources possess well understood probabilistic properties, and as the process of rescaling does not change its fundamental intervals, the new sources keep the memory of some important probabilistic features of the initial source. Thus, these new sources may be thoroughly analysed, and their main probabilistic properties precisely described. We focus in particular on two important questions: exhibiting asymptotical normal behaviours à la Shannon-MacMillan-Breiman; analysing the depth of the tries built on the sources. In each case, we obtain a parameterized class of precise behaviours. The paper deals with the analytic combinatorics methodology and makes a great use of generating series.
BibTeX - Entry
@InProceedings{akhavi_et_al:LIPIcs.AofA.2022.1,
author = {Akhavi, Ali and Paccaut, Fr\'{e}deric and Vall\'{e}e, Brigitte},
title = {{Building Sources of Zero Entropy: Rescaling and Inserting Delays}},
booktitle = {33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
pages = {1:1--1:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-230-3},
ISSN = {1868-8969},
year = {2022},
volume = {225},
editor = {Ward, Mark Daniel},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16087},
URN = {urn:nbn:de:0030-drops-160879},
doi = {10.4230/LIPIcs.AofA.2022.1},
annote = {Keywords: Information Theory, Probabilistic analysis of sources, Sources with zero-entropy, Analytic combinatorics, Dirichlet generating functions, Transfer operator, Trie structure, Continued fraction expansion, Rice method, Quasi-power Theorem}
}
|
Keywords: |
|
Information Theory, Probabilistic analysis of sources, Sources with zero-entropy, Analytic combinatorics, Dirichlet generating functions, Transfer operator, Trie structure, Continued fraction expansion, Rice method, Quasi-power Theorem |
|
Collection: |
|
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
08.06.2022 |
