Relecture Sylvain avec commentaires/questions

diff --git a/chaos.tex b/chaos.tex
index 511a11acab24bdb7d8554928d7afb8cf1c2f5afa..ec2723aef86663af75c4d60192d7e8fab1104041 100644 (file)
--- a/chaos.tex
+++ b/chaos.tex
@@ -245,6 +245,7 @@ $\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digi
 
 
 
 
 
 

+\newcommand{\ns}{$\hspace{.1em}$}

 
 \begin{xpl}
 Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=2$), and that
 
 \begin{xpl}
 Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=2$), and that


@@ -262,7 +263,7 @@ $\check{s}=\left\{
 \end{array}
 \right.$.
 
 \end{array}
 \right.$.
 

-So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
+So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.01\ns00\ns04\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns01\ns10\ns05 ...$

 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
 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


@@ -479,7 +480,7 @@ Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0,
 Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
 2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
 That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
 Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
 2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
 That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$

-and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
+and $n\in \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$

 cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive.
 \end{proof}
 
 cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive.
 \end{proof}
 


@@ -498,7 +499,7 @@ $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^
 $$\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),$$
 and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
 $$\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),$$
 and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,

-there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
+there is at least a path from the Boolean state $y_1$ of $y$ and $e$ \ANNOT{Phrase pas claire : "from ... " mais pas de "to ..."}.

 Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
 Then the point:
 $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
 Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
 Then the point:
 $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 

diff --git a/conclusion.tex b/conclusion.tex
index a9bf6364160a8485b4009b1fe6eda6ff36f96866..2705043fe2335fd223c705c26e86b2bc2409800a 100644 (file)
--- a/conclusion.tex
+++ b/conclusion.tex
@@ -14,11 +14,11 @@ applied here to generate function $f$ with strongly connected
 $\Gamma_{\mathcal{P}}(f)$. 
 The iterated map inside the generator is built by first removing from a 
 $\mathsf{N}$-cube an Hamiltonian path and next 
 $\Gamma_{\mathcal{P}}(f)$. 
 The iterated map inside the generator is built by first removing from a 
 $\mathsf{N}$-cube an Hamiltonian path and next 

-adding  a self loop to each vertex. 
-The PRNG can thus be seen as a random walks of length in $\mathsf{P}$
-into  $\mathsf{N}$ this new cube.
-We furthermore have exhibit a bound on the number of iterations 
-that are sufficient to obtain a uniform distribution of the output.
+by adding  a self loop to each vertex. 
+The PRNG can thus be seen as a random walk of length in $\mathsf{P}$
+into  this new $\mathsf{N}$-cube.
+We furthermore have exhibited a bound on the number of iterations 
+that is sufficient to obtain a uniform distribution of the output.

 Finally,  experiments through the  NIST battery have shown that
 the statistical properties are almost established for
 $\mathsf{N} = 4, 5, 6, 7, 8$.
 Finally,  experiments through the  NIST battery have shown that
 the statistical properties are almost established for
 $\mathsf{N} = 4, 5, 6, 7, 8$.

diff --git a/generating.tex b/generating.tex
index 3d22441cf0684057f949b1c90f68ed18474f7a97..d512a9803b59c27f0a95a6a6bff958b887a8f30d 100644 (file)
--- a/generating.tex
+++ b/generating.tex
@@ -45,10 +45,10 @@ cycle is removed, is doubly stochastic.
 Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian 
 cycle is removed.
 Let $f$ be the corresponding function.
 Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian 
 cycle is removed.
 Let $f$ be the corresponding function.

-The question which remains to solve is
-can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected.
+The question which remains to solve is:
+\emph{can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected?}

 
 

-The answer is indeed positive. We furtheremore have the following strongest 
+The answer is indeed positive. We furthermore have the following strongest 

 result.
 \begin{thrm}
 There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
 result.
 \begin{thrm}
 There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.


@@ -58,7 +58,7 @@ There is an arc $(x,y)$ in the
 graph $\Gamma_{\{b\}}(f)$ if and only if $M^b_{xy}$ is positive
 where $M$ is the Markov matrix of $\Gamma(f)$.
 It has been shown in~\cite[Lemma 3]{bcgr11:ip}  that $M$ is regular.
 graph $\Gamma_{\{b\}}(f)$ if and only if $M^b_{xy}$ is positive
 where $M$ is the Markov matrix of $\Gamma(f)$.
 It has been shown in~\cite[Lemma 3]{bcgr11:ip}  that $M$ is regular.

