X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/e9f2cb916f164b15bce8fe96e4f5432d3df9b7b2..0d1c31c9837325e2dad26554c2cde3a457455158:/annexePreuveMarquagefldblement.tex?ds=sidebyside

diff --git a/annexePreuveMarquagefldblement.tex b/annexePreuveMarquagefldblement.tex
index 4cb4138..2c7c1e1 100644
--- 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}
-\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{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)$.
-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,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)$
- 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)$
- 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)$
- 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)$
- 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}
-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$.
