Entropic Inequalities and the Marginal Problem

Lin Zhang, Hongjin He, Yuan-hong Tao

Tobias Fritz, Rafael Chaves

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.

Huzihiro Araki, Élliott H. Lieb

Rafael Chaves, Lukas Luft, David Gross

Bell's theorem in physics, as well as causal discovery in machine learning, both face the problem of deciding whether observed data is compatible with a presumed causal relationship between the variables (for example, a local hidden variable model). Traditionally, Bell inequalities have been used to describe the restrictions imposed by causal structures on marginal distributions. However, some structures give rise to non-convex constraints on the accessible data, and it has recently been noted that linear inequalities on the observable entropies capture these situations more naturally. In this paper, we show the versatility of the entropic approach by greatly expanding the set of scenarios for which entropic constraints are known. For the first time, we treat Bell scenarios involving multiple parties and multiple observables per party. Going beyond the usual Bell setup, we exhibit inequalities for scenarios with extra conditional independence assumptions, as well as a limited amount of shared randomness between the parties. Many of our results are based on a geometric observation: Bell polytopes for two-outcome measurements can be naturally imbedded into the convex cone of attainable marginal entropies. Thus, any entropic inequality can be translated into one valid for probabilities. In some situations the converse also holds, which provides us with a rich source of candidate entropic inequalities.

Thomas Gläßle, D Gross, R Chaves

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.

Huzihiro Araki, Élliott H. Lieb