Strong data-processing inequalities for channels and Bayesian networks

• The paper frames SDPIs as strict forms of data processing that quantify how distributions become closer and information is lost through non-degenerate noisy channels.Source: §1 · p. 3
• Given SDPIs for constituent channels, the central problem is deriving an SDPI for the composite source-to-sinks channel in a multi-terminal network.Source: §1 · p. 4
• The Evans-Schulman method is applied to mutual information, total variation, and FI-curves, with network bounds interpreted through site percolation.Source: §1 · p. 4
• The paper also studies product memoryless channels, including an n-letter binary symmetric channel example, and connects linear SDPIs with erasure-channel comparisons.Source: §1 · pp. 3–4

2.1 Contraction coefficients for f-divergence and mutual information

• Contraction coefficients compare how channels shrink f-divergences, total variation, KL divergence, and mutual information, with Dobrushin’s coefficient upper-bounding other coefficients in general.Source: §2.1 · p. 5

2.2 Non-linear SDPI

• For nonlinear strong data processing, the FI-curve gives the optimal input-independent bound relating output mutual information to input mutual information.Source: §2.2 · pp. 7–8
• The FI-curve need not be concave, motivating its concavified version for extending contraction-coefficient arguments.Source: §2.2 · p. 8

2.3 Some applications: classical and new

• SDPIs support applications in impossibility results, noisy-circuit analysis, percolation, distributed estimation, privacy, and bounded cumulative approximation error in hidden Markov models.Source: §2.3 · pp. 8–9

Network model

• Bayesian networks combine node-wise conditional channels into an end-to-end channel from a source node to any selected set of nodes.The network is a finite directed acyclic graph with one distinguished source and conditional distributions indexed by parent sets.Source: §3 · p. 9

Recursive contraction bound

• ηKL(PV,W|X) ≤ ηW·ηKL(PV,pa(W)|X) + (1−ηW)·ηKL(PV|X) provides the recursive step for peeling off a last node.The proof uses conditional mutual-information inequalities and the fact that the channel into W is a restriction of its parent channel.Source: §3 · pp. 9–10

Percolation interpretation

• If each node coefficient satisfies ηv < 1, then the network-level mutual-information coefficient ηKL(PV|X) is strictly below 1.The bound is interpreted through site percolation, where node v is retained with probability ηv and connectivity from X to V determines the upper bound.Source: §3 · pp. 9–10

Network estimates

• Theorem 5 enables contraction estimates for arbitrary finite networks by removing terminal nodes successively, with related path-based bounds compared in Table 1.The section also presents union-bound and shortcut-free-path estimates derived from the recursive theorem.Source: §3 · pp. 11–13

Parallel channels with feedback

• For an n-letter memoryless channel with perfect feedback, applying the single-letter bound n times yields an end-to-end contraction estimate.The result is stated as a corollary for repeated channel use with feedback.Source: §3 · p. 11

Evaluation for the BSC

• For BSC(δ)^n, the single-letter value ηKL=(1−2δ)^2 gives an n-letter upper bound, while repetition coding supplies a lower bound showing ηKL approaches 1 exponentially fast.The section compares these estimates and introduces an improvement needed to obtain the exact exponent.Source: §3 · pp. 12–13

Proof strategy

• The coupling proof supplies an exact counterpart to the mutual-information network theorem despite total variation lacking the mutual-information chain rule.The construction uses maximal couplings of conditional laws and preserves the required joint coupling properties.Source: §4 · pp. 13–14

Recursive contraction bound

• The total-variation recursion is ηTV(PV,W|X) ≤ (1−ηW)ηTV(PV|X)+ηWηTV(Ppa(W),V|X).Its proof constructs a coupling and bounds the probability that the outputs differ after adding W.Source: §4 · pp. 13–14

Percolation interpretation

• If every node coefficient is below one, then ηTV(PV|X) is also below one, with the resulting bound represented as site-percolation connectivity.Nodes are retained independently with probabilities ηv, and the probability of a surviving path from X to V bounds the network coefficient.Source: §4 · p. 13

Parallel channels with feedback

• For repeated single-letter channels with feedback, the total-variation coefficient obeys ηTV(PY^n|W) ≤ 1−(1−ηTV(PY|X))^n.The total-variation corollaries extend the corresponding mutual-information results with ηKL replaced by ηTV.Source: §4 · p. 14

Evaluation for the BSC

• For the n-letter BSC, sharp binomial-tail estimates should be compared with the recursive bound, which has the correct exponential convergence but a nonoptimal exponent.The limitation is stated for the bound obtained from the feedback-style corollary.Source: §4 · p. 15

• Theorem 11 bounds a Bayesian network’s FI-curve using constituent FI-curves and their concavified versions.Source: §5 · p. 15
• The network FI-curve estimate also implies the paper’s contraction-coefficient bounds, while the bound cannot generally be improved near zero.Source: §5 · pp. 15–16
• If every constituent channel has a nontrivial FI-curve, the composite channel also has a strict contractive FI-curve.Source: §5 · p. 15
• For n-letter BSCs with feedback, Corollary 12 applies the single-letter bound through iterated composition of ψ.Source: §5 · pp. 16–17
• The BSC bound is order-optimal because F(t) approaches t exponentially fast as n grows for fixed t.Source: §5 · p. 17

6 SDPI via comparison to erasure channels

• For a q-ary erasure channel, ηKL equals 1 − δ and FI(t) equals min((1 − δ)t, log q).Source: §6 · p. 18
• A channel’s KL contraction coefficient is equivalently characterized by being less noisy than an erasure channel with matching erasure probability.Source: §6 · p. 18
• Less-noisy ordering tensorizes, allowing channel comparisons and KL-contraction statements to extend across product channels.Source: §6 · p. 19

