+We will show in this section that chaotic properties as defined in the
+mathematical theory of chaos are related to some statistical tests that can be found
+in the NIST battery. Furthermore, we will check that, when mixing defective PRNGs with
+chaotic iterations, the new generator presents better statistical properties
+(this section summarizes and extends the work of~\cite{bfg12a:ip}).
+
+
+
+\subsection{Qualitative relations between topological properties and statistical tests}
+
+
+There are various relations between topological properties that describe an unpredictable behavior for a discrete
+dynamical system on the one
+hand, and statistical tests to check the randomness of a numerical sequence
+on the other hand. These two mathematical disciplines follow a similar
+objective in case of a recurrent sequence (to characterize an intrinsically complicated behavior for a
+recurrent sequence), with two different but complementary approaches.
+It is true that these illustrative links give only qualitative arguments,
+and proofs should be provided later to make such arguments irrefutable. However
+they give a first understanding of the reason why we think that chaotic properties should tend
+to improve the statistical quality of PRNGs.
+
+Let us now list some of these relations between topological properties defined in the mathematical
+theory of chaos and tests embedded into the NIST battery. Such relations need to be further
+investigated, but they presently give a first illustration of a trend to search similar properties in the
+two following fields: mathematical chaos and statistics.
+
+
+\begin{itemize}
+ \item \textbf{Regularity}. As stated in Section~\ref{subsec:Devaney}, a chaotic dynamical system must
+have an element of regularity. Depending on the chosen definition of chaos, this element can be the existence of
+a dense orbit, the density of periodic points, etc. The key idea is that a dynamical system with no periodicity
+is not as chaotic as a system having periodic orbits: in the first situation, we can predict something and gain a
+knowledge about the behavior of the system, that is, it never enter into a loop. A similar importance for regularity is emphasized in
+the two following tests~\cite{Nist10}:
+ \begin{itemize}
+ \item \textbf{Non-overlapping Template Matching Test}. Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern.
+ \item \textbf{Discrete Fourier Transform (Spectral) Test}. Detect periodic features (i.e., repetitive patterns that are near each other) in the tested sequence that would indicate a deviation from the assumption of randomness.
+ \end{itemize}
+
+\item \textbf{Transitivity}. This topological property introduced previously states that the dynamical system is intrinsically complicated: it cannot be simplified into
+two subsystems that do not interact, as we can find in any neighborhood of any point another point whose orbit visits the whole phase space.
+This focus on the places visited by orbits of the dynamical system takes various nonequivalent formulations in the mathematical theory
+of chaos, namely: transitivity, strong transitivity, total transitivity, topological mixing, and so on~\cite{bg10:ij}. A similar attention
+is brought on stated visited during a random walk in the two tests below~\cite{Nist10}:
+ \begin{itemize}
+ \item \textbf{Random Excursions Variant Test}. Detect deviations from the expected number of visits to various states in the random walk.
+ \item \textbf{Random Excursions Test}. Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence.
+ \end{itemize}
+
+\item \textbf{Chaos according to Li and Yorke}. Two points of the phase space $(x,y)$ define a couple of Li-Yorke when $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillates as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according
+to Li-Yorke~\cite{Li75,Ruette2001}. This property is related to the following test~\cite{Nist10}.
+ \begin{itemize}
+ \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow.
+ \end{itemize}
+ \item \textbf{Topological entropy}. Both in topological and statistical fields.
+ \begin{itemize}
+\item \textbf{Approximate Entropy Test}. Compare the frequency of overlapping blocks of two consecutive/adjacent lengths (m and m+1) against the expected result for a random sequence (m is the length of each block).
+ \end{itemize}
+
+ \item \textbf{Non-linearity, complexity}.
+ \begin{itemize}
+\item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence.
+\item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random (M is the length in bits of a block).
+ \end{itemize}
+\end{itemize}
+
+
+
+
