Computing the entropy

Question

Input

A matrix M represented as two space separated lines of integers. Each line will have the same number of integers and each integer will be either -1 or 1. The number of integers per line will be at most 20. M will therefore be 2 by n where n is the number of integers on each of the two lines.

Your code should be a complete program. and accept the input either on standard in or from a file (that is your choice). You can accept input from standard in, from a file or simply as a parameter. However, if you do the latter please give an explicit example of how your code should work and remember that it must be a complete program and how the matrix M will be represented in the input. In other words, you are likely to have to do some parsing.

Output

The binary Shannon entropy of the distribution of M*x where the elements of x are uniformly and independently chosen from {-1,1}. x is an n-dimensional column vector.

The entropy of a discrete probability distribution is

- sum p_i log_2(p_i)

In this case, p_i is the probability of the ith unique possible M*x.

Example and helpful hints

As a worked example, let the matrix M be

-1 1
-1 -1

Now look at all 2^2 different possible vectors x. For each one we compute M*x and put all the results in an array (a 4-element array of 2-component vectors). Although for each of the 4 vectors the probability of it occurring is 1/2^2 = 1/4, we are only interested in the number of times each unique resultant vector M*x occurs, and so we sum up the individual probabilities of the configurations leading to the same unique vectors. In other words, the possible unique M*x vectors describe the outcomes of the distribution we're investigating, and we have to determine the probability of each of these outcomes (which will, by construction, always be an integer multiple of 1/2^2, or 1/2^n in general) to compute the entropy.

In the general n case, depending on M the possible outcomes of M*x can range from "all different" (in this case we have n values of i in p_i, and each p_i is equal to 1/2^n), to "all the same" (in this case there is a single possible outcome, and p_1 = 1).

Specifically, for the above 2x2 matrix M we can find by multiplying it with the four possible configurations ([+-1; +-1]), that each resulting vector is different. So in this case there are four outcomes, and consequently p_1 = p_2 = p_3 = p_4 = 1/2^2 = 1/4. Recalling that log_2(1/4) = -2 we have:

- sum p_i log_2(p_i) = -(4*(-2)/4) = 2

So the final output for this matrix is 2.

Test cases

Input:

-1 -1 
-1 -1

Output:

1.5

Input:

-1 -1 -1 -1
-1 -1 -1 -1

Output:

2.03063906223

Input:

-1  -1  -1  1
1  -1  -1  -1

Output:

3

Answer 1

Mathematica, 48 68 bytes

Edit: Preprocess is added for accepting string as the parameter.

With the help of Tuples and Entropy, the implementation is both concise and readable.

Entropy[2,{-1,1}~Tuples~Length@#.#]&@Thread@ImportString[#,"Table"]&

where Tuples[{-1,1},n] gives all possible n-tuples from {-1,1}, and Entropy[2,list] gives the base-2 information entropy.

One of the cool things is that Mathematica will actually return an accurate expression:

%["-1 -1 \n -1 -1"]
(* 3/2 *)

Approximate result can be achieved with an extra . added (Entropy[2., ...).

Answer 2

Perl, 160 159 141 bytes

includes +1 for -p since 141 byte update

@y=(@z=/\S+/g)x 2**@z;@{$.}=map{evals/.1/"+".$&*pop@y/egr}glob"{-1,+1}"x@z}{$H{$_.$2[$i++]}++for@1;$\-=$_*log($_/=1<<@z)/log 2 for values%H;

The input is expected on STDIN as 2 lines consisting of space-separated 1 or -1.
Run as perl -p 140.pl < inputfile.

It won't win any prizes, but I thought I'd share my effort.
Explained:

    @y=                             # @y is (@z) x (1<<$n)
       (@z = /\S+/g)                # construct a matrix row from non-WS
       x 2**@z;                     # repeat @z 2^$n times
    @{$.} = map {                   # $.=$INPUT_LINE_NUMBER: set @1 or @2
      eval s/.1/"+".$&*pop@y/egr    # multiply matrix row with vector
    } glob "{-1,+1}" x @z           # produce all possible vectors

}{                                  # `-p` trick: end `while(<>)`, reset `$_`

$H{ $_ . $2[$i++] }++               # count unique M*x columns
    for @1;

$\ -= $_ * log($_/=1<<@z) / log 2   # sum entropy distribution
        for values %H;

DATA

• update 159: save 1 by eliminating () by using ** instead of <<.
• update 141: save 18 by using $. and -p.

Answer 3

Pyth, 37 bytes

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8

Test suite

This is somewhat trickier when you have to manually implement matrix multiplication.

Explanation:

K^_B1lhJrR7.z_s*LldcRlKhMrSmms*VdkJK8
       JrR7.z                            Parse input into matrix, assign to J.
  _B1                                    [1, -1]
K^   lhJ                                 All +-1 vectors of length n, assign to K.
                           m       K     Map over K
                            m     J      Map over the rows of J
                             s*Vdk       Sum of vector product of vector and row.
                          S              Sort
                         r          8    Run length encode.
                       hM                Take just occurrence counts.
                   cRlK                  Divide by len(K) to get probabilities.
               *Lld                      Multiply each probabiliity by its log.
              s                          Sum.
             _                           Negate. Print implicitly.

Answer 4

MATLAB, 196 194 187 184 126 154 bytes

(The extra 28 bytes from 126 to 154 are due to input parsing: now the code accepts the input as two lines of whitespace-separated numbers.)

f=@()str2num(input('','s'));M=[f();f()];n=size(M,2);x=(dec2bin(0:n^2-1,n)-48.5)*2*M';[~,~,c]=unique(x,'rows');p=accumarray(c,1)/2^n;disp(-sum(p.*log2(p)))

Ungolfed version:

f=@()str2num(input('','s'));        % shorthand for "read a line as vector"
M=[f();f()];                        % read matrix
n=size(M,2);                        % get lenght of vectors

x=(dec2bin(0:n^2-1,n)-48.5)*2*M';   % generate every configuration
                                    %    using binary encoding
[~,~,c]=unique(x,'rows');           % get unique rows of (Mx)^T
p=accumarray(c,1)/2^n;              % count multiplicities and normalize
disp(-sum(p.*log2(p)))              % use definition of entropy

I could do away with 6 bytes if an "ans = ..." type of output was allowed, I'm never sure about this.

I'm sorry to say that my original and surely witty solution was way too ungolfed compared to my current solution. This is also the first time I'm using accumarray. A six-input-parameter application still has to wait, though:)

Outputs (following format long):

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
   1.500000000000000

[-1 -1 -1 -1
-1 -1 -1 -1]
   2.030639062229566

[-1  -1  -1  1
1  -1  -1  -1]
     3

Outputs with the default format short g:

[-1 1
-1 -1]
     2

[-1 -1
-1 -1]
          1.5

[-1 -1 -1 -1
-1 -1 -1 -1]
       2.0306

[-1  -1  -1  1
1  -1  -1  -1]
     3