×

Hyperbolic automorphisms of tori and pseudo-random sequences. (English) Zbl 0793.65001

Summary: A method for generating pseudo-random sequences of \(d\)-dimensional vectors is considered; it is based on the ergodic theory of periodic orbits for unstable dynamical systems such as the hyperbolic automorphisms of the \(d\)-dimensional torus. Since these systems enjoy strong chaotic properties, their orbits are both dense and chaotic in some sense, however the ergodic property holds only for orbits having initial points with irrational coordinates, the remaining ones being periodic.
Unfortunately, those orbits are the only ones that a computer is able to generate. Since a pseudo-random sequence in \([0,1]^ d\) is a long periodic orbit which has chaotic behaviour similar in some sense to the one of aperiodic orbits we prove lower and upper bounds for the length of the period of orbits of the hyperbolic automorphisms of the \(d\)- dimensional torus, expressed in terms of the (rational) starting point.
The algorithms proposed are free of computational error, since they work in integer arithmetic. Surprisingly the elimination of the round off errors turns out in an increase of the length of the period. Statistical testing and the problem of estimating the discrepancy of the obtained sequences are also treated.

MSC:

65C10 Random number generation in numerical analysis
11K45 Pseudo-random numbers; Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. V. Anosov,Geodesic flows on closed Riemann manifolds with negative curvature, Tr. Mat. Inst. Steklov 90, (in Russian). English transl.: Proc. Steklov Inst. Math. 90, (1967), 235. · Zbl 0176.19101
[2] L. Accardi, F. De Tisi, A. Di Libero,Sistemi Dinamici Instabili e Generazione di Successioni Pseudo-casuali, C. N. R. Rassegna di Metodi Statistici ed Applicazioni, Cagliari, Giugno 1981.
[3] V. I. Arnold, A. Avez,Ergodic problems of Classical Mechanisms (1968), Benjamin, New York. · Zbl 0167.22901
[4] R. L. Adler, B. Weiss,Similarity of automorphisms of the torus, Mem Amer. Math. Soc. 98, New York, 1968.
[5] N. Bouleau,On effective computation of expectations in large or infinite dimension, J. Comput. Appl. Math. 31 (1990), 23–34. · Zbl 0704.65108 · doi:10.1016/0377-0427(90)90333-U
[6] R. Bowen,Markov partitions for axiom A diffeomorphisms, Am. J. Math. n. 92, (1970), 725–747. · Zbl 0208.25901 · doi:10.2307/2373370
[7] R. Bowen,Equilibrium states and the ergodic theory of Anosov diffeomorphismus, Lecture Notes in Math., 470, Springer-Verlag 1975. · Zbl 0308.28010
[8] K. L. Chung,An estimate concerning the Kolmogoroff limit distribution, Trans. Amer. Math. Soc. 67, (1949), 36–50. · Zbl 0034.22602
[9] M. Cugiani,Metodi Numerico statistici, 1980. · Zbl 0456.65080
[10] G. Halasz,Remarks on the remainder in Birkhoff’s ergodic theorem, Acta Math. Hungar., 28, (1976), 389–395. · Zbl 0336.28005 · doi:10.1007/BF01896805
[11] J. Kiefer,On large deviations of the empiric d.f. of vector chance variables and a law of the iterated logarithm, Pacific J. Math., 11, (1961), 649–660. · Zbl 0119.34904
[12] D. E. Knuth,The Art of Computer Programming, Vol. II, (1981), Addison-Wesley. · Zbl 0477.65002
[13] U. Krengel,On the speed of convergence in the ergodic theorem, Monatsh. Math. 86, (1978), 3–6. · Zbl 0384.28016 · doi:10.1007/BF01300052
[14] H. Niederreiter,Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84, N. 6, (1978), 957–1041. · Zbl 0404.65003 · doi:10.1090/S0002-9904-1978-14532-7
[15] H. Niederreiter,Statistical independence properties of pseudorandom vectors produced by matrix generators, J. Comput. Appl. Math. 31, (1990), 139–151. · Zbl 0708.65007 · doi:10.1016/0377-0427(90)90345-Z
[16] H. Niederreiter,Recent trends in random number and random vector generation, Ann. Oper. Res. 31, (1991), 323–346. · Zbl 0737.65001 · doi:10.1007/BF02204856
[17] Ya. B. Pesin, Ya. G. Sinai,Gibbs measures for partially hyperbolic attractors, Ergodic Theory Dynamical Systems 2, (1982), 417–438. · Zbl 0519.58035
[18] P. Sarnak,Asymptotic behaviour of periodic orbits of the horocycle flow and Eisenstein series, Comm. Pure Appl. Math. 34, (1981), 719–739. · Zbl 0501.58027 · doi:10.1002/cpa.3160340602
[19] Ya. G. Sinai (Ed.),Dynamical systems, Encyclopaedia of Mathematical Sciences, Vol. II (1989), Springer-Verlag. · Zbl 0671.00010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.