Symmetric Projections of the Entropy Region

Abstract

Entropy inequalities play a central role in proving converse coding theorems for network information theoretic problems. This thesis studies two new aspects of entropy inequalities. First, inequalities relating average joint entropies rather than entropies over individual subsets are studied. It is shown that the closures of the average entropy regions where the averages are over all subsets of the same size and all sliding windows of the same size respectively are identical, implying that averaging over sliding windows always suffices as far as unconstrained entropy inequalities are concerned. Second, the existence of non-Shannon type inequalities under partial symmetry is studied using the concepts of Shannon and non-Shannon groups. A complete classification of all permutation groups over four elements is established. With five random variables, it is shown that there are no non-Shannon type inequalities under cyclic symmetry.