stoping

[rairo15.git] / main.tex

diff --git a/main.tex b/main.tex
index 9192540d0e63df06a217b721822a424cd018f880..9e544ca0cc3b052ba3638631921f6d4c411ec1a9 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -1,17 +1,37 @@
 \documentclass{ita}
 \usepackage{graphicx}
 \documentclass{ita}
 \usepackage{graphicx}

+\usepackage{caption}
+\usepackage{subcaption}
+

 \usepackage{dsfont}
 \usepackage{stmaryrd}
 \usepackage{dsfont}
 \usepackage{stmaryrd}

-\usepackage[font=footnotesize]{subfig}
+%\usepackage[font=footnotesize]{subfig}

 \usepackage{ifthen}
 \usepackage{color}
 \usepackage{algorithm2e}
 \usepackage{ifthen}
 \usepackage{color}
 \usepackage{algorithm2e}

-\usepackage[hyperfirst=true,nogroupskip,nonumberlist,xindy]{glossaries}
+\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}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}


@@ -28,22 +48,23 @@
   }
 }
 
   }
 }
 

-% \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{Def}{Definition}
+%\newtheorem{Lemma}{\underline{Lemma}}
+\newtheorem{Theo}{Theorem}
+\newtheorem{Corollary}{Corollary}
+\newtheorem{Lemma}{Lemma}
+\newtheorem{proposition}{Proposition}
+\newtheorem*{xpl}{Running Example}

 
 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
 %\newcommand{\ie}{\textit{i.e.}}
 
 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
 %\newcommand{\ie}{\textit{i.e.}}


@@ -55,7 +76,7 @@
 \newcommand{\Gall}[0]{\ensuremath{\mathcal{G}}}
 
 
 \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]{''}
 \newcommand{\CG}[1]{\begin{color}{blue}\textit{}\end{color}}
 \newcommand{\og}[0]{``}
 \newcommand{\fg}[1]{''}


@@ -63,67 +84,68 @@
 
 
 
 
 
 

-\makeglossaries
-\loadglsentries{glossaire}

 
 
 
 

-\title{XXX}
+\title{Random Walk in a N-cube Without Hamiltonian Cycle 
+  to Chaotic Pseudorandom Number Generation: Theoretical and Practical 
+  Considerations}

 
 \begin{document}
 
 
 \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-Cyrile Heam}
+\address{Institut FEMTO-ST, Université de Franche-Comté, Belfort, France}

 
 

-\author{Sylvain Contassot-Vivier}
-\address{Loria - UMR 7503, Université de Lorraine, Nancy, France}

 
 

-\date{...}

 
 \begin{abstract}
 
 \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 passe
+the classical statsitcal tests.

 \end{abstract}
 
 \end{abstract}
 

+\maketitle
+

 \section{Introduction}
 \input{intro}
 
 \section{Introduction}
 \input{intro}
 

-\section{Préliminaires}
-\label{section:chaos}
-\input{sdd}
+ \section{\uppercase{Preliminaries}}\label{sec:preliminaries}
+\input{preliminaries}

 
 

-\section{Caractérisation des systèmes dynamiques booléens chaotiques}
-\label{section:caracterisation}
-\input{cs}
+\section{Proof Of Chaos}\label{sec:proofOfChaos}
+\input{chaos}

 
 

+\section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
+\input{generating}

 
 

-\section{Application  à la génération de nombres pseudo-aléatoires}
-\label{section:genpa}
-\input{exp}
+\section{Random walk on the modified Hypercube}\label{sec:hypercube}
+\input{stopping}

 
 

+% 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{Expérimentations}
-\label{section:expes}
-\input{nist}

 
 

-\section{Conclusion}
-\input{conclusion}

 
 

-%\acknowledgements{...}

 
 

-\appendix%\begin{annex}
-   \section{Preuve de continuité de $G_f$ dans $(\mathcal{X},d)$}
-  \label{anx:cont}
-  \input{annexecontinuite}
+%\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{Application to Pseudorandom Number Generation}\label{sec:prng}
+\input{prng}
+\JFC{ajouter ici les expérimentations}

 
 
 
 

-\printglossaries
+\section{Conclusion}
+\input{conclusion}
+
+%\acknowledgements{...}

 
 

+\bibliographystyle{alpha}

 \bibliography{biblio}
 
 \end{document}
 \bibliography{biblio}
 
 \end{document}