A method for generating pseudo-random sequences of d-dimensional vectors is considered; it is based on the ergodic theory of periodic orbits in the sense of [2] 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, in this note, we shall 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. © 1992 Instituto di Elaborazione della Informazione del CNR.

Abundo M, Accardi L, & Auricchio A (1992). Hyperbolic automorphisms of tori and pseudo-random sequences. CALCOLO, 29(2009/04/03 00:00:00.000), 213-240 [10.1007/BF02576183].

Hyperbolic automorphisms of tori and pseudo-random sequences

ABUNDO, MARIO ROSOLINO;ACCARDI, LUIGI;
1992

Abstract

A method for generating pseudo-random sequences of d-dimensional vectors is considered; it is based on the ergodic theory of periodic orbits in the sense of [2] 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, in this note, we shall 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. © 1992 Instituto di Elaborazione della Informazione del CNR.
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/06 - Probabilita' e Statistica Matematica
eng
Con Impact Factor ISI
Abundo M, Accardi L, & Auricchio A (1992). Hyperbolic automorphisms of tori and pseudo-random sequences. CALCOLO, 29(2009/04/03 00:00:00.000), 213-240 [10.1007/BF02576183].
Abundo, Mr; Accardi, L; Auricchio, A
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/23055
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact