Logo image
Back
Relationships among bounds for the region of entropic vectors in four variables
Conference proceeding

Relationships among bounds for the region of entropic vectors in four variables

J M Walsh and S Weber
2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp 1319-1326
Sep 2010
DOI: https://doi.org/10.1109/ALLERTON.2010.5707066

Abstract

Channel coding Classification algorithms Cramer-Rao bounds Entropy Joints Random variables Vectors
Extreme point representations are utilized together with facet membership to gain insights about the relationship between various bounds on the set of normalized entropic vectors in 4 random variables. Echoing prior results from Matúš (1995), we begin by showing that the 206 extreme points of the Shannon outer bound comprise 33 forms where 16 of these forms are entropic and achievable with binary random variables (one bit), 16 of the forms are entropic and achievable using two bits, and the remaining single form of six extreme points is not entropic, not achievable with two bits, and is the only violator of the Ingleton inequality. Thus, the Ingleton inner bound is matched to the Shannon outer bound in that it contains all entropic Shannon extreme points. Further novel investigation of the structure of the Ingleton and Shannon polytopes reveal that every facet of the Shannon outer bound requires two bits per variable and can be improved upon. The inner bound formed from the convex hull of the set of binary entropic vectors is shown to neither contain nor be contained in the Ingleton inner bound, and is shown to not be a polytope. The addition of the non-Shannon-type inequality due to Zhang and Yueng plus the six non-Shannon-type inequalities due to Dougherty, Freiling, and Zeger yield a polytopic outer bound where none of the non-Shannon extreme points obey Ingleton or are binary achievable. Worst case distance gaps between the various bounds are calculated.

Metrics

16 Record Views
7 citations in Scopus

Details

Logo image