+
+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.
+
+\begin{enumerate}
+\item \label{item:nondet}Let $l$ be an even positive integer. Find
+$u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$
+such that $S_{\mathsf{N}-2}$ is the concatenation of
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
+\item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$
+ by
+ $\mathsf{N} - 1, u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+ respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that
+ $u^R$ is $u$ in reversed order.
+ The obtained sequence is further denoted as $U$.
+\item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first
+two elements have been exchanged.
+\item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
+\end{enumerate}
+
+It has been proven in~\cite{ZanSup04} that
+$S_{\mathsf{N}}$ is 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
+yielded Gray code is balanced.
+Next section shows how to choose the sequence $l$ to have the balancy property.
+
+\subsection{Balanced Codes}
+Let us first recall how to formalize the balancy property of a Gray code.
+Let $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence
+of a $\mathsf{N}$-bits cyclic Gray code.
+The transition sequence
+$S = s_1, s_2, \dots, s_{2^n}$, $s_i$, $1 \le i \le 2^\mathsf{N}$,
+indicates which bit position changes between
+codewords at index $i$ and $i+1$ modulo $2^\mathsf{N}$.
+The \emph{transition count} function
+$\textit{TC}_{\mathsf{N}} : \{1,\dots, \mathsf{N}\} \rightarrow \{0, \ldots, 2^{\mathsf{N}}\}$
+gives the number of times $i$ occurs in $S$,
+\textit{i.e.}, the number of times
+the bit $i$ has been switched in $L$.
+
+The Gray code is \emph{totally balanced} if $\textit{TC}_{\mathsf{N}}$
+is constant (and equal to $\frac{2^{\mathsf{N}}}{\mathsf{N}}$).
+It is \emph{balanced} if for any two bit indices $i$ and $j$,
+$|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le 2$.
+
+
+
+\begin{xpl}
+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
+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$,
+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}
+
+
+\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$.
+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)$
+are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$
+for any $i$, $1 \le i \le \mathsf{N}$.
+\end{thrm}
+
+
+
+
+
+The proof is done by induction on $\mathsf{N}$. Let us imadialty verify
+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$.
+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$
+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
+$U= 1,3,2,3,4,1,4,3,2$, $V = 4$, $W= 3, 1, 2, 1,2, 4$, and $W' = 1, 3, 2, 1,2, 4 $.
+Finally, $S_4$ is
+$
+2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4
+$
+such that $\textit{TC}_4(i) = 4$ and the theorem is established for
+odd and even initial values.
+
+
+For the inductive case, let us first define some variables.
+Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements
+whose transistion 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} -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 defined.
+Both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are obviously positves.
+
+
+
+
+
+
+\subsection{Toward a local uniform distribution of switches}
