LemmaStatement: 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.

Information-density concentration for a fixed finite DMC input law

Statement

Let $W (y ∣ u)$ be a finite DMC and let $P_{U}$ be any fixed input probability vector. Let $P_{Y} (y) = \sum_{u} P_{U} (u) W (y ∣ u)$ . On the joint support $P_{U} (u) W (y ∣ u) > 0$ , define

$J (u, y) : = \ln \frac{W (y ∣ u)}{P_{Y} (y)}, I : = I (U; Y), σ^{2} : = \sum_{u, y : P_{U} (u) W (y ∣ u) > 0} P_{U} (u) W (y ∣ u) (J (u, y) - I)^{2} .$

For IID pairs $(U_{i}, Y_{i}) \sim P_{U} W$ , write $S_{n} = \sum_{i = 1}^{n} J (U_{i}, Y_{i})$ and $B : = \max (0, \max_{P_{U} (u) W (y ∣ u) > 0} J (u, y))$ . Then $J$ is bounded and $E [J] = I$ . For every $δ > 0$ ,

$\Pr [∣ \frac{S_{n}}{n} - I ∣ \geq δ] \leq \frac{σ^{2}}{n δ^{2}} .$

For every $γ > 0$ there is a $ρ \in (0, 1)$ , depending only on $(P_{U}, W, γ)$ , such that

$\Pr [S_{n} > n (I + γ)] \leq ρ^{n} .$

Facts & Assumptions

Given: For each blocklength $n$ , the joint law is $P_{U^{n}, Y^{n}} (u^{n}, y^{n}) = \prod_{i = 1}^{n} P_{U} (u_{i}) W (y_{i} ∣ u_{i})$ for a finite DMC $W$ and input probability vector $P_{U}$ .

[F1]

Finite discrete memoryless channels: for the input word $u^{n}$ , the output law is $W^{n} (y^{n} ∣ u^{n}) = \prod_{i = 1}^{n} W (y_{i} ∣ u_{i})$ .

[F2]

Finite mutual information: $I (U; Y) = \sum_{u, y : P_{U} (u) W (y ∣ u) > 0} P_{U} (u) W (y ∣ u) \ln \frac{W (y ∣ u)}{P_{Y} (y)}$ .

[F3]

Information units and logarithm-base convention: unmarked logarithms are natural, so the information quantities are in nats.

[F4]

The natural logarithm as the inverse of the exponential function: $e^{t}$ is the exponential whose inverse on $(0, \infty)$ is the natural logarithm.

[F5]

The exponential function is smooth and $(\exp)^{'} = \exp$ : the real exponential is differentiable with derivative itself, so a finite sum of exponential functions may be differentiated term by term.

Proof

1.1givenF1F3construct

If $P_{U} (u) W (y ∣ u) > 0$ , then $P_{Y} (y) \geq P_{U} (u) W (y ∣ u) > 0$ . Hence every displayed logarithm is finite; because the joint support is finite, $J$ is bounded and $B < \infty$ . The unmarked logarithm uses nats by [F3].

2.1F1F2givenstep 1.1algebra

The expectation $E [J (U, Y)]$ is the finite sum in [F2], so it equals $I$ . Independence and the common product law in [F1] give $E [S_{n}] = n I$ and $E [(S_{n} - n I)^{2}] = n σ^{2}$ : the cross terms vanish because each centered summand has mean zero, and each diagonal term has second moment $σ^{2}$ . For the nonnegative variable $(S_{n} - n I)^{2}$ , the pointwise inequality $1 {(S_{n} - n I)^{2} \geq n^{2} δ^{2}} \leq (S_{n} - n I)^{2} / (n^{2} δ^{2})$ gives the Chebyshev bound after taking expectations.

3.1F4F5step 2.1choosealgebra

Fix $γ > 0$ and define $ϕ (t) : = E [e^{t (J - I - γ)}]$ . Finite support makes $ϕ$ differentiable at zero, with $ϕ (0) = 1$ and $ϕ^{'} (0) = E [J - I - γ] = - γ < 0$ . By the definition of derivative, some sufficiently small $t > 0$ has $0 < ρ : = ϕ (t) < 1$ .

4.1step 3.1algebra∎

The event $S_{n} > n (I + γ)$ implies $e^{t \sum_{i} (J (U_{i}, Y_{i}) - I - γ)} > 1$ . Its indicator is therefore at most that nonnegative exponential. Independence of the IID pairs gives $\Pr [S_{n} > n (I + γ)] \leq E [e^{t \sum_{i} (J (U_{i}, Y_{i}) - I - γ)}] = ϕ (t)^{n} = ρ^{n} .$ This proves the exponential tail.

Depends on

Used by

Dependency tree · two levels

21 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

Paul Cuff, Princeton ELE 538: Information Theoretic Security, Lecture 12 (standard reference, not scraped)
Abbas El Gamal and Young-Han Kim, Network Information Theory, arXiv:1001.3404v3 (standard reference, not scraped)