Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
\mathcal{X} \rightarrow \mathcal{X}$.
-\begin{Def}
+\begin{dfntn}
The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets
$U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
\varnothing$.
-\end{Def}
+\end{dfntn}
-\begin{Def}
+\begin{dfntn}
An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$
if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$
-\end{Def}
+\end{dfntn}
-\begin{Def}
+\begin{dfntn}
$f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic
points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$,
any neighborhood of $x$ contains at least one periodic point (without
necessarily the same period).
-\end{Def}
+\end{dfntn}
-\begin{Def}[Devaney's formulation of chaos~\cite{Devaney}]
+\begin{dfntn}[Devaney's formulation of chaos~\cite{Devaney}]
The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
topologically transitive.
-\end{Def}
+\end{dfntn}
The chaos property is strongly linked to the notion of ``sensitivity'', defined
on a metric space $(\mathcal{X},d)$ by:
-\begin{Def}
+\begin{dfntn}
\label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}
if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
$d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.
-\end{Def}
+\end{dfntn}
Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of
Let us show that,
-\begin{proposition}
+\begin{prpstn}
$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
-\end{proposition}
+\end{prpstn}
\begin{proof}
Before being able to study the topological behavior of the general
chaotic iterations, we must first establish that:
-\begin{proposition}
+\begin{prpstn}
For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on
$\left( \mathcal{X},d\right)$.
-\end{proposition}
+\end{prpstn}
\begin{proof}
\subsection{Proofs of chaos}
We will show that,
-\begin{proposition}
+\begin{prpstn}
\label{prop:trans}
$\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is
topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
-\end{proposition}
+\end{prpstn}
\begin{proof}
We show now that,
-\begin{proposition}
+\begin{prpstn}
If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is
regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
-\end{proposition}
+\end{prpstn}
\begin{proof}
Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
\end{proof}
$G_f$ being topologically transitive and regular, we can thus conclude that
-\begin{Theo}
+\begin{thrm}
The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
-\end{Theo}
+\end{thrm}
-\begin{Corollary}
+\begin{crllr}
The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
-\end{Corollary}
+\end{crllr}
\begin{proof}
In this context, $\mathcal{P}$ is the singleton $\{b\}$.
If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach
Hamiltonian cycle
has the awaited property with regard to the connectivity.
-\begin{Theo}
+\begin{thrm}
The iteration graph $\Gamma(f)$ issued from
the ${\mathsf{N}}$-cube where an Hamiltonian
cycle is removed is strongly connected.
-\end{Theo}
+\end{thrm}
Moreover, if all the transitions have the same probability ($\frac{1}{n}$),
we have proven the following results:
-\begin{Theo}
+\begin{thrm}
The Markov Matrix $M$ resulting from the ${\mathsf{N}}$-cube in
which an Hamiltonian
cycle is removed, is doubly stochastic.
-\end{Theo}
+\end{thrm}
Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian
cycle is removed.
The answer is indeed positive. We furtheremore have the following strongest
result.
-\begin{Theo}
+\begin{thrm}
There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
-\end{Theo}
+\end{thrm}
\begin{proof}
There is an arc $(x,y)$ in the
graph $\Gamma_{\{b\}}(f)$ if and only if $M^b_{xy}$ is positive
$$\P_X(X_\tau=Y)=\pi(Y).$$
-\begin{Theo}
+\begin{thrm}
If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
\P_X(\tau > t)$.
-\end{Theo}
+\end{thrm}
%Let $\Bool^n$ be the set of words of length $n$.
The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$,
$\ov{h}(\ov{h}(X))\neq X$.
-\begin{Lemma}\label{lm:h}
+\begin{lmm}\label{lm:h}
If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
-\end{Lemma}
+\end{lmm}
\begin{proof}
Let $\ov{h}$ be bijective.
the Markov chain $(X_t)$.
-\begin{Lemma}
+\begin{lmm}
The integer $\ts$ is a strong stationary time.
-\end{Lemma}
+\end{lmm}
\begin{proof}
Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
lemma.\end{proof}
-\begin{Theo} \label{prop:stop}
+\begin{thrm} \label{prop:stop}
If $\ov{h}$ is bijective and square-free, then
$E[\ts]\leq 8{\mathsf{N}}^2+ {\mathsf{N}}\ln ({\mathsf{N}}+1)$.
-\end{Theo}
+\end{thrm}
For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$,
let $S_{X,\ell}$ be the
$$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$
-\begin{Lemma}\label{prop:lambda}
+\begin{lmm}\label{prop:lambda}
If $\ov{h}$ is a square-free bijective function, then the inequality
$E[\lambda_h]\leq 8{\mathsf{N}}^2$ is established.
-\end{Lemma}
+\end{lmm}
\begin{proof}
For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq
Let $\ts^\prime$ be the first time that there are exactly ${\mathsf{N}}-1$ fair
elements.
-\begin{Lemma}\label{lm:stopprime}
+\begin{lmm}\label{lm:stopprime}
One has $E[\ts^\prime]\leq {\mathsf{N}} \ln ({\mathsf{N}}+1).$
-\end{Lemma}
+\end{lmm}
\begin{proof}
This is a classical Coupon Collector's like problem. Let $W_i$ be the
