annexePreuveDistribution.tex

   1
   2 Considérons le lemme technique suivant:
   3 \begin{lemma}\label{lem:stoc}
   4 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
   5 $2^n\times 2^n$  définie par
   6 $M = \frac{1}{n}\check{M}$.
   7 Alors $M$ est une matrice stochastique régulière si et seulement si
   8 $\textsc{giu}(f)$ est fortement connexe.
   9 \end{lemma}
  10
  11 \begin{Proof}
  12 On remarque tout d'abord que $M$
  13 est une matrice stochastique par construction.
  14 Supposons $M$ régulière.
  15 Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
  16 1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
  17 Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
  18 dans $\textsc{giu}(f)$ et puisque ce nombre est positif, alors
  19 $\textsc{giu}(f)$ est fortement connexe.
  20
  21 Réciproquement si $\textsc{giu}(f)$
  22 est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
  23 Il existe donc
  24 $k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.
  25 Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que
  26 $\check{M}_{ij}^{l\times  k_{ij}}>0$,
  27 on peut conclure que, si
  28 $k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
  29 $\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$.
  30 Ainsi, $\check{M}$ et donc $M$ sont régulières.
  31 \end{Proof}
  32
  33 Ces résultats permettent formuler et de prouver le théorème suivant:
  34
  35 \begin{theorem}
  36   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son
  37   graphe d'itérations , $\check{M}$ sa matrice d'adjacence
  38   et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
  39   Si $\textsc{giu}(f)$ est fortement connexe, alors
  40   la sortie du générateur de nombres pseudo aléatoires détaillé par
  41   l'algorithme~\ref{CI Algorithm} suit une loi qui
  42   tend vers la distribution uniforme si
  43   et seulement si  $M$ est une matrice doublement stochastique.
  44 \end{theorem}
  45
  46 \begin{Proof}
  47   $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc})
  48   qui a un unique vecteur de probabilités stationnaire
  49   (Théorème \ref{th}).
  50   Soit $\pi$  défini par
  51   $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
  52   On a  $\pi M = \pi$ si et seulement si
  53   la somme des valeurs de chaque colonne de $M$  est 1,
  54   \textit{i.e.} si et seulement si
  55   $M$ est  doublement  stochastique.
  56 \end{Proof}
  57
  58
  59
  60 Montrons que
  61 \begin{lemma}
  62 $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
  63 \end{lemma}
  64
  65
  66 \begin{proof}
  67  $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming.
  68  Prouvons que
  69  $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est aussi une distance;
  70 $d$ sera ainsi une distance comme somme de deux distances.
  71  \begin{itemize}
  72 \item De manière évidente, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, et si $s=\check{s}$, alors
  73 $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$.
  74 Réciproquement si $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, alors
  75 $\forall k \in \mathds{N}, v^k=\check{v}^k$ d'après la définition de $d$.
  76 Or les éléments entre les positions $p+1$ et  $p+n$
  77 sont nules et correspondent à $|u^0-\check{u}^0|$,
  78 on peut conclure que $u^0=\check{u}^0$.
  79 On peut étendre ce résultat aux $n \times \max{(\mathcal{P})}$ premiers
  80 bloc engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$,
  81 et en vérifiant tous les  $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
  82  \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est évidemment  symétrique
  83 ($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$).
  84 \item l'inégalité triangulaire est établie puisque la valeur absolue la vérifie
  85 aussi.
  86  \end{itemize}
  87 \end{proof}
  88
  89
  90
  91 Montrons que:
  92 \begin{lemma}
  93 Le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$
  94 est fortement connexe si et seulement si
  95 la fonction $G_{f_u,\mathcal{P}}$ est topologiquement transitive sur
  96 $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$.
  97 \end{lemma}\label{prop:trans}
  98
  99 \begin{proof}
 100 Supposons tout d'abord que  $G_{f_u,\mathcal{P}}$ fortement connexe.
 101 Soit $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v}))
 102 \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$.
 103 On cherche un point $y$ dans une boule ouverte $\mathcal{B}(x,\varepsilon )$
 104 et un nombre
 105 $n_0 \in \mathds{N}$ tels que $G_{f_u,\mathcal{P}}^{n_0}(y)=\check{x}$:
 106 Cette transitivité forte entrainera la propriété de transitivité classique.
 107 On peut supposer que $\varepsilon <1$ sans perte de généralité.
 108
 109 Soit $(E,(U,V))$ les éléments de  $y$. Comme
 110 $y$ doit appartenir à $\mathcal{B}(x,\varepsilon)$ et  $\varepsilon < 1$,
 111 $E$ est égal à $e$.
 112 Soit $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
 113 La distance $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ est inférieure à
 114 $\varepsilon$: les  $k$ premiers éléments de la partie décimale de
 115 $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ sont nuls.
 116 Soit $k_1$ le plus petit entier tel que, si $V^0=v^0$, ...,  $V^{k_1}=v^{k_1}$,
 117 alors $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
 118 Alors $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
 119 En d'autres mots, chaque $y$ de la forme $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
 120 (v^0, ..., v^{k_1}))$ est dans $\mathcal{B}(x,\varepsilon)$.
 121
 122 Soit $y^0$ un tel point et $z=G_{f_u,\mathcal{P}}^{k_1}(y^0) = (e',(u',v'))$.
 123 $G_{f_u,\mathcal{P}}$ étant fortement connexe,
 124 il existe un chemin entre $e'$ et $\check{e}$.
 125 Soit $a_0, \hdots, a_{k_2}$ les arêtes visitées le long de ce chemin.
 126 On fixe $V^{k_1}=|a_0|$
 127 (le nombre de termes dans la séquence finie $a_1$),
 128 $V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, et
 129 $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}$,
 130 $U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,\ldots
 131
 132 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|},...,
 133  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
 134  $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
 135  |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$.
 136 Ainsi
 137  $y\in \mathcal{B}(x,\varepsilon)$
 138  et $G_{f}^{k_1+k_2}(y)=\check{x}$.
 139
 140 Réciproquement, si  $G_{f_u,\mathcal{P}}$ n'est pas fortement connexe,
 141 il y a donc deux n{\oe}uds
 142 $e_1$ et $e_2$ sans chemins entre eux.
 143 Il n'est ainsi pas possible de trouver un couple $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
 144 et $n \mathds{N}$ tel que  $G_{f_u,\mathcal{P}}^n(e,(u,v))_1=e_2$.
 145 La boule ouverte  $\mathcal{B}(e_2, 1/2)$ ne peut ainsi pas être atteinte
 146 depuis n'importe quel voisins de $e_1$:
 147 $G_{f_u,\mathcal{P}}$ n'est pas transitive.
 148 \end{proof}
 149
 150
 151 Montrons maintenant que
 152 \begin{lemma}
 153 Si $G_{f_u,\mathcal{P}}$ est fortement connexe, alors $G_{f_u,\mathcal{P}}$ est
 154 régulière sur  $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 155 \end{lemma}
 156
 157 \begin{proof}
 158 Soit $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$.
 159 Comme dans la preuve du lemme~\ref{prop:trans}, soit $k_1 \in \mathds{N}$ tel
 160 que
 161 $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
 162 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 163 \subset \mathcal{B}(x,\varepsilon),$$
 164 et $y=G_{f_u,\mathcal{P}}^{k_1}(e,(u,v))$.
 165 $G_{f_u,\mathcal{P}}$ étant fortement connexe,
 166 il existe au moins un chemin entre l'état booléen $y_1$ de $y$ et $e$.
 167 Nommons $a_0, \hdots, a_{k_2}$ les arêtes d'un tel chemin.
 168 Le point
 169 $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},...,
 170  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
 171 $$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}|,...))$$
 172 est un point périodique dans le voisinage $\mathcal{B}(x,\varepsilon)$ de $x$.
 173 \end{proof}
 174
 175 $G_{f_u,\mathcal{P}}$ étant topologiquement transitive and regulière,
 176 on peut conclure le théorème:
 177
 178
 179 \begin{theorem}
 180 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur
 181  $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si
 182 graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$
 183 est fortement connexe.
 184 \end{theorem}
 185
 186