Finite random-codebook covering and selected-codeword law

Let $\rho >0$ be any desired relative accuracy for a constructed joint type. For each positive-mass $x$, let $n_x$ be its count in $x^n$. Choose $\delta <1\mathrm{/}2$; then $n_x\mathrm{/}n$ is within relative error $\delta$ of $P_X(x)$, so for all sufficiently large $n$ every such $n_x$ is positive and grows linearly in $n$, uniformly over $x^n\in T_{\delta }^{(n)}(P_X)$. For each row, take floors of $n_x{P}_{U\mathrm{\mid }X}(u\mathrm{\mid }x)$ on its positive conditional support and distribute the fewer than $\mathrm{\mid }\mathcal{U}\mathrm{\mid }$ remaining counts among those entries; set zero-conditional-probability counts to zero. Every resulting count differs from its target by at most $\mathrm{\mid }\mathcal{U}\mathrm{\mid }$. As there are finitely many positive joint atoms, first choose $\delta$ small and then $n$ large so that the joint type $q_{XU}(x,u)=(n_x\mathrm{/}n)q_{U\mathrm{\mid }X}(u\mathrm{\mid }x)$ has relative error at most $\rho$ on every positive atom of $P_{XU}$. Zero joint atoms receive zero counts. Thus the associated conditional type class is nonempty and its joint type lies in $T_{\rho }^{(n)}(P_{XU})$.

The conditional type class from step 1.1 has at least ${\prod }_{x:P_X(x)>0}(n_x+1{)}^{-\mathrm{\mid }\mathcal{U}\mathrm{\mid }}\exp (n_{x}H(q_{U\mathrm{\mid }x}))$ words by [F2]. Every word in it has the same $P_U^{\otimes n}$ probability. Its marginal type $q_U$ is supported on $\mathrm{supp}(P_U)$, and this probability is $\exp \text{\hspace{0.17em}⁣}(n{\sum }_{u:P_U(u)>0}{q}_U(u)\ln P_U(u))=\exp [-n(H(q_U)+D(q_U\mathrm{\parallel }{P}_U))]\mathrm{.}$ For any finite probability vector, each entropy summand $-t\ln t$ is continuous at zero because $t\ln t\to 0$. The finite conditional-entropy sum expands as $H_q(U\mathrm{\mid }X)=-{\sum }_{x,u:q(x,u)>0}q(x,u)\ln \frac{q(x,u)}{q_X(x)}=H(q_{XU})-H(q_X)\mathrm{.}$ On $\mathrm{supp}(P_U)$, $D(r\mathrm{\parallel }{P}_U)={\sum }_{u:P_U(u)>0}r(u)\ln r(u)-{\sum }_{u:P_U(u)>0}r(u)\ln P_U(u),$ so $D(r\mathrm{\parallel }{P}_U)$ is continuous even when some $r(u)=0$. The displayed identity makes $H_q(U\mathrm{\mid }X)$ continuous in $q_{XU}$. Consequently $\mathrm{\Phi }(q):=H_q(U\mathrm{\mid }X)-H(q_U)-D(q_U\mathrm{\parallel }{P}_U)$ is continuous at $P_{XU}$ on the simplex of laws supported by $P_{XU}$, including its boundary. Expanding the finite KL sum [F3] and the entropy formulas [F4]–[F5] gives $I(X;U)=H(U)-H(U\mathrm{\mid }X)$, so $\mathrm{\Phi }(P_{XU})=H(U\mathrm{\mid }X)-H(U)=-I(X;U)$. Choose $\rho <ϵ$ small enough that $\mathrm{\Phi }(q)\ge -I(X;U)-\eta \mathrm{/}3$ whenever $q$ is within relative tolerance $\rho$ of $P_{XU}$. The type-class bound and the product probability then give $p_n(x^n)\ge (n+1{)}^{-\mathrm{\mid }\mathcal{X}\mathrm{\mid }\mathrm{\mid }\mathcal{U}\mathrm{\mid }}\exp [-n(I(X;U)+\eta \mathrm{/}3)]$ uniformly over $x^n\in T_{\delta }^{(n)}(P_X)$.

By independence of the codewords, the probability that none of $M_n$ words lies in the conditional typical set is $(1-p_n(x^n){)}^{M_n}\le e^{-M_n{p}_n(x^n)}$. Choose the tolerances so that the exponent in step 2.1 leaves a positive gap below $R$; then $M_n{p}_n(x^n)\to \mathrm{\infty }$ uniformly, and the no-match probability tends to zero.

For a fixed $x^n$, let $A=T_{ϵ}^{(n)}(P_{XU}\mathrm{\mid }{x}^n)$. The event that index $\mathrm{\ell }$ is the first successful index depends on codewords before $\mathrm{\ell }$ failing and the $\mathrm{\ell }$th codeword lying in $A$; those events are independent across codewords. Consequently, conditional on the first-success event at any $\mathrm{\ell }$, the selected word has law $P_U^{\otimes n}(\cdot \mathrm{\mid }A)$, and averaging over $\mathrm{\ell }$ gives the same conditional law given a match. On each joint type class inside $A$, the marginal type of $U^n$ is fixed, so all its words have the same product probability; the conditional law is therefore uniform on that class.