From: couchot Date: Sun, 15 Mar 2015 10:23:27 +0000 (+0100) Subject: modifs pour le style ita X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/4da7584dffe58a5bbdcd406436a5b139ee4c13fd?ds=inline modifs pour le style ita --- diff --git a/chaos.tex b/chaos.tex index 569d44a..d5ab5f9 100644 --- a/chaos.tex +++ b/chaos.tex @@ -40,41 +40,41 @@ This necessitates a rigorous proof, which is the aim of this section. 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 @@ -318,9 +318,9 @@ $$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \su 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} @@ -342,10 +342,10 @@ definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null an 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} @@ -433,11 +433,11 @@ since the function $f_0$ is equal to its inverse $f_0^{-1}$. \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} @@ -485,10 +485,10 @@ cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transiti 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$. @@ -508,15 +508,15 @@ is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$. \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 diff --git a/generating.tex b/generating.tex index 7e41a7d..5b0d393 100644 --- a/generating.tex +++ b/generating.tex @@ -29,19 +29,19 @@ states that the ${\mathsf{N}}$-cube without one 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. @@ -51,9 +51,9 @@ can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected. 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 diff --git a/main.tex b/main.tex index 701bcb6..465fbf5 100644 --- a/main.tex +++ b/main.tex @@ -58,12 +58,6 @@ \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}} diff --git a/stopping.tex b/stopping.tex index d3b4f4d..9cc720c 100644 --- a/stopping.tex +++ b/stopping.tex @@ -139,10 +139,10 @@ such that the distribution of $X_\tau$ is $\pi$: $$\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$. @@ -182,9 +182,9 @@ $(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 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. @@ -233,9 +233,9 @@ are fair. The integer $\ts$ is a randomized stopping time for 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 @@ -252,10 +252,10 @@ the same probability. Therefore, for $t\geq \tau_\ell$, the $\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 @@ -268,11 +268,11 @@ $$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.)\tex $$\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 @@ -318,9 +318,9 @@ which concludes the proof. 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