-
+
+\section{Chaînes de Markov associées à $\textsc{giu}(f)$}
Considérons le lemme technique suivant:
\begin{lemma}\label{lem:stoc}
Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\textsc{giu}(f)$, et $M$ la matrice
$\textsc{giu}(f)$ est fortement connexe.
\end{lemma}
-\begin{Proof}
+\begin{proof}
On remarque tout d'abord que $M$
est une matrice stochastique par construction.
Supposons $M$ régulière.
$k$ est le plus petit multiple commun de $\{k_{ij} \big/ i,j \in \llbracket 1, 2^n \rrbracket \}$ alors
$\forall i,j \in \llbracket 1, 2^n \rrbracket, \check{M}_{ij}^{k}>0$.
Ainsi, $\check{M}$ et donc $M$ sont régulières.
-\end{Proof}
-
-Ces résultats permettent formuler et de prouver le théorème suivant:
-
-\begin{theorem}
- Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son
- graphe d'itérations , $\check{M}$ sa matrice d'adjacence
- et $M$ une matrice $2^n\times 2^n$ définie comme dans le lemme précédent.
- Si $\textsc{giu}(f)$ est fortement connexe, alors
- la sortie du générateur de nombres pseudo aléatoires détaillé par
- l'algorithme~\ref{CI Algorithm} suit une loi qui
- tend vers la distribution uniforme si
- et seulement si $M$ est une matrice doublement stochastique.
-\end{theorem}
-
-\begin{Proof}
+\end{proof}
+
+Ces résultats permettent formuler et de prouver le théorème annoncé.
+\PrngCIUniforme*
+\begin{proof}
$M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc})
qui a un unique vecteur de probabilités stationnaire
(Théorème \ref{th}).
la somme des valeurs de chaque colonne de $M$ est 1,
\textit{i.e.} si et seulement si
$M$ est doublement stochastique.
-\end{Proof}
+\end{proof}
+
+\section{Chaoticité de la fonction $G_{f_u,\mathcal{P}}$ dans
+$(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$}
+
+Montrons le théorème
+\distancedsxnp*
+
+
+\begin{proof}
+ $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming.
+ Prouvons que
+ $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est aussi une distance;
+$d$ sera ainsi une distance comme somme de deux distances.
+ \begin{itemize}
+\item De manière évidente, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, et si $s=\check{s}$, alors
+$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$.
+Réciproquement si $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, alors
+$\forall k \in \mathds{N}, v^k=\check{v}^k$ d'après la définition de $d$.
+Or les éléments entre les positions $p+1$ et $p+n$
+sont nulles et correspondent à $|u^0-\check{u}^0|$,
+on peut conclure que $u^0=\check{u}^0$.
+On peut étendre ce résultat aux $n \times \max{(\mathcal{P})}$ premiers
+blocs engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$,
+et en vérifiant tous les $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
+ \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est évidemment symétrique
+($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$).
+\item l'inégalité triangulaire est établie puisque la valeur absolue la vérifie
+aussi.
+ \end{itemize}
+\end{proof}
+
+
+
+Montrons que:
+\begin{lemma}
+Le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$
+est fortement connexe si et seulement si
+la fonction $G_{f_u,\mathcal{P}}$ est topologiquement transitive sur
+$(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$.
+\end{lemma}\label{prop:trans}
+
+\begin{proof}
+Supposons tout d'abord que $G_{f_u,\mathcal{P}}$ fortement connexe.
+Soit $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v}))
+\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$.
+On cherche un point $y$ dans une boule ouverte $\mathcal{B}(x,\varepsilon )$
+et un nombre
+$n_0 \in \mathds{N}$ tels que $G_{f_u,\mathcal{P}}^{n_0}(y)=\check{x}$:
+Cette transitivité forte entraînera la propriété de transitivité classique.
+On peut supposer que $\varepsilon <1$ sans perte de généralité.
+
+Soit $(E,(U,V))$ les éléments de $y$. Comme
+$y$ doit appartenir à $\mathcal{B}(x,\varepsilon)$ et $\varepsilon < 1$,
+$E$ est égal à $e$.
+Soit $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
+La distance $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ est inférieure à
+$\varepsilon$: les $k$ premiers éléments de la partie décimale de
+$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ sont nuls.
+Soit $k_1$ le plus petit entier tel que, si $V^0=v^0$, ..., $V^{k_1}=v^{k_1}$,
+alors $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
+Alors $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
+En d'autres mots, chaque $y$ de la forme $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
+(v^0, ..., v^{k_1}))$ est dans $\mathcal{B}(x,\varepsilon)$.
+
+Soit $y^0$ un tel point et $z=G_{f_u,\mathcal{P}}^{k_1}(y^0) = (e',(u',v'))$.
+$G_{f_u,\mathcal{P}}$ étant fortement connexe,
+il existe un chemin entre $e'$ et $\check{e}$.
+Soit $a_0, \hdots, a_{k_2}$ les arêtes visitées le long de ce chemin.
+On fixe $V^{k_1}=|a_0|$
+(le nombre de termes dans la séquence finie $a_1$),
+$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, et
+$U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,
+$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,\ldots
+
+Soit $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},...,
+ a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
+ $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
+ |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$.
+Ainsi
+ $y\in \mathcal{B}(x,\varepsilon)$
+ et $G_{f}^{k_1+k_2}(y)=\check{x}$.
+
+Réciproquement, si $G_{f_u,\mathcal{P}}$ n'est pas fortement connexe,
+il y a donc deux n{\oe}uds
+$e_1$ et $e_2$ sans chemins entre eux.
+Il n'est ainsi pas possible de trouver un couple $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
+et $n \mathds{N}$ tel que $G_{f_u,\mathcal{P}}^n(e,(u,v))_1=e_2$.
+La boule ouverte $\mathcal{B}(e_2, 1/2)$ ne peut ainsi pas être atteinte
+depuis n'importe quel voisins de $e_1$:
+$G_{f_u,\mathcal{P}}$ n'est pas transitive.
+\end{proof}
+
+
+Montrons maintenant que
+\begin{lemma}
+Si $G_{f_u,\mathcal{P}}$ est fortement connexe, alors $G_{f_u,\mathcal{P}}$ est
+régulière sur $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
+\end{lemma}
+
+\begin{proof}
+Soit $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$.
+Comme dans la preuve du lemme~\ref{prop:trans}, soit $k_1 \in \mathds{N}$ tel
+que
+$$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
+$$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
+\subset \mathcal{B}(x,\varepsilon),$$
+et $y=G_{f_u,\mathcal{P}}^{k_1}(e,(u,v))$.
+$G_{f_u,\mathcal{P}}$ étant fortement connexe,
+il existe au moins un chemin entre l'état booléen $y_1$ de $y$ et $e$.
+Nommons $a_0, \hdots, a_{k_2}$ les arêtes d'un tel chemin.
+Le point
+$$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},...,
+ a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
+$$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$
+est un point périodique dans le voisinage $\mathcal{B}(x,\varepsilon)$ de $x$.
+\end{proof}
+
+$G_{f_u,\mathcal{P}}$ étant topologiquement transitive and régulière,
+on peut démontrer le théorème:
+\thmchoticitgfp*
+
