Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
On the Biased Partial Word Collector Problem
verfasst von : Philippe Duchon, Cyril Nicaud
Erschienen in: LATIN 2018: Theoretical Informatics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this article we consider the following question: N words of length L are generated using a biased memoryless source, i.e. each letter is taken independently according to some fixed distribution on the alphabet, and collected in a set (duplicates are removed); what are the frequencies of the letters in a typical element of this random set? We prove that the typical frequency distribution of such a word can be characterized by considering the parameter \(\ell = L/\log N\). We exhibit two thresholds \(\ell _0<\ell _1\) that only depend on the source, such that if \(\ell \le \ell _0\), the distribution resembles the uniform distribution; if \(\ell \ge \ell _1\) it resembles the distribution of the source; and for \(\ell _0\le \ell \le \ell _1\) we characterize the distribution as an interpolation of the two extremal distributions.