Are Guessing, Source Coding and Tasks Partitioning Birds of A Feather?

Area of Science:

• Information Theory
• Coding Theory
• Statistical Inference

Background:

• Four distinct information-theoretic problems are explored: Campbell source coding, Arikan guessing, Huleihel et al. memoryless guessing, and Bunte and Lapidoth tasks' partitioning.
• These problems are analyzed within the independent and identically distributed (IID) lossless data compression framework.

Purpose of the Study:

• To establish a mathematical relationship among the four specified information theoretic problems.
• To introduce a general framework for analyzing mismatched versions of these problems.
• To investigate a practically relevant variant of the Bunte-Lapidoth tasks partitioning problem.

Main Methods:

• Mathematical formulation relating the problems via a general moment minimization problem.
• Utilizing Renyi entropy to define the optimal solution for the minimization problem.
• Developing a unified framework to derive asymptotic results for mismatched scenarios.
• Analyzing a generalized variant of the Bunte-Lapidoth problem.

Main Results:

• A close relationship is established among Campbell source coding, Arikan guessing, Huleihel et al. memoryless guessing, and Bunte and Lapidoth tasks' partitioning problems.
• The optimal solution for the moment minimization problem is expressed in terms of Renyi entropy.
• A unified framework is proposed for mismatched versions, yielding asymptotic results.
• A practically appealing variant of the Bunte-Lapidoth problem is studied, generalizing Arıkan's guessing problem.

Conclusions:

• An equivalence is demonstrated among all four problems under the unified framework.
• Solutions for one problem can be asymptotically optimized for the others, simplifying analysis and application.