1
$\begingroup$

I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :)

Each integer is 6-digits, so representing such a list naively, let's say we'll allocate a fixed 20 bits per integer, stored in whichever order they happen to be present in, though again, order is irrelevant to the task at hand. For 1,000 integers, that's 1,000 * 20 bits, or 20kb. Baseline established.

Now for the Shannon entropy, we start with:

$$H(x) = -\sum_{i=1}^n{P(x_i) \log_2P(x_i)}$$

The total set of available integers is the set of all 6-digit integers, or 1,000,000, so $P(x = int)$ for any given choice of $int$ is $\frac{1}{1,000,000}$. Plug it in:

$$H(x) = -\sum_{i=1}^{1,000,000}{\frac{1}{1,000,000} \log_2\frac{1}{1,000,000}} = { \log_21,000,000} = 19.93 \ \textrm{bits}$$

We're back at 20 bits, given that $\log_2(\textrm{max_value})$ is how we got 20 bits in the first place. Of course, multiplying by 1,000, we get 20kb again.

This is provably not the true entropy of the list, because one fairly trivial compression scheme is to sort the list, then subtract each element from the next and encode the list as the first integer in the set and the differences between each integer and the one before it.

In that way, this:

$[123456, 192939, 201202, 203204, 500500]$

Becomes this, where the longer the list above, the denser the set, and the better the compression:

$[123456, 69483, 8263, 2002, 297296]$

If we can trivially compress down to smaller than the entropy, then that pretty clearly proves the calculated entropy is not actually the entropy.

If fact, given that all the differences are guaranteed to have a sum less than 1,000,000, otherwise our last value wouldn't fit in 6 digits, the differences between integers will be $\frac{1,000,000}{\textrm{num_integers}}$ on average, requiring $\log_2\frac{1,000,000}{\textrm{num_integers}}$ bits to store. This compression scheme will compress 1,000 integers down to $1,000 * \log_2\frac{1,000,000}{1,000} = 9.97 \ \textrm{kilobits}$, setting that as the upper bound on entropy.

Now that we've shown that applying Shannon's formula in the way I did does not give us the entropy of an unordered list, what does?

$\endgroup$
3
$\begingroup$

There are $\binom{10^6}{n}$ sets consisting of $n$ distinct 6-digit integers. If you choose such a set at random, then you get a random variable whose entropy is $\log_2 \binom{10^6}{n}$. This means that you can encode such a set using $\lceil \log_2 \binom{10^6}{n} \rceil$ many bits. You can obtain such an encoding using ranking/unranking of combinations, see for example this link.

$\endgroup$
5
  • $\begingroup$ This gives us 11.4 kilobits for 1,000 such integers, which is much closer, but still above that achieved by the compression with differences $\endgroup$ Sep 10 at 23:23
  • $\begingroup$ It’s optimal. It cannot be improved upon. $\endgroup$ Sep 10 at 23:24
  • $\begingroup$ Please, run the numbers yourself. Plug in $1,000$ for $n$, and use Stirling's algorithm or a similar approximation to find that the entropy this answer provides is higher than that in my toy compression algorithm in the question. I greatly appreciate your answer, and it makes a lot of sense, but it seems there's a mistake somewhere $\endgroup$ Sep 10 at 23:42
  • $\begingroup$ No need to run the numbers. You need $n$ bits to encode one of $2^n$ possibilities (or about one bit less if you allow variable length encoding). This is both in the worst case and on average (with some small loss). $\endgroup$ Sep 10 at 23:45
  • 1
    $\begingroup$ The difference is 1000 in average. Any individual difference can be much larger. You can’t encode “1000 on average” in 10 bits. $\endgroup$
    – gnasher729
    Sep 11 at 7:07
1
$\begingroup$

The problem with your first entropy argument is that you're counting each permutation separately, even though you don't care about preserving the order. In particular, every list of $1000$ distinct elements is counted $1000!$ times, so your entropy is too high by around $\frac{1}{1000}\log_2 1000! \approx 8.5$ bits per element.

The problem with your second argument is that it doesn't follow from the fact that the average value of the differences is $k$ that they can be stored in $\log_2 k$ bits. If the differences were equidistributed across the range 0-2000 then the average difference would be 1000, but they would require around 11 bits to store, not 10. The distribution is more likely to be Poisson than flat, but you'll still find that the best encoding uses more than 10 bits.

Yuval Filmus's counting is correct if the elements are all distinct. If duplicates are allowed then the count is slightly larger: $\binom{10^6+n-1}{n}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.