A Tight Second-Order Converse Bound for Variable-Length Feedback Codes
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ú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the ε-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 −C/C1, where C is the channel capacity and C1 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 C1. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi 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.
Related
- Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection
- Input-to-state stability of second-order port-Hamiltonian systems under nonlinear dynamic boundary feedback
- Encoding Trees: A Method for Producing a Variable-Length Prefix Code From Sets of Arbitrary Size
- Confined elastic wires of large length: the sharp second-order asymptotics
- Oscillation of Second-Order Delay Equations with Positive Feedback
BibTeX
@misc{yavas2026tight,
title = {{A Tight Second-Order Converse Bound for Variable-Length Feedback Codes}},
author = {Recep Can Yavas},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11368},
eprint = {2609.11368},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11368},
}
RIS
TY - UNPB
TI - A Tight Second-Order Converse Bound for Variable-Length Feedback Codes
AU - Recep Can Yavas
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11368
UR - https://arxiv.org/abs/2609.11368
AB - 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ú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the ε-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 −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ényi 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.
ER -