Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

@misc{merhav2026fanos,
  title = {{Fano's Inequality and Channel Capacity in the Individual-Sequence Regime}},
  author = {Neri Merhav},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06182},
  eprint = {2611.06182},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06182},
}

TY  - UNPB
TI  - Fano's Inequality and Channel Capacity in the Individual-Sequence Regime
AU  - Neri Merhav
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06182
UR  - https://arxiv.org/abs/2611.06182
AB  - We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence {x_t}, the channel maps the input to an output {y_t} in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time t is y_t = f(x_t, v_t), v_t being a `noise' variable, and f(·,v) is a bijection for every fixed v. This class includes group-additive channels y_t = x_t ⊕ v_t studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every v^n in a given noise set 𝒩, provided 𝒩 is closed under block permutations; this condition is satisfied by any noise set that depends on v^n only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.
ER  -