X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/bba3979e3f3ee00ce44b16d13b4e61e434310b61..88947af28fe7e7f5b1dd35d21d71b2f69130b798:/review_prng.tex?ds=inline

diff --git a/review_prng.tex b/review_prng.tex
index a5d1388..0cdeb04 100644
--- a/review_prng.tex
+++ b/review_prng.tex
@@ -3,7 +3,7 @@
 \usepackage[standard]{ntheorem}
 \usepackage[english]{babel}
 
-
+\usepackage{stmaryrd}
 \usepackage{amsmath}
 \usepackage{color}
 \usepackage{dsfont}
@@ -80,7 +80,7 @@ these units have not the same processing frequency.
 \end{itemize} 
 
 These considerations lead to the following definition of an iterative
-system.
+system~\cite{GuyeuxThese10}.
 
 \begin{definition}
 Iterative systems on a set $\mathcal{X}$ are defined by
@@ -93,197 +93,175 @@ $$\left\{
 where $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$.
 \end{definition}
 
+Some particular cases of these iterative systems are well documented,
+namely the serial, parallel, or chaotic modes.
+In the serial mode, each component is updated one by one, whereas the
+parallel mode consists in updating all the components at each iteration,
+leading to an usual discrete dynamical system.
+These modes are compliant with the definition above, 
+as the parallel mode consists in considering that the sequence
+$f^n$ defined above is constant equal to a given $f: \mathcal{X} 
+\longrightarrow \mathcal{X}$,
+whereas the serial mode can be rewritten as parallel iterations of
+$$ G=F_\mathsf{N} \circ \ldots \circ F_2 \circ F_1 $$
+where, $\forall i \in \llbracket 1, \mathsf{N} \rrbracket $:
+$$\begin{array}{rccc}
+F_i: & \mathcal{X} & \longrightarrow & \mathcal{X}\\
+        & (x_1, \hdots, x_\mathsf{N}) & \longmapsto & \left(x_1, \hdots, x_{i-1},f_i\left(x_1, \hdots, x_\mathsf{N}\right), x_{i+1}, \hdots, x_\mathsf{N}\right).
+\end{array}$$
+
+
+
+Finally, iterative systems in chaotic mode, simply called chaotic iterations,
+are defined as follows~\cite{Robert}.
+ 
 
+\begin{definition}
+Let $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ and 
+$S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. 
+\emph{Chaotic iterations} $(f, (x^0, S))$ are defined by:
+$$\left\{
+\begin{array}{l}
+x^0 \in \mathds{B}^\mathsf{N} \\
+\forall n \in \mathds{N}^*, \forall i \in \llbracket 1; \mathsf{N} \rrbracket,  x^{n}_i = \left\{
+\begin{array}{ll}
+x^{n-1}_{i} & \textrm{ if } i \notin S^n\\
+f(x^{n-1})_{i} & \textrm{ if } i \in S^n
+\end{array}
+\right.
+\end{array}
+\right.$$
+\end{definition}
 
+\emph{A priori}, there is no relation between these chaotic iterations
+and the mathematical theory of chaos recalled in the previous section.
+On our side, we have regarded whether these chaotic iterations can 
+behave chaotically, as it is defined for instance by Devaney, and if so, 
+in which applicative context this behavior can be profitable.
+This questioning has led to a first necessary condition of non convergence~\cite{GuyeuxThese10}.
+
+\begin{proposition}
+Let $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ and 
+$S \in \llbracket 1, \mathsf{N} \rrbracket^{\mathds{N}}$. 
+If the chaotic iterations $\left(f,(x^0,S)\right)$ are not convergent, then:
+\begin{itemize}
+\item either $f$ is not a contraction, meaning that there is no Boolean matrix
+    $M$ of size $\mathsf{N}$ satisfying $\forall x,y\in \mathds{B}^\mathsf{N}$,
+    $d(f(x),f(y)) \leqslant M d(x,y)$, where $d$ is here the ``vectorial distance''
+    defined by $d(x,y) = \left(\begin{array}{c} \delta(x_1,y_1)\\ \vdots \\ \delta(x_\mathsf{N}, 
+    y_\mathsf{N}) \end{array}\right)$, with $\delta$ the discrete metric defined by $\delta(x,y) = \left\{\begin{matrix} 1 &\mbox{if}\ x\neq y , \\ 0 &\mbox{if}\ x = y \end{matrix}\right.$, and $\leqslant$ is the inequality term by term~\cite{Robert}.
+\item or $S$ is not pseudo-periodic: it is not constituted by an infinite succession of finite sequences, each having any element of $\llbracket
+    1, \mathsf{N} \rrbracket$ at least once.
+\end{itemize}
+\end{proposition}
+
+The second alternative of the proposition above concerns the strategy,
+which should be provided by the outside world. Indeed, in our opinion, 
+chaotic iterations can receive a PRNG $S$ as input, and due to 
+properties of disorder of $f$, generate a new pseudorandom sequence
+that presents better statistical properties than $S$. Having this 
+approach in mind, we thus have searched vectorial Boolean iteration
+functions that are not contractions. The vectorial negation function
+$f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{N}^\mathsf{N},$
+$(x_1, \hdots, x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, 
+\overline{x_\mathsf{N}}) $ is such a function, which served has a
+model in our further studies ($\overline{x}$ stands for the negation
+of the Boolean $x$).
+
+The quantity of disorder generated by such chaotic iterations, when
+satisfying the proposition above, has then been measured. To do so, 
+chaotic iterations have first been rewritten as simple discrete 
+dynamical systems, as follows.
+
+
+\subsection{Chaotic Iterations as Dynamical Systems}
+
+The problems raised by such a formalization can be summarized as 
+follows. 
+Chaotic iterations are defined in the discrete mathematics framework,
+considering $x^0 \in \mathds{B}^\mathds{N}$ and $S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$, and iterations having the
+form 
+$$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$$ 
+where $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$.
+However, the mathematical theory of chaos takes place into a 
+topological space $(\mathcal{X},\tau)$. It studies the iterations
+$x^0 \in \mathcal{X}$, $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$,
+where $f : \mathcal{X} \to \mathcal{X}$ is continuous for the
+topology $\tau$.
+
+To realize the junction between these two frameworks, the following
+material has been introduced~\cite{GuyeuxThese10,bgw09:ip}:
+\begin{itemize}
+\item the shift function: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
+\item the initial function, defined by $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
+\item and $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto  \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
+\end{itemize}
+where $\delta$ is the discrete metric.
 
 
-%%  \end{block}
-%%\uncover<2->{
-%%DiffÃ©rents modes d'itÃ©rations: sÃ©ries, parallÃ¨les, chaotiques, asynchrones...
-%%}
-%%}
-
-
-
-
-
-
-
-
-
-
-%\subsection*{Cas des ItÃ©rations chaotiques}
-%\frame{
-%  \frametitle{Les Â« itÃ©rations chaotiques Â»}
-%    \begin{block}{DÃ©finition (ItÃ©rations chaotiques)}
-% Soient $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ et $S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. Les \emph{itÃ©rations chaotiques} sont:
-%$$\left\{
-%\begin{array}{l}
-%x^0 \in \mathds{B}^\mathsf{N} \\
-%\forall n \in \mathds{N}^*, \forall i \in \llbracket 1; \mathsf{N} \rrbracket,  x^{n}_i = \left\{
-%\begin{array}{ll}
-%x^{n-1}_{i} & \textrm{ si } i \notin S^n\\
-%f(x^{n-1})_{i} & \textrm{ si } i \in S^n
-%\end{array}
-%\right.
-%\end{array}
-%\right.$$
-%\end{block}
-%%\uncover<2->{
-%%ItÃ©rations chaotiques et thÃ©orie du chaos: a priori, rien Ã  voir.
-%%}
-%%\uncover<3->{Y a-t-il un lien ?}\uncover<4->{ Pour quoi faire ?}
-%}
-
-
-
-
-
-%\frame{
-%  \frametitle{Non-convergence des IC}
-%   \begin{alertblock}{ThÃ©orÃ¨me (Condition nÃ©cessaire de non-convergence)}
-%    % Soit $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ et $S \in \mathcal{S}$. 
-%    Si les itÃ©rations chaotiques $\left(f,(x^0,S)\right)$ sont non convergentes, alors:
-%\begin{itemize}
-%\item soit $f$ n'est pas contractante,
-%\item soit $S$ n'est pas pseudo-pÃ©riodique (complÃ¨te).
-%\end{itemize}
-%   \end{alertblock}
-%   \uncover<2->{
-%   Quelle quantitÃ© de dÃ©sordre ?
-%   }
-%}
-
-
-
-
-
-
-
-
-
-
-%\frame{
-%\frametitle{PrÃ©sentation du problÃ¨me}
-
-%\begin{tabular}{c||c}
-%MATHS DISCRÃTES & TOPOLOGIE MATHÃMATIQUE \tabularnewline
-%\hline
-%\multirow{2}{5cm}{\centering $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$} & $(\mathcal{X},\tau)$ espace topologique\\
-%& $f : \mathcal{X} \to \mathcal{X}$ continue pour $\tau$\\
-%\hline
-%$S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$ & \multirow{2}{5cm}{\centering $x^0 \in \mathcal{X}$} \\
-%$x^0 \in \mathds{B}^\mathds{N}$ & \\ 
-%\hline
-%$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$ & $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$ \\ 
-%\end{tabular}
-
-%}
-
-
-
-
-
-
-%\frame{
-%\frametitle{DÃ©finitions et notations}
-%\begin{block}{Introduisons quelques fonctions...}
-%\begin{itemize}
-%\item dÃ©calage: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
-%\item initiale: $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
-%\item $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto  \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
-%\end{itemize}
-%oÃ¹ $\delta(x,y) = \left\{\begin{array}{ll}
-%0 & \textrm{ si } x=y, \\
-%1 & \textrm{ sinon.}
-% \end{array}\right.
-%$
-%\end{block}
-%}
-
-
-
-
-%\frame{
-%\frametitle{ModÃ©lisation des IC}
-%\begin{alertblock}{ModÃ©lisation des IC en topologie}
-%Soit $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ et $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$ 
-
-
-%On modÃ©lise les itÃ©rations chaotiques $\left(f, (S,x^0)\right)$ par le systÃ¨me dynamique discret:
-%$$\left\{
-%\begin{array}{l}
-%X^0 = (S,x^0) \in \mathcal{X}, \\
-%\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
-%\end{array}
-%\right.$$
-%\end{alertblock}
-
-% \uncover<2>{
-% On peut donc Ã©tudier leur dÃ©sordre topologique.
-% }
-%}
-
-
-
-
-
-%\frame{
-% \frametitle{MÃ©trique et continuitÃ©}
-
-%Distance sur $\mathcal{X}:$
-%$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) +  d_s(S,\check{S})$$
-
-%\noindent oÃ¹ $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~et~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
-%%\end{block}
-
-%\vspace{0.5cm}
-
-%\begin{alertblock}{ThÃ©orÃ¨me}
-%La fonction $G_f : (\mathcal{X},d) \to  (\mathcal{X},d)$ est continue.
-%\end{alertblock}
-
-%}
-
-
-
-% \frame{
-%  \frametitle{\'Etude de $(\mathcal{X},d)$}
-%  \begin{block}{PropriÃ©tÃ©s de $(\mathcal{X},d)$}
-%  \begin{itemize}
-%    \item $\mathcal{X}$ est infini indÃ©nombrable
-%    \vspace{0.15cm}
-%    \item $(\mathcal{X},d)$ est un espace mÃ©trique compact, complet et parfait
-%  \end{itemize}
-%  \end{block}
-% 
-%  \vspace{0.5cm}
-% 
-%    \begin{block}{\'Etude de $G_{f_0}$}
-%    $G_{f_0}$ est surjective, mais pas injective \vspace{0.3cm}\newline $\Rightarrow (\mathcal{X},G_{f_0})$ pas rÃ©versible.
-%  \end{block}
-
-% }
-
 
 
-%%\frame{
-%% \frametitle{Etude des pÃ©riodes}
-%% \begin{block}{MultiplicitÃ© des pÃ©riodes ?}
-%% Soit $f_0:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$ la nÃ©gation vectorielle.
-%%   \begin{itemize}
-%%     \item $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$ \vspace{0.3cm} \linebreak  $\Rightarrow G_{f_0}$ pas chaotique sur $\mathcal{X}$
-%%     \item Cependant :
-%%     \begin{itemize}
-%%       \item Il y a chaos sur $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
-%%       \item $G_{f_0}$ possÃ¨de plus de $n^2$ points pÃ©riodiques de pÃ©riode $2n$.
-%%     \end{itemize}
-%%   \end{itemize}
-%% \end{block}
-%% \uncover<2->{
-%%    Cette multiplicitÃ© des pÃ©riodes n'est pas le dÃ©sordre complet...
-%% }
-%%}
+Let $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ and $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$ 
+Chaotic iterations $\left(f, (S,x^0)\right)$ can be modeled by the 
+discrete dynamical system:
+$$\left\{
+\begin{array}{l}
+X^0 = (S,x^0) \in \mathcal{X}, \\
+\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
+\end{array}
+\right.$$
+Their topological disorder can then be studied.
+To do so, a relevant distance must be defined of $\mathcal{X}$, as
+follows~\cite{GuyeuxThese10,bgw09:ip}:
+$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) +  d_s(S,\check{S})$$
+\noindent where $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~and~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
+
+This new distance has been introduced in \cite{bgw09:ip} to satisfy the following requirements.
+\begin{itemize}
+\item When the number of different cells between two systems is increasing, then their distance should increase too.
+\item In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. Indeed, the two dynamical systems start with the same initial condition, use the same update function, and as strategies are the same for a while, then components that are updated are the same too.
+\end{itemize}
+The distance presented above follows these recommendations. Indeed, if the floor value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$ cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the differences between strategies $S$ and $\check{S}$. More precisely, this floating part is less than $10^{-k}$ if and only if the first $k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the $k^{th}$ terms of the two strategies are different.
+
+It has then be stated that
+\begin{proposition}
+$G_f : (\mathcal{X},d) \to  (\mathcal{X},d)$ is a continuous function
+\end{proposition}
+
+With all this material, the study of chaotic iterations as a discrete
+dynamical system has then be realized. 
+This study is summarized in the next section.
+
+\subsection{Topological Properties of Chaotic Iterations}
+
+The topological space on which chaotic iterations are defined has
+firstly been investigated, leading to the following result~\cite{gb11:bc,GuyeuxThese10}:
+\begin{proposition}
+$\mathcal{X}$ is an infinitely countable metric space, being both
+compact, complete, and perfect (each point is an accumulation point).
+\end{proposition}
+These properties are required in some topological specific 
+formalization of a chaotic dynamical system, justifying their
+proofs.
+
+Concerning $G_{f_0}$, it has been stated that~\cite{GuyeuxThese10}.
+\begin{proposition}
+$G_{f_0}$ is surjective, but not injective, and so the dynamical system $(\mathcal{X},G_{f_0})$ is not reversible.
+
+Furthermore, if we denote by $Per_k(f)$ the set of periodic points 
+of period $k$ for $f$, we have 
+ $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$.
+\end{proposition}
+ 
+So $\Rightarrow G_{f_0}$ does not present the existence of points of any period referred as chaos in the article of Li and Yorke~\cite{Li75}.
+However~\cite{GuyeuxThese10}:
+     \begin{itemize}
+       \item This kind of disorder can be stated on $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
+       \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.
 
 
 
