X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/2bf0bca226facdce323e96552021bf90952eefce..refs/heads/master:/annexePreuveDistribution.tex?ds=inline diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex index 8de466c..af03fed 100644 --- 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 @@ -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} -\begin{Proof} +\begin{proof} 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. -\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}). @@ -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. -\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} @@ -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$ -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)$). @@ -85,3 +74,95 @@ et en vérifiant tous les $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. 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* + +