Abstract

A sequence produced by a memoryless source is to be described using a fixed number of bits that is proportional to its length. Based on the description, a list that is guaranteed to contain the sequence must be produced. The trade-off between the description length and the moments of the listsize is studied when the sequence's length tends to infinity. It is characterized by the source's Rényi entropy. Extensions to scenarios with side information are also studied, where the key is conditional Rényi entropy. The lossy case where at least one of the elements of the list must be within a specified distortion from the source sequence is also solved.