A Tight Second-Order Converse Bound for Variable-Length Feedback Codes
TL;DR
A converse is derived, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$, which covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities.
Abstract
We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verd\'u (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $\epsilon$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses R\'enyi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.