6.1 FI-curve of erasure channels

• The q-ary erasure-channel FI-curve is bounded by E[min(B log q, t)], with B distributed as Binom(n, 1 − δ).Source: §6.1 · pp. 19–20
• For n ≥ 3 in the binary case, FI(t) is nonconcave on (1, 2), while equality with its concavification holds for t ≤ log 2 or t ≥ (n − 1) log 2.Source: §6.1 · p. 20
• At t = 2 and n = 4, the erasure-channel upper bound is not tight because no [4, 2, 3] binary code exists.Source: §6.1 · pp. 20–21

6.2 Samorodnitsky’s SDPI

• Samorodnitsky’s SDPI bounds inferred information by subsets of inputs, informally restricting relevant information to subsets of size at most ηn.Source: §6.2 · pp. 21–22

• The construction preserves finite divergence and nonzero separation from the reference distribution under the required assumptions.Source: §A.1 · p. 23
• The proof handles general alphabets by approximating distributions so likelihood ratios remain bounded away from zero and infinity.Source: §A.1 · pp. 23–24
• A quadratic perturbation around the reference distribution yields the χ2-based lower bound for the f-divergence contraction coefficient.Source: §A.1 · p. 24

• The proof begins with ηKL ≥ ηχ2 and establishes the reverse direction through an integral representation of the relevant divergence.Source: §A.2 · p. 24
• For finite alphabets, concavity of the map PX ↦ Vr(PX, QX) at r = ηχ2 yields the desired global inequality.Source: §A.2 · p. 24

A.3 Proof of Theorem 4

• A non-degenerate input law is required so that conditional distributions supported on measurable subsets provide valid finite-divergence test measures.The construction uses a measurable set E with positive probability and an indicator-valued auxiliary variable.Source: §A.3 · p. 25
• The proof reduces the contraction-coefficient characterization to comparing divergence ratios through carefully constructed Markov chains U → X → Y.It uses conditional input distributions and a small-mixture argument to relate mutual information to relative divergence.Source: §A.3 · p. 25
• The argument first treats likelihood ratios bounded by a constant and then removes that assumption through truncation and convergence arguments.The proof invokes bounded convergence, lower semicontinuity, and dominated convergence to pass to the unrestricted case.Source: §A.3 · p. 25
• The constructed mixtures preserve the desired joint distribution while making the mutual-information comparison recover the corresponding divergence inequality.The output mixture is expressed through PY and the channel applied to the perturbed input law.Source: §A.3 · p. 25

A.4 Proof of Proposition 14

• The proof also handles singular measures and approximation details using binary divergence, absolute continuity, and convergence properties of divergence.These steps cover cases where direct density manipulations require additional care.Source: §A.4 · p. 26
• D(QY∥PY) ≤ D(QY′∥PY′) implies I(W;Y) ≤ I(W;Y′) for every auxiliary variable W generating the channel inputs.The implication follows by applying the divergence inequality conditionally on W and averaging.Source: §A.4 · p. 26
• Conversely, a binary auxiliary W mixing arbitrary PX and QX converts the assumed mutual-information ordering into a divergence comparison.The proof analyzes the small-mixture limit as the mixing probability tends to zero.Source: §A.4 · p. 27
• The lower bound I(W;Y) ≥ ǫD(QY∥PY) + o(ǫ) supplies the reverse implication after comparison with the corresponding expansion for Y′.This yields D(QY∥PY) ≤ D(QY′∥PY′), including finiteness of the latter divergence.Source: §A.4 · p. 27

B Contraction coefficients for binary-input channels

• The coefficient ηKL(PY|X) equals ηχ2(PY|X) and depends only on the two output laws P and Q induced by the binary inputs.It vanishes when P = Q and reaches one when P and Q are mutually singular.Source: B Contraction coefficients for… · p. 27
• Theorem 21 bounds this common coefficient through Hellinger-based quantities, making it essentially equivalent to Hellinger distance.The result is obtained by relating Hellinger and Le Cam divergences.Source: B Contraction coefficients for… · pp. 27–28
• The general total-variation upper bound is weaker, while for binary-valued outputs it holds with equality and the coefficient remains within a factor of two of Hellinger distance.The comparison distinguishes arbitrary outputs from the binary-output special case.Source: B Contraction coefficients for… · p. 27
• The proof identifies the χ2 coefficient through an input-dependent expression and then transfers the result to the input-independent KL coefficient.Cauchy–Schwarz supplies the key inequality used in the Hellinger comparison.Source: B Contraction coefficients for… · pp. 27–28

C Simultaneously maximal couplings

• A coupling exists satisfying π{(X,Y)≠(X′,Y′)} = dTV(PXY,QXY) and π{X≠X′} = dTV(PX,QX) simultaneously.The result follows by minimizing the sum of the two mismatch probabilities and observing that each term meets its individual lower bound.Source: C Simultaneously maximal couplings · pp. 28, 30
• The construction is non-constructive because it relies on Kantorovich’s dual representation, although the result was previously established in.The authors retain a proof different from.Source: C Simultaneously maximal couplings · p. 28
• A triply-optimal coupling that also maximizes the Y coupling need not exist, even when the marginal total-variation distances for X and Y are zero.The binary counterexample has X = Y under one law and X = 1 − Y under the other.Source: C Simultaneously maximal couplings · p. 28
• The proof reformulates the coupling problem as a bounded-cost Kantorovich optimization and solves its dual using constrained functions.The cost counts joint mismatches together with X mismatches.Source: C Simultaneously maximal couplings · pp. 28–29