Communications in Information and Systems

Volume 2 (2002)

Number 2

A new class of non-Shannon-type inequalities for entropies

Pages: 147 – 166

DOI: http://dx.doi.org/10.4310/CIS.2002.v2.n2.a3

Authors

Konstantin Makarychev (Department of Mathematical Logic and Theory of Algorithms, Moscow State University, Moscow, Russia)

Yury Makarychev (Department of Mathematical Logic and Theory of Algorithms, Moscow State University, Moscow, Russia)

Andrei Romashchenko (Institute of Problems of Information Transmission, Moscow, Russia)

Nikolai Vereshchagin (Department of Mathematical Logic and Theory of Algorithms, Moscow State University, Moscow, Russia)

Abstract

In this paper we prove a countable set of non-Shannon-type linear information inequalities for entropies of discrete random variables, i.e., information inequalities which cannot be reduced to the “basic” inequality $I (X : Y | Z) \geq 0$. Our results generalize the inequalities of Z. Zhang and R. Yeung (1998) who found the first examples of non-Shannon-type information inequalities.

Full Text (PDF format)