LINC: Non-Shannon Type Information Inequalities

From LINC

Presentation

Presented by:	Jared Grubb
Purpose:	Student seminar series
Date:	2006-10-20
Location:	ENS 109

Abstract

In Information Theory, a fundamental fact we drilled into our minds is that for any n random variables, every possible way to write $I (y a d a; y a d a | y a d a)$ is non-negative. From this set of truths, other truths follow: $H(X) \ge 0$ , $H(A,B) \le H(A)+H(B)$ , etc. These are called Shannon-type Inequalities.

Question: Given any n random variables, are there any other true statements that CANNOT be derived from that basic set? In other words, are the equations $I( * ; * | * ) \ge 0$ a basis for the set of all true inequalities of n random variables?

The answer is no. The following inequality is the first non-Shannon-type information inequality discovered; it is true for any set of 4 random variables, but it cannot be proved using the $I(...) \ge 0$ facts in 4 variables:

$2I(C;D) \le I(A;B) + I(A;C,D) + 3 I(C;D | A) + I(C;D | B)$

How many true inequalities are there? What does this space look like? How can I possibly prove something that I just said cannot be proven? On Friday, bring your love of information theory and fascination for higher-dimension Euclidean spaces and find out.

Facts about Non-Shannon Type Information InequalitiesRDF feed

Written by	Jared Grubb +
Date	20 October 2006 +

Navigation

Search

From LINC

Presentation

Abstract