Likelihood-ratio network coding for finite or Euclidean multicast networks

Write $C_k=I(Y_k;{\widehat{Y}}_k\mathrm{\mid }{X}_k,Q)$. Fix $a>0$ and $0<ϵ<1\mathrm{/}2$. Choose a deterministic word $q^n$ whose symbol proportions tend to $P_Q$, omitting zero-probability symbols. For node $k$ let $r_k^n(du\mathrm{\mid }x,y)={\prod }_t{P}_{{\widehat{Y}}_k\mathrm{\mid }{X}_k,Y_k,q_t}(d{u}_t\mathrm{\mid }{x}_t,y_t)$ and ${\mu }_k^n(du\mathrm{\mid }x)={\prod }_t{P}_{{\widehat{Y}}_k\mathrm{\mid }{X}_k,q_t}(d{u}_t\mathrm{\mid }{x}_t)$. Define $H_k(x,y)=\{u:\log (d{r}_k^n\mathrm{/}d{\mu }_k^n)(u)\le n(C_k+a)\}$ and $Z_k(x,y)=r_k^n(H_k\mathrm{\mid }x,y)$. Under the target product law, the information density is a sum of the stated square-integrable local log likelihoods. Apply [F4] separately to the finitely many positive-probability $q$ subblocks; their lengths tend to infinity and their proportions tend to $P_Q$. Thus its normalized sum tends in probability to $C_k$, so $\mathbb{E}(1-Z_k)\to 0$. The pointwise inequality ${\mathbf{1}}_{\{1-Z_k>ϵ\}}\le (1-Z_k)\mathrm{/}ϵ$ shows that pairs with $Z_k<1-ϵ$ have probability tending to zero.

For a good pair $Z_k\ge 1-ϵ$, put $T_k=r_k^n{\mathbf{1}}_{H_k}\mathrm{/}{Z}_k$ and $M_k=e^{n(C_k+a)}\mathrm{/}(1-ϵ)$. Generate $L_k=\lceil e^{n{\rho }_k}\rceil$ independent reconstruction entries with law ${\mu }_k^n$, where ${\rho }_k>C_k+a$. Test entries in order, accepting $u$ with probability $(d{T}_k\mathrm{/}d{\mu }_k^n)(u)\mathrm{/}{M}_k$ using an independent uniform for each entry. This is at most one, its mean is $p_k=1\mathrm{/}{M}_k$, and $p_k$ is independent of the good pair. The no-acceptance probability is $(1-p_k{)}^{L_k}\le e^{-L_k\mathrm{/}{M}_k}\to 0$. Use a fixed default index on a bad pair or no acceptance. Conditional on acceptance at a specified label $\mathrm{\ell }$, the accepted entry has law $T_k$; an earlier rejected entry has law ${\mu }_k^n(du\mathrm{\mid }x)(1-(d{T}_k\mathrm{/}d{\mu }_k^n)(u)\mathrm{/}{M}_k)\mathrm{/}(1-p_k)$, bounded by $2{\mu }_k^n$ for large $n$; later entries retain law ${\mu }_k^n$. Multiplication of the independent entry and uniform densities proves these statements and conditional independence of the entries given the pair and $\mathrm{\ell }$.

Since $T_k\le r_k^n\mathrm{/}(1-ϵ)$ and $\mathrm{\parallel }{T}_k-r_k^n{\mathrm{\parallel }}_{\mathrm{T}\mathrm{V}}=1-Z_k$ on good pairs, the averaged total variation error of the selected reconstruction kernel tends to zero by step 1.1. Summing these errors over the finitely many nodes compares their product kernels to the target product test channel; the bound follows by replacing one kernel at a time and integrating bounded indicator functions. Consequently every full-tuple target event of probability tending to one also holds with probability tending to one for the selected reconstructions, apart from the already vanishing selection failures. Draw one independent uniform for each node, block, message, previous-index branch, and reconstruction entry. A transmitted branch exposes each such uniform at most once. Uninspected branches retain their independent codewords and uniforms; the finite array will be fixed at the end.

