Search

The scope of this paper is two-fold. First, to present to the researchers in combinatorics an interesting implementation of permutations avoiding generalized patterns in the framework of discrete-time dynamical systems. Indeed, the orbits generated by piecewise monotone maps on one-dimensional intervals have forbidden order patterns, i.e., order patterns that do not occur in any orbit. The allowed patterns are then those patterns avoiding the so-called forbidden root patterns and their shifted patterns. The second scope is to study forbidden patterns in shift systems, which are universal models in information theory, dynamical systems and stochastic processes. Due to its simple structure, shift systems are accessible to a more detailed analysis and, at the same time, exhibit all important properties of low-dimensional chaotic dynamical systems (e.g., sensitivity to initial conditions, strong mixing and a dense set of periodic points), allowing to export the results to other dynamical systems via order-isomorphisms., Comment: 21 pages, expanded Section 5 and corrected Propositions 3 and 4

Permutation entropy quantifies the diversity of possible orderings of the values a random or deterministic system can take, as Shannon entropy quantifies the diversity of values. We show that the metric and permutation entropy rates--measures of new disorder per new observed value--are equal for ergodic finite-alphabet information sources (discrete-time stationary stochastic processes). With this result, we then prove that the same holds for deterministic dynamical systems defined by ergodic maps on $n$% -dimensional intervals. This result generalizes a previous one for piecewise monotone interval maps on the real line (Bandt, Keller and Pompe, "Entropy of interval maps via permutations",\textit{Nonlinearity} \textbf{15}, 1595-602, (2002)), at the expense of requiring ergodicity and using a definition of permutation entropy rate differing in the order of two limits. The case of non-ergodic finite-alphabet sources is also studied and an inequality developed. Finally, the equality of permutation and metric entropy rates is extended to ergodic non-discrete information sources when entropy is replaced by differential entropy in the usual way.

Many data-based statistical algorithms require that one find \textit{near or nearest neighbors} to a given vector among a set of points in that vector space, usually with Euclidean topology. The k-d data structure and search algorithms are the generalization of classical binary search trees to higher dimensional spaces, so that one may locate near neighbors to an example vector in $O(\log N)$ time instead of the brute-force O(N) time, with $N$ being the size of the data base. KDTREE2 is a Fortran 95 module, and a parallel set of C++ classes which implement tree construction and search routines to find either a set of $m$ nearest neighbors to an example, or all the neighbors within some Euclidean distance $r.$ The two versions are independent and function fully on their own. Considerable care has been taken in the implementation of the search methods, resulting in substantially higher computational efficiency (up to an order of magnitude faster) than the author's previous Internet-distributed version. Architectural improvements include rearrangement for memory cache-friendly performance, heap-based priority queues for large $m$searches, and more effective pruning of search paths by geometrical constraints to avoid wasted effort. The improvements are the most potent in the more difficult and slowest cases: larger data base sizes, higher dimensionality manifolds containing the data set, and larger numbers of neighbors to search for. The C++ implementation requires the Standard Template Library as well as the BOOST C++ library be installed., Comment: Software is available at ftp://lyapunov.ucsd.edu/pub/nonlinear/kd_tree/kdtree2.tar.gz

A symbolic analysis of observed time series data requires making a discrete partition of a continuous state space containing observations of the dynamics. A particular kind of partition, called ``generating'', preserves all dynamical information of a deterministic map in the symbolic representation, but such partitions are not obvious beyond one dimension, and existing methods to find them require significant knowledge of the dynamical evolution operator or the spectrum of unstable periodic orbits. We introduce a statistic and algorithm to refine empirical partitions for symbolic state reconstruction. This method optimizes an essential property of a generating partition: avoiding topological degeneracies. It requires only the observed time series and is sensible even in the presence of noise when no truly generating partition is possible. Because of its resemblance to a geometrical statistic frequently used for reconstructing valid time-delay embeddings, we call the algorithm ``symbolic false nearest neighbors''.

We investigate synchronization and subsequently communication using chaotic rare-earth-doped fiber ring lasers, represented by a physically realistic model. The lasers are coupled by transmitting a fraction c of the circulating electric field in the transmitter and injecting it into the optical cavity of the receiver. We then analyze a coupling strategy which relies on modulation of the intensity of the light alone. This avoids problems associated with the polarization and phase of the laser light. We study synchronization as a function of the coupling strength and see excellent convergence, even with small coupling constants. We prove that in an open-loop configuration (c=1) synchronization is guaranteed due to the particular structure of our equations and of the injection method we use for these coupled laser systems. We also analyze the generalized synchronization of these model lasers when there is parameter mismatch between the transmitter and the receiver. We then address communicating information between the transmitter and receiver lasers by modulation of the chaotic optical waveform. Finally we comment on the cryptographic setting of our algorithms, especially the open-loop strategy at c=1, and hope this may lead others to perform the cryptographic analyses to determine which, if any, of the communications strategies we investigate are secure., Comment: 37 pages, 25 encapsulated postscript figures, 1 table. To be submitted to Phys. Rev. E

We construct a statistic and null test for examining the stationarity of time-series of discrete symbols: whether two data streams appear to originate from the same underlying unknown dynamical system, and if any difference is statistically significant. Using principles and computational techniques from the theory of data compression, the method intelligently accounts for the substantial serial correlation and nonlinearity found in realistic dynamical data, problems which bedevil naive methods. Symbolic methods are computationally efficient and robust to noise. We demonstrate the method on a number of realistic experimental datasets., Comment: Isaac Newton Institute Preprint, 1998

Information in the time distribution of points in a state space reconstructed from observed data yields a test for ``nonstationarity''. Framed in terms of a statistical hypothesis test, this numerical algorithm can discern whether some underlying slow changes in parameters have taken place. The method examines a fundamental object in nonlinear dynamics, the geometry of orbits in state space, with corrections to overcome difficulties in real dynamical data which cause naive statistics to fail., Comment: REVTEX, 4 encapsulated postscript figures, in uuencoded, gzipped tar archive; email: kennel@msr.epm.ornl.gov

It is frequently asserted that in a chaotic system two initially close points will separate at an exponential rate governed by the largest global Lyapunov exponent. Local Lyapunov exponents, however, are more directly relevant to predictability. The difference between the local and global Lyapunov exponents, the large variations of local exponents over an attractor, and the saturation of error growth near the size of the attractor---all result in non-exponential scalings in errors at both short and long prediction times, sometimes even obscuring evidence of exponential growth. Failure to observe exponential error scaling cannot rule out deterministic chaos as an explanation. We demonstrate a simple model that quantitatively predicts observed error scaling from the local Lyapunov exponents, for both short and surprisingly long times. We comment on the relevance to atmospheric predictability as studied in the meteorological literature., Comment: In REVTeX format, followed by uuencoded, compressed ".tar.Z" file which includes Postscript version of manuscript and 5 Postscript figures. PACS:{05.45.+b,92.60.Wc}, email:[mbk,hdia,sid]@inls1.ucsd.edu