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

Markov typicality for independently selected finite codewords

Statement

Let $P_{X Y Z} (x, y, z) = P_{X Y} (x, y) P_{Z ∣ X} (z ∣ x)$ be a finite-alphabet Markov law. For every $ϵ > 0$ there are $δ > 0$ and $n_{0}$ such that the following holds for $n \geq n_{0}$ : if $(x^{n}, y^{n}) \in T_{δ}^{(n)} (P_{X Y})$ and a random $Z^{n}$ is supported on $T_{δ}^{(n)} (P_{Z ∣ X} ∣ x^{n})$ and, conditional on each joint type of $(x^{n}, Z^{n})$ , is uniform on that conditional type class, then $\Pr {(x^{n}, y^{n}, Z^{n}) \in T_{ϵ}^{(n)} (P_{X Y Z})} \geq 1 - \frac{C}{n},$ where $C < \infty$ depends only on the fixed finite law, alphabets, and $ϵ$ , not on the particular typical source block or conditional type.

Facts & Assumptions

Given: The finite Markov law, $ϵ > 0$ , a typical fixed source block $(x^{n}, y^{n})$ , and the stated conditional-type-uniform law of $Z^{n}$ .

[A1]

$P_{X Y Z} = P_{X Y} P_{Z ∣ X}$ : conditional on $X = x$ , the target law of $Z$ does not depend on $Y$ .

[F1]

Finite strongly typical sets with support restriction: relative typicality excludes every zero-probability atom and bounds each positive empirical frequency by its relative tolerance.

[F2]

Finite random-codebook covering and selected-codeword law: conditional on a successful iid marginal-codebook search, the selected codeword is supported on the conditional typical set and is uniform within each conditional type class.

Proof

1.1A1F1F2construct

Fix a conditional type $q_{Z ∣ X}$ that can occur under the stated law. For each $x$ with $n_{x} : = ∣ {t : x_{t} = x} ∣ > 0$ , there are $n_{x y}$ positions with $(x_{t}, y_{t}) = (x, y)$ and $n_{x z}$ positions with $(x_{t}, Z_{t}) = (x, z)$ . Conditional-type uniformity means that, among the $n_{x}$ positions with $X = x$ , the $z$ labels are assigned uniformly over all arrangements with these counts. Hence $N_{x y z} : = ∣ {t : (x_{t}, y_{t}, Z_{t}) = (x, y, z)} ∣$ is hypergeometric, with $E N_{x y z} = \frac{n_{x y} n_{x z}}{n_{x}}, Var (N_{x y z}) \leq n_{x} .$ When $n_{x} = 0$ , all these counts vanish.

2.1A1F1step 1.1algebra

By [F1], $n_{x y} / n$ and $n_{x z} / n$ are uniformly close to $P_{X Y} (x, y)$ and $P_{X Z} (x, z)$ , respectively. For $P_{X} (x) > 0$ , division by $n_{x} / n$ shows that $n_{x z} / n_{x}$ is close to $P_{Z ∣ X} (z ∣ x)$ . Thus, after choosing $δ$ sufficiently small, the mean frequency $E N_{x y z} / n = (n_{x y} / n) (n_{x z} / n_{x})$ is within half the required relative tolerance of $P_{X Y Z} (x, y, z)$ for every positive-probability triple. If $P_{X Y Z} (x, y, z) = 0$ , either $(x, y)$ is excluded by the source support condition or $(x, z)$ is excluded by the conditional support condition, so $N_{x y z} = 0$ .

3.1F1step 1.1step 2.1algebra∎

For a positive-probability triple, Chebyshev's inequality and step 1.1 give $\Pr {∣ N_{x y z} - E N_{x y z} ∣ > \frac{1}{2} n ϵ P_{X Y Z} (x, y, z)} \leq \frac{4 n_{x}}{n^{2} ϵ^{2} P_{X Y Z} (x, y, z)^{2}} \leq \frac{4}{n ϵ^{2} P_{X Y Z} (x, y, z)^{2}} .$ There are finitely many triples. A union bound makes the probability that any empirical triple frequency misses its required tolerance at most $C / n$ for a finite constant $C$ depending only on the law, alphabets, and $ϵ$ . This bound is uniform in every admissible conditional type, so it remains valid after mixing over the conditional-type distribution of $Z^{n}$ . The complement event is exactly strong typicality of $(x^{n}, y^{n}, Z^{n})$ , proving the claim.

Depends on

Used by

Dependency tree · two levels

7 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, Network Information Theory, author lecture notes (standard reference, not scraped)
João Barros, Reachback Communication in Wireless Sensor Networks, doctoral dissertation (standard reference, not scraped)