Encoding Tasks and Rényi Entropy

Abstract

A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum $\rho$-th moment of the number of performed tasks are derived. The case where a sequence of tasks is produced by a source and $n$ tasks are jointly described using $nR$ bits is considered. If $R$ is larger than the Rényi entropy rate of the source of order $1/(1+\rho )$ (provided it exists), then the $\rho$-th moment of the ratio of performed tasks to $n$ can be driven to one as $n$ tends to infinity. If $R$ is smaller than the Rényi entropy rate, this moment tends to infinity. The results are generalized to account for the presence of side-information. In this more general setting, the key quantity is a conditional version of Rényi entropy that was introduced by Arimoto. For IID sources two additional extensions are solved, one of a rate-distortion flavor and the other where different tasks may have different nonnegative costs. Finally, a divergence that was identified by Sundaresan as a mismatch penalty in the Massey-Arikan guessing problem is shown to play a similar role here.

12 pages; accepted for publication in the IEEE Transactions on Information Theory; minor changes in the presentation; added a section on tasks with costs; presented in part at ITW 2013; to be presented in part at ISIT 2014

References in corpus (1)

• Guessing under source uncertainty

Cited by in corpus (11)

• Operational Interpretation of Renyi Information Measures via Composite Hypothesis Testing Against Product and Markov Distributions
• Multi-user guesswork and brute force security
• Two Measures of Dependence
• A Scale-invariant Generalization of the Rényi Entropy, Associated Divergences and their Optimizations under Tsallis' Nonextensive Framework
• A tight uniform continuity bound for the Arimoto-Rényi conditional entropy and its extension to classical-quantum states
• Conditional Rényi entropy and the relationships between Rényi capacities
• A precise bare simulation approach to the minimization of some distances. Foundations
• Variable-Length Source Dispersions Differ under Maximum and Average Error Criteria
• Some Useful Integral Representations for Information-Theoretic Analyses
• Sharp Bounds on Arimoto's Conditional Rényi Entropies Between Two Distinct Orders
• Generalized Fisher-Darmois-Koopman-Pitman Theorem and Rao-Blackwell Type Estimators for Power-Law Distributions