ajout d'intro et de conclusion

[hdrcouchot.git] / annexePreuveMarquagefldblement.tex

diff --git a/annexePreuveMarquagefldblement.tex b/annexePreuveMarquagefldblement.tex
index 4cb4138b52e34b2110b7b082141b8851c9edbe72..2c7c1e1d9e5a234a9e266e0eed39827fdb1ed993 100644 (file)
--- a/annexePreuveMarquagefldblement.tex
+++ b/annexePreuveMarquagefldblement.tex
@@ -1,64 +1,66 @@
-On considère   le  mode
+On considère le  mode

 $f_l: \Bool^l \rightarrow \Bool^l$ t.q. le $i^{\textrm{ème}}$ composant 
 est défini par 
 \begin{equation}
 {f_l}(x)_i =
 \left\{
 \begin{array}{l}
 $f_l: \Bool^l \rightarrow \Bool^l$ t.q. le $i^{\textrm{ème}}$ composant 
 est défini par 
 \begin{equation}
 {f_l}(x)_i =
 \left\{
 \begin{array}{l}

-\overline{x_i} \textrm{ if $i$ is odd} \\
-x_i \oplus x_{i-1} \textrm{ if $i$ is even}
+\overline{x_i} \textrm{ si $i$ est impair} \\
+x_i \oplus x_{i-1} \textrm{ si $i$ est pair}

 \end{array}
 \right.
 \end{array}
 \right.

-\end{equation}\label{eq:fqq}
+\tag{\eqref{eq:fqq}}
+\end{equation}

 
 

-Prouvons que la matrice de Markov associée est doublement stochastique.

 
 

-the Markov chain is stochastic by construction. 
+Prouvons que la matrice de Markov associée est doublement stochastique par induction 
+sur la longueur $l$.
+Pour $l=1$ et $l=2$ la preuve est évidente.
+Considérons que le résulat est établi jusqu'à $l=2k$ avec $k \in \Nats$.

 
 

-Let us prove that its Markov chain is doubly stochastic by induction on the 
-length $l$.
-For $l=1$ and $l=2$ the proof is obvious. Let us consider that the 
-result is established until $l=2k$ for some $k \in \Nats$.
-
-Let us then firstly prove the doubly stochasticity for $l=2k+1$.
-Following notations introduced in~\cite{bcgr11:ip}, 
-Let  $\textsc{giu}(f_{2k+1})^0$ and $\textsc{giu}(f_{2k+1})^1$ denote
-the subgraphs of $\textsc{giu}(f_{2k+1})$ induced by the subset $\Bool^{2k} \times\{0\}$
-and $\Bool^{2k} \times\{1\}$ of $\Bool^{2k+1}$ respectively.
-$\textsc{giu}(f_{2k+1})^0$ and   $\textsc{giu}(f_{2k+1})^1$ are isomorphic to $\textsc{giu}(f_{2k})$.
-Furthermore, these two graphs are linked together only with arcs of the form
-$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ and 
+On montre d'abord que la double stochasticité est établie pour $l=2k+1$.
+En suivant les notations introduites à la section~\ref{anx:sccg}, soit
+$\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ les sous-graphes 
+de $\textsc{giu}(f_{2k+1})$ induits par les ensembles $\Bool^{2k} \times\{0\}$
+et $\Bool^{2k} \times\{1\}$ de $\Bool^{2k+1}$ respectivement.
+Les graphes $\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ sont isomorphes à $\textsc{giu}(f_{2k})$.
+De plus, ils ne sont liés dans $\textsc{giu}(f_{2k+1})$ que par 
+des arcs de la forme 
+$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ et 

 $(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$.
 $(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$.

-In $\textsc{giu}(f_{2k+1})$ the number of arcs whose extremity is $(x_1,\dots,x_{2k},0)$
-is  the same than the number of arcs whose extremity is $(x_1,\dots,x_{2k})$ 
-augmented with 1, and similarly for $(x_1,\dots,x_{2k},1)$.
-By induction hypothesis, the Markov chain associated to $\textsc{giu}(f_{2k})$ is doubly stochastic. All the vertices $(x_1,\dots,x_{2k})$ have thus the same number of 
-ingoing arcs and the proof is established for $l$ is $2k+1$.
+Dans $\textsc{giu}(f_{2k+1})$, deux sortes d'arcs pointent vers $(x_1,\dots,x_{2k},0)$.
+Ceux qui sont de la forme $(y_1,\dots,y_{2k},0)$, où un seul des $y_i$ est différent de $x_i$, 
+et leur nombre est celui des arcs qui pointent vers $(x_1,\dots,x_{2k})$ dans $\textsc{giu}(f_{2k})$.
+L'arc $(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},0)$ qui existe d'après la définition de $f_l$
+De même pour le nombre d'arcs dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$.
+Par hypothèse d'induction, la chaîne de Markov associée à $\textsc{giu}(f_{2k})$ 
+est doublement stochastique.
+Ainsi tous les sommets $(x_1,\dots,x_{2k})$ ont le même nombre d'arcs entrants et la preuve est établie pour $l= 2k+1$.

 
 

-Let us then  prove the doubly stochasticity for $l=2k+2$.
-The map $f_l$ is defined by 
-$f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$.
-With previously defined  notations, let us focus on 
-$\textsc{giu}(f_{2k+2})^0$ and   $\textsc{giu}(f_{2k+2})^1$ which are isomorphic to $\textsc{giu}(f_{2k+1})$. 
-Among configurations of $\Bool^{2k+2}$, only four suffixes of length 2 can be
-obviously observed, namely, $00$, $10$, $11$ and $01$.
-Since 
+Montrons à présent la double stochasticité pour $l=2k+2$.
+La fonction $f_l$ est définie par $f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$.  On se concentre sur  
+$\textsc{giu}(f_{2k+2})^0$ et   $\textsc{giu}(f_{2k+2})^1$ qui sont isomorphes à  $\textsc{giu}(f_{2k+1})$. 
+Parmi les configurations de  $\Bool^{2k+2}$, seuls  quatre suffixes de longueur 2 peuvent appraître:
+$00$, $10$, $11$ et $01$.
+Puisque 

 $f_{2k+2}(\dots,0,0)_{2k+2}=0$, $f_{2k+2}(\dots,1,0)_{2k+2}=1$, 
 $f_{2k+2}(\dots,0,0)_{2k+2}=0$, $f_{2k+2}(\dots,1,0)_{2k+2}=1$, 

-$f_{2k+2}(\dots,1,1)_{2k+2}=0$ and $f_{2k+2}(\dots,0,1)_{2k+2}=1$, the number of 
-arcs whose extremity is 
+$f_{2k+2}(\dots,1,1)_{2k+2}=0$ et  $f_{2k+2}(\dots,0,1)_{2k+2}=1$, le nombre d'arcs dont les extrémités est  

 \begin{itemize}
 \item $(x_1,\dots,x_{2k},0,0)$
 \begin{itemize}
 \item $(x_1,\dots,x_{2k},0,0)$

- is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,0)$).
+est le même que celui dont l'extrémité est de la forme  $(x_1,\dots,x_{2k},0)$ dans $\textsc{giu}(f_{2k+1})$
+ auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,0)$);

 \item $(x_1,\dots,x_{2k},1,0)$
 \item $(x_1,\dots,x_{2k},1,0)$

