-
+
+\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 que
-\begin{lemma}
-$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
-\end{lemma}
+Montrons le théorème
+\distancedsxnp*
\begin{proof}
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 nules et correspondent à $|u^0-\check{u}^0|$,
+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
-bloc engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$,
+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)$).
Montrons que:
\begin{lemma}
-Le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$
+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)$.
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 entrainera la propriété de transitivité classique.
+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
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 regulière,
-on peut conclure le théorème:
-
-
-\begin{theorem}
-La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur
- $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si
-graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$
-est fortement connexe.
-\end{theorem}
+$G_{f_u,\mathcal{P}}$ étant topologiquement transitive and régulière,
+on peut démontrer le théorème:
+\thmchoticitgfp*
