]> AND Private Git Repository - prng_gpu.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Correction d'une preuve
authorguyeux <guyeux@gmail.com>
Sun, 30 Oct 2011 16:02:33 +0000 (17:02 +0100)
committerguyeux <guyeux@gmail.com>
Sun, 30 Oct 2011 16:02:33 +0000 (17:02 +0100)
prng_gpu.tex

index 11dd246f44d0012ce3cda2c421af4b48e7c26113..c504e98c5964867f7c6a8869150e57ea31081ea3 100644 (file)
@@ -623,10 +623,27 @@ claimed in the lemma.
 We can now prove the Theorem~\ref{t:chaos des general}...
 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
- On the one hand, strong transitivity implies transitivity. On the other hand, 
-the regularity is exactly Lemma~\ref{strongTrans} with $Y=X$. As the sensitivity
-to the initial condition is implied by these two properties, we thus have
-the theorem.
+Firstly, strong transitivity implies transitivity.
+
+Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To
+prove that $G_f$ is regular, it is sufficient to prove that
+there exists a strategy $\tilde S$ such that the distance between
+$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that
+$(\tilde S,E)$ is a periodic point.
+
+Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the
+configuration that we obtain from $(S,E)$ after $t_1$ iterations of
+$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ 
+and $t_2\in\mathds{N}$ such
+that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
+
+Consider the strategy $\tilde S$ that alternates the first $t_1$ terms
+of $S$ and the first $t_2$ terms of $S'$: $$\tilde
+S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
+is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
+$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
+point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we
+have $d((S,E),(\tilde S,E))<\epsilon$.
 \end{proof}