Synthesizing Chaotic Maps with Prescribed Invariant Densities

Synthesizing Chaotic Maps with Prescribed Invariant Densities Alan Rogers a,∗Robert Shorten bDaniel M. Heffernan c,1 aDepartment of Electronic Engineering, NUI Maynooth, Co. Kildare, Ireland bHamilton Institute, NUI Maynooth, Co. Kildare, Ireland cDepartment of Mathematical Physics, NUI Maynooth, Co. Kildare, Ireland Abstract The Inverse Frobenius-Perron problem (IFPP) concerns the creation of discrete chaotic mappings with arbitrary invariant densities. In this note, we present a new and elegant solution to the IFPP, based on positive matrix theory. Our method allows chaotic maps with arbitrary piecewise-constant invariant densities, and with arbitrary mixing properties, to be synthesized. Key words: Chaos, Chaotic Maps, Chaos Control, Inverse Frobenius-Perron Problem PACS: 05.45.-a, 02.50.-r 1 Introduction The synthesis, or custom-design of chaotic maps, is a natural extension of the research carried out on nonlinear dynamical systems over the past thirty years. Ulam and Von Neumann had even studied the logistic map in the 1940s [1]. Notwithstanding Von Neumann’s famous point about using deterministic processes to generate randomness, synthetic chaotic maps do have many potential applications, especially in hardware-based random-number generators, and digital noise generators [2–4]. They may also be used to artifically recreate physical data from real-world systems [5]. In this paper, we present an elegant ∗Corresponding Author. Email address: [email protected] (Alan Rogers). 1Also at: School of Theoretical Physics, Dublin Institute for Advanced Studies, Dublin 4, Ireland Preprint submitted to Physics Letters A 6 August 2004 way of creating designer chaotic maps with arbitrary invariant densities. The synthesis method presented is based on the theory of positive matrices, and originates in work on synchronised communication networks. When a chaotic map is iterated, different initial conditions exponentially diverge leading to completely different long-run behaviour. However, when looked at statistically, many chaotic maps possess a single physically relevant invariant density, which remains stable when random noise is added to the process [6]. Given an arbitrary initial condition, the invariant density describes where iterates end up on average. For simple maps such as the tent map, or the Bernoulli (2xmod 1) map, iterates have an equal probability of landing anywhere in the state-space: the natural invariant density ρis constant, and equals one [7]. Many maps, however, do not possess a simple invariant measure. The Frobenius-Perron operator Pτis an operator on the space of probability density functions [8]. The invariant density is a fixed point of the FrobeniusPerron equation: Pτf(x) = d dxZfdλ τ−1[a,x] (1) While it is relatively straightforward to calculate the invariant density ρof piecewise affine maps, most continuous maps do not possess a closed-form solution to the Frobenius-Perron equation (especially where the invariant density is a fractal). Clearly, if it is very difficult to analyse a map to find its invariant density, then the synthesis problem - generating a map which possesses a desired invariant density - must seem quite a daunting prospect. However, Ulam conjectured that the Frobenius-Perron operator could be approximated by the action of a Markov map acting on a partition of the interval concerned [9]. The Ulam conjecture was proved in 1976 by Li [10]. The Ulam matrix is a column stochastic matrix which gives the probability of moving from any particular interval in the partition to any other interval. The principle eigenvector of the Ulam matrix is the invariant density of the map. Thus if a Markov matrix can be synthesized for a particular eigenvector, then we have a solution for the Inverse Frobenius-Perron problem (IFPP). The IFPP has been tackled and solved by various groups (see [11] and references therein). The method most relevant to this work is the solution of G´ora and Boyarsky [12], [5]. They show how to generate a 3-band transformation from any given invariant density. However, our method is more direct in that both the eigenvector and the Ulam transition matrix are parameterized. No work is required to generate the matrix - the procedure is completely mechanical. Our method also gives complete control over the mixing properties of the map, independent of the invariant density. 2 In the following section, we outline the synthesis method. We then give a simple example of the application of the method to synthesize a map with a prescribed invariant density. Some properties of the transition matrix are also given, followed by conclusions. The appendix gives a little extra background on the origins of the matrix used. 2 Synthesis Method The following matrix arises naturally in the dynamical analysis of synchronised communication networks based on TCP (Transmission Control Protocol). Further properties of the matrix are given in the appendix, and the interested reader should refer to [13], or [14], for the origins of this matrix. A=           β10· · · 0 0β20 0 . . . 0 ...0 0 0 · · · βn           +1 Pn i=1 αi           α1 α2 . . . αn           µ1−β11−β2· · · 1−βn¶(2) The matrix Ais a column stochastic matrix, and is strictly positive when αi≥0 and 0 < βi<1∀i∈ {1,· · · , n}, and so Acan represent a Markov process. From the theory of positive matrices, it is well-known that the matrix Ahas a leading eigenvalue ρ(A) = 1, and a single eigenvector in the positive orthant, called the Perron eigenvector [15]. The Perron eigenvector, xpof the Amatrix has the following form: xT p=µα1 1−β1, . . . , αn 1−βn¶(3) Clearly, we can control the dominant eigenvector of the matrix through choice of the αiand βi. For our purposes, the matrix Ais the Ulam matrix, and the Perron eigenvector represents the invariant density of the process governed by A. The Ulam matrix may be represented as a one-dimensional chaotic map if we let each entry of the matrix denote the transition probability from one interval to another. More formally, partition the unit interval into Nequal subintervals, {I1, . . . , IN}. Let entry aji of the Amatrix denote the probability of a transition from interval Iito interval Ij, denoted pij. To construct the map, place a line segment of slope ±1/pij in the square defined by the intervals Ii, Ij, for each entry of the matrix. It is convenient to start at the point (0,0) and place the line segments end to end, although there are many possibilities, as illustrated in Figure 1. The map in Figure 1 is one possible implementation of the following transition matrix: 3 01 1 x n x n+1 I 1 I 2 I 3 I 4 I 1 I 2 I 3 I 4 p 42 =1 p 11 =1/4 p 12 =1/4 p 13 =1/2 p 14 =0 Fig. 1. A possible one-dimensional map corresponding to a 4 ×4 transition matrix A=           1/4 1/3 1/4 0 1/4 1/6 1/4 1 1/2 1/4 1/4 0 0 1/4 1/4 0           (4) We can write the matrix Ain the following, more compact, form, where we have normalized the alphas: Pαi= 1. A=           β1+α1(1 −β1)α1(1 −β2)· · · α1(1 −βn) α2(1 −β1)β2+α2(1 −β2) . . .... αn(1 −β1)βn+αn(1 −βn)           (5) It is possible to choose the αiand βiso that the eigenvector represents any desired invariant density. For simplicity, we can set all of the βi= 0.1 say, and then determine the αifor the desired density. Once the αiand βiare determined, the matrix Ais fully determined, and can then be implemented as a map. 4 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 X n X n+1 Fig. 2. Map corresponding to the A matrix in the example (6) 3 Example As an example, we will synthesize a chaotic map whose invariant density has a triangular shape: For simplicity, we partition the unit interval into five equal segments. Let ρdesired = [1,3,5,3,1]. We then determine the αiwith βi= 0.1. This gives us the following column-stochastic transition matrix: A=               0.1692 0.0692 0.0692 0.0692 0.0692 0.2077 0.3077 0.2077 0.2077 0.2077 0.3462 0.4462 0.3462 0.3462 0.3462 0.2077 0.2077 0.2077 0.3077 0.2077 0.0692 0.0692 0.0692 0.0692 0.1692               (6) A possible 1-D chaotic map corresponding to this transition matrix is shown in Figure 2, and the invariant density of the map after 30000 iterations, ρactual is shown in Figure 3. The density has been scaled such that the first entry of ρactual = 1 to allow ready comparison with the desired invariant density. It can be seen that ρactual is very close to the desired invariant density, ρ= [1,3,5,3,1]. Figure 4 shows a typical output from the map. (MATLAB code to implement the method is freely available at http://www.eeng.may.ie /˜arogers/ifpp.) 5 12345 0 1 2 3 4 5 6 Interval Number Relative number of iterations per interval Fig. 3. Invariant density of map in Figure 2 after 30000 iterations 0 50 100 150 200 250 300 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Iteration Number X n Fig. 4. Chaotic time-series produced by the map in Figure 2 4 Further Properties of the Transition Matrix The matrix Aarises naturally in the study of synchronised communication networks, and is used to model the dynamics of networks employing TCP congestion control [13] [14]. It has a number of interesting properties, which we mention here. (1) The matrix Ais strictly positive as defined in section 2, or strictly nonnegative if we allow αi= 0. As such, it possesses a dominant eigenvalue called the Perron eigenvalue λpof geometric and algebraic multiplicity 1. The corresponding Perron eigenvector xT p=µα1 1−β1, . . . , αn 1−βn¶ represents a fixed point of the linear system W(k+ 1) = AW(k). For any other eigenvalue λi6=λp, we have |λi|< λp. (2) The rate of convergence to the fixed point is bounded by the second 6 largest eigenvalue of A. For our application, the second-largest eigenvalue determines how quickly we get to the desired invariant density. The second-largest eigenvalue thus controls the mixing properties of the map. As we can make the second-largest eignevalue as large or as small as we like, we have complete control over the mixing properties, independent of the invariant density. It can be shown that, apart from the Perron eigenvalue, all the the eigenvalues of Alie within the interval [β1, βn]. (3) If the βiare distinct, and are ordered such that β1< β2<· · · < βn, then it can be shown that the eigenvalues of Aare interlaced with the βithus: β1< λ1< β2< λ2<···< βn< λn=λp= 1.(7) (4) The Lyapunov exponent of the map resulting from the matrix Acan be shown to be Λ≃α1α2. . . αnln 1 α1α2. . . αn +α2 1ln 1 α1 +· · · +α2 nln 1 αn (8) in the limit βi→0. We find this to be a very good approximation for small βi. 5 Conclusions From an engineering viewpoint, custom-design of chaotic maps is absolutely necessary for possible future applications. Maps must be tailored to fit the application. In this paper, we have presented a direct way of creating designer chaotic maps with arbitrary invariant densities. The synthesis method presented is based on the theory of positive matrices, and originated in work on synchronised communication networks. Its most useful property is its straightforward implementation. Moreover, our method allows complete control of the mixing properties of the map, independent of the invariant density. Acknowledgements We thank the referees for their useful comments. This work was supported by the Irish science and technology agency, Enterprise Ireland, under research grant No. SC-00-86 7 A Transition matrix - supplementary material The special form of the matrix Aarises in the context of communication networks, and its origins are described thoroughly in [13] and [14]. Essentially, the matrix comes about from a model of synchronised information sources operating an Additive-Increase Multiplicative-Decrease (AIMD) congestion control algorithm. Networks of such devices in the presence of a bottleneck buffer may be modelled as a positive linear system, whence we get the Amatrix. More recent results will be found in [16]. We present some further properties of the matrix Abelow, which are proved in the aforementioned papers. Lemma 1 For a positive column stochastic matrix Aof the following form: diag(β1, . . . , βn)+(1/Pn i=1 αi)[α1, . . . , αn]T[1−β1, . . . , 1−βn], and βi∈(0,1), αi>0, then the dominant (Perron) eigenvector of A, corresponding to the sole unity eigenvalue is given by xp=θ[α1 1−β1 ,..., αn 1−βn ], θ ∈R(A.1) Theorem 1 Consider the matrix Ain Lemma 1. The following statements are true: (1) Except for the Perron eigenvalue, all of the eigenvalues lie in the interval [β1, βn]. (2) If all the βs are distinct, then β1< λ1< β2< . . . < βn< λn= 1 Outline Proof: The matrix Ais diagonally similar to a matrix of the form G−1(D+αβT)Gwhere D=diag(β1, . . . , βn), and Gis a diagonal matrix (simple calculation). Using Lemma 1 together with this result, and standard results on the symmetric eigenvalue problem (see for instance Theorem 8.6.2 in [17], or [18]), the proof of (1) and (2) follow directly. References [1] S. Ulam, J. von Neumann, On combinations of stochastic and deterministic processes, Bulletin of the American Mathematical Society 53 (1947) 1120. [2] R. L. Kautz, Using chaos to generate white noise, Journal of Applied Physics 86 (10) (1999) 5794–5800. [3] L. Kocarev, Chaos-based cryptography: A brief overview, IEEE Circuits and Systems Magazine 1 (3) (2001) 6–21. [4] M. Delgado-Restituto, A. Rodriguez-Vazquez, Integrated chaos generators, Proceedings of the IEEE 90 (5) (2002) 747–767. 8 [5] A. Boyarsky, P. G´ora, Chaotic maps derived from trajectory data, Chaos 12 (1) (2002) 42–48. [6] H. G. Schuster, Deterministic Chaos, VCH, 1989. [7] E. Ott, Chaos in Dynamical Systems, 2nd Edition, Cambridge University Press, 2002. [8] A. Lasota, M. Mackey, Chaos, Fractals, and Noise, Vol. 97 of Applied Mathematical Sciences, Springer-Verlag, 1994. [9] S. M. Ulam, A Collection of Mathematical Problems, Vol. 8 of Interscience Tracts in Pure and Applied Math, Interscience, 1960. [10] T. Li, Finite approximation for the frobenius-perron operator: A solution to ulam’s conjecture, Journal of Approximation Theory 17 (1976) 177–186. [11] E. M. Bollt, Controlling chaos and the inverse frobenius-perron problem: Global stabilization of arbitrary invariant measures, International Journal of Bifurcation and Chaos 10 (5) (2000) 1033–1050. [12] P. G´ora, A. Boyarsky, A matrix solution to the inverse frobenius-perron problem, Proceedings of the American Mathematical Society 118 (2) (1993) 409–414. [13] R. Shorten, D. Leith, J. Foy, R. Kilduff, Analysis and design of synchronised communication networks, in: Proceedings of 12th Yale Workshop on Adaptive and Learning Systems, 2003. [14] A. Berman, R. Shorten, D. Leith, Positive matrices associated with synchronised communication networks, Linear Algebra and Its Applications (Accepted). [15] D. G. Luenberger, Introduction to Dynamic Systems, Wiley, 1979. [16] D. Leith, et al., Stochastic equilibria of aimd communication networks, submitted to SIAM Journal on Matrix Analysis and Applications. [17] G. Golub, C. van Loan, Matrix Computations, Johns Hopkins University Press, 1996. [18] R. Horn, C. Johnson, Matrix Analysis, Cambridge University Press, 1985. 9