+\newcommand{\ns}{$\hspace{.1em}$}
\begin{xpl}
Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=2$), and that
\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
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}
$$\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|},...,
$\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$.
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.
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
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
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 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
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
\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
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
\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)$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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$}}
}
}
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}))
$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.
\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$.
\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}$.
