Information Theory and Statistics

There are $\lvert\mathcal{X}\rvert$ components in the vector specifying $P_x$, and the numerator in each can take only $n+1$ values, so there are at most $(n+1)^{\lvert\mathcal{X}\rvert}$ choices. These are not independent (the last is fixed by the others), but the bound is good enough.

∎

$Q^n(x) = \prod_{i=1}^n Q(x_i) = \prod_{a\in\mathcal{X}} Q(a)^{N(a\mid x)} = \prod_a Q(a)^{nP_x(a)} = \prod_a 2^{nP_x(a)\log Q(a)}$

Now the trick: add and subtract $P_x(a)\log P_x(a)$ inside the exponent,

$= \prod_a 2^{n\left(P_x(a)\log Q(a) - P_x(a)\log P_x(a) + P_x(a)\log P_x(a)\right)} = 2^{n\sum_a\left(-P_x(a)\log\frac{P_x(a)}{Q(a)} + P_x(a)\log P_x(a)\right)}$

$= 2^{n\left(-D(P_x\Vert Q) - H(P_x)\right)}$

∎

The exact size is the multinomial $\binom{n}{nP(a_1),\ldots,nP(a_{\lvert\mathcal{X}\rvert})}$, hard to manipulate, so we derive exponential bounds. (Stirling’s formula also works; this argument is cleaner.)

Upper bound. A type class has probability at most 1 under its own distribution:

$1 \ge P^n(T(P)) = \sum_{x\in T(P)} P^n(x) = \sum_{x\in T(P)} 2^{-nH(P)} = \lvert T(P)\rvert 2^{-nH(P)}$

using Theorem 2’s corollary. Hence $\lvert T(P)\rvert \le 2^{nH(P)}$.

Lower bound, step 1: $T(P)$ has the highest probability of any type class under $P$. For any $\hat P \in \mathcal{P}_n$, the ratio of probabilities is

$\frac{P^n(T(P))}{P^n(T(\hat P))} = \frac{\lvert T(P)\rvert}{\lvert T(\hat P)\rvert}\prod_a P(a)^{n(P(a) - \hat P(a))} = \prod_a \frac{(n\hat P(a))!}{(nP(a))!}P(a)^{n(P(a)-\hat P(a))}$

Using the simple bound $\frac{m!}{n!} \ge n^{m-n}$ (prove by separately considering $m\ge n$ and $m<n$):

$\ge \prod_a (nP(a))^{n\hat P(a) - nP(a)}P(a)^{n(P(a)-\hat P(a))} = \prod_a n^{n(\hat P(a) - P(a))} = n^{n(1-1)} = 1$

Lower bound, step 2. Since there are at most $(n+1)^{\lvert\mathcal{X}\rvert}$ types and $T(P)$ is the most probable,

$1 = \sum_{Q\in\mathcal{P}_n} P^n(T(Q)) \le (n+1)^{\lvert\mathcal{X}\rvert}P^n(T(P)) = (n+1)^{\lvert\mathcal{X}\rvert}\lvert T(P)\rvert 2^{-nH(P)}$

∎

$Q^n(T(P)) = \sum_{x\in T(P)}Q^n(x) = \lvert T(P)\rvert\, 2^{-n(D(P\Vert Q)+H(P))}$ and substitute the bounds on $\lvert T(P)\rvert$: the $2^{nH(P)}$ cancels the $2^{-nH(P)}$ exactly, leaving $2^{-nD(P\Vert Q)}$ up to the polynomial factor.

∎

The inequality is the derivation above. Summing over $n$ gives $\sum_{n=1}^\infty \Pr\{D(P_{x^n}\Vert P)>\epsilon\} < \infty$, so the expected number of occurrences of the event is finite, hence the actual number is finite with probability 1 (Borel–Cantelli) — giving almost-sure convergence, stronger than the in-probability statement of the AEP.

∎

Step 1: Define the set. Let $R_n = R - \lvert\mathcal{X}\rvert\frac{\log(n+1)}{n}$ (the rate, discounted by the polynomial type count) and