- is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations 
-$(x_1,\dots,x_{2k},1,1)$ to configurations 
-$(x_1,\dots,x_{2k},1,0)$) 
+est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ 
+ auquel on ajoute 1 (l'arc entre les configurations  $(x_1,\dots,x_{2k},1,1)$ et les  configurations 
+$(x_1,\dots,x_{2k},1,0)$); 

 \item $(x_1,\dots,x_{2k},0,1)$
 \item $(x_1,\dots,x_{2k},0,1)$

- is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,1)$).
+est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ 
+ auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,1)$);

 \item $(x_1,\dots,x_{2k},1,1)$
 \item $(x_1,\dots,x_{2k},1,1)$

- is the same than the one whose extremity is $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations 
-$(x_1,\dots,x_{2k},1,0)$ to configurations 
+est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$
+auquel on ajoute 1 (l'arc entre les configurations  
+$(x_1,\dots,x_{2k},1,0)$ et les configurations 

 $(x_1,\dots,x_{2k},1,1)$).
 \end{itemize}
 $(x_1,\dots,x_{2k},1,1)$).
 \end{itemize}

-Thus all the vertices $(x_1,\dots,x_{2k})$ have  the same number of 
-ingoing arcs and the proof is established for $l=2k+2$.
+Chacun des sommets $(x_1,\dots,x_{2k+2})$ a donc le même nombre d'arcs entrants,  
+la preuve est donc établie pour $l=2k+2$.