Joint typicality probability tends to one for a finite IID multisource

Fix $a\in \mathcal{X}$ and put $B_{t,a}:={\mathbf{1}}_{\{Z_t=a\}}$. For any distinct $t_1,\dots ,t_r$ and sets $E_j\subseteq \{0,1\}$, ${\bigcap }_j\{B_{t_j,a}\in E_j\}={\bigcap }_j\{Z_{t_j}\in {\varphi }_a^{-1}(E_j)\}$, where ${\varphi }_a(z)={\mathbf{1}}_{\{z=a\}}$. Mutual independence in [F1, F4] factors the probability of this intersection, and the common law $P$ gives every $B_{t,a}$ the same distribution; hence $(B_{t,a})$ are IID. Their mean is $P(a)$ and variance is $P(a)(1-P(a))\le 1\mathrm{/}4$. Their sample mean is ${\widehat{P}}_{Z^n}(a)$ by [F3]. Independence gives $\mathbb{E}[({\widehat{P}}_{Z^n}(a)-P(a){)}^2]=\mathrm{Var}(B_{1,a})\mathrm{/}n\le 1\mathrm{/}(4n)$; since a square is at least ${\delta }^2$ on the event of deviation at least $\delta$, that event has probability at most $1\mathrm{/}(4n{\delta }^2)$. If $P(a)=0$, the probability that $a$ occurs at any of the first $n$ positions is zero. A union bound over the finite alphabet proves that the support and empirical-coordinate requirements in [F2] fail with probability at most $\mathrm{\mid }\mathcal{X}\mathrm{\mid }\mathrm{/}(4n{\delta }^2)$.

By [F5], the full-information requirement in [F2] fails with probability at most $V(P)\mathrm{/}(n{ϵ}^2)$.

Fix a nonempty $S\subseteq [k]$ and write $C=S^c$. On the support of $P$, define $W_t^S:=-\ln P_{X_S\mid X_C}(X_{S,t}\mid X_{C,t})$, and set it to $0$ off the support. This is a finite-valued function ${\psi }_S(Z_t)$. For distinct $t_1,\dots ,t_r$ and Borel sets $B_1,\dots ,B_r$, ${\bigcap }_j\{W_{t_j}^S\in B_j\}={\bigcap }_j\{Z_{t_j}\in {\psi }_S^{-1}(B_j)\}$; [F1, F4] therefore give mutual independence and a common law, so $(W_t^S)$ are IID. Its mean is $H_P(X_S\mid X_C)$ by the finite sum in [F6] and the zero-term convention in [F8], and its variance ${\sigma }_S^2$ is finite because its range is finite. By [F7], $J_{S,n}=n^{-1}{\sum }_{t=1}^n{W}_t^S$ almost surely. Independence gives $\mathbb{E}[(J_{S,n}-H_P(X_S\mid X_C){)}^2]={\sigma }_S^2\mathrm{/}n$, so the same squared-deviation argument bounds failure of this conditional requirement by ${\sigma }_S^2\mathrm{/}(n{ϵ}^2)$.

There are finitely many symbols and finitely many nonempty subsets $S$. The union bound over the failure events in steps 1.1, 1.2, and 1.3 is at most $\frac{\mathrm{\mid }\mathcal{X}\mathrm{\mid }}{4n{\delta }^2}+\frac{V(P)+{\sum }_{\mathrm{\varnothing }\mathrm{\ne }S\subseteq [k]}{\sigma }_S^2}{n{ϵ}^2}$, which tends to zero. Its complement is exactly the event in the Statement, proving the claimed limit.