From: couchot Date: Thu, 30 Jun 2016 12:46:51 +0000 (+0200) Subject: Merge branch 'master' of ssh://bilbo.iut-bm.univ-fcomte.fr/16dcc X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/commitdiff_plain/a57f211cb3b73d523ff516e65f2559b296775c11?hp=789817c68132962fe415afd50e1105d04fabea47 Merge branch 'master' of ssh://bilbo.iut-bm.univ-fcomte.fr/16dcc --- diff --git a/main.pdf b/main.pdf index 58e266f..ff7928d 100644 Binary files a/main.pdf and b/main.pdf differ diff --git a/main.tex b/main.tex index f49eef6..6225751 100644 --- a/main.tex +++ b/main.tex @@ -551,15 +551,15 @@ Moreover, it is not clear that embedding such kind of functions into a PRNG allows to get a chaotic output, which could be required for simulating some chaotic behaviours. -In a previous work, some of the authors have proposed the idea of walking into a -$\mathsf{N}$-cube where a balanced Hamiltonian cycle have been removed -as the basis of a chaotic PRNG. -In this article, all the difficult issues observed in the previous work have been tackled. -The chaotic behavior of the whole PRNG is proven. -The construction of the balanced Hamiltonian cycle is theoretically and practically solved. -A upper bound of the length of the walk to obtain a uniform distribution is calculated. -Finally practical experiments show that the generators successfully pass -the classical statistical tests. +In a previous work, some of the authors have proposed the idea of walking +into a $\mathsf{N}$-cube where a balanced Hamiltonian cycle have been +removed as the basis of a chaotic PRNG. In this article, all the difficult +issues observed in the previous work have been tackled. The chaotic behavior +of the whole PRNG is proven. The construction of the balanced Hamiltonian +cycle is theoretically and practically solved. An upper bound of the +expected length of the walk to obtain a uniform distribution is calculated. +Finally practical experiments show that the generators successfully pass the +classical statistical tests. \end{abstract} diff --git a/stopping.tex b/stopping.tex index 284fc49..539d653 100644 --- a/stopping.tex +++ b/stopping.tex @@ -60,12 +60,14 @@ $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreov $\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ -Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the -distribution induced by the $X$-th row of $P$. If the Markov chain induced by -$P$ has a stationary distribution $\pi$, then we define +Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. For any +$X\in \Bool^{\mathsf{N}}$, let $P(X,\cdot)$ be the distribution induced by the +${\rm bin}(X)$-th row of $P$, where ${\rm bin}(X)$ is the integer whose +binary encoding is $X$. If the Markov chain induced by $P$ has a stationary +distribution $\pi$, then we define $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$ -\ANNOT{incohérence de notation $X$ : entier ou dans $B^N$ ?} +%\ANNOT{incohérence de notation $X$ : entier ou dans $B^N$ ?} and $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$