Version 3.0, Aug 24, 2001
(Press here to download the most updated version)

• Raymond W. Yeung is with Department of Information Engineering, The Chinese University of Hong Kong, N.T., Hong Kong, China.

Email:whyeung@ie.cuhk.edu.hk
• Ying-On Yan was with School of Electrical Engineering, Cornell University, NY, USA.  He is now with Aware, Inc.

Email:yy26@cornell.edu

What is ITIP?

ITIP is a piece of software running on MATLAB on Unix or PC for verifying Shannon-type inequalities.

Installation

For Unix

For PC

How to use the program

ITIP('E1','E2','E3',...,'En') checks whether the information expression E1 is a Shannon-type inequality under the equality constraints E2,E3,...,En. Note that there must be an "'" immediately before and after each expression.

Information expressions of the following forms are recognized:
 

1. E1 = 0
2. E1 = E2
3. E1 >= 0
4. E1 <= 0
5. E1 >= EXP2
6. E1 <= E2


where E1 and E2 are linear combinations of entropies, mutual informations, or their conditional versions. Moreover, the notation I(X1;X2;X3;...;Xn) for the mutual information between more than two random variables is accepted. At most 26 variables (A-Z) can be used.

To facilitate checking a large number of similar expressions, MATLAB variables whose names are in the lower-case alphabet can be used as coefficients. Blanks and commas in the expressions are ignored.

Examples:

H(XY)+2H(Z)-H(U)+I(X;Y|UZ)=0

0.8H(AZ)+I(A;ZY)>=3I(A;Y)-2.5H(Y|Z)

hello H(X) + world I(X;Y) <= fun H(X|Y)
 

Moreover, there are three types of macros for entering frequently used expressions:
 
1. R1/R2/R3/.../Rn means that R1,R2,R3,...,Rn form a Markov chain.
2. R1:R2 means that R1 is a function of R2, i.e., H(R1|R2)=0.
3. R1.R2.R3...Rn means that R1,R2,R3,...,Rn are mutually independent, i.e., H(R1,R2,...,Rn)=H(R1)+H(R2)+...+H(Rn).

Environment variables:

• ITIP_result: will be set to 1 if the expression is implied by the nonnegativity of Shannon's information measures, otherwise 0.
• ITIP_display: If it is non-zero, ITIP will display 'True' or 'Not provable by ITIP'.
• ITIP_optim: If it is non-zero, ITIP will treat random variables that always appear together as one random variable. This will speed up the proof.
• ITIP_parse: If it is non-zero, ITIP will only parse the inputs. No computation will be performed.


Remark: Before using these environment variables, they must be declared global in MATLAB's workspace.

Optional usage:

• [b,t,n]=ITIP(E1,E2,E3,...,En)
• [b,t,n,m]=ITIP(E1,E2,E3,...,En)


b, t, n and m are for diagnostic purposes and their values should be interpreted as follows:

n is a string of upper-case letters separated by blank spaces. They represent the random variables appearing in E1,E2,E3,...,En. If two or more letters are grouped together, it means that ITIP treated the corresponding random variables as one random variable.

b is a matrix whose elements are the coefficients of the joint entropies in the canonical form of the inputs. The column vectors represent E1,E2,E3,...,En sequentially. Note that two or more columns may be needed to represent a Markov chain. To determine which joint entropy the ith coefficient in a column corresponds to, we first find the binary representation of i. If the rth least significant bit is 1, the rth random variable shown in the string n is included in the joint entropy.

t is a column vector showing the type of expressions b represents. If the ith row of t is 1, the ith column of b represents an inequality.

m is the number of columns of b that are to be proved.

Examples:

>> ITIP('H(X)>=H(X|Y)')
True
>> ITIP('I(Y;ZA)>=I(X;U)','X/Y/ZA/U','X.Y.U')
True
>> ITIP('Z.U','X/Y/Z/U','X.Y.U')
Not provable by ITIP
>> ITIP('I(X;Y;Z)>=0')
Not provable by ITIP
>> ITIP('I(X;Y;Z)>=0','X/Y/Z')
True
>> hello = 2;
>> world = 0.5;
>> fun = -3;
>> ITIP('hello H(X) + world I(X;Z) <= fun H(XZ|Y)','X.Y.Z')
Not provable by ITIP
>> fun=100;
>> ITIP('hello H(X) + world I(X;Z) <= fun H(XZ|Y)','X.Y.Z')
True


In the above, those inequalities which are not provable by ITIP are actually invalid, as can be shown by examples. However, the non-Shannon-type inequality below is valid but it cannot be proved by ITIP.
 

>> ITIP('I(U;Z)<=I(U;Z|X)+I(U;Z|Y)','I(X;Y)=0','I(X;Y|Z)=0')
Not provable by ITIP


Nevertheless, only very few such inequalities are known so far. Therefore, if an inequality cannot be proved by ITIP, it is very likely to be invalid.

The files ITIP_kern.m and make_D.c are subroutines invoked by ITIP.m. ITIP_kern is not designed to be used directly, while make_D may be used to compute the matrix 'D' representing the elemental inequalities. The following commands will produce the matrix 'D' for n random variables.
 

>> [row,col,coef,nc,nr]=make_D(n);
>> D=full(sparse(row,col,coef,nc,nr));


Each row of D represents one elemental inequality. To determine which joint entropy the ith element corresponds to, we first find the binary representation of i. If the rth least significant bit is 1, the rth random variable is included in the joint entropy.