Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Considering a list of numbers $\{a_1,a_2,...,a_n\}$, after sorting the $n$ numbers in increasing order, how much the entropy changes?

Updated

Or we can understand the problem by using the number of bits to describe the list: For a sorted list in increasing order which is $\{a_1^', a_2^',...,a_n^'\}$, we can convert the list to d-gap list $\{a_1^', a_2^'-a_1^',...,a_n^'-a_{n-1}^'\}$, if we use fix-length code, we need $n \log (\max_i (a_i^'-a_{i-1}^'+1)$) bits, while if a list is in random order, we need $n \log (\max_i a_i+1)$ bits to describe it, which is more than that of d-gap list.

share|improve this question
    
I don't understand how the title and the body of your question fit together. In the title you're asking how to define the entropy; in the body you ask how much it changes. Those are two different questions, and the second one only makes sense if you have an answer to the first. –  joriki Sep 7 '11 at 8:55
    
@joriki I mean, after sorting the list, the uncertainty should be decreased, I want a measure how much the uncertainty decrease. –  Fan Zhang Sep 7 '11 at 9:04
    
Uncertainty about what? It sounds as if you have some statistical model in mind -- perhaps you could explicate that? Usually, the informational entropy of a set of numbers is defined as the entropy of the probability distribution given by the relative frequencies of the numbers. Since those don't change when you sort the list, it seems that can't be what you have in mind. –  joriki Sep 7 '11 at 9:12
    
@joriki If the list is sorted, we can get a gap list $\{a_1, a_2-a_1,...,a_n-a_{n-1}\}$, which we can use less bits to describe, so less uncertainty. Does it make sense? –  Fan Zhang Sep 7 '11 at 9:18
    
It might make sense; it's just not quite clear what you mean as long as you don't specify some model or something. For instance, the list could already be sorted, but if your model of it doesn't take that into account, you'll need lots of bits to describe it anyway. Then when you sort it and your model now takes into account that it's sorted, you can describe it with fewer (not "less", BTW) bits even though it hasn't changed. –  joriki Sep 7 '11 at 9:35

2 Answers 2

up vote 2 down vote accepted

I would argue that under any "natural" formulation of this problem (e.g., the numbers are drawn independently from the same probability distribution), the entropy should decrease by $\lg n!$.

share|improve this answer
    
I don't quite understand your point, can you explain more? –  Fan Zhang Sep 7 '11 at 15:31
1  
So you have a probability distribution on each number. The joint probability distribution is symmetric in all orderings. The probability distribution of the ordered list should have $\lg n!$ bits fewer entropy, because for any generic draw from your joint distribution, the $n!$ different orderings of that draw occur with equal probability. The ordered list picks one of those orderings specifically, thereby cutting down the sample space by a factor of $n!$ uniformly. This reduces the entropy by $\lg n!$. –  Craig Sep 7 '11 at 15:56
    
Assume your sample space is of size M, $M >> n$, and that we have the uniform distribution on the sample space. Then any given unordered draw occurs with probability $p = 1/M^n$ and there are $M^n$ such draws, and the entropy of the joint distribution is $H = -\sum p \lg p = n \lg M$. Now we order the draws. Each draw occurs with probability approximately $p' = n!/M^n$ and there are $~ M^n/n!$ such draws. The resulting entropy is $H - \lg n!$. –  Craig Sep 7 '11 at 16:00
    
We don't actually require that the probability distribution be uniform, we just require that the odds of any two $a_i$ being equal is vanishingly small. –  Craig Sep 7 '11 at 16:02

This should be a coment to Craig's answer. I agree that a decrease by $\log(n!)$ seems the right answer, almost obvious from the "information" point of view - but we don't have a proof yet.

Assuming we have $n$ iid random variables $x_i$, we know the joint entropy of $(x_1, x_2 \cdots x_n)$ is $n H(x)$. The question amounts to compute the joint entropy of the ordered variables $(y_1, y_2 \cdots y_n)$ , where $y_1 =x_{(1)}$ is the first order statistic , etc. This is in principle doable, but I don't see how a general result should be obtained.

To put an example: assume $x_i$ is uniform in $[0,M]$ (continuous variables are more tricky in regards to entropy interpretations, but here the math is a little simpler, and as long as we dont change scales, we are allowed to compare entropies; anyway, this also could be done with discrete variables). We have a join (differential) entropy of $H_0 = n \log(M)$ The ordered variable $y$ can equivalently be specifed by the differences $(z_1,z_2 ... z_n)$ where $z_i=y_i-y_{i-1}$. We know that, for large $n$, $z_i$ are asympotically independent, and exponential with mean $M/n$; the joint entropy then tends to $H_1 = n [1-\log(n/M)] \approx - n \log(n) + n \log(M)$. Then, the decrease of entropy that results from ordering is about $n \log(n) \approx \log(n!)$

share|improve this answer
    
@leonblog How to get $H_1=n[1-\log(n/m)]$ from $z_i$ being asympotically independent and exponential with mean $M/n$. –  Fan Zhang Sep 8 '11 at 3:53
    
@Fan Zhang: The entropy of an exponential rv is $1 - \log(\lambda)$ en.wikipedia.org/wiki/Exponential_distribution –  leonbloy Sep 8 '11 at 13:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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