ajout du dossier talk

[hdrcouchot.git] / annexePreuveMarquagefldblement.tex

diff --git a/annexePreuveMarquagefldblement.tex b/annexePreuveMarquagefldblement.tex
index 2c7c1e1d9e5a234a9e266e0eed39827fdb1ed993..a56ddc2840069142214e435a8bda9ed2385a2ecf 100644 (file)
--- a/annexePreuveMarquagefldblement.tex
+++ b/annexePreuveMarquagefldblement.tex
@@ -16,7 +16,7 @@ x_i \oplus x_{i-1} \textrm{ si $i$ est pair}
 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.
 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$.
+Considérons que le résultat est établi jusqu'à $l=2k$ avec $k \in \Nats$.

 
 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
 
 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


@@ -31,7 +31,7 @@ $(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$.
 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})$.
 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$
+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.
 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.


@@ -40,22 +40,22 @@ Ainsi tous les sommets $(x_1,\dots,x_{2k})$ ont le même nombre d'arcs entrants
 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})$. 
 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:
+Parmi les configurations de  $\Bool^{2k+2}$, seuls  quatre suffixes de longueur 2 peuvent apparaî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$, 
 $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$ et  $f_{2k+2}(\dots,0,1)_{2k+2}=1$, le nombre d'arcs dont les extrémités est  
+$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 sont  

 \begin{itemize}
 \item $(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})$
 \begin{itemize}
 \item $(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)$);
+ auquel on ajoute 1 (une boucle autour des configurations $(x_1,\dots,x_{2k},0,0)$);

 \item $(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)$
 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})$ 
 \item $(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)$
 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)$);
+ auquel on ajoute 1 (une boucle autour des configurations $(x_1,\dots,x_{2k},0,1)$);

 \item $(x_1,\dots,x_{2k},1,1)$
 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  
 \item $(x_1,\dots,x_{2k},1,1)$
 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