On a partition of a finite set and its relationships to encoding tasks and the Rényi entropy
Hiroki Koga · 2015
In the problem of encoding tasks introduced by Bunte and Lapidoth, a finite alphabet χ is partitioned to M disjoint subsets {ℒm}mM=1 called lists. In this paper we consider the partition of χ into M lists satisfying L(x) ≤ λ(x) for all x ∈ χ for an arbitrarily given mapping λ: χ → [1, ∞), where L(x) denotes the cardinality of the list ℒmsatisfying x ∈ ℒm. We investigate the minimum number M*(λ) of the lists meeting this constraint and give a lower and an upper bounds on M*(λ) described in terms of λ. We also show that the partition algorithm given by Bunte and Lapidoth attains M*(λ) with a slight modification. Relationships between M*(λ) and the Rényi entropy are also discussed.