Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1112.4788 · IEEE Transactions on Information Theory

Entropic Inequalities and Marginal Problems

Tobias Fritz, Rafael Chaves

Published Oct 22, 2012• 97 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2012.2222863

Related papers

Tests for quantum contextuality in terms of Q-entropies

Alexey E. Rastegin

The information-theoretic approach to Bell's theorem is developed with use of the conditional $q$-entropies. The $q$-entropic measures fulfill many similar properties to the standard Shannon entropy. In general, both the locality and noncontextuality notions are usually treated with use of the so-called marginal scenarios. These hypotheses lead to the existence of a joint probability distribution, which marginalizes to all particular ones. Assuming the existence of such a joint probability distribution, we derive the family of inequalities of Bell's type in terms of conditional $q$-entropies for all $q\geq1$. Quantum violations of the new inequalities are exemplified within the Clauser--Horne--Shimony--Holt (CHSH) and Klyachko--Can--Binicio\v{g}lu--Shumovsky (KCBS) scenarios. An extension to the case of $n$-cycle scenario is briefly mentioned. The new inequalities with conditional $q$-entropies allow to expand a class of probability distributions, for which the nonlocality or contextuality can be detected within entropic formulation. The $q$-entropic inequalities can also be useful in analyzing cases with detection inefficiencies. Using two models of such a kind, we consider some potential advantages of the $q$-entropic formulation.

arXiv:1210.6742•Quantum Information and Computation•Sep 1, 2014•18 citations

Non-Shannon inequalities in the entropy vector approach to causal structures

Mirjam Weilenmann, Roger Colbeck

A causal structure is a relationship between observed variables that in general restricts the possible correlations between them. This relationship can be mediated by unobserved systems, modelled by random variables in the classical case or joint quantum systems in the quantum case. One way to differentiate between the correlations realisable by two different causal structures is to use entropy vectors, i.e., vectors whose components correspond to the entropies of each subset of the observed variables. To date, the starting point for deriving entropic constraints within causal structures are the so-called Shannon inequalities (positivity of entropy, conditional entropy and conditional mutual information). In the present work we investigate what happens when non-Shannon entropic inequalities are included as well. We show that in general these lead to tighter outer approximations of the set of realisable entropy vectors and hence enable a sharper distinction of different causal structures. Since non-Shannon inequalities can only be applied amongst classical variables, it might be expected that their use enables an entropic distinction between classical and quantum causal structures. However, this remains an open question. We also introduce techniques for deriving inner approximations to the allowed sets of entropy vectors for a given causal structure. These are useful for proving tightness of outer approximations or for finding interesting regions of entropy space. We illustrate these techniques in several scenarios, including the triangle causal structure.

arXiv:1605.02078•Quantum•Mar 14, 2018•33 citations

Information Inequalities for Five Random Variables

László Csirmaz, Elod P. Csirmaz

The entropic region is formed by the collection of the Shannon entropies of all subvectors of finitely many jointly distributed discrete random variables. For four or more variables, the structure of the entropic region is mostly unknown. We utilize a variant of the Maximum Entropy Method to obtain five-variable non-Shannon entropy inequalities, which delimit the five-variable entropy region. This method adds copies of some of the random variables in generations. A significant reduction in computational complexity, achieved through theoretical considerations and by harnessing the inherent symmetries, allowed us to calculate all five-variable non-Shannon inequalities provided by the first nine generations. Based on the results, we define two infinite collections of such inequalities and prove them to be entropy inequalities. We investigate downward-closed subsets of non-negative lattice points that parameterize these collections, and based on this, we develop an algorithm to enumerate all extremal inequalities. The discovered set of entropy inequalities is conjectured to characterize the applied method completely.

arXiv:2512.23316•Computation•Feb 2, 2026•2 citations

Entropic inequalities as a necessary and sufficient condition to noncontextuality and locality

Rafael Chaves

The assumption of local realism, in a Bell locality scenario, imposes nontrivial conditions on the Shannon entropies of the associated probability distributions, expressed by linear entropic Bell inequalities. In principle, these entropic inequalities provide necessary but not sufficient criteria for the existence of a local hidden variable model reproducing the correlations, as, for example, the paradigmatic nonlocal Popescu-Rohrlich (PR) box is entropically not different from a classically correlated box. In this paper we show that for the $n$-cycle scenario, entropic inequalities completely characterize the set of local correlations. In particular, every nonsignaling box which violates the Clauser-Horne-Shimony-Holt (CHSH) inequality---including the PR box---can be locally modified so that it also violates the entropic version of CHSH inequality. As we show, any nonlocal probabilistic model when appropriately mixed with a local model, violates an entropic inequality, thus evidencing a very peculiar kind of nonlocality. As the $n$-cycle captures equally well both the notion of local realism introduced by Bell and that of noncontextuality presented by the Kochen-Specker theorem, the results are also valid for noncontextuality scenarios.

arXiv:1301.5714•Physical Review A•Feb 4, 2013•42 citations

Entropic approach to local realism and noncontextuality

Rafael Chaves, T. A. Fritz

