The Inflation Technique Completely Solves the Causal Compatibility Problem

Abstract

The causal compatibility question asks whether a given causal structure graph -- possibly involving latent variables -- constitutes a genuinely plausible causal explanation for a given probability distribution over the graph's observed variables. Algorithms predicated on merely necessary constraints for causal compatibility typically suffer from false negatives, i.e. they admit incompatible distributions as apparently compatible with the given graph. In [arXiv:1609.00672], one of us introduced the inflation technique for formulating useful relaxations of the causal compatibility problem in terms of linear programming. In this work, we develop a formal hierarchy of such causal compatibility relaxations. We prove that inflation is asymptotically tight, i.e., that the hierarchy converges to a zero-error test for causal compatibility. In this sense, the inflation technique fulfills a longstanding desideratum in the field of causal inference. We quantify the rate of convergence by showing that any distribution which passes the $n^{th}$-order inflation test must be $O\left(n^{-1/2}\right)$-close in Euclidean norm to some distribution genuinely compatible with the given causal structure. Furthermore, we show that for many causal structures, the (unrelaxed) causal compatibility problem is faithfully formulated already by either the first or second order inflation test.

Updated to match forthcoming journal publication as closely as possible. Some content removed for brevity. Expanded citations. Most footnotes moved into the main text. Significant changes to subsection 4.1, where we corrected an error in the example of second order inflation not converging, and added an converse example where second order inflation outperforms other techniques

References in corpus (21)

• Beyond Bell's Theorem: Correlation Scenarios
• Theory-independent limits on correlations from generalised Bayesian networks
• The Inflation Technique for Causal Inference with Latent Variables
• On the Testability of Causal Models with Latent and Instrumental Variables
• Maximal violation of n-locality inequalities in a star-shaped quantum network
• Causal Compatibility Inequalities Admitting Quantum Violations in the Triangle Structure
• Limits on correlations in networks for quantum and no-signaling resources
• Nested Markov Properties for Acyclic Directed Mixed Graphs
• Causal hierarchy of multipartite Bell nonlocality
• Pre- and Post-selection paradoxes and contextuality in quantum mechanics
• Correlations in star networks: from Bell inequalities to network inequalities
• Quantifier Elimination for Statistical Problems
• Quantum violations in the Instrumental scenario and their relations to the Bell scenario
• On the Testable Implications of Causal Models with Hidden Variables
• Analysing causal structures with entropy
• Inferring latent structures via information inequalities
• Which causal structures might support a quantum-classical gap?
• The entropic approach to causal correlations
• Semidefinite tests for latent causal structures
• Dimension Correction for Hierarchical Latent Class Models
• Inequality Constraints in Causal Models with Hidden Variables

Cited by in corpus (26)

• Bell nonlocality in networks
• Quantum Inflation: A General Approach to Quantum Causal Compatibility
• Semidefinite programming relaxations for quantum correlations
• Quantum nonlocality in networks can be demonstrated with an arbitrarily small level of independence between the sources
• Proofs of network quantum nonlocality in continuous families of distributions
• Test of Genuine Multipartite Nonlocality
• How quantum computing can enhance biomarker discovery
• Understanding the interplay of entanglement and nonlocality: motivating and developing a new branch of entanglement theory
• Any Physical Theory of Nature Must Be Boundlessly Multipartite Nonlocal
• Experimental nonclassicality in a causal network without assuming freedom of choice
• Inflation: a Python library for classical and quantum causal compatibility
• A convergent inflation hierarchy for quantum causal structures
• Covariance Decomposition as a Universal Limit on Correlations in Networks
• Analysing causal structures in generalised probabilistic theories
• The inflation hierarchy and the polarization hierarchy are complete for the quantum bilocal scenario
• Witnessing Non-Classicality in a Simple Causal Structure with Three Observable Variables
• Relating Wigner's Friend Scenarios to Nonclassical Causal Compatibility, Monogamy Relations, and Fine Tuning
• Two convergent NPA-like hierarchies for the quantum bilocal scenario
• Bipartite quantum states admitting a causal explanation
• Experimental genuine quantum nonlocality in the triangle network
• Symmetric observations without symmetric causal explanations
• Linear Program Witness for Network Nonlocality in Arbitrary Networks
• Monogamy relations for relativistically causal correlations
• Quantum interpretations, causality and quantum computation
• Fully quantum inflation: quantum marginal problem constraints in the service of causal inference
• Experimental verification of multi-copy activation of genuine multipartite entanglement