How do I go about calculating the entropy level of this algorithm?

I have a set of items. These items are (pseudo)randomly placed into buckets. The buckets are ordered and items placed in them are ordered. After all of the items are placed in buckets, the items are read back out of the buckets starting with the first item in the first bucket, then the second item in the first bucket, and so one until there are no more items in the bucket. Then the items are read from the second bucket and so on.

For example, I have three buckets, and the items a through e. a is inserted into bucket 2:

1   2   3
a


b into bucket 1

1   2   3
b   a


c into bucket 2

1   2   3
b   a
c


and so on until we have the following buckets

1   2   3
b   a   d
e   c
f


The items are then read out as the list b, e, a, c, f, d.

A naïve examination seems to say that items inserted first have a higher chance of being first and items inserted last have a higher chance of being inserted last. This makes me fairly certain that the list has less entropy than just shuffling the items with an algorithm like fisher-yates, but how do I calculate the difference in entropy?

-
You're right, it's not uniformly random: for instance, assuming that the number of buckets is less than the number of items, the descending permutation (like f e d c b a) has zero probability of being the final list. – ShreevatsaR Jul 14 '11 at 7:06
If your final list marks the buckets separately, e.g. you write it as be, acf, d, then each list corresponds to a unique map from the $n$ items to the $m$ buckets, so the entropy is easy to calculate: it's $\log n! \approx n\log n$ for the original case, versus $\log m^n = n\log m$ for your setup. But if you don't, then each list can correspond to multiple maps (e.g. a b c e f d may be either a, bcef, d or ab, cef, d or abc, ef, d) and the entropy is harder to calculate. It's definitely less than $n\log m$, though, as there are at most $m^n$ achievable permutations. – ShreevatsaR Jul 14 '11 at 10:43

1 Answer

I assume that the probability to choose a bucket is uniformly distributed. Then, to compute entropy, you enumerate (in your mind) all possible outcomes and count the resulting sequences. Some sequences will appear more than once, see below. These counts are plugged into the calculation of the entropy.

In your experiment, the crucial point is the number of 'steps back' in the resulting sequence. A 'step back' must come with a bucket change by design of your experiment. In your example, be|acf|d. there are two of those 'steps back', marked by |. Such an outcome is possible only with the given distribution of the letters into the buckets. As @ShreevatsaR pointed out, f|e|d|c|b|a is not possible at all. Why? Because the number of 'steps back' (5) is larger than the number of buckets, as a 'step back' can occur only when switching to the next bucket. In contrast, the sequence bef|acd appears much more often: We'd have to insert one imaginary 'step back' that is not taken but corresponds to a bucket change. We can choose among $(3 + 1) + ((3 + 1) - 1) = 7$ positions (inserting after f and before a is equivalent), and this number does not depend on the position of the real 'step back'. For the sequence abcdef, we have $\sum_{i=1}^7 i = \frac{7\cdot8}{2} = 28$ options to insert two |.

What remains is the calculation of the number of sequences with zero, one or two 'steps back'. Obviously, there is only one sequence with zero 'steps back'. For one step back, it is the number of partitions of a six-element set excluding those that would lead to a sorted sequence: $2^6 - 7 = 57$. For two steps back, this gets more complicated if you try to solve it directly this way. However, a solution can be obtained by recurring over the sample size $n$.

Let $B_i^n$ be the number of sequences of length $n$ with $i$ steps back. $B_0^n = 1$, and $B_n^n = 0$ for all $n$. We try to derive $B_i^n$ from $B_i^{n-1}$ and $B_{i-1}^{n-1}$. There are two ways to obtain a sequence of length $n$ with $i$ steps back: Adding the $n$-th element to a sequence with $i$ steps back 'in order', or adding it to a sequence with $i-1$ steps back 'out of order'. Using this experiment, for each sequence there is only one possible way to construct it, so uniformity is maintained.

In a sequence of length $n-1$ with exactly $i$ steps back, we have exactly $i+1$ positions where we don't add a step back by placing the $n$-th element: After each existing step back, and at the end. For $i-1$ steps back, this is $i$, and leaves $n-i$ choices to place the $n$-th element so that one more step back is added. That is, $$B_{i}^{n} = (i+1) \cdot B_{i}^{n-1} + (n-i)\cdot B_{i-1}^{n-1}.$$

We compute $B_1^6$:

$$B_1^6 = 2 \cdot B_1^5 + 5 \cdot B_0^5 = 2 \cdot 2 \cdot B_1^4 + 2 \cdot 4 \cdot B_0^4+5 = 8 \cdot B_1^3 + 12 \cdot B_3^0 + 13$$ $$= 16 \cdot B_1^2 + 16 \cdot B_0^5 + 25 = 32 \cdot B_1^1 + 16 \cdot B_0^1 + 41 = 57.$$

There are $B_2^6=302$ different sequences with two steps back.

From this, you should be able to compute the entropy. Please notify me if something needs clarification.

-