From Permutations to Horizontal Visibility Patterns of Periodic Series ^†

Abstract

Periodic series of period T can be mapped into the set of permutations of $[T-1]=\{1,2,3,\dots ,T-1\}$. These permutations of period T can be classified according to the relative ordering of their elements by the horizontal visibility map. We prove that the number of horizontal visibility classes for each period T coincides with the number of triangulations of the polygon of $T+1$ vertices that, as is well known, is the Catalan number $C_{T-1}$. We also study the robustness against Gaussian noise of the permutation patterns for each period and show that there are periodic permutations that better resist the increase of the variance of the noise.

1. Introduction

Periodic or noisy periodic time series appear in many natural phenomena. Strictly speaking, real signals are approximately periodic and are considered to incorporate a certain seasonality [1,2]. They can also be solutions of dynamical systems, either discrete or continuous [3,4]. In practice, periodicity is finite, that is, it appears in a finite set of points. However, theoretically, these periodic series extend to infinity and, thus, they allow the consideration of the limit of infinite periods. This paper is focused on the study of the complete set of periodic natural series for each period $T\in \mathbb{N}$. Indeed, there are other classical approaches, such as, for instance, the Fourier analysis, that provide a complete set of solutions to this problem. However, our approach does not pretend to surpass them but, on the contrary, to offer an alternative viewpoint for studying this kind of time series.

A discrete series ${\left\{X_n\right\}}_{n\in \mathbb{N}}$, infinite or not, is said to be periodic if there is a natural number T such that $X_{n+T}=X_n$ for all $n>n_t$, that is, after a transient period $n_t$. For real valued series $X_n$, there are infinite periodic series for each period T (see Figure 1 for an example). However, this infinite number of cases can be reduced to a finite number by means of the application of discrete mappings, such as the horizontal visibility map [5]. It is worth pointing out that, for the horizontal visibility map, the time scale is not relevant, since only the values of any pair of points are compared. This means that the same horizontal visibility pattern is obtained if the time units are either seconds or years or, in the case of spatial series, either millimeters or kilometers.

2. Permutations of Periodic Series and Their Horizontal Visibility Patterns

A real valued periodic time series can be mapped into a positive integer series in which the elements within the period are ranked according to their value. For instance, as shown in Figure 1, a period 4 series with real values:

$\{\dots ,0.5008842,0.8749973,0.3828197,0.8269407,0.5008842,\dots \}$

obtained from the logistic equation, $X_n=r{X}_{n-1}(1-X_{n-1})$, $n=1,2\dots$, is mapped into the positive integer series: $\{\dots ,4,1,3,2,4,\dots \}$. Thus, any real valued time series can be transformed using this method. Let us assume that the largest value is fixed as the first value in each period. Then, if no equal values occur within the period, there are $(T-1)!$ possible permutations for the period T. Formally, given a periodic series of period T, we define its permutation pattern as the natural numbers that rank the values within the period, starting from the largest, that takes the value T. It is worth noting that all of these permutation patterns are effectively generated by applying the generic function Rank, a command that is defined in most programming languages.

All periodic patterns can be obtained as permutations of the set $\{T-1,T-2,\dots ,2,1\}$ and studied by applying combinatorial techniques [6,7]. In this context, the question is how these permutation patterns can be classified with regards to a definite order, for example, that turns out from the horizontal visibility map [5].

Two points of the series, $X_i$ and $X_j$ with $i<j$, are said to see each other horizontally if

$$X_i,X_j>X_k\forall i<k<j.$$

(1)

Since the horizontal visibility algorithm is only dependent on the relative values between the points of the integer series, it turns out that different permutation patterns could be classified within the same category. Indeed, the application of the horizontal visibility map enables a substantial reduction of the set of all permutation patterns.

In practice, for any permutation pattern, we can obtain the associated horizontal visibility pattern: for each value of the series, we calculate the ordinal of its horizontal visibility basin, that is, the number of points that are horizontally seen from the said value, for example, as shown in Figure 1, the horizontal visibility pattern of the permutation $\{4,1,3,2,(4\left)\right\}$ is $\{6,2,4,2,(6\left)\right\}$. This means that the largest value has six points in its visibility basin and the remaining points, 1,3,2 have two, four and two points, respectively, in their visibility basins.

In order to count the number of horizontal visibility patterns that exist for each permutation pattern of period T, it is convenient to represent the values of the period as a convex polygon of $T+1$ vertices. To each vertex of this polygon, we assign the corresponding value of the element of the series and read counterclockwise (see Figure 2). If we link the vertices forming the corresponding horizontal visibility graph, the projection of the edges forms a triangulation of the polygon. If we map each of the permutations into a polygon and compute their triangulation, we obtain all of the possible triangulations of these polygons of $T+1$ vertices. For example, Figure 3 depicts the six polygons that appear for period $T=4$. Please note that the label 4 appears twice, in order to close the period.

The triangulation of convex polygons is a classical problem and it is well known that, for a polygon of $T+1$ vertices, the number of possible triangulations is given by the Catalan number $C_{T-1}$:

$$C_{T-1}=\frac{(2T-2)!}{T!(T-1)!}.$$

This means that the infinite real valued series of period T can be reduced to $C_{T-1}$ horizontal visibility patterns. Nonetheless, even after this reduction, the number of horizontal visibility patterns increase exponentially with the period:

$$C_{T-1}\approx 0.021e^{1.269T}.$$

For example, for a period $T=20$, the number of possible horizontal visibility patterns rises to $1767263190\approx 1.8{10}^9$.

A property that can be immediately deduced from the polygon triangulations is that the total visibility, $V_{tot}\left(T\right)$, of any horizontal visibility pattern is the same for each period [8]: it is the sum of the edges that appear in the triangulated polygon multiplied by 2:

$$V_{tot}\left(T\right)=2(\#\mathit{edges})=4T-2.$$

It can also be proven that, for each period T, the maximum visibility that any permutation pattern can attain is $V_{max}\left(T\right)=T+2$. In addition, the other $T-3$ permutation patterns reach other maxima: $T+1,T,\dots$ (see

Table 2. Number of maximal visibilities for low period series.

T	# Max Visib	Max. Visibilities
2	1	4
3	1	5
4	2	(5,6)
5	3	(5,6,7)
6	4	(5,6,7,8)
7	5	(5,6,7,8,9)
8	6	(5,6,7,8,9,10)

). For instance, for $T=4$, there are four permutations with the largest visibility $V_{max}\left(4\right)=6$ and two permutation patterns with a maximum visibility of 5. Note that the maximum visibility might not occur for the largest value. For instance, the permutation pattern $\{6,5,1,2,3,4\}$ corresponds to the horizontal visibility pattern: $\{6,7,3,4,4,4\}$.

Another property that is worth mentioning is the average visibility of a point for each period, $\overline{V}$ [9]. It is obtained from the total visibility of each period divided by the period:

$$\overline{V}=\frac{V_{tot}\left(T\right)}{T}.$$

Evidently, it tends to four as T tends to infinity.

The correspondence between permutation patterns and horizontal visibility patterns is not evident, as shown in

Table 3. Each entry indicates the number of permutations for period T that corresponds to the number of visibility patterns. For instance, for period $T=5$, there are eight permutation patterns related one-to-one to one visibility pattern. The other two appear each from two permutations and four come from three different permutations (see Table 1). The sum of each row yields the total number of visibility patterns for each period. The total permutation patterns for each period are obtained from each row, multiplying the entry by the value of each column. For example, the sum of the entries of the second row, for $T=5$, gives the Catalan number $C_4=14$ and the weighted sum ($8·1+2·2+4·3$) equals the number of permutations $(T-1)!=4!=24$.

$\mathit{T}\backslash \#$	1	2	3	4	5	6	7	8	9	10	12	14	15	16	18	20
4	4	1
5	8	2	4
6	16	4	8	8		4		2
7	32	8	16	16	16	8		4		20			8			4
8	64	16	32	32	32	48		8		40	8		48	16		24
9	128	32	64	64	64	96	64	16		80	16	16	96	32		48
10	256	64	128	128	128	192	128	160		160	32	32	192	32	64	96
11	512	128	256	256	256	384	256	320	256	320	64	64	384	64	192	192

. Columns provide the relation between permutations and horizontal visibility pattens. The first column indicates the number of permutations that are related univocally to a visibility pattern for each period T (rows). Similarly, the entries of the second column provide the number of permutations that are related to two visibility patterns for each period T, and so on. This table forms a reduced schelon matrix with some internal patterns that deserve to be commented on briefly. The entries of the first column grow as $2^{T-2}$, whereas for the second column, they grow as $2^{T-4}$. For the first three rows, the number of columns with non null entries are 2, 3 and 6. Surprisingly, there are some columns, for example, 7 and 9, which appear for the first time at period $T=9$ and $T=11$, respectively. Unfortunately, the table is not complete, so no rigorous conclusions can be drawn for a larger order of columns and rows.

Table 1. The 6 and 24 permutation patterns for period $T=4$ and $T=5$. These patterns correspond to 5 and 14 different horizontal visibility patterns. The number of interior pinnacles [6] and their values are shown in the fourth and the fifth columns.

Period	Permutation Pattern	H. Visibility Pattern	# Pinnacle	Max.Pinnacle
4	4 1 2 3 (4)	6 2 3 3 (6)	0
4	4 1 3 2 (4)	6 2 4 2 (6)	1	3
4	4 2 1 3 (4)	5 3 2 4 (5)	0
4	4 2 3 1 (4)	6 2 4 2 (6)	1	3
4	4 3 1 2 (4)	5 4 2 3 (5)	0
4	4 3 2 1 (4)	6 3 3 2 (6)	0
5	5 1 2 3 4 (5)	7 2 3 3 3 (7)	0
5	5 1 2 4 3 (5)	7 2 3 4 2 (7)	1	4
5	5 1 4 2 3 (5)	6 2 5 2 3 (6)	1	4
5	5 4 1 2 3 (5)	5 5 2 3 3 (5)	0
5	5 4 1 3 2 (5)	6 4 2 4 2 (6)	1	3
5	5 1 4 3 2 (5)	7 2 4 3 2 (7)	1	4
5	5 1 3 4 2 (5)	7 2 3 4 2 (7)	1	4
5	5 1 3 2 4 (5)	6 2 4 2 4 (6)	1	3
5	5 3 1 2 4 (5)	5 4 2 3 4 (5)	0
5	5 3 1 4 2 (5)	6 3 2 5 2 (6)	1	4
5	5 3 4 1 2 (5)	6 2 5 2 3 (6)	1	4
5	5 4 3 1 2 (5)	6 3 4 2 3 (6)	0
5	5 4 3 2 1 (5)	7 3 3 3 2 (7)	0
5	5 3 4 2 1 (5)	7 2 4 3 2 (7)	1	4
5	5 3 2 4 1 (5)	6 3 2 5 2 (6)	1	4
5	5 3 2 1 4 (5)	5 3 3 2 5 (5)	0
5	5 2 3 1 4 (5)	6 2 4 2 4 (6)	1	3
5	5 2 3 4 1 (5)	7 2 3 4 2 (7)	1	4
5	5 2 4 3 1 (5)	7 2 4 3 2 (7)	1	4
5	5 4 2 3 1 (5)	6 4 2 4 2 (6)	1	3
5	5 4 2 1 3 (5)	5 4 3 2 4 (5)	0
5	5 2 4 1 3 (5)	6 2 5 2 3 (6)	1	4
5	5 2 1 4 3 (5)	6 3 2 5 2 (6)	1	4
5	5 2 1 3 4 (5)	6 3 2 4 3 (6)	0

also shows the number of maxima (pinnacles) in the permutation patterns [6,10]. For these two periods $T=\{4,5\}$, there are permutations that have no maximum, while others exhibit only one. The former permutations are related one-to-one to a horizontal visibility pattern. On the other hand, those permutations with one pinnacle can share the same horizontal visibility pattern. As a matter of fact, if the pinnacle takes the value of 3, for each horizontal visibility pattern there are two permutations, whereas if this value is 4, this correspondence is 3 to 1. Table 3 provides this equivalence for each period precisely.

3. Patterns of Noisy Periodic Series

As has been described in the previous section, for each period, more than one permutation is reduced to the same horizontal visibility pattern. The question is whether this equivalence remains when the signal is affected by any kind of noise, in particular Gaussian noise. It is expected that, when the intensity of the noise is small, the permutations of the noisy signal fall in the same visibility class as the non-perturbed time series and, consequently, all have the same horizontal visibility pattern. A similar problem has also been studied in [9]. Here, we focus on the problem of robustness against noise, for example, how Gaussian noise affects the permutation patterns as a function of the variance [11].

The way noisy series have been considered is detailed as follows:

(i) For each period T, we generate the $(T-1)!$ synthetic permutations.

(ii) From each of these patterns, a $1000*T$ series is generated.

(iii) To each of these series we add a random variable according to a normal distribution of null mean and standard deviation (specifically, the R-function $rnorm$ [12]).

(iv) We vary the standard deviation from 0 to 6, with increments of 0.1. Consequently, 61 noisy series are generated from the initial permutation.

(v) The visibility algorithm is applied for all of the 61 series, including the periodic synthetic series.

(vi) To compare the noisy series with the periodic one, we count the number of coincidences between each pair of noisy-periodic series.

Figure 4 depicts the proportion of digit coincidences between the horizontal visibility patterns obtained from the noisy permutations as a function of the variance of the Gaussian noise for low periods. The same plot for each of the visibility patterns for period $T=4$ is presented in Figure 4. The proportion of coincidences is greater in both permutations, corresponding to the same visibility pattern: $\{6,2,4,2\}$.

4. Concluding Remarks

Periodic or noisy periodic patterns appear in data sets from multiple fields of science [2]. In particular, a huge amount of data is formed by time series in which a unique variable, either discrete or continuous, is presented as a function of time that, indifferently, can also be considered discrete or continuous [3,4]. Many mathematical models also exhibit this oscillatory behavior and have been applied extensively to study its properties. Visibility algorithms are useful tools for the analysis of univariate series, for example, time series [13]. In particular, the horizontal visibility map provides analytical results about different types of series, namely periodic, random, fractional or chaotic [5]. Contrary to the natural visibility algorithm, the properties derived from the horizontal visibility map only depend on the ratio between the values of the points of the series, not on the distance between them. As shown in this paper, this enables a complete reduction of the infinite number of real valued periodic series to a finite set of visibility patterns. We prove that the number of horizontal visibility patterns for any period T is given by the Catalan number $C_{T-1}$. Despite this huge reduction, the number of horizontal visibility patterns still grows exponentially as a function of T.

This exponential growth contrasts with the low number of visibility patterns that are found in the logistic map [14]. This is a consequence of the form of the field, $f(x;r)=rx(1-x)$, which sets the following rules of period doubling bifurcations:

• If previous values are such that $x_1<x_2$, then the new duplicated values verify $x_{11},x_{12}<x_{21},x_{22}$.
• The new points coming from $x_1$ and $x_2$ must be intercalated in time.

For instance, if these rules are applied to each period in the Feigenbaum cascade, a sequence of horizontal visibility patterns appears that, at the limit of the infinite period, converge to the ruler sequence [14,15]. Other unknown integer patterns are to be discovered in each of the infinite period doubling cascades that occur in the bifurcation diagram of the logistic and, in general, in unimodal maps.

Lastly, we would like to point out that it is also possible to obtain an elementary periodic pattern that corresponds to a given horizontal visibility pattern. The algorithm seeks to find a periodic pattern with the minimum positive integers that are compatible with the horizontal visibility map. Starting from the initial pattern $\{1,1,1,1,1,1\}$, the program recurrently increases these values until the given horizontal visibility pattern is obtained. For example, for the horizontal visibility pattern $\{7,2,3,5,2,3,(7\left)\right\}$, associated with permutation: $\{6,1,3,5,2,4,(6\left)\right\}$, the elementary periodic pattern would be $\{4,1,2,3,1,2,(4\left)\right\}$. It is important to remark that this relationship is one-to-one, that is, it is the unique elementary pattern that yields the given horizontal visibility pattern.