Strong data-processing inequalities for channels and Bayesian networks

2015/08/25 by Yury Polyanskiy, Yihong Wu, Polyanskiy, Yury +1 · 8 citations
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Statistics Theory (math.ST) #cs.IT #math.IT #math.ST #stat.TH

paper · pdf · doi:10.48550/arxiv.1508.06025

openalex publication_date 2015/08/25 · arxiv created 2016/07/28 · arxiv updated 2016/08/01 · openalex created_date 2022/11/17 · openalex updated_date 2026/07/28

Abstract

The data-processing inequality, that is, I(U;Y) ≤ I(U;X) for a Markov chain U → X → Y, has been the method of choice for proving impossibility (converse) results in information theory and many other disciplines. Various channel-dependent improvements (called strong data-processing inequalities, or SDPIs) of this inequality have been proposed both classically and more recently. In this note we first survey known results relating various notions of contraction for a single channel. Then we consider the basic extension: given SDPI for each constituent channel in a Bayesian network, how to produce an end-to-end SDPI? Our approach is based on the (extract of the) Evans-Schulman method, which is demonstrated for three different kinds of SDPIs, namely, the usual Ahslwede-Gács type contraction coefficients (mutual information), Dobrushin's contraction coefficients (total variation), and finally the F_I-curve (the best possible non-linear SDPI for a given channel). Resulting bounds on the contraction coefficients are interpreted as probability of site percolation. As an example, we demonstrate how to obtain SDPI for an n-letter memoryless channel with feedback given an SDPI for n=1. Finally, we discuss a simple observation on the equivalence of a linear SDPI and comparison to an erasure channel (in the sense of "less noisy" order). This leads to a simple proof of a curious inequality of Samorodnitsky (2015), and sheds light on how information spreads in the subsets of inputs of a memoryless channel.

Cited by

• Bounds on Maximal Leakage over Bayesian Networks
• Credal Graph Neural Networks
• Assessing the Quality of Denoising Diffusion Models in Wasserstein Distance: Noisy Score and Optimal Bounds
• Renyi partial orders for BISO channels
• Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
• Observations Meet Actions: Learning Control-Sufficient Representations for Robust Policy Generalization
• Trade-offs in Data Memorization via Strong Data Processing Inequalities
• Partial orders and contraction for BISO channels

Related

• Strong Data Processing Inequalities and their Applications to Reliable Computation
• Strong Data Processing Inequalities for Input Constrained Additive Noise Channels
• Strong data processing constant is achieved by binary inputs
• Strong data processing inequalities and Φ-Sobolev inequalities for discrete channels
• Strong Converses using Typical Changes of Measures and Asymptotic Markov Chains