Given a fixed dependency graph G that describes a Bayesian network of binary variables X1,…,Xn, our main result is a tight bound on the mutual information Ic(Y1,…,Yk)=∑kj=1H(Yj)/c−H(Y1,…,Yk) of an observed subset Y1,…,Yk of the variables X1,…,Xn. Our bound depends on certain quantities that can be computed from the connective structure of the nodes in G. Thus it allows to discriminate between different dependency graphs for a probability distribution, as we show from numerical experiments.
The entropy region is a fundamental object of study in mathematics, statistics, and information theory. On the one hand, it involves pure group theory, governing inequalities satisfied by subgroup indices, whereas on the other hand, computing network coding capacities amounts to a convex optimization over this region. In the case of four random variables, the points in the region that satisfy the Ingleton inequality (corresponding to abelian groups and to linear network codes) form a well-understood polyhedron, and so attention has turned to Ingleton-violating points in the region. How far these points extend is measured by their Ingleton score, where points with positive score are Ingleton-violating. The Four-Atom Conjecture stated that the Ingleton score cannot exceed 0.089373, but this was disproved by Matúš and Csirmaz. In this paper we employ two methods to investigate Ingleton-violating points and thereby produce the currently largest known Ingleton scores. First, we obtain many Ingleton-violating examples from non-abelian groups. Factorizability appears in many of those and is used to propose a systematic way to produce more. Second, we rephrase the problem of maximizing Ingleton score as an optimization question and introduce a new Ingleton score function, which is a limit of Ingleton scores with maximum unchanged. We use group theory to exploit symmetry in these new Ingleton score functions and the relations between them. Our approach yields some large Ingleton scores and, using this methodology, we find that there are entropic points with score 0.09250007770, currently the largest known score., Nigel Boston and Ting-Ting Nan., and Obsahuje bibliografické odkazy