balanced Gray codes. In the transition sequence of these codes,
the number of transitions of each element must differ
at most by 2.
-This uniformity is a global property on the cycle, \textit{i.e.}
+This uniformity is a global property on the cycle, \textit{i.e.},
a property that is established while traversing the whole cycle.
On the opposite side, when the objective is to follow a subpart
of the Gray code and to switch each element approximately the
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
+$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing an Hamiltonian
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 pseudorandom number,
+\textit{i.e.}, a vertex in the
$\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
+to provide an uniform output distribution.
+To reduce the number of iterations, it can be claimed
+that the provided Gray code
should ideally possess both balanced and locally balanced properties.
However, none of the two algorithms is compatible with the second one:
balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
where the authors have explicitly shown how to construct such a subsequence.
Finally the authors of~\cite{ZanSup04} have presented
the \emph{Robinson-Cohn extension}
-algorithm. There rigorous presentation of this one
-have mainly allowed them to prove two properties.
+algorithm. Their rigorous presentation of this one
+has 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
Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
$S_{\mathsf{N}-2}$. What follows is the
\emph{Robinson-Cohn extension} method~\cite{ZanSup04}
-which produces a $n$-bits Gray code.
+which produces a $\mathsf{N}$-bits Gray code.
\begin{enumerate}
\item \label{item:nondet}Let $l$ be an even positive integer. Find
\begin{xpl}
-Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to
+Let $L^*=000,100,101,001,011,111,$ $110,010$ be the Gray code that corresponds to
the Hamiltonian cycle that has been removed in $f^*$.
Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is
$\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and $\textit{TC}_3(3)=4$. Such a Gray code is balanced.
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
+$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
is thus totally balanced.
On the contrary, for the standard $4$-bits Gray code
-$L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$
-$1101,1111,1110,1010,1011,1001,1000$,
+$L^{\textit{st}}=0000,0001,0011,$
+$0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000$,
we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
the code is neither balanced nor totally balanced.
\end{xpl}
The proof is done by induction on $\mathsf{N}$. Let us immediately verify
-that it is established for both odd and even smallest values, \textit{i.e.}
+that it is established for both odd and even smallest values, \textit{i.e.},
$3$ and $4$.
-For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have: $S_1=1,1$, $l=2$, $u_0 = \emptyset$, and $v=\emptyset$.
+For the initial case where $\mathsf{N}=3$, \textit{i.e.}, $\mathsf{N-2}=1$ we successively have: $S_1=1,1$, $l=2$, $u_0 = \emptyset$, and $v=\emptyset$.
Thus again the algorithm successively produces
$U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$.
Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem.
- For the initial case where $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$
+ For the initial case where $\mathsf{N}=4$, \textit{i.e.}, $\mathsf{N-2}=2$
we successively have: $S_1=1,2,1,2$, $l=4$,
$u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$.
Thus again the algorithm successively produces
whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
These two variables are defined by the system
-$$
+\[
\left\{
\begin{array}{lcl}
c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}}
\end{array}
\right.
-\qquad
\Leftrightarrow
-\qquad
\left\{
\begin{array}{lcl}
d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
c_{\mathsf{N}} &= &\mathsf{N} - d_{\mathsf{N}}
\end{array}
\right.
-$$
+\]
Since $a_{\mathsf{N}}$ is even, $d_{\mathsf{N}}$ is an integer.
-Let us first proove that both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are positive
+Let us first prove that both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are positive
integers.
Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be
-the quotient and the remainder in the Euclidean disvision
-of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.}
+the quotient and the remainder in the Euclidean division
+of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.},
$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$.
Next, $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently
For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$)
-be the occurence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$
+be the occurrence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$
(resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
in step (\ref{item:nondet}) of the algorithm.
Let us now prove that the resulting system has always positive integer
solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$
and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$.
-This latter consraint is obviously established if the system has a solution.
+This latter constraint is obviously established if the system has a solution.
We thus have the following system.
We thus have
-$$
+\[
\begin{array}{rcl}
\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)
&\ge&
\frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
&\ge&
-\dfrac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
+\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
\end{array}
-$$
+\]
A simple variation study of the function $t:\R \rightarrow \R$ such that
$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that
-its derivative is strictly postive if $x \ge 6$ and $t(8)=224$.
+its derivative is strictly positive if $x \ge 6$ and $t(8)=224$.
The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive
for any $\mathsf{N} \ge 8$ and the proof is established.
For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions
among $\textit{TC}_{\mathsf{N}}(i)$, which leads to
${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.
-Notice that all such choices lead to a hamiltonian path.
+Notice that all such choices lead to an Hamiltonian path.
