# Terminology for how "grouped" an ordered data set is

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.

• I also don't know how to tag this because I do not know the right words; requesting tag improvement, please! Aug 6, 2014 at 23:29

## 2 Answers

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$$

• 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)$? Aug 7, 2014 at 5:53
• ... I guess not; because then $I(X,Y)$ would always be 0. Aug 7, 2014 at 6:27
• @Jason C I think I understand your problem better. See my edits. Aug 7, 2014 at 12:11

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

• 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. Aug 7, 2014 at 2:40
• (I am currently looking through Google results for "asymmetric entropy" although I haven't hit gold there yet.) Aug 7, 2014 at 2:47
• ohh!! so both samples are just rearrangements?? I thought only for illustrations you used re-arrangements
– Sid
Aug 7, 2014 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. Aug 7, 2014 at 3:54