\documentclass{ita}
\usepackage{graphicx}
+\usepackage{caption}
+\usepackage{subcaption}
+
\usepackage{dsfont}
\usepackage{stmaryrd}
-\usepackage[font=footnotesize]{subfig}
+%\usepackage[font=footnotesize]{subfig}
\usepackage{ifthen}
\usepackage{color}
\usepackage{algorithm2e}
+\usepackage{epstopdf}
+%\usepackage{ntheorem}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[english]{babel}
+\usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
+\usepackage{pstricks,pst-node,pst-coil}
+
+\usepackage{url,tikz}
+\usepackage{pgflibrarysnakes}
+\usepackage{multicol}
+
+\usetikzlibrary{arrows}
+\usetikzlibrary{automata}
+\usetikzlibrary{snakes}
+\usetikzlibrary{shapes}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% Définitions personnelles
+% Définitions personnelles
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
}
}
-% \theoremstyle{plain}
-% \theoremheaderfont{\normalfont\bfseries\sc}
-% \theorembodyfont{\slshape}
-% \theoremsymbol{\ensuremath{\diamondsuit}}
-% \theoremprework{\bigskip}
-% \theoremseparator{.}
-\newtheorem{Def}{\underline{Définition}}
-\newtheorem{Lemma}{\underline{Lemme}}
-\newtheorem{Theo}{\underline{Théorème}}
-% \theoremheaderfont{\sc}
-% \theorembodyfont{\upshape}
-% \theoremstyle{nonumberplain}
-% \theoremseparator{}
-% \theoremsymbol{\rule{1ex}{1ex}}
-\newtheorem{Proof}{Preuve :}
-\newtheorem{xpl}{Exemple illustratif :}
+
+
+\newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
+\def \top {1.8}
+\def \topt {2.3}
+\def \P {\mathbb{P}}
+\def \ov {\overline}
+\def \ts {\tau_{\rm stop}}
+
+
+\newtheorem*{xpl}{Running Example}
\newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
%\newcommand{\ie}{\textit{i.e.}}
\newcommand{\Gall}[0]{\ensuremath{\mathcal{G}}}
-\newcommand{\JFC}[1]{\begin{color}{green}\textit{}\end{color}}
+\newcommand{\JFC}[1]{\begin{color}{green}\textit{#1}\end{color}}
\newcommand{\CG}[1]{\begin{color}{blue}\textit{}\end{color}}
\newcommand{\og}[0]{``}
\newcommand{\fg}[1]{''}
-\title{XXX}
+\title{Random Walk in a N-cube Without Hamiltonian Cycle
+ to Chaotic Pseudorandom Number Generation: Theoretical and Practical
+ Considerations}
\begin{document}
-\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrile Heam}
-\address{Institut FEMTO-ST, Université de Franche-Comté, Belfort, France}
+\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam}
+\address{FEMTO-ST Institute, University of Franche-Comté, Belfort, France}
-\author{Sylvain Contassot-Vivier}
-\address{Loria - UMR 7503, Université de Lorraine, Nancy, France}
+\keywords{Pseudorandom Number Generator, Theory of Chaos, Markov Matrice, Hamiltonian Path, Mixing Time, Stopping Time, Statistical Test}
-\date{...}
+\subjclass{34C28, 37A25,11K45}
\begin{abstract}
-This paper extends the results presented in~\cite{bcgr11ip}
-and~\cite{chgw14oip} by using the \emph{chaotic} updating mode, in the sense
-of F. Robert~\cite{Robert}. In this mode, several components of the system
-may be updated at each iteration. At the theoretical level, we show that
- the properties of chaos and uniformity of the obtained PRNG are preserved.
- At the practical level, we show that the algorithm that builds strongly
- connected iteration graphs, with doubly stochastic Markov matrix, has a
- reduced mixing time.
+This paper is dedicated to the design of chaotic random generators
+and extends previous works proposed by some of the authors.
+We propose a theoretical framework proving both the chaotic properties and
+that the limit distribution is uniform.
+A theoretical bound on the stationary time is given and
+practical experiments show that the generators successfully pass
+the classical statistical tests.
\end{abstract}
+\maketitle
+
\section{Introduction}
-%\input{intro}
+\input{intro}
\section{\uppercase{Preliminaries}}\label{sec:preliminaries}
\input{preliminaries}
-\section{Stopping Time}
-% Donner la borne du stopping time quand on marche dedans (nouveau).
-% Énoncer le problème de la taille de cette borne (elle est certes finie, mais grande).
+\section{Proof Of Chaos}\label{sec:proofOfChaos}
+\input{chaos}
+\section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
+\input{generating}
-\section{Jumping in a specific $n$-cube}
-% Proposer alors les sauts dans ce n-cube (nouveau)
-% Il y a des preuves que j'ai faites dans TSI sur la préservation des propriétés de chaos lorsqu'on saute, qu'on peut traduire et qui n'ont pas été publiées en anglais, je crois (nouveau).
+\section{Stopping Time}\label{sec:hypercube}
+\input{stopping}
-\section{Stopping Time (continued)}
-% Donner la borne du stopping time quand on marche dedans (nouveau).
-% Énoncer le problème de la taille de cette borne (elle est certes finie, mais grande).
+\section{Experiments}\label{sec:prng}
+\input{prng}
-\section{Quality study of the strategy}
-%6) Se pose alors la question de comment générer une stratégie de "bonne qualité". Par exemple, combien de générateurs aléatoires embarquer ? (nouveau)
-
-
-\section{Expérimentations}
-%
\section{Conclusion}
-%\input{conclusion}
+\input{conclusion}
%\acknowledgements{...}
-
+\bibliographystyle{alpha}
\bibliography{biblio}
\end{document}
