]> AND Private Git Repository - review_prng.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
dezq
authorguyeux <guyeux@gmail.com>
Fri, 1 Jun 2012 11:51:13 +0000 (13:51 +0200)
committerguyeux <guyeux@gmail.com>
Fri, 1 Jun 2012 11:51:13 +0000 (13:51 +0200)
review_prng.tex

index 0cdeb04a63b5d3ebfafd21bfc934808d71e226d3..b395874366e480ce7a1c77b37cfd24ea34e63025 100644 (file)
@@ -260,57 +260,45 @@ However~\cite{GuyeuxThese10}:
        \item $G_{f_0}$ possesses more than $n^2$ points of period $2n$.
      \end{itemize}
 Additionally, this existence of points of any period has been rejected
-by the community to the benefit of more recent notions of chaos, as
-they are detailed in the following paragraphs.
+by the community to the benefit of more recent notions of chaos, 
+like those developed these last decades by Devaney~\cite{Devaney}, Knudsen~\cite{Knudsen94}, etc.
+
+In these approaches, three ingredients are required for unpredictability. 
+Firstly, the system must be intrinsically complicated, undecomposable: it cannot be simplified into two
+subsystems that do not interact, making any divide and conquer strategy 
+applied to the system inefficient. In particular, a lot of orbits must visit
+the whole space. Secondly, an element of regularity is added, to counteract
+the effects of the first ingredient, leading to the fact that closed points
+can behave in a completely different manner, and this behavior cannot be predicted.
+Finally, sensibility of the system is demanded as a third ingredient, making that
+closed points can finally become distant during iterations of the system.
+This last requirement is, indeed, often implied by the two first ingredients.
+
+Having this understanding of an unpredictable dynamical system, Devaney has
+formalized in~\cite{Devaney} the following definition of chaos.
 
+\begin{definition}
+A discrete dynamical system $x^0 \in \mathcal{X}, x^{n+1}=f(x^n)$ on a
+metric space $(\mathcal{X},d)$ is said to be chaotic according to Devaney
+if it satisfies the three following properties:
+    \begin{enumerate}
+\item \emph{Transitivity:} For each couple of open sets $A,B \subset \mathcal{X}$, there exists $k \in \mathbb{N}$ such that $f^{(k)}(A)\cap B \neq \varnothing$.
+\item \emph{Regularity:} Periodic points are dense in $\mathcal{X}$.
+\item \emph{Sensibility to the initial conditions:} There exists $\varepsilon>0$ such that $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ and } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon.$$
+\end{enumerate}
+\end{definition}
 
-
-%\subsection*{Approche type Devaney/Knudsen}
-
-%\frame{
-%  \frametitle{Les approches Devaney et Knudsen}
-%  \begin{block}{3 propriétés pour de l'imprévisibilité}
-%    \begin{enumerate}
-%      \item \emph{Indécomposabilité.} On ne doit pas pouvoir simplifier le système
-%      \begin{itemize}
-%        \item Impossible de diviser pour régner
-%        \item Des orbites doivent visiter tout l'espace
-%      \end{itemize}
-%      \item \emph{Élément de régularité.}
-%      \begin{itemize}
-%        \item Contrecarre l'effet précédent
-%        \item Des points proches \textit{peuvent} se comporter complètement différemment
-%      \end{itemize}
-%      \item \emph{Sensibilité.} Des points proches \textit{peuvent} finir éloignés
-%    \end{enumerate}
-%  \end{block}
-%}
-
-
-%\frame{
-% \frametitle{Exemple : définition de Devaney}
-%\begin{enumerate}
-%\item \emph{Transitivité:} Pour chaque couple d'ouverts non vides $A,B \subset \mathcal{X}$, il existe $k \in \mathbb{N}$ tel que $f^{(k)}(A)\cap B \neq \varnothing$
-%\item \emph{Régularité:} Les points périodiques sont denses
-%\item \emph{Sensibilité aux conditions initiales:} Il existe $\varepsilon>0$ tel que $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ et } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$$
-%\end{enumerate}
-%}
-
-%\frame{
-%   \frametitle{Systèmes intrinsèquement compliqués}
-%   \begin{block}{Définitions de l'indécomposabilité}
-%   \begin{itemize}
-%     \item \emph{Indécomposable}: pas la réunion de deux parties non vides, fermées et t.q. $f(A) \subset A$
-%     \item \emph{Totalement transitive}: $\forall n \geqslant 1$, l'application composée $f^{(n)}$ est transitive.
-%     \item \emph{Fortement transitif}:
-%$\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$
-%     \item \emph{Topologiquement mélangeant}:  pour toute paire d'ouverts disjoints et non vides $U$ et $V$, il existe $n_0 \in \mathbb{N}$ tel que $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$.
-%   \end{itemize}
-%   \end{block}
-%}
-
+The system can be intrinsically complicated for various other understanding of this wish, that are 
+not equivalent one another, like:
+\begin{itemize}
+    \item \emph{Undecomposable}: it is not the union of two nonempty closed subsets that are positively invariant ($f(A) \subset A$).
+  \item \emph{Total transitivity}: $\forall n \geqslant 1$, the function composition $f^{(n)}$ is transitive.
+  \item \emph{Strong transitivity}: $\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$
+  \item \emph{Topological mixing}:  for all pairs of disjoint open nonempty sets $U$ and $V$, there exists $n_0 \in \mathbb{N}$ such that $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$.
+\end{itemize}
 
 
+Concerning the ingredient of sensibility, it can be formulated as follows.
 
 %\frame{
 %\frametitle{Stabilité et expansivité}