Fixed Error Asymptotics For Erasure and List Decoding

Understand

We derive the optimum second-order coding rates, known as second-order capacities, for erasure and list decoding.

• For erasure decoding for discrete memoryless channels, we show that second-order capacity is $\sqrt{V}\Phi^{-1}(\epsilon_t)$ where $V$ is the channel dispersion and $\epsilon_t$ is the total error probability, i.e., the sum of the erasure and undetected errors.
• We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate.
• We also show that the analogous result also holds for lossless source coding with decoder side information, i.e., Slepian-Wolf coding.