Rewriting the Partial Order Permutation Entropy Using Partially Commutative Monoids

Andresso da Silva, Francisco M. Assis

DOI: 10.14209/sbrt.2025.1571157387

Evento: XLIII Simpósio Brasileiro de Telecomunicações e Processamento de Sinais (SBrT2025)

Keywords:

Abstract

Permutation entropy is a popular complexity measure for time series based on the distribution of ordinal patterns defined over a totally ordered alphabet. The extension to partially ordered alphabets, known as Partially Ordered Permutation Entropy (POPE), allows analysis of data where only a partial order between symbols exists, broadening the applicability of the method. However, the lack of a known formula to enumerate equivalence classes under partial order has prevented the definition of a normalized entropy in this setting. In this work, we reinterpret POPE through the algebraic framework of partially commutative monoids, which naturally model commutativity relations among symbols via a graph structure. This approach enables the explicit calculation of the number of equivalence classes (generalized ordinal patterns) of length $L$ as a function of the commutativity graph. Leveraging these results, we introduce a normalized version of the partially ordered permutation entropy, allowing for a meaningful complexity measure comparable across different systems.

Download