$A = \{x \in \mathcal{X}^n : H(P_x) \le R_n\}$

Step 2: Check it fits in $2^{nR}$ indices.

$\lvert A\rvert = \sum_{P\in\mathcal{P}_n : H(P)\le R_n}\lvert T(P)\rvert \le \sum_{P : H(P)\le R_n}2^{nH(P)} \le \sum_{P:H(P)\le R_n}2^{nR_n}$

$\le (n+1)^{\lvert\mathcal{X}\rvert}2^{nR_n} = 2^{n\left(R_n + \lvert\mathcal{X}\rvert\frac{\log(n+1)}{n}\right)} = 2^{nR}$

This is exactly why $R_n$ was defined with that discount — it is sized precisely to absorb the polynomial number of types.

Step 3: Encode. $f_n(x)$ is the index of $x$ in $A$ if $x\in A$, else 0. The decoder maps each index to the corresponding element, so all of $A$ is recovered and everything else errs.

Step 4: Error probability. With true distribution $Q$, $H(Q)<R$:

$P_e^{(n)} = 1 - Q^n(A) = \sum_{P : H(P)>R_n}Q^n(T(P)) \le (n+1)^{\lvert\mathcal{X}\rvert}\max_{P:H(P)>R_n}Q^n(T(P))$

$\le (n+1)^{\lvert\mathcal{X}\rvert}2^{-n\min_{P : H(P) > R_n}D(P\Vert Q)}$

Since $R_n \uparrow R$ and $H(Q) < R$, there is $n_0$ beyond which $R_n > H(Q)$; then the minimizing $D$ is strictly positive and $P_e^{(n)}\to0$ exponentially.

∎

Upper bound. Sum over types in $E$, bound each by Theorem 4, replace each by the maximum, and count types with Theorem 1:

$Q^n(E) = \sum_{P\in E\cap\mathcal{P}_n}Q^n(T(P)) \le \sum_{P\in E\cap\mathcal{P}_n}2^{-nD(P\Vert Q)} \le \sum_{P\in E\cap\mathcal{P}_n}2^{-n\min_{P\in E}D(P\Vert Q)} \le (n+1)^{\lvert\mathcal{X}\rvert}2^{-nD(P^*\Vert Q)}$

Note $P^*$ need not be a member of $\mathcal{P}_n$ — it is the minimizer over all of $E$, not over types.

Lower bound. Here we need a nice set so that for large $n$ we can find a type in $E$ close to $P^*$. If $E$ is the closure of its interior (so the interior is nonempty), then since $\cup_n\mathcal{P}_n$ is dense in the set of all distributions, $E\cap\mathcal{P}_n$ is nonempty for $n\ge n_0$, and we can find $P_n \in E\cap\mathcal{P}_n$ with $D(P_n\Vert Q)\to D(P^*\Vert Q)$. Then

$Q^n(E) \ge Q^n(T(P_n)) \ge \frac{1}{(n+1)^{\lvert\mathcal{X}\rvert}}2^{-nD(P_n\Vert Q)}$

and taking $\liminf$ of $\frac1n\log$ kills the polynomial factor, giving $\ge -D(P^*\Vert Q)$.

∎

Let $P_\lambda = \lambda P + (1-\lambda)P^*$; by convexity of $E$, $P_\lambda\in E$ for $0\le\lambda\le1$, and $P_\lambda\to P^*$ as $\lambda\to0$. Since $D(P^*\Vert Q)$ is the minimum along this path, the derivative of $D_\lambda = D(P_\lambda\Vert Q)$ is non-negative at $\lambda = 0$:

$\frac{dD_\lambda}{d\lambda} = \sum (P(x) - P^*(x))\left[\log\frac{P_\lambda(x)}{Q(x)} + 1\right]$

Setting $\lambda = 0$ (so $P_\lambda = P^*$) and using $\sum P(x) = \sum P^*(x) = 1$ to kill the $+1$:

$0 \le \sum(P(x) - P^*(x))\log\frac{P^*(x)}{Q(x)} = \sum P(x)\log\frac{P(x)}{Q(x)}\frac{P^*(x)}{P(x)} - \sum P^*(x)\log\frac{P^*(x)}{Q(x)}$

$= D(P\Vert Q) - D(P\Vert P^*) - D(P^*\Vert Q)$

∎

Binary case. For $p\ge q$, let $g(p,q) = p\log\frac pq + (1-p)\log\frac{1-p}{1-q} - \frac{4}{2\ln2}(p-q)^2$. Then

$\frac{dg}{dq} = \frac{q-p}{q(1-q)\ln2} - \frac{4}{\ln2}(q-p) \le 0$

since $q(1-q)\le\tfrac14$ and $q\le p$. As $g(p,p)=0$, we get $g(p,q)\ge0$ for $q\le p$.

General case. Let $A = \{x : P_1(x)>P_2(x)\}$ and $Y = \mathbb{1}_A(X)$, with $\hat P_1,\hat P_2$ the induced binary distributions. By the data processing inequality for relative entropy,

$D(P_1\Vert P_2) \ge D(\hat P_1\Vert\hat P_2) \ge \frac{4}{2\ln2}(P_1(A)-P_2(A))^2 = \frac{1}{2\ln2}\lVert P_1-P_2\rVert_1^2$

∎

Step 1: Define the shells. Let $S_t = \{P : D(P\Vert Q)\le t\}$, convex since $D$ is convex in $P$; and $D^* = D(P^*\Vert Q)$, with $P^*$ unique since $D$ is strictly convex. Set

$A = S_{D^*+2\delta}\cap E, \qquad B = E - S_{D^*+2\delta}\cap E$

so $A\cup B = E$: $A$ is the part of $E$ at about $P^*$‘s distance from $Q$, $B$ the part at least $2\delta$ farther.

Step 2: Bound the far shell above.

$Q^n(B) = \sum_{P\in E\cap\mathcal{P}_n : D>D^*+2\delta}Q^n(T(P)) \le (n+1)^{\lvert\mathcal{X}\rvert}2^{-n(D^*+2\delta)}$

Step 3: Bound the near shell below. For $n$ large there is at least one type in $S_{D^*+\delta}\cap E\cap\mathcal{P}_n$, and a sum exceeds one of its terms:

$Q^n(A) \ge Q^n(S_{D^*+\delta}\cap E) \ge \frac{1}{(n+1)^{\lvert\mathcal{X}\rvert}}2^{-n(D^*+\delta)}$

Step 4: The ratio vanishes.

$\Pr(P_{X^n}\in B \mid P_{X^n}\in E) \le \frac{Q^n(B)}{Q^n(A)} \le (n+1)^{2\lvert\mathcal{X}\rvert}2^{-n\delta} \to 0$

so the conditional probability of $A$ goes to 1. The $\delta$ gap between the two shells is what makes the exponentials separate.

Step 5: Everything in $A$ is close to $P^*$. For $P\in A$ we have $D(P\Vert Q)\le D^*+2\delta$, so by the Pythagorean theorem

$D(P\Vert P^*) + D^* \le D(P\Vert Q) \le D^* + 2\delta \quad\Longrightarrow\quad D(P\Vert P^*)\le2\delta$

Step 6: Transfer to the marginal. Small relative entropy implies small $L_1$ by Pinsker, so $\max_a\lvert P_{X^n}(a) - P^*(a)\rvert$ is small with conditional probability $\to1$, i.e. $\Pr(X_1 = a\mid P_{X^n}\in E)\to P^*(a)$.

∎

For all $x$, $(\phi_A(x) - \phi_B(x))(P_1(x) - TP_2(x)) \ge 0$ — check the cases $x\in A$ and $x\notin A$ separately. Summing over the space:

$0 \le \sum_A (P_1 - TP_2) - \sum_B(P_1 - TP_2) = (1-\alpha^*) - T\beta^* - (1-\alpha) + T\beta = T(\beta - \beta^*) - (\alpha^* - \alpha)$