TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pending

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.

Binary Hamming rate-distortion function

Statement

Let $X \sim Bernoulli (p)$ , $0 \leq p \leq 1$ , and let the reproduction alphabet be ${0, 1}$ with Hamming distortion $d (x, \hat{x}) = 1_{{x \neq \hat{x}}}$ . Write $p_{0} : = \min (p, 1 - p)$ and

h_{2} (u) : = - u \log_{2} u - (1 - u) \log_{2} (1 - u), 0 \log_{2} 0 : = 0.

For every $D \geq 0$ , the finite-alphabet information rate-distortion function is

R (D) = {\begin{cases} h_{2} (p) - h_{2} (D), & 0 \leq D \leq p_{0}, \\ 0, & D \geq p_{0} . \end{cases}

Facts & Assumptions

Given: A Bernoulli source parameter $p \in [0, 1]$ , binary reproduction, and Hamming distortion.

[F1]

Finite-alphabet information rate-distortion function: $R (D)$ is the minimum finite mutual information in bits over test channels of expected distortion at most $D$ .

[F2]

Finite mutual information: finite mutual information is the finite joint-law KL sum; its base- $2$ version is obtained by replacing $\ln$ with $\log_{2}$ . All entropies and mutual informations in this proof use that bit convention.

[F3]

Finite conditional mutual information identities and equality: conditional mutual information is a finite conditional KL sum and is nonnegative.

[F4]

Finite entropy and mutual-information chain rules: finite conditional entropy obeys the chain rule, here with every finite entropy scaled from nats to bits by $1 / \ln 2$ .

[F5]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite mutual information and conditional mutual information are nonnegative.

Proof

Given: The objects in the statement and suppliers [F1]–[F5].

1.1F2F3F4F5givenalgebra

Let $Y$ be any test-channel output and put $E = X \oplus Y$ , where $\oplus$ is addition modulo two; write $e = P (E = 1) = E d (X, Y)$ . Since $X = Y \oplus E$ , the map $(Y, E) \mapsto X$ is deterministic and bijective in E for each Y, so $H (X ∣ Y) = H (E ∣ Y)$ . By [F4], $H (E) - H (E ∣ Y) = I (E; Y)$ , and this mutual information is nonnegative by [F3] and [F5]; hence $H (E ∣ Y) \leq H (E) = h_{2} (e)$ . If $0 \leq D \leq p_{0} \leq 1 / 2$ and $e \leq D$ , then $h_{2} (e) \leq h_{2} (D)$ : on $(0, 1 / 2)$ , $h_{2}^{'} (u) = \log_{2} ((1 - u) / u) \geq 0$ , and continuity supplies the endpoints. The entropy identity in [F4] therefore gives $I (X; Y) \geq h_{2} (p) - h_{2} (D)$ .

1.2givenconstructalgebra

Suppose $0 \leq D \leq p_{0}$ and $(p, D) \neq (1 / 2, 1 / 2)$ . Then $1 - 2 D > 0$ and $q : = (p - D) / (1 - 2 D) \in [0, 1]$ : nonnegativity follows from $D \leq p$ (since $D \leq p_{0}$ ), while $q \leq 1$ is equivalent to $p + D \leq 1$ , which follows from $D \leq 1 - p$ . Let $Y \sim Bernoulli (q)$ , independently let $E \sim Bernoulli (D)$ , and set $X = Y \oplus E$ . Then $P (X = 1) = q (1 - D) + (1 - q) D = D + q (1 - 2 D) = p$ , and the Hamming distortion is exactly $D$ .

2.1F1F5step 1.1given

If $D \geq p_{0}$ , reconstructing constantly by the more probable source symbol has expected Hamming distortion $p_{0}$ and zero mutual information; [F5] makes zero the minimum. This proves the formula on that branch, including deterministic sources.

3.1F2F4step 1.1step 2.1step 1.2givenalgebra∎

Since E is independent of Y and determines X given Y, $H (X ∣ Y) = H (E ∣ Y) = H (E) = h_{2} (D)$ . Thus $I (X; Y) = h_{2} (p) - h_{2} (D)$ , attaining the converse in step 1.1. The excluded corner $p = 1 / 2, D = 1 / 2$ is covered by step 2.1. This proves the formula for all parameters.

Depends on

Used by

Binary Hamming rate-distortion curve at p equals one quarter Example

Dependency tree · two levels

17 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

MIT OpenCourseWare 6.441, Chapter 25: Evaluating R(D) (standard reference, not scraped)
Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed. (standard reference, not scraped)