Introduction

In this paper we consider the problem of identifying rules, in the form of binary patterns, that are perfect, or in the worst case good, short-term predictors of complex binary sequences. A binary pattern of length L is defined as perfect short-term predictor if its presence in any place of the binary sequence is declarative of the value of the next bit. By definition, perfect predictors, enable the risk-free prediction of the next bit. Similarly, good short-term predictors, are binary patterns whose appearance in any position of the binary sequence renders the value of the next bit highly predictable.

Complex binary sequences are derived through the application of binary transformations on real-valued data sequences obtained from the tent map. The tent map is a piecewiselinear, continuous map on the unit interval [0, 1] into itself:

fr(x) =  rx, x ∈ [0, 1/2] r(1 − x), x ∈ (1/2, 1] ,(1)

where r is a control parameter that assumes values in the interval [0, 2]. We consider a discrete process generated by: xn+1 = fr(xn) = fr (fr (.

(n) r denotes the nth iterate of fr. The Lyapunov exponent is given by:

λr(x) = lim n→∞ 1 n ln ˛d dx f (n) r (x) ˛= ln r,

everywhere in [0, 1]. For r ∈ (0, 1), the orbit, f

r (x0), for any x0 ∈ [0, 1] converges to the unique fixed point 0, as n increases. For r = 1, every point x ∈ [0, 1/2] is a fixed point. The chaotic region is 1 < r 2, in which λr > 0 [5]. For r > 1 the map has two unstable fixed points, one at 0 and the other at x * (r) = r/(r + 1). Using the notation in [5], we write, xn(r) ≡ f , and m = 1, 2, . . .. By setting r0 = 2, then, for rm+1 < r < rm, there exist 2 m disjoint intervals Ai 1 ,i 2 ,...,im , i k = (0, 1) in which the invariant density is positive (the 2 m -band regime). Defining, l = 1+i1 + 2i2 +• • •+2 m−1 im, and J l ≡ Ai 1 ,i 2 ,...,im , it is shown in [5] that fr(J l ) = J l+1 for 1 l 2 m − 1, and fr(JM ) = J1, where M = 2 m . Therefore, if r lies in the interval `1, √ 2 ˜, fr maps a set of intervals between r − r 2 /2 and r/2 to themselves. If, on the other hand, r > √ 2 these intervals merge. This is illustrated in the bifurcation diagram of Fig. 1.

Real-world time series are frequently contaminated by noise. To this end, we investigate the resilience of the predictors to the presence of noise in the data generating process. We include an additive Gaussian noise term with zero mean, to Eq. ( 1), and study the extent to which the predictors detected in the original sequences retain their predictive power for different values of the variance of the distribution.

Methods

The tent map, described in Eq. (1), was employed to generate raw data sequences xn(x0, r). To generate the raw data from the tent map the GNU Multiple Precision Arithmetic Library (GMP) [1] was utilized to generate floating point numbers with precision of at least 5000 bits. Subsequently, binary data sequences bn(x0, r) were produced by applying the simple, threshold, binary transformation originally proposed for the logistic equation in [4]:

bn(x0, r) =  0, if xn 0.5, 1, if xn > 0.5.(3)

Eq. ( 3) produces a bit with value '1' when the value of the tent map is greater that 0.5 and a bit with value '0' otherwise. To avoid transient phenomena, the first 10 4 iterations of the map were discarded. A number of real-valued sequences xn(x0, r) were generated through Eq. ( 1) for different values of the control parameter, r, and starting points, x0. Binary sequences, bn(x0, r), of 10 6 bits were produced by applying Eq. (3) on the raw data, xn(x0, r).

A second binary transformation, also proposed in [4] for the logistic equation, was applied on the raw data. This transformation is also a simple, linear, threshold binary transformation, but with a variable threshold. The threshold value is the previous value of the raw data of the tent map. Hence, the second transformation is formulated as:

bn(x0, r) =  0, if xn xn−1, 1, if xn > xn−1.(4)

The number of all possible patterns of length L, 2 L , increases exponentially with respect to L. For large values of L, therefore, it is infeasible to perform exhaustive search, and more efficient search methods, such as Genetic Algorithms (GAs), are required [2,3]. To this end, a simple GA with binary representation was implemented and utilized. The GA population consisted of L-bit patterns. The fitness of a pattern p, was the number of times p was encountered in the binary sequence bn(x0, r). The selection process used was roulette wheel selection. As crossover operator the well-known one-point crossover operator was employed. Finally, the mutation operator utilized was the flip bit mutation operator . GAs were applied for several values of L and a number of binary sequences, bn(x0, r). Consequently, patterns that can account as perfect, or good, predictors can be identified by comparing the obtained results for L-bit and (L + 1)-bit patterns.

Presentation of Results

Fixed threshold

In the following, we present indicative results for binary sequences of length 10 6 , obtained by applying the transformation of Eq. (3). In Fig. 2 the distribution of bits with value '1' and '0' for different values of r is plotted. Evidently, an equal distribution of the two occurs only as r tends to 2. The number of distinct patterns of length L that appear for different values of r, is reported in Table 1. In detail, the first column of Table 1 reports the value of r; the second column indicates the length of the binary patterns L; the third column corresponds to the number of different patterns of length L identified in each binary sequence (#f); and finally the fourth column reports the ratio of the number of patterns of length L found (#f) to the number of possible binary patterns of this length (2 L ). The lower the ratio shown in the last column of the table the fewer the patterns that appear in the binary sequence and hence the higher the predictability.

An inspection of Table 1 suggests that increasing the value of r, gradually increases the number of patterns that are encountered for each value of L and hence degrades predictability. This effect becomes clear by comparing the results for r = 1.44 and r = 1.999. For r = 1.44 and L = 2, already the ratio of appearing to all possible patterns is 0.75 suggesting that one out of the four possible patterns is absent. This ratio decreases as L increases to reach 0.091 for L = 9 indicating that less than 10% of all possible patterns of this length are present in the sequence b 10 6 (0.1, 1.44). On the contrary, for r = 1.999 all possible patterns appear for all the different values of L up to and including L = 9. It should be noted that for r = 1.999 and L = 10 the ratio of column four becomes less than unity, but still its value is very close to that, 0.999, suggesting that even in this case increasing L reduces the ratio but this effect takes place very slowly.

Next, the impact of introducing noise to the data generating process is investigated. A normally distributed, ε ∼ N (0, σ 2 ), additive noise term was included in the tent map equation, yielding xn+1 = fr(xn) + ε, where fr(xn) is given by Eq. (1). It should be noted that we enforced the resulting raw data series to lie in the interval [0, 1] by rejecting realizations of the noise term that would result in xn+1 / ∈ [0, 1]. The obtained experimental results for the most predictable binary sequence when no noise is included, b 10 6 (0.1, 1.44), are summarised in Table 2. The first column of the table corresponds to the pattern length L; the second lists all the possible binary patterns of length L (due to space limitations, only patterns of length up to four are included); while columns three to six report the number of occurrences of each pattern for different values of the variance, σ 2 , starting with the case of no noise (σ 2 = 0). Starting from the case of no noise, we observe that more than three quarters of the binary sequence consists of bits with value '1'. Furthermore, from the patterns with length two, the pattern '00' is missing, indicating that a '0' is always followed by a '1'. This fact renders the unit length pattern '0' (and consequently all patterns of any length ending with a '0') a perfect predictor, and hence approximately 23% of the sequence is perfectly predictable. The inclusion of the additive noise term distorts these findings gradually as the variance increases. For σ 2 = 0.01 findings are marginally altered as the length two pattern '00' appears only 17 times in the length 10 6 binary sequence. Thus, the probability of a '1' following a bit with value '0' is 0.99993. For σ 2 = 0.1 and σ 2 = 0.5 this probability becomes 0.56109 and 0.44146 respectively. In the case of σ 2 = 0.5, therefore, the impact of noise is so large that the original finding is reversed and a '0' is more likely to be followed by a '0'. The fact that increasing the variance of the noise term deteriorates the predictability of the binary sequence is also evident from the fact that patterns that did not appear in the not contaminated with noise sequence, appear frequently in the contaminated series. The predictive power of the binary pattern '0' (perfect predictors in the noise-free binary sequence) with respect to the value of the variance of the additive noise term, σ 2 is illustrated in Fig. 3. To generate Fig. 3, σ 2 assumed values in the interval [0, 0.5] with stepsize 10 −3 . with respect to the variance σ 2 of the noise term.

Variable threshold

In this subsection we present results from the analysis of binary sequences derived by applying the transformation of Eq. ( 4), according to which the threshold is equal to the previous value of the tent map. The distribution of bits with value '1' and '0' for different values of the control parameter r is illustrated in Fig. 4. Comparing Figs. 2 and 4 it is evident that the two transformations yield substantially different distributions of ones and zeros. For the second transformation, the proportion of ones exceeds that of zeros for r marginally larger than 1. As shown in Fig. 4 the two proportions are equal until r becomes equal to √ 2. This finding is attributed to the band splitting phenomenon, briefly described in Section 1, that occurs for r ∈ (1,

√ 2] [5].

From that point and onward their difference increases.

The number of patterns of different length L that appear in the binary sequences of length 10 6 , are reported in Table 3 for different values of the control parameter r. More specifically, the first column of Table 3 reports the value of r; the second column corresponds to the length L of the binary patterns; the third column reports the number of different patterns of length L that were identified in the sequence (#f); and lastly, column four depicts the proportion of the patterns encountered (#f) to the number of possible binary patterns of length L (2 L ).

As in the case of the fixed threshold binary transformation, increasing the value of the control parameter r increases the number of patterns that appear in the derived binary sequences. However, this effect is more pronounced for the fixed threshold transformation of Eq. ( 3) than for the variable threshold transformation of Eq. ( 4). Even for r = 1.999, Table 3 reports that the number of binary patterns of length two is three, suggesting that one pattern of length two does not appear, and hence a unit length perfect binary predictor exists. In contrast, for the fixed threshold binary transformation, Table 1, all four length two binary patterns are present in the sequences that are generated with r 1.7. Moreover, the ratio of the patterns of length L found to the number of possible patterns of this length decreases more rapidly in the sequences generated by the variable threshold transformation. For instance, for r = 1.44, the number of patterns of length nine is 47 for the fixed threshold transformation, while for the variable threshold transformation this number is 10.

The impact of introducing noise on the short-term predictors is studied next. Table 4 reports the patterns of length two to four that were encountered in the binary sequence b 10 6 (0.1, 1.44) that was obtained through the second transformation, for different values of σ 2 . In detail, the first column of Table 4 corresponds to the length L of the patterns; the second column lists all possible binary patterns of this length; while columns three to six report the number of occurrences of each pattern in the binary sequences obtained for different values of the variance of the additive noise term ε ∼ N (0, σ 2 ). Note that as in the previous case, the resulting raw data sequence {xn} 10 6 n=0 was restrained in the interval [0, 1] by rejecting realizations of the noise term that would result in xn / ∈ [0, 1].

Starting from the case of no noise, we observe that zeros and ones are approximately equally distributed in the binary sequence. As in the case of the first transformation, pattern '00' is missing from the patterns of length two, a finding which implies that a '0' is always followed by a '1', and hence all the binary patterns of any length that end with '0' are perfect predictors. Furthermore, the pattern '111' was not encountered, implying that '11' is always followed by a '0'. From the inspection of the findings for patterns of length three we also obtain a good predictor of length two, namely the pattern '01', for which the probability of appearance of '0' immediately after this pattern is 0.96919. Comparing the aforementioned findings for the case of no noise, with the corresponding ones obtained by the first, fixed threshold, transformation we conclude that the binary sequence obtained through the variable threshold transformation is more predictable.

As expected, the introduction of noise eliminates all the perfect predictors identified in the original binary sequence. For a low value of the variance, σ 2 = 0.01, the findings are marginally distorted. The previously not encountered pattern '00' appears 5979 times yielding a probability of encountering a bit with the value '1' following a bit with a value of '0' equal to 0.987688. This probability is marginally lower than the corresponding probability for the first transformation. On the other hand, when the variance of the noise term increases to σ 2 = 0.1 and σ 2 = 0.5 this probability becomes 0.867348 and 0.698495, respectively. Both these probabilities are higher than the corresponding ones for the case of the transformation of Eq. (3). Moreover, note that for the case of the first transformation and σ 2 = 0.5 a bit with value '0' is more likely to be followed by a bit with the same value (probability equal to 0.55854); a phenomenon that does not occur at present. For the pattern '11' the probability of encountering a zero immediately after it becomes 0.933909, 0.628256, and 0.717049, for σ 2 equal to 0.01, 0.1, and 0.5, respectively. Finally, for the pattern '01' the probability of zero after its appearance is 0.932387, 0.538762, and 0.568140 for σ 2 equal to 0.01, 0.1, and 0.5, respectively. The predictive power of the binary patterns, '0', '11', (perfect predictors in the noise-free binary sequence) and '01' (good predictor in the noise-free binary sequence), with respect to the value of the variance of the additive noise term, σ 2 is illustrated in Fig. 5. To generate Fig. 5, σ 2 assumed values in the interval [0, 0.5] with a stepsize of 10 −3 .

Conclusions

Despite the chaotic nature of the tent map and the resulting complexity of the binary sequences that were derived after the application of two threshold, binary, transformations a large number of short-term predictors was detected. The reported experimental results indicate that the binary sequences generated through the variable threshold binary transformation are more predictable than those obtained through the fixed threshold transformation. This finding is clearer for values of the control parameter, r, close to its upper bound, 2. Indeed for r = 1.999 all the patterns of length up to nine appear in the binary sequences obtained through the first transformation, suggesting that there is no perfect predictor. On the contrary, for the sequences generated through the second transformation with the same value of r, only three out of the four possible patterns of length two are encountered, suggesting that there is a perfect short-term predictor of length one. The inclusion of an additive Gaussian noise term with zero mean in the tent map equation eliminated all perfect predictors. However, for small values of the variance of the Gaussian noise binary patterns with high predictive power were identified. Future work on the subject will include the investigation of multiplicative noise, as well as, the application of this methodology to real-world time series and in particular financial time series. It is worth noting that the second binary transformation is particularly meaningful in the study of financial time series as it corresponds to the direction of change of the next value relative to the present one.