Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Apologies in advance for poor terminology / description below; I'm trying my best but I do not know the correct wording.

Let's say a "sample" is some fixed number $n$ of boolean values (I'll use 1=true, 0=false):

1 0 0 0 1 0 0 1 1 1 1 1 0

Now I have a list of samples all of size $n$, and the order of items in the list is significant. So, for example, list A:

Sample 1:  0 1 1
Sample 2:  1 0 0
Sample 3:  0 0 1
Sample 4:  0 1 0
Sample 5:  1 0 1
Sample 6:  0 1 0
Sample 7:  1 0 0

Consider also this list, which is the same data as above but in a different order, call it list B:

Sample 1:  1 0 0
Sample 2:  1 0 0
Sample 3:  1 0 1
Sample 4:  0 0 1
Sample 5:  0 1 1
Sample 6:  0 1 0
Sample 7:  0 1 0

Both list A and list B have the same sets of samples, but the order of the samples in list B minimizes "vertical gaps" of 1's ("true" items).

My question is: Is there a word that expresses some quantification of how "grouped" individual elements across samples are for a given order of the list? Sorry if that was vague, but what I mean is, is there some word where I can say "List B has a higher/lower ______ than list A"?

Another way to state my question is, if I was given list A, and wanted to reorder it to get list B, I'm looking for a word that fits "Reordering list A such that the ______ is minimized/maximized gives list B."

From my understanding, the concept is not "entropy", as entropy is independent of order, and so the entropy of list A and list B is the same (if a given "sample" is a value of the variable that entropy is being calculated of). Unless there is some other type of entropy or entropy-like concept that is order-dependent (so XXXXYYYY has less of it than XYXYXYXY).

I'm looking for an actual statistics word / concept that I can search for (because I need to analyze this quality of various lists, somehow), not just descriptive English words like "List B is nicer looking than list A". I'm trying to research algorithms to quantify this but I am frustrated because I do not know what to Google for.

share|improve this question
    
I also don't know how to tag this because I do not know the right words; requesting tag improvement, please! –  Jason C Aug 6 at 23:29

2 Answers 2

You are looking for the entropy of a random variable describing 3 successive coin tosses. I am not sure in what context nicer is relevant but the link below should help

"http://en.wikipedia.org/wiki/Entropy_(information_theory)

share|improve this answer
    
Thanks; although I'm not sure this is quite the right concept. Entropy, at least Shannon entropy, is symmetric - independent of order; that is XYXYXYXY has the same entropy as XXXXYYYY. So both my list A and list B would have the same entropy by this model. –  Jason C Aug 7 at 2:40
    
(I am currently looking through Google results for "asymmetric entropy" although I haven't hit gold there yet.) –  Jason C Aug 7 at 2:47
    
ohh!! so both samples are just rearrangements?? I thought only for illustrations you used re-arrangements –  Sid Aug 7 at 3:13
    
Yes, sorry for explaining poorly. I'm trying to quantify this quality for two lists of the same set of samples that differ only in order - i.e. for different permutations of the same sample set. –  Jason C Aug 7 at 3:54

Define a similarity metric, $f$, between two rows. For each consecutive pairs of rows compute $f(row_i, row_j)$. Define an "ideal ordering" to be any member of the permutation of the list that minimizes the sum over $f$.

A reasonable starting point for $f$ is would be the sum of the squared mismatched positions, $$||row_i - row_j||^2 $$

$$Table_1=[3^2, 2^2, 2^2, 3^2, 3^2, 2^2]=39$$ $$Table_2=[0^2, 1^2, 1^2, 1^2, 1^2, 0^2]=4$$

share|improve this answer
    
If my lists contain every sample in the population, is it reasonable to let $p(x)$ be the observed relative frequency of $x$, and then $p(x,y)=p(x)p(y)$? –  Jason C Aug 7 at 5:53
    
... I guess not; because then $I(X,Y)$ would always be 0. –  Jason C Aug 7 at 6:27
1  
@Jason C I think I understand your problem better. See my edits. –  Jacob Mick Aug 7 at 12:11

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.