On the ϵ-Capacity of Finite Compound Channels with Applications to the Strong Converse and Second Order Coding Rate

This paper considers the compound channel where the actual channel realization is unknown. It is only known that it comes from a given uncertainty set and that it remains constant throughout the entire duration of transmission. The capacity has been established providing a complete characterization and a simple formula for the computation of the maximal transmission rate. This is no longer the case for the ϵ-capacity of a compound channel, which characterizes the maximum transmission rate when a non-vanishing average error ϵ is tolerated. In this case, the compound channel is known to have no strong converse under the average error criterion and, therewith, the ϵ-capacity may be larger than the capacity for a vanishing error. As the capacity of compound channels is unknown, Ahlswede raised the question of whether or not there exists a (simple) recursive formula for it. This paper approaches this question from a fundamental, algorithmic point of view by studying whether or not such formulas can be found algorithmically in principle (without putting any constraints on the computational complexity of the algorithms). To this end, it is shown that there exists no algorithm or Turing machine that takes the compound channel and error as inputs and computes the corresponding ϵ-capacity. Accordingly, there is also no recursive formula for the ϵ-capacity providing a negative answer to Ahlswede’s initial question. The developed framework is subsequently applied to the question of the existence of a strong converse, the existence of an optimal second order coding rate, and whether or not the pessimistic and optimistic definitions of the ϵ-capacity coincide. Cast as decision problems, it is shown that these questions are undecidable and therewith impossible to be answered algorithmically.