-There exists thus $b$ such there is an arc between any $x$ and $y$.
+Thus, there exists $b$ such that there is an arc between any $x$ and $y$.

 \end{proof}
 
 This section ends with the idea of removing a Hamiltonian cycle in the 
 \end{proof}
 
 This section ends with the idea of removing a Hamiltonian cycle in the 


@@ -66,12 +66,12 @@ $\mathsf{N}$-cube.
 In such a context, the Hamiltonian cycle is equivalent to a Gray code.
 Many approaches have been proposed a way to build such codes, for instance 
 the Reflected Binary Code. In this one, one of the bits is switched 
 In such a context, the Hamiltonian cycle is equivalent to a Gray code.
 Many approaches have been proposed a way to build such codes, for instance 
 the Reflected Binary Code. In this one, one of the bits is switched 

-exactly $2^{\mathsf{N}-}$ for a $\mathsf{N}$-length cycle. 
+exactly $2^{\mathsf{N}-}$ \ANNOT{formule incomplète : $2^{\mathsf{N}-1}$ ??} for a $\mathsf{N}$-length cycle. 

 
 %%%%%%%%%%%%%%%%%%%%%
 
 The function that is built 
 
 %%%%%%%%%%%%%%%%%%%%%
 
 The function that is built 

-from the 
+from the \ANNOT{Phrase non terminée}

 
 The next section presents how to build balanced Hamiltonian cycles in the 
 $\mathsf{N}$-cube with the objective to embed them into the 
 
 The next section presents how to build balanced Hamiltonian cycles in the 
 $\mathsf{N}$-cube with the objective to embed them into the 

diff --git a/hamilton.tex b/hamilton.tex
index dc19f08390c9f4a29042af57abbf099de4d86769..40e4ba32a16114bea72a22feae672a4bd9695afe 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -1,5 +1,5 @@
 Many approaches have been developed to solve the problem of building
 Many approaches have been developed to solve the problem of building

-a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 
+a Gray code in a $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 

 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 


@@ -16,10 +16,10 @@ and an algorithm that establishes locally balanced Gray codes is given.
  
 The current context is to provide a function 
 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian 
  
 The current context is to provide a function 
 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian 

-cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
+cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated

 $b$ times to produce a pseudo random number,
 \textit{i.e.} a vertex in the 
 $b$ times to produce a pseudo random number,
 \textit{i.e.} a vertex in the 

-$\mathsf{N}$ cube.
+$\mathsf{N}$-cube.

 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 To reduce the number of iterations, the provided Gray code
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 To reduce the number of iterations, the provided Gray code


@@ -50,7 +50,7 @@ have mainly allowed them to prove two properties.
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
 The latter states that for every $\mathsf{N}$ there 
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
 The latter states that for every $\mathsf{N}$ there 

-exists a Gray code such that all transition count numbers are 
+exists a Gray code such that all transition count numbers 

 are 2-powers whose exponents are either equal
 or differ from each other by 1.
 However, the authors do not prove that the approach allows to build 
 are 2-powers whose exponents are either equal
 or differ from each other by 1.
 However, the authors do not prove that the approach allows to build 


@@ -83,7 +83,7 @@ two elements have been exchanged.
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 

-$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
+$S_{\mathsf{N}}$ is the transition sequence of a cyclic $\mathsf{N}$-bits Gray code 

 if $S_{\mathsf{N}-2}$ is. 
 However, the step~(\ref{item:nondet}) is not a constructive 
 step that precises how to select the subsequences which ensures that 
 if $S_{\mathsf{N}-2}$ is. 
 However, the step~(\ref{item:nondet}) is not a constructive 
 step that precises how to select the subsequences which ensures that 


@@ -120,7 +120,7 @@ $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray co
 Let now  
 $L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$
 $0100, 1100, 1101, 1001, 1011, 1010, 1000$
 Let now  
 $L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$
 $0100, 1100, 1101, 1001, 1011, 1010, 1000$

-be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ $\textit{TC}_4$ is equal to 4 everywhere, this code
+be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code

 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  


@@ -133,7 +133,7 @@ the code is neither balanced nor totally balanced.
 
 \begin{thrm}\label{prop:balanced}
 Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by
 
 \begin{thrm}\label{prop:balanced}
 Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by

-$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$. 
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. 

 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 

