On the Generalization of Fano's Inequality for Countably Infinite Alphabets, List-Decoding, and General Conditional Information Measures

摘要

Analogues of Fano's inequality are investigated under the following settings: Firstly, the alphabet X of a discrete random variable X is allowed to be countably infinite. Secondly, instead of a fixed finite cardinality X, a fixed X-marginal distribution is given. Thirdly, information measures are generalized from the conditional Shannon entropy H{X Y) to a general type of conditional information measures without explicit form, which contains Arimoto's and Hayashi's conditional Renyi entropies. And fourthly, the average probability of error is defined on list-decoding settings. The main results of this study are tight upper bounds on the generalized conditional information measures for given (i) an X-marginal distribution; (ii) a size of fist-decoding; and (iii) a tolerated probability of error. Our Fano-type inequalities are formalized by specific discrete probability distributions. Sufficient conditions of the sharpness of our Fano-type inequalities are then also clarified on the cardinality of the alphabet Y of a side information Y of X. Technical details of this study can be found in 18.