stopping time jet 1

[hdrcouchot.git] / 15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index e4f88582bd0509d851b304af9065da937d114af5..010beb92fd0d5d96d3345424c18899bb1fd2f4d9 100644 (file)
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -146,8 +146,8 @@ et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
 Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter}
 vérifient les hypothèses du théorème~\ref{th:Adrien}. 
 Leurs graphes d'itérations
 Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter}
 vérifient les hypothèses du théorème~\ref{th:Adrien}. 
 Leurs graphes d'itérations

-sont donc fortement connexes, ce que l'on peut vérifier aux figures
-\ref{fig:g:iter} et \ref{fig:h:iter}.
+sont donc fortement connexes, ce que l'on peut vérifier aux figures~\ref{fig:g:iter} 
+et~\ref{fig:h:iter}.

 \textit{A priori}, ces deux fonctions pourraient être intégrées
 dans un générateur de nombres pseudo aléatoires. Montrons que ce n'est pas le cas pour $g$ et 
 que cela l'est pour $h$.
 \textit{A priori}, ces deux fonctions pourraient être intégrées
 dans un générateur de nombres pseudo aléatoires. Montrons que ce n'est pas le cas pour $g$ et 
 que cela l'est pour $h$.


@@ -332,15 +332,21 @@ ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
 -- autrement dit, où la déviation par rapport à la distribution uniforme --
  est inférieure 
 à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
 -- autrement dit, où la déviation par rapport à la distribution uniforme --
  est inférieure 
 à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour

- $b$. Ainsi, on a 
-$$
+ $b$. 
+Ainsi, on a 
+\begin{equation}

 b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
 \{
 \min \{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
 \}
 \}. 
 b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
 \{
 \min \{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
 \}
 \}. 

-$$
+\label{eq:mt:ex}
+\end{equation}
+
+\noindent Par la suite, ce nombre sera appelé \emph{temps de mélange}.
+
+

 
 \begin{figure}%[h]
   \begin{center}
 
 \begin{figure}%[h]
   \begin{center}


@@ -517,45 +523,76 @@ $\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_
 où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
 \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
 \begin{itemize}
 où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
 \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
 \begin{itemize}

-\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. The Hamming distance
-on their binary decomposition, that is, the number of dissimilar binary digits, constitutes the integral
-part of $d(X,\check{X})$.
-\item The fractional part is constituted by the differences between $v^0$ and $\check{v}^0$, followed by the differences
-between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, followed by 
- differences between $v^1$ and $\check{v}^1$, followed by the differences
-between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and  $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
-More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
+\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. 
+La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les 
+décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le 
+le nombre de bits qu'elles ont de différent) constitue 
+la partie entière de $d(X,\check{X})$.
+\item la partie décimale est construite à partir des différences entre 
+$v^0$ et $\check{v}^0$, suivie des différences entre les séquences finies
+$u^0, u^1, \hdots, u^{v^0-1}$ et  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, suivie par les différences entre  $v^1$ et $\check{v}^1$, 
+suivie par les différences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et
+$\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
+
+Plus précisemment, soit 
+$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et 
+$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.

 \begin{itemize}
 \begin{itemize}

-\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits).
-\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first
-digits are $|u^0-\check{u}^0|$. They are followed by 
-$|u^1-\check{u}^1|$ written with $n$ digits, etc.
+\item Les $p$ premiers éléments de $d(x,\check{x})$ sont $|v^0-\check{v}^0|$ 
+  écrits en base 10 et sur $p$ indices;
+\item les $n\times \max{(\mathcal{P})}$ éléments suivants servent 
+  à évaluer de combien $u^0, u^1, \hdots, u^{v^0-1}$ diffère de 
+  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. 
+  Les $n$ premiers éléments sont $|u^0-\check{u}^0|$. Il sont suivis de 
+$|u^1-\check{u}^1|$ écrits à l'aide de $n$ éléments, etc.

 \begin{itemize}
 \begin{itemize}

-\item If
-$v^0=\check{v}^0$, then the process is continued until $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ and the fractional
-part of $d(X,\check{X})$ is completed by 0's until reaching
-$p+n\times \max{(\mathcal{P})}$ digits.
-\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$  blocs of $n$
-digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
-$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required.
-\item The case $v^0>\check{v}^0$ is dealt similarly.
+\item Si
+$v^0=\check{v}^0$,
+alors le processus se continue jusqu'à $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ et la 
+partie décimale de $d(X,\check{X})$ est complétée par des 0
+jusqu'à atteindre 
+$p+n\times \max{(\mathcal{P})}$ éléments.
+\item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$  blocs de $n$
+éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
+$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivi par des 0, si besoin.
+\item Le cas $v^0>\check{v}^0$ est similaire, et donc omis

 \end{itemize}
 \end{itemize}

-\item The next $p$ digits are $|v^1-\check{v}^1|$, etc.
+\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.

 \end{itemize}
 \end{itemize}
 
 
 \end{itemize}
 \end{itemize}
 
 

