Skip to Main content Skip to Navigation
Conference papers

On Essentially Conditional Information Inequalities

Tarik Kaced 1, * Andrei Romashchenko 1
* Corresponding author
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In 1997, Z. Zhang and R.W. Yeung found the first example of a conditional information inequality in four variables that is not "Shannon-type". This linear inequality for entropies is called conditional (or constraint) since it holds only under condition that some linear equations are satisfied for the involved entropies. Later, the same authors and other researchers discovered several unconditional information inequalities that do not follow from Shannon's inequalities for entropy. In this paper we prove that some non Shannon-type conditional inequalities are "essentially" conditional, i.e., they cannot be extended to any unconditional inequality. We prove one new essentially conditional information inequality for Shannon's entropy and discuss conditional information inequalities for Kolmogorov complexity.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736159
Contributor : Tarik Kaced <>
Submitted on : Tuesday, October 30, 2012 - 2:26:09 PM
Last modification on : Wednesday, May 13, 2020 - 3:02:09 PM
Long-term archiving on: : Thursday, January 31, 2013 - 2:30:10 AM

Files

isit2011-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Tarik Kaced, Andrei Romashchenko. On Essentially Conditional Information Inequalities. ISIT'11: International Symposium on Information Theory, Jul 2011, St. Petersburg, Russia. pp.1935-1939, ⟨10.1109/ISIT.2011.6033889⟩. ⟨lirmm-00736159⟩

Share

Metrics

Record views

289

Files downloads

650