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.

Conditional random-codebook covering for finite alphabets

Statement

Let $(V, X, U)$ have a joint law $P_{V} (v) P_{X ∣ V} (x ∣ v) P_{U ∣ X, V} (u ∣ x, v)$ on finite alphabets. Fix $η > 0$ . There are tolerances $0 < δ_{i n} < δ_{o u t}$ such that, for every sufficiently large $n$ , every $(v^{n}, x^{n})$ in the support-restricted strongly typical set $T_{δ_{i n}}^{(n)} (P_{V X})$ , and every $R > I (X; U ∣ V) + η$ , a codebook of $⌈ e^{n R} ⌉$ conditionally independent words drawn from $P_{U ∣ V}^{\otimes n} (\cdot ∣ v^{n})$ contains a word making $(v^{n}, x^{n}, u^{n}) \in T_{δ_{o u t}}^{(n)} (P_{V X U})$ with probability tending to one uniformly over those fixed pairs.

Facts & Assumptions

Given: A finite law $P_{V X U} = P_{V} P_{X ∣ V} P_{U ∣ X, V}$ and $η > 0$ .

[F1]

Finite strongly typical sets with support restriction: a block is strongly typical when each positive-mass joint letter has empirical frequency within a relative tolerance of its probability and zero-mass letters are absent.

[F2]

Finite conditional mutual information: $I (X; U ∣ V)$ is the finite average, over $v$ , of $D (P_{X U ∣ v} ∥ P_{X ∣ v} P_{U ∣ v})$ in nats.

Proof

1.1F1givenalgebra

Fix $(v^{n}, x^{n}) \in T_{δ_{i n}}^{(n)} (P_{V X})$ . For this concentration calculation, draw an auxiliary word under $Q_{n} : = P_{U ∣ X, V}^{\otimes n} (\cdot ∣ x^{n}, v^{n})$ , rather than under the codebook law $C_{n} : = P_{U ∣ V}^{\otimes n} (\cdot ∣ v^{n})$ . For each positive-mass triple $(v, x, u)$ , its empirical frequency under $Q_{n}$ has mean ${\hat{P}}_{v^{n} x^{n}} (v, x) P_{U ∣ X, V} (u ∣ x, v)$ , which differs from $P (v, x, u)$ by at most $δ_{i n} P (v, x, u)$ . Its variance is at most $1 / (4 n)$ because its indicator summands are independent across positions. Chebyshev's inequality with deviation threshold $(δ_{o u t} - δ_{i n}) P (v, x, u)$ and a finite union bound show that all positive-mass triple frequencies meet the $δ_{o u t}$ conditions with probability tending to one uniformly over the fixed input pairs. Zero-mass input pairs are absent and zero conditional-probability outputs are never generated.

2.1F1F2step 1.1algebra

For a triple word in $T_{δ_{o u t}}^{(n)} (P_{V X U})$ , the exact likelihood ratio is $\ln \frac{P_{U ∣ X, V}^{\otimes n} (u^{n} ∣ x^{n}, v^{n})}{P_{U ∣ V}^{\otimes n} (u^{n} ∣ v^{n})} = n \sum_{v, x, u} {\hat{P}}_{v^{n} x^{n} u^{n}} (v, x, u) \ln \frac{P (u ∣ x, v)}{P (u ∣ v)} .$ Every logarithm on the positive target support is finite. At the target law this finite sum is $I_{P} (X; U ∣ V)$ by [F2]; it is linear in the empirical probabilities. Choose $δ_{o u t}$ small enough that it is at most $I_{P} (X; U ∣ V) + η / 3$ on every target-typical triple. On the target-typical set $T$ , $Q_{n} / C_{n} \leq e^{n (I_{P} (X; U ∣ V) + η / 3)}$ and $Q_{n} ≪ C_{n}$ . Therefore $C_{n} (T) \geq e^{- n (I_{P} (X; U ∣ V) + η / 3)} Q_{n} (T)$ ; step 1.1 gives a one-word match probability at least $(1 - o (1)) e^{- n (I_{P} (X; U ∣ V) + η / 3)}$ , uniformly over the fixed input pairs.

3.1givenstep 2.1algebra∎

The codewords are conditionally independent given $v^{n}$ . If $p_{n} (v^{n}, x^{n})$ is their one-word match probability and $M_{n} = ⌈ e^{n R} ⌉$ , then the probability that no word matches is $(1 - p_{n})^{M_{n}} \leq e^{- M_{n} p_{n}}$ . Since $R > I_{P} (X; U ∣ V) + η$ , step 2.1 gives $M_{n} p_{n} \to \infty$ uniformly, so the no-match probability tends to zero. This proves the covering claim.

Depends on

Used by

Nothing in the library uses this result yet.

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, 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)