Abstract In this paper, we study random instances of the classical marginal problem. We encode the problem in a graph, where the vertices have assigned fixed binary probability distributions, and edges have assigned random bivariate distributions having the incident vertex distributions as marginals. We provide estimates on the probability that a joint distribution on the graph exists, having the bivariate edge distributions as marginals. Our study is motivated by Fine’s theorem in quantum mechanics. We study in great detail the graphs corresponding to CHSH and Bell–Wigner scenarios providing rations of volumes between the local and non-signaling polytopes.
Abstract In this paper, we study random instances of the classical marginal problem. We encode the problem in a graph, where the vertices have assigned fixed binary probability distributions, and edges have assigned random bivariate distributions having the incident vertex distributions as marginals. We provide estimates on the probability that a joint distribution on the graph exists, having the bivariate edge distributions as marginals. Our study is motivated by Fine’s theorem in quantum mechanics. We study in great detail the graphs corresponding to CHSH and Bell–Wigner scenarios providing rations of volumes between the local and non-signaling polytopes.
We study the problem of constructing a probability density in 2N-dimensional phase space which reproduces a given collection of n joint probability distributions as marginals. Only distributions authorized by quantum mechanics, i.e., depending on a (complete) commuting set of N variables, are considered. A diagrammatic or graph theoretic formulation of the problem is developed. We then exactly determine the set of “admissible” data, i.e., those types of data for which the problem always admits solutions. This is done in the case where the joint distributions originate from quantum mechanics as well as in the case where this constraint is not imposed. In particular, it is shown that a necessary (but not sufficient) condition for the existence of solutions is n⩽N+1. When the data are admissible and the quantum constraint is not imposed, the general solution for the phase space density is determined explicitly. For admissible data of a quantum origin, the general solution is given in certain (but not all) cases. In the remaining cases, only a subset of solutions is obtained.
Marginal distributions in (bf2N)-dimensional phase space and the quantum (bfN+1) marginal theorem
We study the problem of constructing a probability density in 2N-dimensional phase space which reproduces a given collection of n joint probability distributions as marginals. Only distributions authorized by quantum mechanics, i.e. depending on a (complete) commuting set of N variables, are considered. A diagrammatic or graph theoretic formulation of the problem is developed. We then exactly determine the set of ``admissible'' data, i.e. those types of data for which the problem always admits solutions. This is done in the case where the joint distributions originate from quantum mechanics as well as in the case where this constraint is not imposed. In particular, it is shown that a necessary (but not sufficient) condition for the existence of solutions is nleqN+1. When the data are admissible and the quantum constraint is not imposed, the general solution for the phase space density is determined explicitly. For admissible data of a quantum origin, the general solution is given in certain (but not all) cases. In the remaining cases, only a subset of solutions is obtained.
Quantum mass functions (QMFs), which are tightly related to decoherence functionals, were introduced by Loeliger and Vontobel [IEEE Trans. Inf. Theory, 2017, 2020] as a generalization of probability mass functions toward modeling quantum information processing setups in terms of factor graphs. Simple quantum mass functions (SQMFs) are a special class of QMFs that do not explicitly model classical random variables. Nevertheless, classical random variables appear implicitly in an SQMF if some marginals of the SQMF satisfy some conditions; variables of the SQMF corresponding to these “emerging” random variables are called classicable variables. Of particular interest are jointly classicable variables. In this paper we initiate the characterization of the set of marginals given by the collection of jointly classicable variables of a graphical model and compare them with other concepts associated with graphical models like the sets of realizable marginals and the local marginal polytope. In order to further characterize this set of marginals given by the collection of jointly classicable variables, we generalize the CHSH inequality based on the Pearson correlation coefficients, and thereby prove a conjecture proposed by Pozsgay et al. A crucial feature of this inequality is its nonlinearity, which poses difficulties in the proof.
Abstract Marginal problems naturally arise in a variety of different fields: basically, the question is whether some marginal/partial information is compatible with a joint probability distribution. To this aim, the characterization of marginal sets via quantifier elimination and polyhedral projection algorithms is of primal importance. In this work, before considering specific problems, we review polyhedral projection algorithms with focus on applications in information theory, and, alongside known algorithms, we also present a newly developed geometric algorithm which walks along the face lattice of the polyhedron in the projection space. One important application of this is in the field of quantum non-locality, where marginal problems arise in the computation of Bell inequalities. We apply the discussed algorithms to discover many tight entropic Bell inequalities of the tripartite Bell scenario as well as more complex networks arising in the field of causal inference. Finally, we analyze the usefulness of these inequalities as nonlocality witnesses by searching for violating quantum states.
Bell inequalities characterize the boundary of the local-realist correlation polytope -- the set of joint probability distributions achievable by classical hidden-variable models. Quantum mechanics exceeds this boundary through non-commutativity, reaching the Tsirelson bound 22 for CHSH. We show that this polytope structure is not specific to quantum foundations: it appears identically in the causal inference literature, where the instrumental inequality, the Balke--Pearl linear programming bounds, and the Tian--Pearl probabilities of causation all arise as facets of the same marginal compatibility polytope. Fine's theorem -- that CHSH inequalities hold if and only if a joint distribution exists -- is precisely the pivot: the instrumental variable model in causal inference is structurally equivalent to the Bell local hidden-variable model, with the instrument playing the role of the measurement setting and the latent confounder playing the role of the hidden variable λ. We develop this correspondence in detail, extending it to algorithmic (Kolmogorov complexity) and entropic formulations of Bell inequalities, the NPA semidefinite programming hierarchy, and the MIP∗=RE undecidability result. We further show that the Born-rule / Bayes-rule duality underlying quantum Bayesian computation exploits the same non-commutativity that enables Bell violation, providing polynomial speedups for posterior inference. The framework yields a concrete dictionary between quantum information theory, causal econometrics, and Bayesian computation, and suggests new directions including NPA-based quantum causal inference algorithms and quantum architectures for function approximation.
A marginal problem asks whether a given family of marginal distributions for some set of random variables arises from some joint distribution of these variables. Here, we point out that the existence of such a joint distribution imposes nontrivial conditions already on the level of Shannon entropies of the given marginals. These entropic inequalities are necessary (but not sufficient) criteria for the existence of a joint distribution. For every marginal problem, a list of such Shannon-type entropic inequalities can be calculated by Fourier-Motzkin elimination, and we offer a software interface to a Fourier-Motzkin solver for doing so. For the case that the hypergraph of given marginals is a cycle graph, we provide a complete analytic solution to the problem of classifying all relevant entropic inequalities, and use this result to bound the decay of correlations in stochastic processes. Furthermore, we show that Shannon-type inequalities for differential entropies are not relevant for continuous-variable marginal problems; non-Shannon-type inequalities are both in the discrete and in the continuous case. In contrast to other approaches, our general framework easily adapts to situations where one has additional (conditional) independence requirements on the joint distribution, as in the case of graphical models. We end with a list of open problems. A complementary article discusses applications to quantum nonlocality and contextuality.