{
  "abstract": "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(\\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \\oplus 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 $\\mathcal{N}$, provided $\\mathcal{N}$ 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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2611.06182",
  "author_total": 1,
  "authors": [
    {
      "name": "Neri Merhav"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/bnfn56tb4ymmw.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2611.06182",
  "fulltext_url": null,
  "id": "bnfn56tb4ymmw",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2611.06182",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.IT"
    ],
    [
      "arxiv",
      "math.IT"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://arxiv.org/pdf/2611.06182",
  "pmcid": null,
  "pmid": null,
  "published": "2026-11-04",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/bnfn56tb4ymmw.ris",
  "sources": [
    {
      "first_seen": "2026-11-05T15:21:00Z",
      "native_id": "2611.06182",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2611.06182"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.IT",
      "subfield": "general"
    }
  ],
  "title": "Fano's Inequality and Channel Capacity in the Individual-Sequence Regime",
  "title_text": "Fano's Inequality and Channel Capacity in the Individual-Sequence Regime",
  "type": "preprint",
  "updated_at": "2026-11-09T00:20:30Z",
  "url": "https://research.draconitic.com/paper/bnfn56tb4ymmw",
  "venue": "arXiv",
  "versions": []
}