Permutation Complexity via Duality between Values and Orderings

Abstract

We study the permutation complexity of finite-state stationary stochastic processes based on a duality between values and orderings between values. First, we establish a duality between the set of all words of a fixed length and the set of all permutations of the same length. Second, on this basis, we give an elementary alternative proof of the equality between the permutation entropy rate and the entropy rate for a finite-state stationary stochastic processes first proved in [Amigo, J.M., Kennel, M. B., Kocarev, L., 2005. Physica D 210, 77-95]. Third, we show that further information on the relationship between the structure of values and the structure of orderings for finite-state stationary stochastic processes beyond the entropy rate can be obtained from the established duality. In particular, we prove that the permutation excess entropy is equal to the excess entropy, which is a measure of global correlation present in a stationary stochastic process, for finite-state stationary ergodic Markov processes.

26 pages

References in corpus (3)

• The Organization of Intrinsic Computation: Complexity-Entropy Diagrams and the Diversity of Natural Information Processing
• The number of permutations realized by a shift
• Permutation Excess Entropy and Mutual Information between the Past and Future

Cited by in corpus (7)

• Partial Transfer Entropy on Rank Vectors
• On the Relation of KS Entropy and Permutation Entropy
• Permutation complexity of interacting dynamical systems
• Measuring information transfer in a soft robotic arm
• Permutation Complexity and Coupling Measures in Hidden Markov Models
• Permutation Excess Entropy and Mutual Information between the Past and Future
• Entropic and algebraic transcript-based tools in time series analysis