reprise de la preuve de PCH

diff --git a/biblio.bib b/biblio.bib
index 6cdde3fb02c295532d4f41587b297e196c762dac..bba6bf037afba836d25096a28b979183ff204272 100644 (file)
--- 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},
 @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 a934599aa930637ea730861d833ede17a2ef9617..5fa40f49c90e3753b0ccb7a792e66d38ea9cb201 100644 (file)
--- 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{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{...}
 
 
 \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{\uppercase{Preliminaries}}\label{sec:preliminaries}
 \input{preliminaries}
 

-

 \section{Proof Of Chaos}
 \section{Proof Of Chaos}

+\JFC{Enlever les refs aux PRNGs, harmoniser l'exemple}

 \input{chaos}
 
 \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). 
 
 \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}
 %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}
 
 \section{Conclusion}
 %\input{conclusion}

diff --git a/stopping.tex b/stopping.tex
index d095a3a44ed709fb9cb928c9db1c603aece2d276..9664549d4fa96496bf1fd20c27d8a90a8fc80b5f 100644 (file)
--- 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}$$
 
 $\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}.$$
 $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$. 
  
 
 $(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
 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).$$
 
 
 $$\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)$.
 \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)
 $$
 
 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}$).
 $\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
 $\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
 
 \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
 
 \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,
 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
 $$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,
 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}
 
 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}
 
 $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,
 
 \begin{proof}
 One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,