On mismatched list decoding

The setup of a general channel is considered in the mismatched case, i.e., when the decoder uses a general decoding metric. An expression for the average error probability in list decoding with block length n, metric q_n, list size e^nΘn and rate R, denoted ε⁽ⁿ⁾_qn(R, Θ_n), is established. Further, a general multi-letter formula for the mismatched capacity with list decoding is derived. It is shown that similarly to the matched capacity of the discrete memoryless channel, if the list size grows exponentially at a fixed rate Θ, then the increase in capacity is Θ bits per channel use. Additionally, a random coding lower bound on ε⁽ⁿ⁾_qn(R, Θ_n) is presented. We conclude by presenting an inequality that can be regarded as an extension of Fano´s inequality in the mismatched case with list decoding. As a special case, we derive a lower bound on the average probability of error at rates above the erasures only capacity of the discrete memoryless channel.