For any Bell locality scenario (or Kochen-Specker noncontextuality scenario), the joint Shannon entropies of local (or noncontextual) models define a convex cone for which the nontrivial facets are tight entropic Bell (or contextuality) inequalities. In this paper we explore this entropic approach and derive tight entropic inequalities for various scenarios. One advantage of entropic inequalities is that they easily adapt to situations such as bilocality scenarios, which have additional independence requirements that are nonlinear on the level of probabilities, but linear on the level of entropies. Another advantage is that, despite the nonlinearity, taking detection inefficiencies into account turns out to be very simple. When joint measurements are conducted by a single detector only, the detector efficiency for witnessing quantum contextuality can be arbitrarily low.

arXiv:1201.3340•Physical Review A•Mar 12, 2012•106 citations

Causal structures from entropic information: geometry and novel scenarios

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.

arXiv:1310.0284•New Journal of Physics•Apr 3, 2014•65 citations
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.
The information-theoretic approach to Bell's theorem is developed with use of the conditional qqq-entropies. The qqq-entropic measures fulfill many similar properties to the standard Shannon entropy. In general, both the locality and noncontextuality notions are usually treated with use of the so-called marginal scenarios. These hypotheses lead to the existence of a joint probability distribution, which marginalizes to all particular ones. Assuming the existence of such a joint probability distribution, we derive the family of inequalities of Bell's type in terms of conditional qqq-entropies for all q≥1q\geq1q≥1. Quantum violations of the new inequalities are exemplified within the Clauser--Horne--Shimony--Holt (CHSH) and Klyachko--Can--Binicio\v{g}lu--Shumovsky (KCBS) scenarios. An extension to the case of nnn-cycle scenario is briefly mentioned. The new inequalities with conditional qqq-entropies allow to expand a class of probability distributions, for which the nonlocality or contextuality can be detected within entropic formulation. The qqq-entropic inequalities can also be useful in analyzing cases with detection inefficiencies. Using two models of such a kind, we consider some potential advantages of the qqq-entropic formulation.
A causal structure is a relationship between observed variables that in general restricts the possible correlations between them. This relationship can be mediated by unobserved systems, modelled by random variables in the classical case or joint quantum systems in the quantum case. One way to differentiate between the correlations realisable by two different causal structures is to use entropy vectors, i.e., vectors whose components correspond to the entropies of each subset of the observed variables. To date, the starting point for deriving entropic constraints within causal structures are the so-called Shannon inequalities (positivity of entropy, conditional entropy and conditional mutual information). In the present work we investigate what happens when non-Shannon entropic inequalities are included as well. We show that in general these lead to tighter outer approximations of the set of realisable entropy vectors and hence enable a sharper distinction of different causal structures. Since non-Shannon inequalities can only be applied amongst classical variables, it might be expected that their use enables an entropic distinction between classical and quantum causal structures. However, this remains an open question. We also introduce techniques for deriving inner approximations to the allowed sets of entropy vectors for a given causal structure. These are useful for proving tightness of outer approximations or for finding interesting regions of entropy space. We illustrate these techniques in several scenarios, including the triangle causal structure.
The entropic region is formed by the collection of the Shannon entropies of all subvectors of finitely many jointly distributed discrete random variables. For four or more variables, the structure of the entropic region is mostly unknown. We utilize a variant of the Maximum Entropy Method to obtain five-variable non-Shannon entropy inequalities, which delimit the five-variable entropy region. This method adds copies of some of the random variables in generations. A significant reduction in computational complexity, achieved through theoretical considerations and by harnessing the inherent symmetries, allowed us to calculate all five-variable non-Shannon inequalities provided by the first nine generations. Based on the results, we define two infinite collections of such inequalities and prove them to be entropy inequalities. We investigate downward-closed subsets of non-negative lattice points that parameterize these collections, and based on this, we develop an algorithm to enumerate all extremal inequalities. The discovered set of entropy inequalities is conjectured to characterize the applied method completely.
The assumption of local realism, in a Bell locality scenario, imposes nontrivial conditions on the Shannon entropies of the associated probability distributions, expressed by linear entropic Bell inequalities. In principle, these entropic inequalities provide necessary but not sufficient criteria for the existence of a local hidden variable model reproducing the correlations, as, for example, the paradigmatic nonlocal Popescu-Rohrlich (PR) box is entropically not different from a classically correlated box. In this paper we show that for the nnn-cycle scenario, entropic inequalities completely characterize the set of local correlations. In particular, every nonsignaling box which violates the Clauser-Horne-Shimony-Holt (CHSH) inequality---including the PR box---can be locally modified so that it also violates the entropic version of CHSH inequality. As we show, any nonlocal probabilistic model when appropriately mixed with a local model, violates an entropic inequality, thus evidencing a very peculiar kind of nonlocality. As the nnn-cycle captures equally well both the notion of local realism introduced by Bell and that of noncontextuality presented by the Kochen-Specker theorem, the results are also valid for noncontextuality scenarios.
For any Bell locality scenario (or Kochen-Specker noncontextuality scenario), the joint Shannon entropies of local (or noncontextual) models define a convex cone for which the nontrivial facets are tight entropic Bell (or contextuality) inequalities. In this paper we explore this entropic approach and derive tight entropic inequalities for various scenarios. One advantage of entropic inequalities is that they easily adapt to situations such as bilocality scenarios, which have additional independence requirements that are nonlinear on the level of probabilities, but linear on the level of entropies. Another advantage is that, despite the nonlinearity, taking detection inefficiencies into account turns out to be very simple. When joint measurements are conducted by a single detector only, the detector efficiency for witnessing quantum contextuality can be arbitrarily low.
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.