CounterexampleConstruction: AI-generatedVerification: AI-generatedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Small expected average code error need not control maximal error

Statement refuted

Expected average error tending to zero for singleton random-code ensembles on finite DMCs forces the corresponding maximal errors to tend to zero.

Facts & Assumptions

Given: $M \geq 2$ , input/output alphabet ${1, \dots, M - 1}$ , and the noiseless DMC $W (y ∣ x) = 1 {y = x}$ .

[F1]

Fixed-length codes for a finite DMC: a fixed-length code consists of an encoder from messages to input words and a deterministic decoder from outputs to messages.

[F2]

Average and maximal error of a fixed-length code: average error is the uniform-message mean, and maximal error is the largest individual error.

Counterexample

For every integer $M \geq 2$ , there is a singleton random-code ensemble on a finite noiseless DMC whose expected average error is $1 / M$ while the code's maximal error is $1$ . Thus a small expected average error alone does not make every message's error small.

1.1F1givenconstruct

Use blocklength one, encode message $m$ as $x = m$ for $1 \leq m \leq M - 1$ and encode message $M$ as $x = 1$ . Decode output $y$ as message $y$ . These maps are defined on the stated finite alphabets and form a code by [F1].

2.1F2step 1.1∎

On the noiseless channel, messages $1, \dots, M - 1$ are decoded correctly, while message $M$ is decoded as $1$ and is always wrong. Hence [F2] gives average error $1 / M$ and maximal error $1$ . Take the random-code ensemble to put probability one on this single code; its expected average error remains $1 / M$ , while its maximal error remains $1$ . Letting $M \to \infty$ proves the claimed separation.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning, Chapter 19 §19.2 (standard reference, not scraped)
MIT 6.441 Information Theory, Lecture 12, Spring 2010 (standard reference, not scraped)