=Paper=
{{Paper
|id=Vol-375/paper-9
|storemode=property
|title=Recognizing predictive patterns in chaotic maps
|pdfUrl=https://ceur-ws.org/Vol-375/paper8.pdf
|volume=Vol-375
}}
==Recognizing predictive patterns in chaotic maps==
https://ceur-ws.org/Vol-375/paper8.pdf
Recognizing predictive patterns in chaotic maps
Nicos G. Pavlidis1, Adam Adamopoulos2 and Michael N. Vrahatis3
Abstract. We investigate the existence of rules (in the form where r is a control parameter that assumes values in the
of binary patterns) that allow the short-term prediction of interval [0, 2]. We consider a discrete process generated by:
highly complex binary sequences. We also study the extent to
which these rules retain their predictive power when the se- xn+1 = fr (xn ) = fr (fr (. . .)) = fr(n+1) (x0 ), n = 0, 1, . . . ,
quence is contaminated with noise. Complex binary sequences
| {z }
(n+1) times
are derived by applying two binary transformations on real- (2)
valued sequences generated by the well known tent map. To (n)
where fr denotes the nth iterate of fr . The Lyapunov ex-
identify short-term predictors we employ Genetic Algorithms.
ponent is given by:
The dynamics of the tent map depend strongly on the value
of the control parameter, r. The experimental results suggest ˛
1 ˛˛ d (n) ˛˛
˛
that the same is true for the number of predictors. Despite λr (x) = lim ln ˛ fr (x)˛ = ln r,
n→∞ n dx
the chaotic nature of the tent map and the complexity of the
derived binary sequences, the results reported suggest that (n)
everywhere in [0, 1]. For r ∈ (0, 1), the orbit, fr (x0 ), for
there exist settings in which an unexpectedly large number
any x0 ∈ [0, 1] converges to the unique fixed point 0, as n
of predictive rules exists. Furthermore, rules that permit the
increases. For r = 1, every point x ∈ [0, 1/2] is a fixed point.
risk free prediction of the value of the next bit are detected in
The chaotic region is 1 < r 6 2, in which λr > 0 [5]. For
a wide range of parameter settings. By incorporating noise in
r > 1 the map has two unstable fixed points, one at 0 and the
the data generating process, the rules that allow the risk free
other at x∗ (r) = r/(r + 1). Using the notation in [5], we write,
prediction of the next bit are eliminated. However, for small (n)
xn (r) ≡ fr (1/2). Then x1 (r) = r/2 and x2 (r) = r(1−r/2).
values of the variance of the Gaussian noise term there exist
The intervals, (0, x2 (r)) and (x1 (r), 1) are transient `√for f˜r , and
rules that retain much of their predictive power.
we have fr A = A for A = [x2 (r), x1 (r)]. If r ∈ 2, 2 , then
√
A is an attractor. At r = 2, the attractor A splits into ` √ two˜
1 Introduction bands, A0 and A1 , at the position x = x∗ (r). For r ∈ 1, 2
√
we have fr (A0 ) = A1 and fr (A1 ) = A0 . Similarly, at r2 = 2,
In this paper we consider the problem of identifying rules, in each of the two bands splits into two bands, Aij (i, j = 0, 1). In
the form of binary patterns, that are perfect, or in the worst this manner, as r decreases, band splitting occurs successively
m
case good, short-term predictors of complex binary sequences. at r = r1 , r2 , . . . , rm , . . ., where rm = 21/2 , and m = 1, 2, . . ..
A binary pattern of length L is defined as perfect short-term By setting r0 = 2, then, for rm+1 < r < rm , there exist 2m
predictor if its presence in any place of the binary sequence is disjoint intervals Ai1 ,i2 ,...,im , ik = (0, 1) in which the invariant
declarative of the value of the next bit. By definition, perfect density is positive (the 2m -band regime). Defining, l = 1+i1 +
predictors, enable the risk-free prediction of the next bit. Sim- 2i2 +· · ·+2m−1 im , and Jl ≡ Ai1 ,i2 ,...,im , it is shown in [5] that
ilarly, good short-term predictors, are binary patterns whose fr (Jl ) = Jl+1 for 1 6 l 6 2m − 1, and fr (J ) = ˜J1 , where
`M √
appearance in any position of the binary sequence renders the M = 2m . Therefore, if r lies in the interval 1, 2 , fr maps
value of the next bit highly predictable. a set of intervals between √ r − r2 /2 and r/2 to themselves.
Complex binary sequences are derived through the applica- If, on the other hand, r > 2 these intervals merge. This is
tion of binary transformations on real–valued data sequences illustrated in the bifurcation diagram of Fig. 1.
obtained from the tent map. The tent map is a piecewise- Real-world time series are frequently contaminated by
linear, continuous map on the unit interval [0, 1] into itself: noise. To this end, we investigate the resilience of the predic-
tors to the presence of noise in the data generating process.
rx, x ∈ [0, 1/2] We include an additive Gaussian noise term with zero mean,
fr (x) = , (1)
r(1 − x), x ∈ (1/2, 1] to Eq. (1), and study the extent to which the predictors de-
tected in the original sequences retain their predictive power
1 Institute for Mathematical Sciences, Imperial College London, for different values of the variance of the distribution.
South Kensington Campus, London SW7 2AZ, United Kingdom,
email: n.pavlidis@imperial.ac.uk
2 Medical Physics Laboratory, Department of Medicine, Democri-
tus University of Thrace, Alexandroupolis GR-68100, Greece,
2 Methods
email: adam@med.duth.gr
3 Department of Mathematics, University of Patras, Patras GR- The tent map, described in Eq. (1), was employed to gener-
26110, Greece, email:vrahatis@math.upatras.gr ate raw data sequences xn (x0 , r). To generate the raw data
43
3 Presentation of Results
3.1 Fixed threshold
In the following, we present indicative results for binary se-
quences of length 106 , obtained by applying the transforma-
tion 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.
Figure 1. Bifurcation diagram of the steady states of the tent
map with respect to r.
from the tent map the GNU Multiple Precision Arithmetic Li-
brary (GMP) [1] was utilized to generate floating point num-
bers with precision of at least 5000 bits. Subsequently, binary
data sequences bn (x0 , r) were produced by applying the sim-
ple, threshold, binary transformation originally proposed for
the logistic equation in [4]: Figure 2. Distribution of ones (dashed) and zeros (solid)
according to the transformation of Eq. (3) for bn (0.1, r) and
r ∈ [1, 2] with stepsize 10−3 .
0, if xn 6 0.5,
bn (x0 , r) = (3)
1, if xn > 0.5.
Eq. (3) produces a bit with value ‘1’ when the value of The number of distinct patterns of length L that appear for
the tent map is greater that 0.5 and a bit with value ‘0’ different values of r, is reported in Table 1. In detail, the first
otherwise. To avoid transient phenomena, the first 104 iter- column of Table 1 reports the value of r; the second column
ations of the map were discarded. A number of real-valued indicates the length of the binary patterns L; the third column
sequences xn (x0 , r) were generated through Eq. (1) for differ- corresponds to the number of different patterns of length L
ent values of the control parameter, r, and starting points, x0 . identified in each binary sequence (#f); and finally the fourth
Binary sequences, bn (x0 , r), of 106 bits were produced by ap- column reports the ratio of the number of patterns of length L
plying Eq. (3) on the raw data, xn (x0 , r). found (#f) to the number of possible binary patterns of this
A second binary transformation, also proposed in [4] for the length (2L ). The lower the ratio shown in the last column of
logistic equation, was applied on the raw data. This transfor- the table the fewer the patterns that appear in the binary
mation is also a simple, linear, threshold binary transforma- sequence and hence the higher the predictability.
tion, but with a variable threshold. The threshold value is the An inspection of Table 1 suggests that increasing the value
previous value of the raw data of the tent map. Hence, the of r, gradually increases the number of patterns that are en-
second transformation is formulated as: countered for each value of L and hence degrades predictabil-
ity. 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
0, if xn 6 xn−1 ,
bn (x0 , r) = (4) ratio of appearing to all possible patterns is 0.75 suggesting
1, if xn > xn−1 .
that one out of the four possible patterns is absent. This ratio
The number of all possible patterns of length L, 2L , in- decreases as L increases to reach 0.091 for L = 9 indicating
creases exponentially with respect to L. For large values of L, that less than 10% of all possible patterns of this length are
therefore, it is infeasible to perform exhaustive search, and present in the sequence b106 (0.1, 1.44). On the contrary, for
more efficient search methods, such as Genetic Algorithms r = 1.999 all possible patterns appear for all the different val-
(GAs), are required [2, 3]. To this end, a simple GA with bi- ues of L up to and including L = 9. It should be noted that
nary representation was implemented and utilized. The GA for r = 1.999 and L = 10 the ratio of column four becomes
population consisted of L–bit patterns. The fitness of a pat- less than unity, but still its value is very close to that, 0.999,
tern p, was the number of times p was encountered in the suggesting that even in this case increasing L reduces the ratio
binary sequence bn (x0 , r). The selection process used was but this effect takes place very slowly.
roulette wheel selection. As crossover operator the well–known Next, the impact of introducing noise to the data generating
one–point crossover operator was employed. Finally, the mu- process is investigated. A normally distributed, ε ∼ N (0, σ 2 ),
tation operator utilized was the flip bit mutation operator . additive noise term was included in the tent map equation,
GAs were applied for several values of L and a number of yielding xn+1 = fr (xn ) + ε, where fr (xn ) is given by Eq. (1).
binary sequences, bn (x0 , r). Consequently, patterns that can It should be noted that we enforced the resulting raw data se-
account as perfect, or good, predictors can be identified by ries to lie in the interval [0, 1] by rejecting realizations of the
comparing the obtained results for L–bit and (L + 1)–bit pat- noise term that would result in xn+1 ∈ / [0, 1]. The obtained
terns. experimental results for the most predictable binary sequence
44
Table 1. Number of patterns in b106 (0.1, r) obtained through Table 2. Patterns in b106 (0.1, 1.44) obtained through the
the transformation of Eq. (3) for different values of r. transformation of Eq. (3) and different values of σ 2 .
L patterns σ 2 = 0.0 σ 2 = 0.01 σ 2 = 0.1 σ 2 = 0.5
r L #f #f/2L r L #f #f/2L 1 0 230307 246757 434808 552264
2 3 0.750 6 36 0.562 1 769693 753243 565192 447736
3 5 0.625 1.7 7 61 0.476 00 0 17 190252 308874
4 7 0.437 8 105 0.410 2 01 231742 246799 243209 244133
5 11 0.343 9 179 0.349 10 231742 246799 243209 244133
1.44 6 15 0.234 2 4 1.000 11 536514 506383 323328 202858
7 23 0.179 3 7 0.875 000 0 0 93237 173043
8 31 0.121 4 13 0.812 001 0 17 97015 135831
9 47 0.091 5 24 0.750 010 112119 119901 108060 133112
2 3 0.750 1.8 6 43 0.671 011 119623 126897 135149 111021
3 5 0.625 7 78 0.609 3 100 0 17 97015 135831
4 7 0.437 8 141 0.550 101 231742 246782 146194 108301
5 11 0.343 9 253 0.494 110 119623 126898 135148 111021
1.5 6 16 0.250 2 4 1.000 111 416890 379485 188179 91837
7 25 0.195 3 8 1.000 0000 0 0 50612 96905
8 37 0.144 4 15 0.937 0001 0 0 42625 76138
9 57 0.111 5 29 0.906 0010 0 17 43068 74254
2 3 0.750 1.9 6 55 0.859 0011 0 0 53947 61577
3 5 0.625 7 105 0.820 0100 0 9 44101 74116
4 8 0.500 8 199 0.777 0101 112119 119892 63959 58995
5 13 0.406 9 379 0.740 0110 0 2915 55812 60753
1.6 6 21 0.328 2 4 1.000 4 0111 119622 123982 79336 50268
7 34 0.265 3 8 1.000 1000 0 0 42625 76138
8 55 0.214 4 16 1.000 1001 0 17 54390 59693
9 88 0.171 5 32 1.000 1010 112119 119884 64992 58858
2 4 1.000 1.999 6 64 1.000 1011 119623 126897 81202 49443
3 7 0.875 7 128 1.000 1100 0 8 52914 61715
1.7 4 12 0.750 8 256 1.000 1101 119623 126890 82234 49306
5 21 0.656 9 512 1.000 1110 119623 123983 79336 50268
1111 297267 255502 108843 41569
when no noise is included, b106 (0.1, 1.44), are summarised in
Table 2. The first column of the table corresponds to the pat-
tern 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 in-
creases. For σ 2 = 0.01 findings are marginally altered as the
length two pattern ‘00’ appears only 17 times in the length Figure 3. Predictive power of the unit length binary pattern ‘0’
in the sequences obtained through the transformation of Eq (3)
106 binary sequence. Thus, the probability of a ‘1’ following with respect to the variance σ 2 of the noise term.
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 3.2 Variable threshold
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 In this subsection we present results from the analysis of
the noise term deteriorates the predictability of the binary se- binary sequences derived by applying the transformation of
quence is also evident from the fact that patterns that did not Eq. (4), according to which the threshold is equal to the previ-
appear in the not contaminated with noise sequence, appear ous value of the tent map. The distribution of bits with value
frequently in the contaminated series. The predictive power ‘1’ and ‘0’ for different values of the control parameter r is
of the binary pattern ‘0’ (perfect predictors in the noise-free illustrated in Fig. 4. Comparing Figs. 2 and 4 it is evident
binary sequence) with respect to the value of the variance of that the two transformations yield substantially different dis-
the additive noise term, σ 2 is illustrated in Fig. 3. To gen- tributions of ones and zeros. For the second transformation,
erate Fig. 3, σ 2 assumed values in the interval [0, 0.5] with the proportion of ones exceeds that of zeros for r marginally
stepsize 10−3 . larger than 1. As shown in Fig. 4 the two proportions are
45
Table 3. Number of patterns in b106 (0.1, r) obtained through
the transformation of Eq. (4) for different values of r.
r L #f #f/2L r L #f #f/2L
2 3 0.750 6 9 0.140
3 4 0.500 1.7 7 12 0.093
4 5 0.312 8 16 0.062
5 6 0.187 9 21 0.041
1.44 6 7 0.109 2 3 0.750
7 8 0.062 3 5 0.625
8 9 0.035 4 7 0.437
9 10 0.019 5 10 0.312
2 3 0.750 1.8 6 14 0.218
3 4 0.500 7 19 0.148
4 5 0.312 8 27 0.105
5 6 0.187 9 38 0.074
1.5 6 7 0.109 2 3 0.750
7 8 0.062 3 5 0.625
Figure 4. Distribution of ones (dashed) and zeros (solid) 8 9 0.035 4 8 0.500
according to the transformation of Eq. (4) for bn (0.1, r) 9 11 0.021 5 12 0.375
and r ∈ [1, 2] with stepsize 10−3 . 2 3 0.750 1.9 6 18 0.281
3 4 0.500 7 27 0.210
4 5 0.312 8 40 0.156
5 7 0.218 9 59 0.115
√ 1.6 6 9 0.140 2 3 0.750
equal until r becomes equal to 2. This finding is attributed 7 12 0.093 3 5 0.625
to the band splitting phenomenon, √ briefly described in Sec- 8 15 0.058 4 8 0.500
tion 1, that occurs for r ∈ (1, 2] [5]. From that point and 9 19 0.037 5 13 0.406
onward their difference increases. 2 3 0.750 1.999 6 21 0.328
1.7 3 4 0.500 7 34 0.265
The number of patterns of different length L that appear 4 5 0.312 8 55 0.214
in the binary sequences of length 106 , are reported in Table 3 5 7 0.218 9 89 0.173
for different values of the control parameter r. More specifi-
cally, the first column of Table 3 reports the value of r; the
second column corresponds to the length L of the binary pat-
terns; the third column reports the number of different pat- of the variance of the additive noise term ε ∼ N (0, σ 2 ). Note
terns of length L that were identified in the sequence (#f); that as in the previous case, the resulting raw data sequence
6
and lastly, column four depicts the proportion of the patterns {xn }10
n=0 was restrained in the interval [0, 1] by rejecting re-
encountered (#f) to the number of possible binary patterns alizations of the noise term that would result in xn ∈ / [0, 1].
of length L (2L ).
As in the case of the fixed threshold binary transforma- Starting from the case of no noise, we observe that zeros
tion, increasing the value of the control parameter r increases and ones are approximately equally distributed in the binary
the number of patterns that appear in the derived binary sequence. As in the case of the first transformation, pattern
sequences. However, this effect is more pronounced for the ‘00’ is missing from the patterns of length two, a finding which
fixed threshold transformation of Eq. (3) than for the vari- implies that a ‘0’ is always followed by a ‘1’, and hence all the
able threshold transformation of Eq. (4). Even for r = 1.999, binary patterns of any length that end with ‘0’ are perfect pre-
Table 3 reports that the number of binary patterns of length dictors. Furthermore, the pattern ‘111’ was not encountered,
two is three, suggesting that one pattern of length two does implying that ‘11’ is always followed by a ‘0’. From the inspec-
not appear, and hence a unit length perfect binary predictor tion of the findings for patterns of length three we also obtain
exists. In contrast, for the fixed threshold binary transforma- a good predictor of length two, namely the pattern ‘01’, for
tion, Table 1, all four length two binary patterns are present which the probability of appearance of ‘0’ immediately after
in the sequences that are generated with r > 1.7. Moreover, this pattern is 0.96919. Comparing the aforementioned find-
the ratio of the patterns of length L found to the number of ings for the case of no noise, with the corresponding ones
possible patterns of this length decreases more rapidly in the obtained by the first, fixed threshold, transformation we con-
sequences generated by the variable threshold transformation. clude that the binary sequence obtained through the variable
For instance, for r = 1.44, the number of patterns of length threshold transformation is more predictable.
nine is 47 for the fixed threshold transformation, while for the As expected, the introduction of noise eliminates all the
variable threshold transformation this number is 10. perfect predictors identified in the original binary sequence.
The impact of introducing noise on the short-term predic- For a low value of the variance, σ 2 = 0.01, the findings are
tors is studied next. Table 4 reports the patterns of length marginally distorted. The previously not encountered pattern
two to four that were encountered in the binary sequence ‘00’ appears 5979 times yielding a probability of encounter-
b106 (0.1, 1.44) that was obtained through the second transfor- ing a bit with the value ‘1’ following a bit with a value of
mation, for different values of σ 2 . In detail, the first column of ‘0’ equal to 0.987688. This probability is marginally lower
Table 4 corresponds to the length L of the patterns; the second than the corresponding probability for the first transforma-
column lists all possible binary patterns of this length; while tion. On the other hand, when the variance of the noise term
columns three to six report the number of occurrences of each increases to σ 2 = 0.1 and σ 2 = 0.5 this probability becomes
pattern in the binary sequences obtained for different values 0.867348 and 0.698495, respectively. Both these probabilities
46
Table 4. Patterns in bn (0.1, 1.44) obtained through the
transformation of Eq. (4) and different values of σ 2 .
L patterns σ 2 = 0.0 σ 2 = 0.01 σ 2 = 0.1 σ 2 = 0.5
1 0 492207 485787 399771 471981
1 507793 514213 600229 528019
00 0 5979 52973 142274
2 01 492415 479647 346368 329606
10 492414 479647 346368 329606
11 15169 34725 254289 198512
000 0 628 7257 32975
001 0 5351 45716 109299
010 477246 447216 186610 187262
011 15169 32430 159758 142343
3 100 0 5351 45716 109299
101 492414 474296 300652 220307
110 15168 32430 159758 142343
111 0 2295 94530 56169 Figure 5. Predictive power of binary patterns identified in the
0000 0 71 979 6175 sequences obtained through the transformation of Eq (4) with
0001 0 557 6278 26800 respect to the variance σ 2 of the noise term.
0010 0 4840 24665 57459
0011 0 511 21051 51840
0100 0 3964 24580 59905
0101 477246 443252 162030 127357
suggesting that there is no perfect predictor. On the contrary,
0110 15168 30378 98071 98715 for the sequences generated through the second transforma-
4 0111 0 2052 61686 43628 tion with the same value of r, only three out of the four pos-
1000 0 557 6278 26800 sible patterns of length two are encountered, suggesting that
1001 0 4794 39438 82499 there is a perfect short-term predictor of length one. The in-
1010 477245 442376 161945 129803
1011 15169 31919 138707 90503 clusion of an additive Gaussian noise term with zero mean in
1100 0 1387 21136 49394 the tent map equation eliminated all perfect predictors. How-
1101 15168 31043 138622 92949 ever, for small values of the variance of the Gaussian noise
1110 0 2052 61686 43628 binary patterns with high predictive power were identified.
1111 0 243 32844 12541
Future work on the subject will include the investigation of
multiplicative noise, as well as, the application of this method-
are higher than the corresponding ones for the case of the
ology to real–world time series and in particular financial time
transformation of Eq. (3). Moreover, note that for the case of
series. It is worth noting that the second binary transforma-
the first transformation and σ 2 = 0.5 a bit with value ‘0’ is
tion is particularly meaningful in the study of financial time
more likely to be followed by a bit with the same value (prob-
series as it corresponds to the direction of change of the next
ability equal to 0.55854); a phenomenon that does not occur
value relative to the present one.
at present. For the pattern ‘11’ the probability of encounter-
ing 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. Acknowledgments
Finally, for the pattern ‘01’ the probability of zero after its
This work was partially supported by the Hellenic Ministry of
appearance is 0.932387, 0.538762, and 0.568140 for σ 2 equal
Education and the European Union under Research Program
to 0.01, 0.1, and 0.5, respectively. The predictive power of the
PYTHAGORAS-89203.
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 REFERENCES
the additive noise term, σ 2 is illustrated in Fig. 5. To gener- [1] Free Software Foundation Inc., GNU Multiple Precision Arith-
ate Fig. 5, σ 2 assumed values in the interval [0, 0.5] with a metic Library ver. 4.1.4.
stepsize of 10−3 . [2] J. H. Holland, Adaptation in Natural and Artificial Systems,
University of Michigan Press, 1975.
[3] M. Mitchell, Introduction to Genetic Algorithms, MIT Press,
4 Conclusions 1996.
[4] N. G. Packard, ‘A genetic learning algorithm for the analysis
of complex data’, Complex Systems, 4(5), 543–572, (1990).
Despite the chaotic nature of the tent map and the resulting [5] T. Yoshida, H. Mori, and H. Shigematsu, ‘Analytic study of
complexity of the binary sequences that were derived after the chaos of the tent map: Band structures, power spectra, and
application of two threshold, binary, transformations a large critical behaviors’, Journal of Statistical Physics, 31(2), 279–
number of short-term predictors was detected. The reported 308, (1983).
experimental results indicate that the binary sequences gen-
erated 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,
47
48