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.