Entropy Inequalities: My Personal Journey.

Abstract: Shannon's information measures, namely entropy, mutual information, and their conditional versions, where each of them can be expressed as a linear combination of unconditional joint entropies. These measures are central in information theory, and constraints on these measures, in particular in the form of inequalities, are of fundamental interest. It is well-known that all Shannon's information measures are nonnegative, forming a set of inequalities on entropy. However, whether these are all the constraints on entropy was unknown, and the problem had been rather evasive until the introduction of the entropy function region in the late 1990s.

This talk consists of two part. The first part is about how I became interested in this subject in the late 1980s. It began with my PhD thesis in which I needed to use inequalities on Shannon's information measures (viz. information inequalities, or equivalently entropy inequalities) to prove converse coding theorems. During that time I was also intrigued by the underlying set-theoretic structure of Shannon's information measures, namely their representation by diagrams that resemble the Venn diagram. In 1991 I introduced the I-Measure to formally establish the one-to-one correspondence between set theory and Shannon's information measures. In the mid-1990s, I introduced the entropy function region Γ* that provides a geometrical interpretation of entropy inequalities. Shortly after, Zhen Zhang and I discovered so-called non-Shannon-type inequalities which are beyond the nonnegativity of Shannon's information measures. Since then this subject has been under active research

A byproduct of the entropy function region and the associated geometrical interpretation is the machine-proving of entropy inequalities. In the second part of this talk, I will discuss the research along this line, including some recent results.

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.