Topological Entropy

Topological Entropy provides a quantification of the complexity of permutation types, in the sense of departure from monotonicity.

Developed in the field of combinatorics, topological entropy is a measure of the complexity of dynamical systems in the one-dimensional interval. It has value zero for a monotonous set of values, and value one (maximum) for a permutation were the difference between adjacent values is maximal. For example, for P = {1 2 3 4 5 6}, h(P) = 0 (minimal), while for R = {4 2 6 1 5 3}, absolute H(R) = 1.3170 (maximal).

One possible application of topological entropy is as a non-parametrical statistic for computing the distance between various rankings of the same set of items. For example, if the ideal ordering of some colored chips is from white to gray to black (that is monotonously increasing or decreasing), then placing the black chip next to the white is a less good ordering. The worst shuffling of the chips is given by the permutation R = {4 2 6 1 5 3} (and its isomorph reflection), where the local color contrast is as maximal as possible for all adjacent chips. Topological entropy provides a quantification of the permutations, with the extreme values corresponding to the best (monotonous) and worst (departure from monotonicity) sequence.

The method of n-minus-one-th order differencing results in the same permutation patterns as obtained for the minimal and maximal topological entropy. It is valid for even n only, but is a more straightforward solution to find patterns with maximal divergence from monotonicity than the topological entropy. Its rationale is to maximize differences between adjacent values. To compensate for the exponential growth induced by the binomial coefficient of differencing, we take the logarithm.