From 6d6fccfc41ac320a93542faf3558ea72bd4897da Mon Sep 17 00:00:00 2001 From: guyeux Date: Sat, 9 Jun 2012 16:07:48 +0200 Subject: [PATCH] =?utf8?q?Avanc=C3=A9es=20dans=20les=20d=C3=A9finitions=20?= =?utf8?q?de=20chaos?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- review_prng.tex | 101 +++++++++++++++++++++++++++++++++++------------- 1 file changed, 75 insertions(+), 26 deletions(-) diff --git a/review_prng.tex b/review_prng.tex index f595d05..7ed72e6 100644 --- a/review_prng.tex +++ b/review_prng.tex @@ -11,7 +11,7 @@ \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators} -\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier, and Christophe Guyeux~\thanks{Authors in alphabetic order}} +\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier,\\ Nicolas Friot, and Christophe Guyeux~\thanks{Authors in alphabetic order}} @@ -27,7 +27,7 @@ \section{Introduction} -\section{Topologycal Study of Disorder} +\section{Topological Study of Disorder} \subsection{Historical Context} @@ -58,16 +58,16 @@ cycles and order. Conversely, Li and Yorke have established in 1975~\cite{Li75} the presence of a point of period three implies chaos in the same situation than previously. By chaos, they mean the existence of points of any period: this kind of disorder, which is the first occurrence of the -term ``chaos'' in the mathematical litterature, is thus related to the +term ``chaos'' in the mathematical literature, is thus related to the multiplicity of periods. Since that time, the mathematical theory of chaos has known several developments to qualify or quantify the richness of chaos presented by a given discrete dynamical system, one of the most -famous work, although old, being the one of Devaney~\cite{devaney}. +famous work, although old, being the one of Devaney~\cite{Devaney}. \subsection{Iterative Systems} In the distributed computing community, dynamical systems have been -generatized to take into account delay transmission or heterogeneous +generalized to take into account delay transmission or heterogeneous computational powers. Mathematically, the intended result is often one fixed point resulting from the iterations of a given function over a Boolean vector, considering that: @@ -321,40 +321,89 @@ are satisfied. -\subsection{Other approaches} +\subsection{Li-Yorke approach} +The approach for chaos presented in the previous section, considering that +a chaotic system is a system intrinsically complicated (undecomposable), +with possibly an element of regularity and/or sensibility, has been +completed by other understanding of chaos. Indeed, as ``randomness'' +or ``infiniteness'', a single universal definition of chaos is cannot +be found. The kind of behaviors that are attempted to be described are +too much complicated to enter into only one definition. Instead, a +large panel of mathematical descriptions have been proposed these last +decades, being all theoretically justified. Each of these definitions +give illustration to some particular aspects of a chaotic behavior. -%\frame{ -% \frametitle{Selon Li et Yorke} -% \begin{block}{Définitions} -% \begin{description} -%\item[Couple de Li-Yorke.] $(x,y)$ en est un quand: $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0.$ +The first of these parallel approaches can be found in the pioneer +work of Li and Yorke~\cite{Li75}. In their well-known article entitled +``Period three implies chaos'', they rediscovered a weaker formulation of +the Sarkovskii's theorem, meaning that when a discrete dynamical system +$(f,[0,1])$, with $f$ continuous, has a 3-cycle, then it has too a +$n-$cycle, $\forall n \leqslant 2$. The community has not adopted this +definition of chaos, as several degenerated systems satisfy this property. +However, on their article~\cite{Li75}, Li and Yorke have studied too +another interesting property, which has led to a notion of chaos +``according to Li and Yorke'', which is recalled below. -%\item[Ensemble brouillé.] $B \subset \mathcal{X}$ en est un si tout couple de points distincts de $B$ est de Li-Yorke. +Let us firstly introduce the definition of Li-Yorke scrambled couple +of points. This is points that never stop to oscillate. -%\item[Systèmes de Li-Yorke.] $\mathcal{X}$ est compact et contient un ensemble brouillé indénombrable. -%\end{description} -%\end{block} -%} +\begin{definition} +Let $(\mathcal{X},d)$ a metric space and $f:\mathcal{X} \longrightarrow +\mathcal{X}$ a continuous map. $(x,y)\in \mathcal{X}^2$ is a scrambled +couple of points if $lim inf_{n\rightarrow \infty} d(f^n(x),f^n(y))=0$ +and $lim sup_{n\rightarrow \infty} d(f^n(x),f^n(y))>0$. +\end{definition} +A scrambled set is a set in which any couple of points oscillate (are +a scrambled couple), whereas a Li-Yorke chaotic system is a system +possessing an uncountable scrambled set. +\subsection{Topological Entropy Approach} +The topological entropy of a topological dynamical system, +firstly introduced in 1965 by Adler, Konheim, and McAndrew~\cite{Adler65}, +is a nonnegative real number that measures the complexity of the system. +It represents the exponential growth rate of the number of distinguishable +orbits of the iterates, for a system given by an iterated function. +It can be formulated as follows. +Let $f:\mathcal{X} \longrightarrow \mathcal{X}$ be a continuous map on +a compact metric space $(\mathcal{X},d)$. For each natural +number $n$, a new metric $d_n$ is defined on $\mathcal{X}$ by +$$d_n(x,y)=\max\{d(f^i(x),f^i(y)): 0\leq i0$ and $n \geqslant 1$, two points of +$\mathcal{X}$ are $\varepsilon$-close with respect to +this metric if their first $n$ iterates are $\varepsilon$-close. This +metric allows one to distinguish in a neighborhood of an orbit the +points that move away from each other during the iteration from the +points that travel together. + +A subset $E$ of $\mathcal{X}$ is said to be $(n,\varepsilon)$-separated +if each pair of distinct points of $E$ is at least $\varepsilon$ apart +in the metric $d_n$. Denote by $N(n, \varepsilon)$ the +maximum cardinality of a $(n,\varepsilon)$-separated set. +$N(n, \varepsilon)$ represents the number of distinguishable orbit +segments of length $n$, assuming that we cannot distinguish points +within $\varepsilon$ of one another. + +\begin{definition} +The topological +entropy of the map $f$ is defined by +$$h(f)=\lim_{\epsilon\to 0} \left(\limsup_{n\to \infty} \frac{1}{n} +\log N(n,\epsilon)\right).$$ +\end{definition} -%\frame{ -% \frametitle{Approche entropie topologique} -% \begin{block}{Entropie topologique} -% \begin{itemize} -% \item $x,y \in \mathcal{X}$ sont ~$\varepsilon-$\emph{séparés en temps $n$} s'il existe $k \leqslant n$ tel que $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. -% \item Les ensembles $(n,\varepsilon)-$séparé sont des ensembles de points qui seront tous $\varepsilon-$séparés en temps $n$ -% \item $s_n(\varepsilon,Y)$: cardinal maximal d'un ensemble $(n,\varepsilon)-$séparé $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}$$ -% \end{itemize} -% \end{block} -%} +The limit defining $h(f)$ may +be interpreted as the measure of the average exponential growth of the +number of distinguishable orbit segments. In this sense, it measures +complexity of the topological dynamical system $(\mathcal{X}, f)$. +\subsection{The Lyapunov Exponent} %\frame{ % \frametitle{Exposant de Lyapunov} -- 2.39.5