Set $J_d(A,U)={\sum }_q{P}_Q(q)D(P_{d,q}\mathrm{\parallel }{Q}_{d,A,U,q})$. The block acceptance test at destination $d$ is the intersection, over every allowed $(A,U)$, of $\log \frac{d{\prod }_t{P}_{d,q_t}}{d{\prod }_t{Q}_{d,A,U,q_t}}(v^n)\ge n(J_d(A,U)-a)\mathrm{.}$ By the square-integrability hypothesis and [F4], all these finitely many tests accept the true target block with probability tending to one. On the displayed event the reference product measure is at most $e^{-n(J_d(A,U)-a)}$ times the target product measure; integration therefore bounds its reference probability by $e^{-n(J_d(A,U)-a)}$. This argument applies to discrete sums and Euclidean integrals alike.

Let $E_d(A)=J_d(A,\mathrm{\varnothing })$. Conditional KL chain rules, using independence of the inputs given $Q$, give $E_d(A)=I(X_A;{\widehat{Y}}_{A^c},Y_d\mathrm{\mid }{X}_{A^c},Q)+{\sum }_{k\in A}I({\widehat{Y}}_k;X_{[N]},{\widehat{Y}}_{A^c},Y_d,{\widehat{Y}}_{\{j\in A:j<k\}}\mathrm{\mid }{X}_k,Q)\mathrm{.}$ For a direct verification in finite alphabets, expand the reference likelihood: the input contribution is ${\sum }_{k\in A}H(X_k\mathrm{\mid }Q)-H(X_A\mathrm{\mid }{X}_{A^c},{\widehat{Y}}_{A^c},Y_d,Q)$, and the reconstruction contribution is ${\sum }_{k\in A}H({\widehat{Y}}_k\mathrm{\mid }{X}_k,Q)-H({\widehat{Y}}_A\mathrm{\mid }{X}_{[N]},{\widehat{Y}}_{A^c},Y_d,Q)$; order the latter entropy by $k$. The conditional-KL expansion gives the identical formula in the Euclidean case without assuming finite differential entropy. A further chain expansion shows that $J_d(A,U)-E_d(A)$ is the conditional KL of $P_{{\widehat{Y}}_U\mathrm{\mid }{X}_{A^c},{\widehat{Y}}_{(A\cup U{)}^c},Y_d,Q}$ from ${\prod }_{k\in U}{P}_{{\widehat{Y}}_k\mathrm{\mid }{X}_k,Q}$, averaged over the displayed conditioning tuple. It is nonnegative; in finite entropy notation it equals ${\sum }_{k\in U}H({\widehat{Y}}_k\mathrm{\mid }{X}_k,Q)-H({\widehat{Y}}_U\mathrm{\mid }{X}_{A^c},{\widehat{Y}}_{(A\cup U{)}^c},Y_d,Q)$. Thus $J_d(A,U)\ge E_d(A)$ for every wrong-current-index pattern.

Subtract $C_k$ from the $k$th reconstruction summand in step 5.1. The test-channel factorization says that given $X_{[N]},Y_A,Q$, the reconstructions in $A$ are conditionally independent and depend only on their own $(X_k,Y_k,Q)$. In finite entropy notation the sum of differences is therefore $H({\widehat{Y}}_A\mathrm{\mid }{X}_{[N]},Y_A,{\widehat{Y}}_{A^c},Y_d,Q)-H({\widehat{Y}}_A\mathrm{\mid }{X}_{[N]},{\widehat{Y}}_{A^c},Y_d,Q)$; conditional-KL chain expansion gives the same identity for the assumed finite Euclidean informations. Consequently $E_d(A)-{\sum }_{k\in A}{C}_k=I(X_A;{\widehat{Y}}_{A^c},Y_d\mathrm{\mid }{X}_{A^c},Q)-I(Y_A;{\widehat{Y}}_A\mathrm{\mid }{X}_{[N]},{\widehat{Y}}_{A^c},Y_d,Q)=F_d(A)\mathrm{.}$ This cancellation uses the product test channels and does not require independent channel outputs.

For each constrained node with a strict mean-cost inequality choose $\mathbb{E}{c}_k(X_k)<{\mathrm{\Gamma }}_k^{\mathrm{\prime }}<{\mathrm{\Gamma }}_k$, and condition each independent product input word on ${\sum }_t{c}_k(x_{k,t})\le n{\mathrm{\Gamma }}_k^{\mathrm{\prime }}$. Its conditioning probability $b_{k,n}$ tends to one by [F4], since the cost has finite second moment; the finite-$Q$ subblock argument of step 1.1 applies. Each such word obeys the cost bound deterministically. Its law has density at most $1\mathrm{/}{b}_{k,n}$ relative to the target product input law and total variation distance $1-b_{k,n}$. At an unconstrained node use the unconditioned word and put $b_{k,n}=1$; at a deterministic already-feasible constrained node use its fixed word and also put $b_{k,n}=1$, so no strict slack is needed there. For a fresh block the transmitted input tuple is within ${\sum }_k(1-b_{k,n})$ of its target product law, uniformly in all previous labels. Passing through a kernel preserves this upper bound, because an event's conditional probability is in $[0,1]$. Thus the vanishing selection-failure and true-test estimates remain valid for these input words.

Choose a fixed block count $B$. At node $k$ in each block $j$, independently generate $X_{k,j}(m,l)$ for $1\le m\le \lfloor e^{nB{r}_k}\rfloor$ and $1\le l\le L_k$, using singleton messages when $r_k=0$ or $k\mathrm{\notin }\mathcal{S}$, and the word law from step 7.1. For each word generate $L_k$ reconstruction words from ${\mu }_k^n(\cdot \mathrm{\mid }{X}_{k,j}(m,l))$ and the uniforms of step 3.1. All nodes, branches and blocks are independent. Initialize $l_{k,0}=1$. In block $j$ send $X_{k,j}(m_k,l_{k,j-1})$, and after the block choose $l_{k,j}$ by step 2.1. This is causal. A destination fixes its own message and its own actual index sequence, and selects the unique other-source message tuple for which some remaining index sequence passes every block test from step 4.1. Ties or no tuple are errors; compression indices need not be uniquely decoded. Every operation is a finite search through measurable tests. The message is repeated across all $B$ blocks, so length $nB$ gives rate tending to $r_k$.

Expose fresh blocks sequentially. Conditional on messages and previous true labels, the next block arrays are independent of the past, so steps 1.1–3.1, 4.1 and 7.1 apply to its actual transmitted branch. A finite union over $NB$ local selections and $B\mathrm{\mid }\mathcal{D}\mathrm{\mid }$ true-message tests gives vanishing true-message failure probability. To track false messages, by symmetry set the true messages to 1. Fix a nonempty wrong-source set $T$, a false message tuple, a true label path $\mathrm{\ell }$, and a candidate label path $l$. Put $A_j=\{k:m_k\mathrm{\ne }1\text{ or }{l}_{k,j-1}\mathrm{\ne }{\mathrm{\ell }}_{k,j-1}\}$ and $U_j=\{k\mathrm{\notin }{A}_j:l_{k,j}\mathrm{\ne }{\mathrm{\ell }}_{k,j}\}$. Then $T\subseteq A_j$, $d\mathrm{\notin }{A}_j$, and $U_j\subseteq A_j^c\setminus \{d\}$. At a node in $A_j$ the false branch is uninspected; at a node in $U_j$ its candidate reconstruction is an unselected entry of the true branch, subject to the factor 2 bound in step 2.1; all other candidate entries are true selected entries, subject to the factor $(1-ϵ{)}^{-1}$.

The exact unnormalized measure for one true block and specified successful labels is $({\prod }_k(1-p_k{)}^{{\mathrm{\ell }}_k-1}{p}_k){\mathbf{1}}_G(x,y)({\prod }_k{\mu }_{X_k,n}(d{x}_k))W^{\otimes n}(dy\mathrm{\mid }x){\prod }_k{T}_k(d{u}_k\mathrm{\mid }{x}_k,y_k),$ where $G$ means every local pair is good and ${\mu }_{X_k,n}$ is the word law. There is no division by $\mathrm{Pr}(G)$. Integrate nuisance true coordinates and use step 9.1. At most two input words per node are exposed, each bounded by $1\mathrm{/}{b}_{k,n}\le 2$ for large $n$. The candidate block subprobability is therefore bounded by the geometric label weight times $K{\prod }_t{Q}_{d,A_j,U_j,q_t}$, with $K=2^{3N}(1-ϵ{)}^{-N}$ independent of all labels and $n$. Retaining the indicator ${\mathbf{1}}_G\le 1$ can only reduce this bound. For a fixed true path, different block arrays are independent; all its branch labels are fixed. The sum of its geometric weights over allowed true paths is at most one. Thus the block packing bounds multiply, with no conditioning on a possibly rare global good event.

