relecture preuve PCH

[rairo15.git] / sdd.tex

Cette section énonce les notions fondamentales relatives aux systèmes dynamiques
booléens  et  à la  mesure  du chaos.   Le  formalisme  des systèmes  dynamiques
booléens est donné en section~\ref{sub:sdd}, suivi des méthodes de déduction des
graphes     d'itérations     (section~\ref{sub:grIter}).
%    et     d'interactions
%(section~\ref{sub:sdd:inter}).
% La notion de retards est présentée en
% section~\ref{sub:sdd:retards}.
Enfin,  une   distance  sur  l'espace   $\llbracket  1;n\rrbracket^{\Nats}\times
\Bool^n$ est  définie en section~\ref{sub:metric}, qui  permet ensuite d'établir
la   nature   chaotique   des   systèmes   dynamiques   booléens,   abordée   en
section~\ref{section:caracterisation}.

\subsection{Système dynamique booléen}\label{sub:sdd}

Soit $n$ un entier naturel. Un système dynamique booléen est 
défini à partir d'une fonction booléenne:
\[
f:\Bool^n\to\Bool^n,\qquad x=(x_1,\dots,x_n)\mapsto f(x)=(f_1(x),\dots,f_n(x)),
\]
et un  {\emph{schéma itératif}} ou  encore \emph{mode de  mise à jour}  qui peut
être parallèle, séquentiel ou asynchrone%, et intégrer ou non des retards
.  À  partir d'une configuration initiale $x^0\in\Bool^n$,  la suite $(x^{t})^{t
  \in  \Nats}$ des  configurations  du  système est  construite  selon l'un  des
schémas suivants :
\begin{itemize}
\item \textbf{Schéma parallèle  synchrone :} basé sur la  relation de récurrence
  $x^{t+1}=f(x^t)$. Tous  les $x_i$, $1 \le  i \le n$,  sont ainsi mis à  jour à
  chaque itération en utilisant l'état global précédent du système ($x^t$).
\item \textbf{Schéma séquentiel synchrone :} basé sur une mise à jour successive
  des différents éléments du système,  selon un ordre défini. Le mode séquentiel
  de référence est basé sur la séquence ordonnée des éléments, de 1 à $n$.
\item \textbf{Schéma  asynchrone :} cette terminologie  a plusieurs acceptations
  dans  la littérature,  mais celle  qui  reste la  plus répandue,  et que  nous
  retenons ici,  consiste à ne modifier  qu'un élément $i$,  $1 \le i \le  n$, à
  chaque itération. Le choix de l'élément qui est modifié à chaque itération est
  défini  par une  suite. Lorsque  cette  suite est  strictement cyclique  (sans
  occurrences multiples  dans le motif) sur l'ensemble  des éléments $\{1,\ldots
  n\}$, alors on retrouve le comportement du mode séquentiel synchrone.
