LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Joint strong typicality for a finite IID source

Statement

Let $P$ be a probability vector on a finite alphabet $A$ . For every $δ > 0$ , the support-restricted strongly typical set $T_{δ}^{(n)} (P)$ of Finite strongly typical sets with support restriction satisfies $P^{\otimes n} (T_{δ}^{(n)} (P)) ⟶ 1 (n \to \infty) .$

Facts & Assumptions

Given: A finite alphabet $A$ , a probability vector $P$ , and $δ > 0$ .

[F1]

Finite strongly typical sets with support restriction: membership requires that each positive-mass letter's empirical frequency differ from its probability by at most the relative tolerance $δ P (a)$ , and excludes zero-mass letters.

Proof

1.1F1givenalgebra

Fix $a \in A$ with $P (a) > 0$ , and set $B_{i} = 1_{{X_{i} = a}}$ . The variables $B_{i}$ are IID Bernoulli with mean $P (a)$ and variance $P (a) (1 - P (a)) \leq 1 / 4$ . Thus ${\hat{P}}_{X^{n}} (a) = n^{- 1} \sum_{i} B_{i}$ has mean $P (a)$ and variance at most $1 / (4 n)$ . If $Z = {\hat{P}}_{X^{n}} (a) - P (a)$ , then pointwise $1_{{∣ Z ∣ > δ P (a)}} \leq Z^{2} / (δ^{2} P (a)^{2})$ . Taking expectations bounds the deviation probability by $1 / (4 n δ^{2} P (a)^{2})$ .

2.1F1step 1.1algebra∎

If $P (a) = 0$ , then $\Pr [X_{i} = a] = 0$ for each $i$ , so the probability that the word contains $a$ is zero by a finite union bound. There are finitely many positive-mass letters; summing the bounds from step 1.1 over them and adding the zero support event shows that the probability of failure of any condition in [F1] tends to zero.

Depends on

Finite strongly typical sets with support restriction

Used by

Decode-forward inner bound for a finite relay channel Theorem

Dependency tree · two levels

2 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

Abbas El Gamal and Young-Han Kim, Lecture Notes on Network Information Theory, arXiv:1001.3404v4 (standard reference, not scraped)
Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning, Cambridge University Press prepublication book (standard reference, not scraped)