après remarques tof

[hdrcouchot.git] / annexePreuveDistribution.tex

diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex
index f53e3b9f7d3f277ff2224884968a6abbfec21280..af03fed84a474785dbc7c8d940ce76452a21fdb4 100644 (file)
--- a/annexePreuveDistribution.tex
+++ b/annexePreuveDistribution.tex
@@ -1,4 +1,5 @@
- 
+
+\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 
 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 


@@ -8,7 +9,7 @@ Alors $M$ est une matrice stochastique régulière si et seulement si
 $\textsc{giu}(f)$ est fortement connexe.
 \end{lemma}
 
 $\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. 
 On remarque tout d'abord que $M$ 
 est une matrice stochastique par construction.
 Supposons $M$ régulière. 


@@ -28,22 +29,11 @@ on peut conclure que, si
 $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.
 $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}).
   $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}).


@@ -53,14 +43,13 @@ Ces résultats permettent formuler et de prouver le théorème suivant:
   la somme des valeurs de chaque colonne de $M$  est 1, 
   \textit{i.e.} si et seulement si 
   $M$ est  doublement  stochastique.
   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}
 
 
 \begin{proof}


@@ -74,10 +63,10 @@ $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$ 
 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 
 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)$). 
 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)$). 


@@ -90,7 +79,7 @@ aussi.
 
 Montrons que: 
 \begin{lemma}
 
 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)$. 
 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)$. 


@@ -103,7 +92,7 @@ Soit $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v}))
 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}$: 
 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 
 On peut supposer que $\varepsilon <1$ sans perte de généralité.
 
 Soit $(E,(U,V))$ les éléments de  $y$. Comme 


@@ -172,15 +161,8 @@ $$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v
 est un point périodique dans le voisinage $\mathcal{B}(x,\varepsilon)$ de $x$.
 \end{proof}
 
 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*