Recognizing predictive patterns in chaotic maps

Abstract

We investigate the existence of rules (in the form of binary patterns) that allow the short-term prediction of highly complex binary sequences. We also study the extent to which these rules retain their predictive power when the sequence is contaminated with noise. Complex binary sequences are derived by applying two binary transformations on realvalued sequences generated by the well known tent map. To identify short-term predictors we employ Genetic Algorithms. The dynamics of the tent map depend strongly on the value of the control parameter, r. The experimental results suggest that the same is true for the number of predictors. Despite the chaotic nature of the tent map and the complexity of the derived binary sequences, the results reported suggest that there exist settings in which an unexpectedly large number of predictive rules exists. Furthermore, rules that permit the risk free prediction of the value of the next bit are detected in a wide range of parameter settings. By incorporating noise in the data generating process, the rules that allow the risk free prediction of the next bit are eliminated. However, for small values of the variance of the Gaussian noise term there exist rules that retain much of their predictive power.

-

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 de ned 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 de nition, 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; r(1 x); xx 22 ([10;=12=;12]] ; ( 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 (: : :)) = fr(n+1)(x0); n = 0; 1; : : : ; |(n+1{)ztimes} ( 2 ) where fr(n) denotes the nth iterate of fr. The Lyapunov exponent is given by: r(x) = lim n!1 n 1

ln ddx fr(n)(x) = ln r; everywhere in [0; 1]. For r 2 (0; 1), the orbit, fr(n)(x0), for any x0 2 [0; 1] converges to the unique xed point 0, as n increases. For r = 1, every point x 2 [0; 1=2] is a xed point. The chaotic region is 1 < r 6 2, in which r > 0 [5]. For r > 1 the map has two unstable xed points, one at 0 and the other at x (r) = r=(r + 1). Using the notation in [5], we write, xn(r) fr(n)(1=2). Then x1(r) = r=2 and x2(r) = r(1 r=2). The intervals, (0; x2(r)) and (x1(r); 1) are transient for fr, and we have frA = A for A = [x2(r); x1(r)]. If r 2 p2; 2 , then A is an attractor. At r = p2, the attractor A splits into two bands, A0 and A1, at the position x = x (r). For r 2 1; p2 we have fr(A0) = A1 and fr(A1) = A0. Similarly, at r2 = p2, each of the two bands splits into two bands, Aij (i; j = 0; 1). In this manner, as r decreases, band splitting occurs successively at r = r1; r2; : : : ; rm; : : :, where rm = 21=2m , and m = 1; 2; : : :. By setting r0 = 2, then, for rm+1 < r < rm, there exist 2m disjoint intervals Ai1;i2;:::;im , ik = (0; 1) in which the invariant density is positive (the 2m-band regime). De ning, l = 1+i1 + 2i2 + +2m 1im, and Jl Ai1;i2;:::;im , it is shown in [5] that fr(Jl) = Jl+1 for 1 6 l 6 2m M = 2m. Therefore, if r lies in th1e, ianntedrvfarl(J1M; p)= J1, where 2 , fr maps a set of intervals between r r2=2 and r=2 to themselves. If, on the other hand, r > p2 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 di erent values of the variance of the distribution. 2

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 oating 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; 1; if xn 6 0:5; if xn > 0:5:

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 rst 104 iterations of the map were discarded. A number of real-valued sequences xn(x0; r) were generated through Eq. ( 1 ) for di erent values of the control parameter, r, and starting points, x0. Binary sequences, bn(x0; r), of 106 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; 1; if xn 6 xn 1; if xn > xn 1:

The number of all possible patterns of length L, 2L, increases exponentially with respect to L. For large values of L, therefore, it is infeasible to perform exhaustive search, and more e cient 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 tness 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 ip 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 identi ed by comparing the obtained results for L{bit and (L + 1){bit patterns. ( 3 ) ( 4 ) 3.1

Presentation of Results

Fixed threshold

In the following, we present indicative results for binary sequences of length 106, obtained by applying the transformation of Eq. ( 3 ). In Fig. 2 the distribution of bits with value `1' and `0' for di erent 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 di erent values of r, is reported in Table 1. In detail, the rst 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 di erent patterns of length L identi ed in each binary sequence (#f); and nally 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 (2L). 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 e ect 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 b106 (0:1; 1:44). On the contrary, for r = 1:999 all possible patterns appear for all the di erent 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 e ect takes place very slowly.

Next, the impact of introducing noise to the data generating process is investigated. A normally distributed, " s 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 2= [0; 1]. The obtained experimental results for the most predictable binary sequence when no noise is included, b106 (0:1; 1:44), are summarised in Table 2. The rst 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 di erent 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 ndings gradually as the variance increases. For 2 = 0:01 ndings are marginally altered as the length two pattern `00' appears only 17 times in the length 106 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 nding 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. 4 L 1 2 3 equal until r becomes equal to p2. This nding is attributed to the band splitting phenomenon, brie y described in Section 1, that occurs for r 2 (1; p2] [5]. From that point and onward their di erence increases.

The number of patterns of di erent length L that appear in the binary sequences of length 106, are reported in Table 3 for di erent values of the control parameter r. More speci cally, the rst 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 di erent patterns of length L that were identi ed 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 (2L).

As in the case of the xed 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 e ect is more pronounced for the xed 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 xed 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 xed 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 b106 (0:1; 1:44) that was obtained through the second transformation, for di erent values of 2. In detail, the rst 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 di erent values of the variance of the additive noise term " s N (0; 2). Note that as in the previous case, the resulting raw data sequence 106 fxngn=0 was restrained in the interval [0; 1] by rejecting realizations of the noise term that would result in xn 2= [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 rst transformation, pattern `00' is missing from the patterns of length two, a nding 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 ndings 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 ndings for the case of no noise, with the corresponding ones obtained by the rst, xed 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 identi ed in the original binary sequence. For a low value of the variance, 2 = 0:01, the ndings 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 rst 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 rst 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. 4

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 xed threshold transformation. This nding 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 rst 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 identi ed.

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 nancial time series. It is worth noting that the second binary transformation is particularly meaningful in the study of nancial time series as it corresponds to the direction of change of the next value relative to the present one.

Acknowledgments

This work was partially supported by the Hellenic Ministry of Education and the European Union under Research Program PYTHAGORAS-89203.

References

[1] Free Software Foundation Inc ., GNU Multiple Precision Arithmetic Library ver. 4.1.4.

[2] J. H. Holland , Adaptation in Natural and Arti cial Systems , University of Michigan Press, 1975 .

[3] M. Mitchell , Introduction to Genetic Algorithms, MIT Press, 1996 .

[4] N. G. Packard , ` A genetic learning algorithm for the analysis of complex data' , Complex Systems , 4 ( 5 ), 543 { 572 , ( 1990 ).

[5] T. Yoshida , H. Mori , and H. Shigematsu , ` Analytic study of chaos of the tent map: Band structures, power spectra, and critical behaviors' , Journal of Statistical Physics , 31 ( 2 ), 279 { 308 , ( 1983 ).