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

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 ₜ\, the channel maps the input to an output ₜ\ 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 symbol-wise invertible channels, in which the channel output at each time t is yₜ = f(xₜ, vₜ), vₜ being a `noise' variable, and f(·,v) is a bijection for every fixed v. This class includes group-additive channels yₜ = xₜ ⊕ vₜ 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ⁿ in a given noise set N, provided N is closed under block permutations; this condition is satisfied by any noise set that depends on vⁿ 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.