Generalized Fano-Type Inequality for Countably Infinite Systems with List-Decoding

This study investigates generalized Fano-type inequalities in the following senses: (i) the alphabet X of a random variable X is countably infinite; (ii) instead of a fixed finite cardinality of X, a fixed X-marginal distribution is given; (iii) information measures are generalized from the conditional Shannon entropy H(X | Y) to a general type of conditional information measures hφ(X | Y) without explicit form; and (iv) the average probability of error is defined on list-decoding rules. As a result, we give tight upper bounds on such generalized conditional information measures for a fixed X-marginal, a fixed list size, and a fixed tolerated probability of error. Then, we also clarify a sufficient condition, which the Fano-type inequalities are sharp, on the cardinality of the alphabet Y of a side information Y. Resulting Fano-type inequalities can apply to not only the conditional Shannon entropy but also the Arimoto's and Hayashi's conditional Rényi entropies. All of the proofs in this study can be found in arXiv:1801.02876 [19].