Second-Order Capacities of Erasure and List Decoding

Abstract—We derive the second-order capacities (supremum of second-order coding rates) for erasure and list decoding. For erasure decoding, we show that second-order capacity is√ V Φ−1(t) where V is the channel dispersion and t is the total error probability, i.e. the sum of the erasure and unde-tected errors. We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate. For list decoding, we consider list codes of deterministic size 2 nl and show that the second-order capacity is l+ V Φ−1() where is the permissible error probability. Both coding schemes use the threshold decoder and converses are proved using variants of the meta-converse. I