Pipeline-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.

Finite-Blocklength Bounds and Reliability — Examples

1 · Prerequisites

2 · Summary

These examples evaluate the one-shot dependence-testing expression and meta-converse on a binary symmetric channel, then give a finite noiseless-channel counterexample separating small average error from maximal error. The calculations retain the null/alternative convention for $β_{ϵ}$ and distinguish average-error bounds from per-message guarantees.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

CounterexampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

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.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Exact evaluation of a one-use BSC dependence-testing bound

Example

For a one-use BSC with crossover $p = 0.1$ , uniform input, and $M = 2$ , the dependence-testing upper bound on achievable average error is exactly $0.35$ .

Facts & Assumptions

Given: The BSC transition probabilities $W (y ∣ x) = 0.9$ for $y = x$ and $0.1$ for $y \neq x$ , uniform input, and $M = 2$ .

[F1]

Finite-DMC dependence-testing achievability bound: a deterministic code exists whose average error is at most $E \exp (- [ı (X; Y) - \ln ((M - 1) / 2)]_{+})$ .

[F2]

Finite discrete memoryless channels: a BSC row is a probability vector, and its output law under an input vector is the matrix product $P W$ .

Verification

1.1F2givenalgebra

Under the uniform input, the output is uniform. Therefore $ı (X; Y) = \ln (0.9 / 0.5) = \ln 1.8$ with probability $0.9$ and $ı (X; Y) = \ln (0.1 / 0.5) = \ln 0.2$ with probability $0.1$ .

2.1F1step 1.1casesalgebra∎

The threshold is $\ln ((M - 1) / 2) = \ln (1 / 2)$ . On the correct-output event, the integrand is $\exp [- (\ln 1.8 - \ln (1 / 2))] = 1 / 3.6 = 5 / 18$ , contributing $0.9 (5 / 18) = 1 / 4$ . On the crossover event, $\ln 0.2 < \ln (1 / 2)$ , so the positive part is zero and the integrand is one, contributing $0.1$ . Thus the expectation is $1 / 4 + 1 / 10 = 7 / 20 = 0.35$ , and [F1] supplies a code with average error at most this value.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Exact beta value for a one-use BSC meta-converse test

Example

For the one-use BSC $(p)$ with $0 < p < 1 / 2$ , the identity encoder/decoder with two equiprobable messages has average error $p$ . With its true joint law $P_{M Y}$ and the uniform-message/uniform-output auxiliary law ${\tilde{Q}}_{M Y}$ , the oriented testing value is exactly $β_{p} (P_{M Y}, {\tilde{Q}}_{M Y}) = 1 / 2 = 1 / M$ .

Facts & Assumptions

Given: Messages $m \in {0, 1}$ are uniform, the input is $x = m$ , the decoder outputs $y$ , and the BSC crossover probability is $0 < p < 1 / 2$ .

[F1]

Finite type-II testing function with explicit orientation: $β_{ϵ} (P, Q)$ minimizes $E_{Q} (1 - ϕ)$ over tests $ϕ \in [0, 1]$ with $E_{P} ϕ \leq ϵ$ .

[F2]

Finite-DMC hypothesis-testing meta-converse: every $M$ -message code with average error $ϵ$ satisfies $β_{ϵ} (P_{M Y}, {\tilde{Q}}_{M Y}) \leq 1 / M$ for any auxiliary output law.

[F3]

Finite discrete memoryless channels: the BSC has transition probability $1 - p$ on $y = x$ and $p$ on $y \neq x$ .

Verification

1.1F3given

The four true joint masses are $(1 - p) / 2$ on $(0, 0), (1, 1)$ and $p / 2$ on $(0, 1), (1, 0)$ . The auxiliary law assigns $1 / 4$ to each pair. The identity decoder is wrong with total true mass $p$ , so its average error is $p$ .

2.1F1step 1.1algebra

Write $ψ = 1 - ϕ$ for the acceptance probability. The constraint in [F1] is $E_{P} ψ \geq 1 - p$ , and the objective is $E_{\tilde{Q}} ψ$ . Let $s$ be the sum of $ψ$ on the two correct pairs and $t$ its sum on the two crossover pairs. Then $0 \leq s, t \leq 2$ , the constraint is $(1 - p) s / 2 + p t / 2 \geq 1 - p$ , and the objective is $(s + t) / 4$ .

3.1F1F2step 2.1casesalgebra∎

If $s \geq 2$ , the objective is at least $1 / 2$ . If $s < 2$ , the constraint forces $t \geq (1 - p) (2 - s) / p$ , so $s + t \geq s + \frac{1 - p}{p} (2 - s) \geq 2,$ where the last inequality follows from $(1 - p) / p > 1$ and $s < 2$ . Thus every randomized feasible test has objective at least $1 / 2$ . Taking $ψ = 1$ on the two correct pairs and $0$ on the crossover pairs attains constraint equality and objective $1 / 2$ . Hence $β_{p} = 1 / 2 = 1 / M$ , as also bounded by [F2].

Finite-Blocklength Bounds and Reliability — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Small expected average code error need not control maximal error

Statement refuted

Facts & Assumptions

Counterexample

Exact evaluation of a one-use BSC dependence-testing bound

Example

Facts & Assumptions

Verification

Exact beta value for a one-use BSC meta-converse test

Example

Facts & Assumptions

Verification

Sources