Version 3.0
August 24, 2001

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

Email: w h y e u n g AT ie DOT cuhk DOT edu DOT hk
• Ying-On Yan was with School of Electrical Engineering, Cornell University, NY, USA.  He is now with The MathWorks, Inc.

Email: y y 2 6 AT cornell DOT edu

What is ITIP?

ITIP is a piece of software running on MATLAB for verifying linear information identities and inequalities (unconstrained and constrained) which can be proved by conventional techniques, namely those implied by the nonnegativity of Shannon's information measures. The theory is described in [2]. We also refer the readers to the tutorial paper [5].

We note that there exist information inequalities which cannot be proved by ITIP, for example, the recently discovered inequalities reported in [3] and [4].

ITIP is available for both Unix and the PC. If you have any comments on this software, please send them directly to the authors.

Installation

For Unix

For PC

How to use the program

ITIP('E1','E2','E3',...,'En') checks whether the information expression E1 is implied by the nonnegativity of Shannon's information measures, 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. EXP1 = 0
2. EXP1 = EXP2
3. EXP1 >= 0
4. EXP1 <= 0
5. EXP1 >= EXP2
6. EXP1 <= EXP2
where EXP1 and EXP2 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 [4]. 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. Blank spaces 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 inequality below is valid but it cannot be proved by ITIP [2].

>> 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 [1]. 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.

References

1. R. W. Yeung, "A new outlook on Shannon's information measures," IEEE Trans. Inform. Theory, vol. 37, pp. 466-474, May 1991.
2. R. W. Yeung, "A framework for linear information inequalities," IEEE Trans. Inform. Theory, vol. 43, pp. 1924-1934, Nov 1997.
3. Z. Zhang and R. W. Yeung, "A non-Shannon-type conditional inequality of information quantities," IEEE Trans. Inform. Theory, vol. 43, pp. 1982-1985, Nov 1997.
4. Z. Zhang and R. W. Yeung, "On characterization of entropy function via information inequalities," IEEE Trans. Inform. Theory, vol. 44, pp. 1440-1452, Jul 1998.
5. R. W. Yeung, "On entropy, information inequalities, and Groups."