diff --git a/main.pdf b/main.pdf
index 4f393a062c5fbaec199b8b1b95bb334f62f5d7e1..c5051f537bd4cd2c5b25c7eea58422a02b4a5273 100644 (file)
Binary files a/main.pdf and b/main.pdf differ

diff --git a/main.tex b/main.tex
index 13d2e2dcbe04df9a317c1bd021559ef80e8f4e34..4a5ede14e08c3e3eb88d9b958a8b88b50d6f2ee6 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -35,16 +35,17 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}

+\newcommand{\danger}{!!}

 \newcommand{\ANNOT}[1]{
   ~\linebreak
   \centerline{
 \newcommand{\ANNOT}[1]{
   ~\linebreak
   \centerline{

-    {\Huge{\danger}}
+    {\Huge{$\Rightarrow$}}

     \large\fcolorbox{black}{bleuclair}{
       \begin{minipage}[h]{.8\linewidth}
         #1
       \end{minipage}
     }
     \large\fcolorbox{black}{bleuclair}{
       \begin{minipage}[h]{.8\linewidth}
         #1
       \end{minipage}
     }

-    {\Huge{\danger}}
+    {\Huge{$\Leftarrow$}}

   }
 }
 
   }
 }
 

diff --git a/prng.tex b/prng.tex
index 6af2803ad6918b63ebfd02793a74d5e87399ab41..ae733d9685b3a679fbf0206207d07dd34c8636f7 100644 (file)
--- a/prng.tex
+++ b/prng.tex
@@ -54,7 +54,7 @@ it preserves this property.
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 the functions according to the method 
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 the functions according to the method 

-given in Sect.~\ref{sec:SCCfunc}. 
+given in Sect.~\ref{sec:SCCfunc} and~\ref{sec:hamilton}. 

 % MENTION FILTRAGE POSSIBLE LORS DE CONSTRUCTION... (SCV) 
 For each $\mathsf{N}$, we have then restricted this evaluation to the function 
 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) 
 % MENTION FILTRAGE POSSIBLE LORS DE CONSTRUCTION... (SCV) 
 For each $\mathsf{N}$, we have then restricted this evaluation to the function 
 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) 

diff --git a/stopping.tex b/stopping.tex
index 989bb9eee1f7cb01b79d4b91bf71f0cc22f1e8f4..75143419beff3d5ac218fb587c8e322435ee45a7 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -65,12 +65,13 @@ distribution induced by the $X$-th row of $P$. If the Markov chain induced by
 $P$ has a stationary distribution $\pi$, then we define
 $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$
 
 $P$ has a stationary distribution $\pi$, then we define
 $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$
 

+\ANNOT{incohérence de notation $X$ : entier ou dans $B^N$ ?}

 and
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 
 Intuitively speaking, $t_{\rm mix}$ is a mixing time 
 and
 
 $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 
 Intuitively speaking, $t_{\rm mix}$ is a mixing time 

-\textit{i.e.}, is the time until the matrix $X$ of a Markov chain  
+\textit{i.e.}, is the time until the matrix $X$ \ANNOT{pas plutôt $P$ ?} of a Markov chain  

 is $\epsilon$-close to a stationary distribution.
 
 
 is $\epsilon$-close to a stationary distribution.
 
 


@@ -114,7 +115,7 @@ $$\P_X(X_\tau=Y)=\pi(Y).$$
 \subsection{Upper bound of Stopping Time}\label{sub:stop:bound}
 
 
 \subsection{Upper bound of Stopping Time}\label{sub:stop:bound}
 
 

-A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
+A stopping time $\tau$ is a \emph{strong stationary time} if $X_{\tau}$ is

 independent of $\tau$. 
 
 
 independent of $\tau$. 
 
 


@@ -401,7 +402,7 @@ $\textit{fair}\leftarrow\emptyset$\;
 \end{algorithm}
 
 Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 
 \end{algorithm}
 
 Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, 

-10 functions have been generaed according to method presented in section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
+10 functions have been generated according to method presented in section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$

 is executed 10000 times with a random seed. The Figure~\ref{fig:stopping:moy}
 summarizes these results. In this one, a circle represents the 
 approximation of $E[\ts]$ for a given $\mathsf{N}$.
 is executed 10000 times with a random seed. The Figure~\ref{fig:stopping:moy}
 summarizes these results. In this one, a circle represents the 
 approximation of $E[\ts]$ for a given $\mathsf{N}$.