\item \textbf{Schéma chaotique:}  dans ce schéma, ce n'est  plus un seul élément
  qui  est  modifié  à  chaque  itération,  mais  une  partie  des  éléments  de
  $\{1,\ldots  n\}$.  Dans  le premier  cas  particulier où  c'est un  singleton
  $\{k\}$, $1 \le k  \le n$, qui est modifié à chaque  itération, on retrouve le
  mode asynchrone,  et si la séquence  des singletons est  ordonnée et cyclique,
  alors on retrouve le mode séquentiel.  Dans le second cas particulier où c'est
  $\{1, \ldots,  n\}$ qui est  modifié à chaque  itération, on retrouve  le mode
  parallèle.  Ce mode généralise donc les trois autres modes précédents.  
  Plus formellement,  à  la  $t^{\textrm{ème}}$
  itération, seuls les éléments de la partie 
  $s_{t} \in \mathcal{P}(\{1, \ldots, n\})$ sont mis à
  jour.  La  suite $S  = \left(s_t\right)_{t \in  \mathds{N}}$ est  une séquence
  de sous-ensembles 
  de   $\{  1, \ldots,n   \}$   appelée   \emph{stratégie}.
  Dans      ce      mode     opératoire,  on définit la fonction\linebreak
  $F_f:~\mathcal{P}(\{1, \ldots, n\}) \times \Bool^{n} \rightarrow \Bool^n$  par
  \[
  F_f(s,x)_i=\left\{
    \begin{array}{l}
      f_i(x) \textrm{ si $i \in s$;}\\   
      x_i \textrm{ sinon.}
    \end{array}\right.
  \]
  Dans le schéma des itérations chaotiques, pour une configuration initiale
  $x^0\in\Bool^n$ et une stratégie $S = \left(s_t\right)_{t \in  \mathds{N}}
\in \mathcal{P}(\{1, \ldots, n\})^{\Nats}$,
  les
  configurations $x^t$ sont définies par la récurrence
  \begin{equation}\label{eq:asyn}
    x^{t+1}=F_f(s_t,x^t).
  \end{equation}
  Soit alors $G_f$ une fonction de $\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times\Bool^n$ 
  dans lui-même définie par 
  \[
  G_f(S,x)=(\sigma(S),F_f(s_0,x)),
  \] 
  où $\forall t\in\Nats,\sigma(S)_t=s_{t+1}$.
  En d'autres termes la fonction $\sigma$ \emph{décale}
  la stratégie fournie en argument d'un élément vers la gauche en supprimant 
  l'élément de tête. 
  Les itérations parallèles de $G_f$ depuis un point initial
  $X^0=(S,x^0)$ décrivent la même orbite que les  
  itérations chaotiques de $f$ induites par $x^0$ et la  stratégie
  $S$.
\end{itemize}

\subsection{Graphe d'itérations chaotiques}\label{sub:grIter}

Soit $f$ une fonction de $\Bool^n$ dans lui-même. 
Le {\emph{graphe des itérations chaotiques}} associé à $f$ est le 
graphe orienté $\Gamma(f)$ défini ainsi: 
l'ensemble de ses sommets est $\Bool^n$ et pour chaque $x\in\Bool^n$ et  
$s\in \mathcal{P}(\{1, \ldots, n\})$, le graphe $\Gamma(f)$ 
contient un arc de $x$ vers $F_f(s,x)$. 
La relation entre $\Gamma(f)$ et $G_f$ est claire: il  existe un 
chemin  de $x$ à  $x'$ dans $\Gamma(f)$ si et seulement s'il existe une 
stratégie  $S$ telle que les itérations  parallèles $G_f$ à partir 
du point $(S,x)$ mènent à un point $(.,x')$.

Dans ce qui suit, et par souci de concision, le terme \emph{graphe des itérations}
est une abréviation de  graphe des itérations chaotiques.
La figure~\ref{fig:xplgraphIter} donne deux exemples de graphes d'itérations 
pour les fonctions $g$ et $h$ définies dans $\Bool^2$, qui sont reprises tout au long 
de cet article. 

\begin{figure}[ht]
  \begin{center}
    \subfloat[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
      \begin{minipage}{0.40\textwidth}
        \begin{center}
          \includegraphics[width=\columnwidth]{images/g}
        \end{center}
      \end{minipage}
      \label{fig:g:iter}
    }
    \subfloat[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
      \begin{minipage}{0.40\textwidth}
        \begin{center}
          \includegraphics[width=\columnwidth]{images/h}
        \end{center}
      \end{minipage}
      \label{fig:h:iter}
    }   
  \end{center}
  \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$.}
  \label{fig:xplgraphIter}
\end{figure}

% \subsection{Graphe d'interactions}\label{sub:sdd:inter}

% Pour $x\in\Bool^n$ et $i\in\llbracket 1;n\rrbracket$, on nomme  
%  $\overline{x}^i$ la configuration obtenue en niant le 
% $i^{\textrm{ème}}$ composant de $x$. En d'autres termes
% $\overline{x}^i=(x_1,\dots,\overline{x_i},\dots,x_n)$.
% Des interactions entre les composants du 
% système peuvent être mémorisées 
% dans la {\emph{matrice Jacobienne discrète}} $f'$.
% Celle-ci est définie comme étant la fonction  qui  à chaque 
% configuration $x\in\Bool^n$ associe la matrice de taille 
% $n\times n$ définie par : 
% \[
% f'(x)=(f'_{ij}(x)),\qquad 
% f'_{ij}(x)=\frac{f_i(\overline{x}^j)-f_i(x)}{\overline{x}^j_j-x_j}\qquad (i,j\in\llbracket1;n\rrbracket).
% \]

% On  note que  dans  l'équation donnant  la  valeur de  $f'_{ij}(x)$, les  termes
% $f_i(\overline{x}^j)$,  $f_i(x)$, $\overline{x}^j_j$  et  $x_j$ sont  considérés
% comme des entiers  naturels égaux à $0$ ou  à $1$ et que le  calcul est effectué
% dans  $\Z$. Cela  est important  car le  signe des  $f'_{ij}(x)$ nous  donne une
% information supplémentaire sur la dynamique du système.

% En outre, les interactions peuvent se  représenter à l'aide d'un 
% graphe $G(f)$ orienté et signé défini ainsi: 
% l'ensemble des sommets est 
% $\llbracket1;n\rrbracket$ et il existe un arc de $j$ à $i$ de signe
%  $s\in\{-1,1\}$, noté $(j,s,i)$, si $f'_{ij}(x)=s$ pour au moins
% un $x\in\Bool^n$. 
% On note que la présence de 
% deux arcs de signes opposés entre deux sommets donnés 
% est possible.

% \begin{figure}%[t]
%   \begin{center}
%     \subfloat[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
%       \begin{minipage}{0.40\textwidth}
%         \begin{center}
%           \includegraphics[height=3cm]{images/gp.pdf}
%         \end{center}
%       \end{minipage}
%       \label{fig:g:inter}
%     }
%     \subfloat[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
%       \begin{minipage}{0.40\textwidth}
%         \begin{center}
%           \includegraphics[height=3cm]{images/hp.pdf}
%         \end{center}
%       \end{minipage}
%       \label{fig:h:inter}
%     }    \end{center}
%     \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$}
%     \label{fig:xplgraphInter}
%   \end{figure}

% Soit $P$ une suite d'arcs de $G(f)$ de la forme
% \[
% (i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
% \]
% Alors, $P$ est dit un \emph{chemin} de $G(f)$ de longueur $r$ et de signe
% $\Pi_{i=1}^{r}s_i$ et  $i_{r+1}$ est dit accessible depuis
% $i_1$. 
% $P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets
% $i_1$,\ldots $i_r$ sont deux à deux disjoints.
% Un sommet $i$ de $G(f)$ a une {\emph{boucle}} 
% positive (resp. négative) , si $G(f)$ a un 
% arc positif (resp. un arc négatif) de $i$ vers lui-même.

% \subsection{Retards entre les éléments du système}
% \label{sub:sdd:retards}

% La notion  de retard provient  initialement du besoin  de prendre en  compte les
% délais de transfert  d'information entre les éléments du  système.  Lorsque l'on
% se place dans  le contexte général, ces délais peuvent  eux-mêmes varier dans le
% temps. On décrit donc  le retard de l'élément $j$ par rapport  à l'élément $i$ à
% l'instant $t$ par  $r_j^i(t)$. Ainsi, l'information reçue de $j$ en  $i$ à $t$ a
% été générée à  l'instant (ou itération) $s_j^i(t)=t-r_j^i(t)$. On  en déduit que
% la mise à jour de l'élément $i$ de l'instant $t$ à $t+1$ s'écrit :
% \begin{equation*}
%   x_i(t+1) = f_i(x_1^{s_1^i(t)},x_2^{s_2^i(t)},\dots,x_i^t,\dots,x_{n-1}^{s_{n-1}^i(t)},x_n^{s_n^i(t)})
% \end{equation*}
% On constate que même si le modèle le permet, on ne met généralement pas de délai
% entre l'élément $i$ et lui-même car cela n'a pas d'intérêt pratique fort.

\subsection{Distance sur l'espace $\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times \Bool^n$}\label{sub:metric}
Pour $A$ et $B$ deux ensembles de l'univers $\Omega$,
on rappelle la définition de l'opérateur 
de \emph{différence ensembliste} symétrique :
\[
A \Delta B = (A \cap \overline{B}) \cup (\overline{A} \cap B)
\]  
où $\overline{B}$ désigne le complémentaire de $B$ dans $\Omega$.

On considère l'espace $\mathcal{X}=\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times
\Bool^n$ et
on définit la distance $d$ entre les points $X=(S,x)$ et
$X'=(S',x')$ de $\mathcal{X}$ par 
\[
d(X,X')= d_H(x,x')+d_S(S,S'),~\textrm{où}~
\left\{
\begin{array}{l}
\displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm] 
\displaystyle{d_S(S,S')=\frac{9}{n}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}.
\end{array}
\right.\,.
\]
On note que dans le calcul de $d_H(x,x')$ -- 
appelée \gls{distanceHamming} (cf. glossaire) 
entre $x$ et $x'$-- 
les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels 
égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
On note aussi que le symbole $|.|$ est utilisé avec deux sémantiques
différentes dans ce calcul: 
on somme des valeurs absolues dans la distance 
de Hamming tandis que l'on somme des cardinalités d'ensemble dans 
$d_S$. 
De plus, la \gls{partieentiere} (cf. glossaire) 
$\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance 
de Hamming entre $x$ et $x'$. 
%D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$ 
%mesure la différence entre $s$ et $s'$.
On remarque que la partie décimale est inférieure à $10^{-l}$ si
et seulement si les $l$ premiers termes des deux stratégies sont égaux. 
De plus, si la 
$(l+1)^{\textrm{ème}}$ décimale  
de $d_S(S,S')$ 
n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 

La fonction $d$ est une somme de deux fonctions.
La fonction $d_H$ est la distance de Hamming; il est aussi établi que la 
somme de deux distances est une distance.
Ainsi, pour montrer que $d$ est aussi une distance, il suffit 
de montrer que $d_S$ en une aussi.

Soit $S$, $S'$ et $S''$ trois parties de $\{1,\ldots,n\}$.
\begin{itemize}
\item De manière évidente, $d_s(S,S')$ est positive ou bien nulle si 
  et seulement si $S$ et $S'$ sont égales.
\item Comme la différence symétrique est commutative, la valeur de  
  $d_S(S,S')$ est égale à  celle de $d_S(S',S)$.
\item On a enfin la succession d'éléments suivants:
  $$
  \begin{array}{rcl}
    S \Delta S' & = & (S \cap \overline{S'}) \cup (\overline{S} \cap S')\\
    & = & (S \cap \overline{S'} \cap S'' ) \cup  (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''})\\
    & \subseteq & (S \cap \overline{S'} \cap S'' ) \cup  (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''}) \cup \\
     & & (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''} ) \cup (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''})\\     
    & = & (\overline{S'} \cap S'' ) \cup  (S \cap \overline{S''} ) \cup (\overline{S} \cap S'') \cup (S'\cap \overline{S''}) \\
    & = & (S \Delta S'') \cup (S'' \Delta S')   
  \end{array}
  $$
  On en déduit ainsi que 
$|S \Delta S'| \le |S \Delta S''| + |S'' \Delta S'|$ et donc que 
l'égalité triangulaire $d_S(S,S') \le d_S(S,S'') + d_S(S'',S')$ est établie.
\end{itemize}

On peut démontrer que pour toute fonction booléenne $f$, 
$G_f$ est continue sur $\mathcal{X}$ (cf.~annexe~\ref{anx:cont}).   

\subsection{Temps de mélange}
\label{sec:mixingtime}

Le  temps de mélange  (\emph{mixing time})~\cite{LevinPeresWilmer2006},  est une
des métriques usuelles  pour estimer la vitesse de  convergence des lignes d'une
matrice de  Markov vers  une distribution spécifique.   Elle est définie  par le
nombre minimal d'itérations nécessaires  pour obtenir une déviation inférieure à
un $\varepsilon$ donné pour chaque ligne de la matrice.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: