Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/~anromash/ps/isit2011-slides.pdf Äàòà èçìåíåíèÿ: Wed Mar 21 14:44:40 2012 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 13:58:31 2012 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: èçó÷åíèå ëóíû

On Essentially Conditional Information Inequalities Tarik Kaced1 and Andrei Romashchenko
2 1 LIF de Marseille, Univ. Aix-Marseille CNRS, LIF de Marseille & IITP of RAS (Moscow)

2

ISIT 2011, August 4

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

1 / 15


Linear information inequalities

arik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

2 / 15


Linear information inequalities Basic inequalities: H (a, b) H (a) + H (b) [I (a : b) 0]

arik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

2 / 15


Linear information inequalities Basic inequalities: H (a, b) H (a) + H (b) [I (a : b) 0] H (a, b, c ) + H (c ) H (a, c ) + H (b, c ) [I (a : b | c ) 0]

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

2 / 15


Linear information inequalities Basic inequalities: H (a, b) H (a) + H (b) [I (a : b) 0] H (a, b, c ) + H (c ) H (a, c ) + H (b, c ) [I (a : b | c ) 0] Shannon typ e inequalities [combinations of basic ineq]: example 1: H (a) H (a | b) + H (a | c ) + I (b : c ) example 2: 2H (a, b, c ) H (a, b) + H (a, c ) + H (b, c )

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

2 / 15


Linear information inequalities General form: A linear information inequality is a combination of reals {i1 ,...,ik } such that i for all (a1 , . . . , an ).
1

,...,i

k

H (ai1 , . . . , aik ) 0

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

3 / 15


Linear information inequalities General form: A linear information inequality is a combination of reals {i1 ,...,ik } such that i for all (a1 , . . . , an ). Applications: multi-source network coding secret sharing combinatorial interpretations group theoretical interpretation Kolmogorov complexity ...
Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities ISIT 2011, August 4 3 / 15

1

,...,i

k

H (ai1 , . . . , aik ) 0


Shannon type information subadditivity H (A B submodularity H (A B C ) + H (C combinations of basic

inequalities: ) H (A) + H (B ), ) H (A C ) + H (B C ), inequalities

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

4 / 15


Shannon type information inequalities: subadditivity H (A B ) H (A) + H (B ), submodularity H (A B C ) + H (C ) H (A C ) + H (B C ), combinations of basic inequalities Th [Z. Zhang, R.W. Yeung 1998] There exists a non-Shannon type information inequality: I (c : d ) 2I (c : d | a) + I (c : d | b) + I (a : b) +I (a : c | d ) + I (a : d | c )

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

4 / 15


Theorem [Z. Zhang, R.W. Yeung 1997] There exists a conditional non Shannon type inequality: I (a : b) = I (a : b | c ) = 0 I (c : d ) I (c : d | a) + I (c : d | b)

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

5 / 15


Conditional information inequalities (a) Trivial, Shannon-typ e: if I (a : b) = 0 then H (c ) H (c | a) + H (c | b)

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

6 / 15


Conditional information inequalities (a) Trivial, Shannon-typ e: if I (a : b) = 0 then H (c ) H (c | a) + H (c | b) this is true since H (c ) H (c | a) + H (c | b)+I (a : b) [Shannon-type unconditional inequalitiy]

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

6 / 15


Conditional information inequalities (b) Trivial, non Shannon-typ e: if I (c : d | e ) = I (e : c | d ) = I (e : d | c ) = 0 then I (c : d ) I (c : d | a) + I (c : d | b) + I (a : b)

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

7 / 15


Conditional information inequalities (b) Trivial, non Shannon-typ e: if I (c : d | e ) = I (e : c | d ) = I (e : d | c ) = 0 then I (c : d ) I (c : d | a) + I (c : d | b) + I (a : b) this is true since I (c : d ) I (c : d | a) + I (c : d | b) + I (a : b) +I (c : d | e ) + I (e : c | d ) + I (e : d | c ) [non Shannon-type unconditional inequalitiy]

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

7 / 15


Conditional information inequalities (c) Non trivial, non Shannon-typ e: Zhang,Yeung 97: if I (a : b) = I (a : b | c ) = 0 then I (c : d ) I (c : d | a) + I (c : d | b)+I (a : b)

arik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

8 / 15


Conditional information inequalities (c) Non trivial, non Shannon-typ e: Zhang,Yeung 97: if I (a : b) = I (a : b | c ) = 0 then I (c : d ) I (c : d | a) + I (c : d | b)+I (a : b) F. Matu 99: if I (a : b | c ) = I (b : d | c ) = 0 then ´s I (c : d ) I (c : d | a) + I (c : d | b) + I (a : b)

arik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

8 / 15


