From: couchot Date: Mon, 9 Mar 2015 20:42:04 +0000 (+0100) Subject: reprise de la preuve de PCH X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/6537ad6b39c8648e4c3597b469e79e505193e358?hp=039eee12186be85d7a74a188489abd12bfe554fd reprise de la preuve de PCH --- diff --git a/biblio.bib b/biblio.bib index 6cdde3f..bba6bf0 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1,3 +1,10 @@ +@Book{proba, + author = {M. Mitzenmacher and Eli Upfal}, + ALTeditor = {}, + title = {Probability and Computing}, + publisher = {Cambridge University Press}, + year = {2005}, +} @Article{TNN2006, author = {Bahi,Jacques M. and Contassot-Vivier,Sylvain}, title = {Basins of attraction in fully asynchronous discrete-time discrete-state dynamic networks}, diff --git a/main.tex b/main.tex index a934599..5fa40f4 100644 --- a/main.tex +++ b/main.tex @@ -100,8 +100,8 @@ \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} +%\author{Sylvain Contassot-Vivier} +%\address{Loria - UMR 7503, Université de Lorraine, Nancy, France} \date{...} @@ -122,26 +122,33 @@ may be updated at each iteration. At the theoretical level, we show that \section{\uppercase{Preliminaries}}\label{sec:preliminaries} \input{preliminaries} - \section{Proof Of Chaos} +\JFC{Enlever les refs aux PRNGs, harmoniser l'exemple} \input{chaos} +\section{Generating....} +\JFC{Reprendre Mons en synthétisant... conclusion: n-cube moins hamitonien. +question efficacité d'un tel algo} +%\input{chaos} \section{Random walk on the modified 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). +% Énoncer le problème de la taille de cette borne +% (elle est certes finie, mais grande). -\section{Quality study of the strategy} +%\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} -%\input{prng} +\input{prng} +\JFC{ajouter ici les expérimentations} + \section{Conclusion} %\input{conclusion} diff --git a/stopping.tex b/stopping.tex index d095a3a..9664549 100644 --- a/stopping.tex +++ b/stopping.tex @@ -17,12 +17,23 @@ $$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^n}|\pi(X)-\mu(X)|.$$ Moreover, if $\nu$ is a distribution on $\Bool^n$, one has $$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ -Let $P$ be the matrix of a Markov chain on $\Bool^n$. $P(x,\cdot)$ is the -distribution induced by the $x$-th row of $P$. If the Markov chain induced by +Let $P$ be the matrix of a Markov chain on $\Bool^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 $$d(t)=\max_{X\in\Bool^n}\tv{P^t(X,\cdot)-\pi}.$$ -It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il -un intérêt dans la preuve ensuite.} + +and + +$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ +One can prove that + +$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ + + + + +% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il +% un intérêt dans la preuve ensuite.} @@ -41,8 +52,6 @@ In other words, the event $\{\tau = t \}$ only depends on the values of $(X_0,X_1,\ldots,X_t)$, not on $X_k$ with $k > t$. -\JFC{Je ne comprends pas la definition de randomized stopping time, Peut-on enrichir ?} - Let $(X_t)_{t\in \mathbb{N}}$ be a Markov chain and $f(X_{t-1},Z_t)$ a random mapping representation of the Markov chain. A {\it randomized stopping time} for the Markov chain is a stopping time for @@ -53,7 +62,6 @@ such that the distribution of $X_\tau$ is $\pi$: $$\P_X(X_\tau=Y)=\pi(Y).$$ -\JFC{Ou ceci a-t-il ete prouvé. On ne définit pas ce qu'est un strong stationary time.} \begin{Theo} If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^n} \P_X(\tau > t)$. @@ -128,9 +136,6 @@ $$ X_t= f(X_{t-1},Z_t) $$ -The pair $(f,Z)$ is a random mapping representation of $P_h$. -\JFC{interet de la phrase precedente} - %%%%%%%%%%%%%%%%%%%%%%%%%%%ù @@ -161,10 +166,12 @@ $b=1$ with probability $\frac{1}{2}$ and $b=0$ with probability $\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th bit of $X_{\tau_\ell}$ is $0$ or $1$ with the same probability ($\frac{1}{2}$). -By symmetry, \JFC{Je ne comprends pas ce by symetry} for $t\geq \tau_\ell$, the + + Moving next in the chain, at each step, +the $l$-th bit is switched from $0$ to $1$ or from $1$ to $0$ each time with +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} +lemma.\end{proof} \begin{Theo} \label{prop:stop} If $\ov{h}$ is bijective and square-free, then @@ -190,27 +197,42 @@ $E[\lambda_h]\leq 8n^2$ is established. \begin{proof} For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq -\frac{1}{4n^2}$. Indeed, if $h(X)\neq \ell$, then -$\P(S_{X,\ell}=1)=\frac{1}{2n}\geq \frac{1}{4n^2}$. If $h(X)=\ell$, then -$\P(S_{X,\ell}=1)=0$. Let $X_0=X$. Since $\ov{h}$ is square-free, -$\ov{h}(\ov{h}^{-1}(X))\neq X$. It follows that $(X,\ov{h}^{-1}(X))\in E_h$. -Therefore $P(X_1=\ov{h}^{-1}(X))=\frac{1}{2n}$. now, -by Lemma~\ref{lm:h}, $h(\ov{h}^{-1}(X))\neq h(X)$. Therefore -$\P(S_{X,\ell}=2\mid X_1=\ov{h}^{-1}(X))=\frac{1}{2n}$, proving that -$\P(S_{X,\ell}\leq 2)\geq \frac{1}{4n^2}$. - -Therefore, $\P(S_{X,\ell}\geq 2)\leq 1-\frac{1}{4n^2}$. By induction, one +\frac{1}{4n^2}$. +Let $X_0= X$. +Indeed, +\begin{itemize} +\item if $h(X)\neq \ell$, then +$\P(S_{X,\ell}=1)=\frac{1}{2n}\geq \frac{1}{4n^2}$. +\item otherwise, $h(X)=\ell$, then +$\P(S_{X,\ell}=1)=0$. +But in this case, intutively, it is possible to move +from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{2N}$). And in +$\ov{h}^{-1}(X)$ the $l$-th bit can be switched. +More formally, +since $\ov{h}$ is square-free, +$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. It follows +that $(X,\ov{h}^{-1}(X))\in E_h$. We thus have +$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2N}$. Now, by Lemma~\ref{lm:h}, +$h(\ov{h}^{-1}(X))\neq h(X)$. Therefore $\P(S_{x,\ell}=2\mid +X_1=\ov{h}^{-1}(X))=\frac{1}{2N}$, proving that $\P(S_{x,\ell}\leq 2)\geq +\frac{1}{4N^2}$. +\end{itemize} + + + + +Therefore, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4n^2}$. By induction, one has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq \left(1-\frac{1}{4n^2}\right)^i$. Moreover, -since $S_{X,\ell}$ is positive, it is known~\cite[lemma 2.9]{}, that +since $S_{X,\ell}$ is positive, it is known~\cite[lemma 2.9]{proba}, that $$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).$$ Since $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, one has $$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\leq -\P(S_{X,\ell}\geq 1)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).$$ +\P(S_{X,\ell}\geq 1)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).$$ Consequently, -$$E[S_{X,\ell}]\leq 1+2 -\sum_{i=1}^{+\infty}\left(1-\frac{1}{4n^2}\right)^i=1+2(4n^2-1)=8n^2-2,$$ +$$E[S_{X,\ell}]\leq 1+1+2 +\sum_{i=1}^{+\infty}\left(1-\frac{1}{4n^2}\right)^i=2+2(4n^2-1)=8n^2,$$ which concludes the proof. \end{proof} @@ -238,7 +260,7 @@ Consequently, $E[\ts^\prime]\leq n (-\frac{1}{2}+\ln(n+1))\leq n\ln(n+1)$. \end{proof} -One can now prove Theo~\ref{prop:stop}. +One can now prove Theorem~\ref{prop:stop}. \begin{proof} One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,