Drop the first block's false-message test. For each remaining block step 4.1 and $J_d(A_j,U_j)\ge E_d(A_j)$ give the factor $K{e}^{-n(E_d(A_j)-a)}$, independently of $U_j$. For a fixed previous-index pattern $A$, at most ${\prod }_{k\in A}{L}_k$ previous-index vectors realize it; at most $2^{N-1}$ sets $A$ contain $T$ and exclude $d$. There are at most ${\prod }_{k\mathrm{\ne }d}{L}_k$ final-index choices and $e^{nBr(T)}$ false message tuples with set $T$, where $r(T)={\sum }_{k\in T}{r}_k$ and $\rho (A)={\sum }_{k\in A}{\rho }_k$. Summing all these paths and the true weights from step 10.1 gives a constant depending only on $N,B,ϵ$ times ${\sum }_{\mathrm{\varnothing }\mathrm{\ne }T\subseteq \mathcal{S}\setminus \{d\}}\exp (nBr(T)+n{\sum }_{k\mathrm{\ne }d}{\rho }_k-n(B-1){\min }_{T\subseteq A,d\mathrm{\notin }A}\{E_d(A)-\rho (A)-a\})\mathrm{.}$ Rounding the $L_k$ contributes only another constant for fixed $B,N$. This is the union bound for every false message/previous-index/current-index pattern.

If constrained cuts exist, their finitely many strict rate gaps have a positive minimum $g$. Choose $a$ small and then ${\rho }_k>C_k+a$ with ${\rho }_k-C_k$ small enough that ${\sum }_{k\in A}({\rho }_k-C_k)+a<g\mathrm{/}2$ on every cut. Step 6.1 gives $E_d(A)-\rho (A)=F_d(A)-{\sum }_{k\in A}({\rho }_k-C_k)$. For every $A\supseteq T$, nonnegativity gives $r(T)\le r(A\cap \mathcal{S})<F_d(A)$. Choose $B$ sufficiently large that $r(T)<\frac{B-1}{B}{\min }_{T\subseteq A,d\mathrm{\notin }A}\{E_d(A)-\rho (A)-a\}-\frac{1}{B}{\sum }_{k\mathrm{\ne }d}{\rho }_k$ for all finitely many $T,d$. This is possible because the remaining strict gaps are at least $g\mathrm{/}2$. Fix those choices and let $n\to \mathrm{\infty }$. Every exponential term in step 11.1 tends to zero, as do the true-message failures. If no constrained cuts exist, all required messages are either absent or already known locally and there is nothing to decode. A finite union over destinations proves multicast reliability.

In the finite branch, every fixed codebook and seed array induces one of finitely many deterministic encoder/decoder functions on the finite message and observation domains. Aggregate the ensemble distribution over this finite set of functions, enumerate it, and take the first code whose error is at most the ensemble average. Thus neither the auxiliary uniforms nor selection of the final finite code assumes AC. In the Euclidean branch average error over codebooks, messages and the finite uniform arrays and select a deterministic realization whose error tends to zero; a realization of error at most twice the positive average exists by integration, while if the average is zero almost every realization has zero error. The fixed-seed encoders and decoders remain measurable and causal. Each chosen input word obeys its shell bound, so concatenating $B$ words gives the claimed pointwise and expected costs; no random ensemble power assertion is used to select the deterministic code. Constant reconstructions contribute zero information and satisfy the same construction. The all-zero tuple uses singleton messages and any allowed fixed inputs, with zero error. Finally choose strict-region tuples tending to any point of the closure and, for the $j$th tuple, a sufficiently long code of error below $1\mathrm{/}j$ and rate within $1\mathrm{/}j$ of that tuple. These codes realize the closure by the definition of achievability.