From: Sylvain C-V Date: Mon, 27 Jun 2016 18:58:21 +0000 (+0200) Subject: Relecture Sylvain avec commentaires/questions X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/commitdiff_plain/31468b39be240f447015be22c252d515b2dcfdac Relecture Sylvain avec commentaires/questions --- diff --git a/chaos.tex b/chaos.tex index 511a11a..ec2723a 100644 --- 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 @@ -262,7 +263,7 @@ $\check{s}=\left\{ \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 @@ -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}}$ -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} @@ -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, -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|},..., diff --git a/conclusion.tex b/conclusion.tex index a9bf636..2705043 100644 --- 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 -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$. diff --git a/generating.tex b/generating.tex index 3d22441..d512a98 100644 --- 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. -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. @@ -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. -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 @@ -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 -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 -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 diff --git a/hamilton.tex b/hamilton.tex index dc19f08..40e4ba3 100644 --- a/hamilton.tex +++ b/hamilton.tex @@ -1,5 +1,5 @@ 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, @@ -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 -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 -$\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 @@ -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 -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 @@ -83,7 +83,7 @@ two elements have been exchanged. \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 @@ -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$ -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 @@ -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 -$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)$ diff --git a/main.pdf b/main.pdf index 4f393a0..c5051f5 100644 Binary files a/main.pdf and b/main.pdf differ diff --git a/main.tex b/main.tex index 13d2e2d..4a5ede1 100644 --- a/main.tex +++ b/main.tex @@ -35,16 +35,17 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \definecolor{bleuclair}{rgb}{0.75,0.75,1.0} +\newcommand{\danger}{!!} \newcommand{\ANNOT}[1]{ ~\linebreak \centerline{ - {\Huge{\danger}} + {\Huge{$\Rightarrow$}} \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 6af2803..ae733d9 100644 --- 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 -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})) diff --git a/stopping.tex b/stopping.tex index 989bb9e..7514341 100644 --- 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}.$$ +\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 -\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. @@ -114,7 +115,7 @@ $$\P_X(X_\tau=Y)=\pi(Y).$$ \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$. @@ -401,7 +402,7 @@ $\textit{fair}\leftarrow\emptyset$\; \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}$.