Lossless finite-blocklength optimal error converse

Exact best error probability for fixed-length almost-lossless coding of a discrete source block.

Specification version 1Published 2006-07-181 evidence records

About this problem

The question, scope, and sources behind this Registry record.

Formal question

For a discrete source X and an M-message fixed-length code, determine the minimum decoding error probability.

Scope & constraints

source: discrete finite or countable
ordering: source outcomes by descending probability
criterion: average block error
codebookSize: M

Primary sources

Elements of Information Theory, second edition — Lossless finite-blocklength optimal error converse Chapters 2, 5, 7, 10, 13 and 15

What we know

Current frontiers derived from accepted Claims.

Exact established valueepsilon*(M) = 1 - sum of the M largest P_X(x)

The accepted equality closes this optimization result.

Claims

Assertions tied to evidence, attribution, and review.

2026

CLM-INFO-003210= epsilon*(M) = 1 - sum of the M largest P_X(x)EXACT VALUEThe cited theorem establishes epsilon*(M) = 1 - sum of the M largest P_X(x) under the current specification; this does not assert universal empirical attainability.Source: Elements of Information Theory, second edition — Lossless finite-blocklength optimal error converse ↗

PROVEN

Timeline

The frontier as it changed over time.

How this frontier is derived

Only accepted Claims matching the current specification contribute to the displayed bounds. Strict inequalities remain open; contradictory Claims require editorial review.

—No breakthrough events recorded yetEvents appear here when an accepted Claim tightens a bound or closes the frontier.

Specification

What question is being asked?

Constraints: source=discrete finite or countable · ordering=source outcomes by descending probability · criterion=average block error · codebookSize=M

Read full specification ↗

Corrections & disputes

Record history

No unresolved corrections or disputes are recorded for this published version.

View timeline ↗

Editorial status

Evidence-backed record

1 accepted Claim, with 1 linked evidence records.

Human-reviewed · No AI-only claims

Verified prizes & bounties

Active verified incentives

No active verified bounties are linked to this Limit.

View verified bounty tracker ↗

Reproducibility

Machine-checked history

No accepted machine-checked reproductions are recorded for this Limit.

Cite this LimitLimits Registry. LR-003210. Lossless finite-blocklength optimal error converse. 2026.