+La fonction $d$ peut se formaliser comme suit:
+$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
+où: % $p=\max \mathcal{P}$ and:
+\begin{itemize}
+\item $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming,
+\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline 
+$$\begin{array}{rcl}
+ d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
+   \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
+   \bigg(|v^k - \check{v}^k|  \\
+   & & + \left| \sum_{l=0}^{v^k-1} 
+       \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
+       \sum_{l=0}^{\check{v}^k-1} 
+       \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
+\end{array}
+$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$
+\end{itemize}
+

 
 
 \begin{xpl}
 
 
 \begin{xpl}

-Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that
+On considère par exemple 
+$\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ ($\mathsf{p}$ vaut ainsi $3$), 
+et 

 $s=\left\{
 \begin{array}{l}
 u=\underline{6,} ~ \underline{11,5}, ...\\
 v=1,2,...
 \end{array}
 \right.$
 $s=\left\{
 \begin{array}{l}
 u=\underline{6,} ~ \underline{11,5}, ...\\
 v=1,2,...
 \end{array}
 \right.$

-while
+avec 

 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\
 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\


@@ -563,68 +600,152 @@ $\check{s}=\left\{
 \end{array}
 \right.$.
 
 \end{array}
 \right.$.
 

-So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
-Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, 
-and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate
-at most $\max{(\mathcal{P})}$ times, we must complete this
-value by some 0's in such a way that the obtained result
-has $n\times \max{(\mathcal{P})}=22$ digits, that is: 
-0600000000000000000000. Similarly, the $\check{v}^0=2$ first
-terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their
-difference is equal to 0004000000000000000000. These digits are concatenated to 01, and
-we start again with the remainder of the sequences.
+Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
+En effet, les $p=2$ premiers éléments sont  01, c'est-à-dire 
+$|v^0-\check{v}^0|=1$, 
+et on utilise $p$ éléments pour représenter cette différence
+(Comme $\mathcal{P}=\{1,2,11\}$, cette différence peut valoir 10).
+On prend alors le $v^0=1$ premier terme de $u$, 
+chaque terme étant codé sur $n=2$ éléments, soit 06.
+Comme on itère au plus $\max{(\mathcal{P})}$ fois, 
+on complète cette valeur par des 0 de sorte que 
+la chaine obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit:
+0600000000000000000000. 
+De manière similaire, les $\check{v}^0=2$ premiers
+termes de $\check{u}$ sont représentés par 
+0604000000000000000000.
+LA valeur absolue de leur différence est égale à 
+0004000000000000000000.
+Ces éléments sont concaténés avec 01. On peut construire alors le reste de 
+la séquence.

 \end{xpl}
 
 
 \begin{xpl}
 \end{xpl}
 
 
 \begin{xpl}

-Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that
-
-$s=\left\{
+On considère à présent que  $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que
+$$s=\left\{

 \begin{array}{l}
 u=\underline{6,7,} ~ \underline{4,2,} ...\\
 v=2,2,...
 \end{array}
 \begin{array}{l}
 u=\underline{6,7,} ~ \underline{4,2,} ...\\
 v=2,2,...
 \end{array}

-\right.$
-while
-$\check{s}=\left\{
+\right.$$
+avec
+$$\check{s}=\left\{

 \begin{array}{l}
 \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\
 \check{v}=7,2,...
 \end{array}
 \begin{array}{l}
 \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\
 \check{v}=7,2,...
 \end{array}

-\right.$
+\right.
+$$

 
 

-So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
-and $|9800000-4200000| = 5600000$.
+Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, 
+puisque 
+$|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
+et $|9800000-4200000| = 5600000$.

 \end{xpl}
 
 
 
 \end{xpl}
 
 
 

-$d$ can be more rigorously written as follows:
-$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
-where: % $p=\max \mathcal{P}$ and:
+On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}.
+\begin{lemma}
+$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
+\end{lemma}
+
+
+\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant  $\textsc{giu}(f)$}
+
+A partir de  $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on 
+definit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante:

 \begin{itemize}
 \begin{itemize}

-\item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance,
-\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline 
-$$\begin{array}{rcl}
- d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
-   \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
-   \bigg(|v^k - \check{v}^k|  \\
-   & & + \left| \sum_{l=0}^{v^k-1} 
-       \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
-       \sum_{l=0}^{\check{v}^k-1} 
-       \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
-\end{array}
-$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$
+\item les n{\oe}uds sont les  $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$,
+%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
+%  having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
+\item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de 
+$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), 
+chaque $u_k$ de la suite appartient à $[\mathsf{N}]$ et 
+$y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.

 \end{itemize}
 \end{itemize}

+Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$.

 
 
 
 

-Let us show that,
-\begin{prpstn}
-$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
-\end{prpstn}

 
 
 
 

-\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant  $\textsc{giu}(f)$}
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
+      \begin{minipage}{0.30\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h2prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h2prng}
+    }
+    \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h3prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h3prng}
+    }
+    \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h23prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h23prng}
+    }
+
+    \end{center}
+    \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
+    %\label{fig:xplgraphIter}
+  \end{figure}
+
+
+
+
+\begin{xpl}
+On reprend l'exemple où $\mathsf{N}=2$ et 
+$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détaillé 
+à la section~\ref{sub:prng:unif}.
+
+Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}.
+Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$  et
+$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. 
+Le premier (repsectivement le second) 
+illustre le comportement du générateur lorsque qu'on itère exactement 
+2 fois (resp. 3 fois) puis qu'on affiche le résultat.
+Le dernier donnerait le comportement d'un générateur qui s'autoriserait 
+à itérer en interne systématiquement 2 ou trois fois avant de retourner un résultat.
+
+\end{xpl}
+

 
 \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
 
 
 \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
 

+Le théorème suivant, similaire à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
+est prouvé en annexes~\ref{anx:generateur}.
+
+\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}
+On alors corollaire suivant 
+
+\begin{corollary}
+  Le générateur de nombre pseudo aléatoire détaillé 
+  à l'algorithme~\ref{CI Algorithm}
+  n'est pas chaotique 
+  sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation.
+\end{corollary}
+\begin{proof}
+  Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$.
+  Que $b$ soit pair ou impair,  $\textsc{giu}_{\mathcal{b}}(f)$
+  n'est pas fortement connexe.
+\end{proof}
+
+