logo

📂Dynamical Systems

A Measure of Time Series Complexity: Permutation Entropy

Definition1

Suppose a time series $\left\{ y_{t} \right\}_{t=1}^{T}$ is given. We consider vectors $\left( y_{t+1}, \cdots , y_{t+n} \right)$ formed by grouping $n$ consecutive time points, where $n$ is called the order, and there will be $T - n + 1$ such vectors in total. The ranking vector $\pi$, obtained by assigning the integers from $1$ to $n$ to the components of the vector according to their magnitude, can have exactly $n!$ types when counted as permutations. $p (\pi)$ is defined as the proportion of vectors belonging to type $\pi$, as follows. $$ p (\pi) := \frac{ \left| \left\{ t : \left( y_{t+1}, \cdots , y_{t+n} \right) \text{ is of type } \pi \right\} \right| }{T - n + 1} $$ Here $\left| \cdot \right|$ denotes the cardinality of a set. For $n$, the permutation entropy $H(n)$ is defined as follows. $$ H (n) := - \sum_{\pi} p (\pi) \log p (\pi) $$

Explanation

In fact, once one properly grasps what $\pi$ is in the definition, the definition of the entropy itself is identical to the Shannon entropy, so it is not difficult at all. The permutation entropy becomes $0$ when the time series is the simplest possible, for instance when it only increases or only decreases, and it will take large values for highly random cases such as chaos or Brownian motion.

On the other hand, even though $0 \le H(n) \le \log n!$, $H(n)$ may increase as $n$ grows regardless of the complexity. Thus, although $H$ is conceptually sufficient, one usually defines and uses the permutation entropy per symbol $h_{n}$ as follows. $$ h_{n} := \frac{H(n)}{n-1} $$

The following compares the bifurcation diagram of the logistic map drawn while varying the bifurcation parameter $r \in [3.5, 4]$, the corresponding Lyapunov exponent $\lambda$, and $h_{6}$ and $h_{12}$.

alt text

One can see that $h_{6}$ and $h_{12}$ show a shape almost similar to that of $\lambda$, with $h_{12}$ appearing more similar. Considering how drastically different the concepts and definitions of the Lyapunov exponent and the permutation entropy are, it is surprising that they are even this similar.

Of course, there is the difference that $\lambda$ clearly indicates whether the system is chaotic by comparing whether it is greater or less than $0$, whereas $h_{n}$ has no such clear reference point; nevertheless, one can at least guess where the periodic intervals are by the short line segments.


  1. Bandt, C., & Pompe, B. (2002). Permutation entropy: a natural complexity measure for time series. Physical review letters, 88(17), 174102. https://doi.org/10.1103/PhysRevLett.88.174102 http://materias.df.uba.ar/dnla2019c1/files/2019/03/permutation_entropy.pdf ↩︎