ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Bernoulli information density and exact typical-set counts

Example

Let $X_{i}$ be IID Bernoulli $(p)$ on ${0, 1}$ , with natural logarithms and entropy $h (p) = - p \ln p - (1 - p) \ln (1 - p),$ where $0 \ln 0 = 0$ . For $x^{n} \in {0, 1}^{n}$ , let $k (x^{n}) = \sum_{i = 1}^{n} x_{i}$ be its number of ones. If $0 < p < 1$ and $p \neq 1 / 2$ , put $η = ε / ∣ \ln ((1 - p) / p) ∣$ . Then $T_{n} (ε) = {x^{n} : ∣ k (x^{n}) / n - p ∣ \leq η}, ∣ T_{n} (ε) ∣ = \sum_{k = \max (0, ⌈ n (p - η) ⌉)}^{\min (n, ⌊ n (p + η) ⌋)} (\binom{n}{k}) .$ Its probability and size also satisfy the bounds of Typical-set probability and cardinality bounds with $H = h (p)$ and $V = p (1 - p) (\ln ((1 - p) / p))^{2}$ for $0 < p < 1$ , and $V = 0$ at $p = 0$ or $p = 1$ . At $p = 1 / 2$ , every binary word is typical for every $ε > 0$ and $∣ T_{n} ∣ = 2^{n}$ . At $p = 0$ or $p = 1$ , the typical set is the single supported word and $∣ T_{n} ∣ = 1$ .

For example, at $p = 1 / 4$ , $n = 4$ , and $ε = (\ln 3) / 4$ , we have $η = 1 / 4$ , so the typical words have zero, one, or two ones. Thus $∣ T_{4} ∣ = 1 + 4 + 6 = 11$ and $P (X^{4} \in T_{4}) = 243 / 256$ .

Facts & Assumptions

Given: The Bernoulli source and typical-set convention in the Example.

[F1]

Self-information and surprisal variance for a finite law: The surprisal variance is $V (p) = \sum_{a \in A_{+}} p (a) (ı_{p} (a) - H (p))^{2}$ .

[F2]

Self-information and surprisal variance for a finite law: On positive support, self-information is $ı_{p} (a) = - \ln p (a)$ .

[F3]

Information density and typical sets for a finite source: $T_{n} (ε)$ is the positive-probability set where $∣ I_{n} - H (p) ∣ \leq ε$ .

[F4]

Finite-alphabet IID source: The Bernoulli coordinates are IID with product block law $p^{n}$ .

[F5]

Finite distributions, entropy, divergence, and stochastic matrices: $H (p) = - \sum_{a : p (a) > 0} p (a) \ln p (a)$ with zero terms set to zero, in natural units.

[F6]

Typical-set probability and cardinality bounds: The typical-set tail probability is at most $V (p) / (n ε^{2})$ , and its cardinality is bounded above and below by the stated entropy exponents.

Verification

Given: $p \in [0, 1]$ , $n \geq 1$ , and $ε > 0$ .

1.1givenF2F4F5algebra

Suppose $0 < p < 1$ and a word has $k$ ones, with $q = k / n$ . Its block probability is $p^{k} (1 - p)^{n - k}$ , so $I_{n} = - q \ln p - (1 - q) \ln (1 - p)$ . Subtracting $h (p)$ gives $I_{n} - h (p) = (q - p) \ln ((1 - p) / p)$ .

1.2F2F3F5algebra

If $p = 1 / 2$ , each supported word has probability $2^{- n}$ , so $I_{n} = h (p) = \ln 2$ and all $2^{n}$ words are typical. If $p = 0$ or $p = 1$ , the support consists of one symbol, its surprisal and entropy are zero, and the only supported length- $n$ word is typical.

2.1F3step 1.1algebra

If additionally $p \neq 1 / 2$ , the typicality condition in [F3] is exactly $∣ q - p ∣ \leq η$ . There are $(\binom{n}{k})$ words of weight $k$ , yielding the displayed sum with endpoints clipped to $0 \leq k \leq n$ . For the stated $p = 1 / 4, n = 4$ check, the allowed weights are $k = 0, 1, 2$ , so the count is $1 + 4 + 6 = 11$ and the probability is $\frac{81 + 108 + 54}{256} = \frac{243}{256}$ .

3.1F1F2F5F6step 1.1step 1.2algebra∎

For $0 < p < 1$ , the one-letter surprisal takes two values whose difference is $\ln ((1 - p) / p)$ . Its variance is $p (1 - p) (\ln ((1 - p) / p))^{2}$ : writing the values as $a, b$ , their mean is $p a + (1 - p) b$ , and the centered-square sum is $p (1 - p)^{2} (a - b)^{2} + (1 - p) p^{2} (a - b)^{2} = p (1 - p) (a - b)^{2}$ . At $p = 0$ or $p = 1$ , the surprisal is zero on its singleton support, so [F1] gives $V = 0$ . Substituting these variances and $h (p)$ into [F6] gives the claimed quantitative probability and cardinality bounds.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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

Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Chapter 3, §§3.1–3.3 (standard reference, not scraped)
MIT OpenCourseWare 6.441 Information Theory, Spring 2010, Lecture 3: AEP and typical sets (standard reference, not scraped)