Finite joint-typicality packing bound for independent random bins

Fix a nonempty $J\subseteq [k]$ and a particular typical conditioning block $(u_{J^c}^n,s^n)$. For each attainable joint type of $(U_J,U_{J^c},S)$ compatible with this block, the number of possible $u_J^n$ is a product of conditional type-class sizes, hence at most $\exp (n{H}_q(U_J\mathrm{\mid }{U}_{J^c},S))$ by [F2]. There are at most $(n+1{)}^m$ such types, where $m=\mathrm{\mid }\mathcal{S}\mathrm{\mid }{\prod }_i\mathrm{\mid }{\mathcal{U}}_i\mathrm{\mid }$. Expanding the finite conditional-entropy sum gives $H_q(U_J\mathrm{\mid }{U}_{J^c},S)=-{\sum }_{u_J,u_{J^c},s:q>0}q(u_J,u_{J^c},s)\ln \frac{q(u_J,u_{J^c},s)}{q(u_{J^c},s)}=H(q_{U_J{U}_{J^c}S})-H(q_{U_{J^c}S})\mathrm{.}$ The finite entropy summands $-t\ln t$ extend continuously at zero, so this conditional entropy is continuous in the joint law. Choose the typicality tolerance small enough that every such type has $H_q(U_J\mathrm{\mid }{U}_{J^c},S)\le H(U_J\mathrm{\mid }{U}_{J^c},S)+\eta \mathrm{/}3$. Therefore the conditional-typical fan has at most $(n+1{)}^m\exp (n(H(U_J\mathrm{\mid }{U}_{J^c},S)+\eta \mathrm{/}3))$ candidates.

Every such candidate tuple has marginal types close to the target $P_{U_i}$: summing the relative errors over the omitted coordinates shows that each positive marginal atom has relative error at most the joint typicality tolerance. For each $i$, the function $q_i\mapsto {\sum }_{u_i:P_{U_i}(u_i)>0}{q}_i(u_i)\ln P_{U_i}(u_i)$ is a finite linear function, hence continuous even when some $q_i(u_i)=0$, and its value at $P_{U_i}$ is $-H(U_i)$. Zero-probability letters do not occur in a typical candidate by [F1]. Thus, when the tolerance is sufficiently small, the product-marginal probability of any fixed candidate tuple is at most $\exp [-n({\sum }_{i\in J}H(U_i)-\eta \mathrm{/}3)]$. Multiplying by the count in step 1.1 bounds the chance that a fresh independent marginal-codeword tuple is jointly typical with any fixed typical conditioning block by $(n+1{)}^m\exp [-n({\sum }_{i\in J}H(U_i)-H(U_J\mathrm{\mid }{U}_{J^c},S)-2\eta \mathrm{/}3)]$.

A wrong tuple differing from the true tuple on exactly $J$ uses at most ${\prod }_{i\in J}{M}_i$ candidate index combinations. For each combination, on the event that all changed indices differ from the selected indices, its bin labels collide with the true labels with probability ${\prod }_{i\in J}{B}_i^{-1}$: after source-selection data and codebooks fix the selected indices, the independent bin assignments give that probability. For every nonempty proper $J$, the selection hypothesis makes the complementary selected block a function only of $Z^n$ and codebooks in $J^c$; because codebooks in $J$ are independent of $(Z^n,S^n)$ and of the codebooks in $J^c$, the pair consisting of the side-information block and complementary selected block is independent of the candidate changed codewords. If $J=[k]$, the complement is just $S^n$, which is independent of all codebooks by assumption, so the same independence holds without a selector restriction. The indicator of a typical true tuple is bounded by the indicator that its complementary block is typical; this latter block is independent of the changed codewords, so step 2.1 bounds candidate typicality. Dropping the additional indicator that candidate indices differ can only increase this probability. Thus the expected number of wrong tuples of this difference set, multiplied by the indicator of a typical true tuple, is at most $(n+1{)}^m\exp [-n\eta \mathrm{/}3]$ under the displayed rate condition, using the natural-log rate convention [F5].

There are finitely many nonempty subsets $J$. Summing the bounds from step 3.1 over all of them still tends to zero because a polynomial factor is dominated by $e^{-n\eta \mathrm{/}3}$. Markov's inequality then bounds the probability that the true tuple is typical and at least one wrong jointly typical tuple exists by the same vanishing expectation.