Conditional information inequalities (c) Non trivial, non Shannon-typ e: Zhang,Yeung 97: if I (a : b) = I (a : b | c ) = 0 then I (c : d ) I (c : d | a) + I (c : d | b)+I (a : b) F. Matu 99: if I (a : b | c ) = I (b : d | c ) = 0 then ´s I (c : d ) I (c : d | a) + I (c : d | b) + I (a : b) our result: if H (c | a, b) = I (a : b | c ) = 0 then I (c : d ) I (c : d | a) + I (c : d | b) + I (a : b)

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

8 / 15


I (a : b ) = I (a : b |c ) = 0 [Zhang­Yeung 97]

I (a : b |c ) = I (b : d |c ) = 0 [Matu 99] ´s

H (c |a, b ) = I (a : b |c ) = 0 [this paper]


I (c : d ) I (c : d | a) + I (c : d | b ) + I (a : b )

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

9 / 15


I (a : b ) = I (a : b |c ) = 0 [Zhang­Yeung 97]

I (a : b |c ) = I (b : d |c ) = 0 [Matu 99] ´s

H (c |a, b ) = I (a : b |c ) = 0 [this paper]


I (c : d ) I (c : d | a) + I (c : d | b ) + I (a : b )

Main Theorem. These three statements are essentially conditional inequalities.

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

9 / 15


Main Theorem [the first case of three] The inequality I (a : b) = I (a : b|c ) = 0 I (c : d ) I (c : d |a)+I (c : d |b) is essentially conditional.

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

10 / 15


Main Theorem [the first case of three] The inequality I (a : b) = I (a : b|c ) = 0 I (c : d ) I (c : d |a)+I (c : d |b) is essentially conditional. More precisely, for all C1 , C2 the inequality I (c : d ) I (c : d | a)+I (c : d | b)+C1 I (a : b)+C2 I (a : b | c ) does not hold!

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

10 / 15


Main Theorem [the first case of three] The inequality I (a : b) = I (a : b|c ) = 0 I (c : d ) I (c : d |a)+I (c : d |b) is essentially conditional. More precisely, for all C1 , C2 there exist (a, b, c , d ) such that I (c : d ) I (c : d | a)+I (c : d | b)+C1 I (a : b)+C2 I (a : b | c )

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

11 / 15


Claim: For any C1 , C2 there exist (a, b, c , d ) such that I (c : d ) I (c : d | a)+I (c : d | b)+C1 I (a : b)+C2 I (a : b | c )

arik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

12 / 15


Claim: For any C1 , C2 there exist (a, b, c , d ) such that I (c : d ) I (c : d | a)+I (c : d | b)+C1 I (a : b)+C2 I (a : b | c ) Proof:
a 0 0 1 1 1 b 0 1 0 1 0 c 0 0 0 0 1 d 1 0 1 1 1 Prob[a, b , c , d ] (1 - )/4 (1 - )/4 (1 - )/4 (1 - )/4

arik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

12 / 15


Claim: For any C1 , C2 there exist (a, b, c , d ) such that I (c : d ) I (c : d | a)+I (c : d | b)+C1 I (a : b)+C2 I (a : b | c ) Proof:
a 0 0 1 1 1 b 0 1 0 1 0 c 0 0 0 0 1 d 1 0 1 1 1 Prob[a, b , c , d ] (1 - )/4 (1 - )/4 (1 - )/4 (1 - )/4 + I (c : d | b ) + C1 I (a : b ) + C2 I (a : b | c )

I (c : d ) I (c : d | a)

()

0

+

0

+

O (2 )

+

0

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

12 / 15


Remark on algorithmic entropy: Exactly the same classes of unconditional linear inequalities hold for Shannon's entropy and for Kolmogorov complexity.

arik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

13 / 15


Remark on algorithmic entropy: Exactly the same classes of unconditional linear inequalities hold for Shannon's entropy and for Kolmogorov complexity. Essentially conditional inequality [ZY97] is true for Shannon's entropy but not for Kolmogorov complexity (in some natural sense). See Proceedings for details.

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

13 / 15


Question 1: Can we apply essentially conditional inequalities (converse coding theorems, secret sharing problems, etc.)?

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

14 / 15


Question 1: Can we apply essentially conditional inequalities (converse coding theorems, secret sharing problems, etc.)? Question 2: May we apply essentially conditional inequalities in `real world' problems? These inequalities are not robust; do they make any `physical' sense?

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

14 / 15


Acknowledgments: We indebted to the anonymous referees for helpful comments; following their suggestions we changed the title, reworked the introduction, modified statements of theorems, the bibliography, ..., and even corrected several really essential things in our paper. Thank you! Any questions?

Tarik Kaced and Andrei Romashchenko (Marseille­Moscow) Essentially Conditional Inf Inequalities

ISIT 2011, August 4

15 / 15