annexePreuveMarquagefldblement.tex

   1 On considère le  mode
   2 $f_l: \Bool^l \rightarrow \Bool^l$ t.q. le $i^{\textrm{ème}}$ composant
   3 est défini par
   4 \begin{equation}
   5 {f_l}(x)_i =
   6 \left\{
   7 \begin{array}{l}
   8 \overline{x_i} \textrm{ si $i$ est impair} \\
   9 x_i \oplus x_{i-1} \textrm{ si $i$ est pair}
  10 \end{array}
  11 \right.
  12 \tag{\eqref{eq:fqq}}
  13 \end{equation}
  14
  15
  16 Prouvons que la matrice de Markov associée est doublement stochastique par induction
  17 sur la longueur $l$.
  18 Pour $l=1$ et $l=2$ la preuve est évidente.
  19 Considérons que le résultat est établi jusqu'à $l=2k$ avec $k \in \Nats$.
  20
  21 On montre d'abord que la double stochasticité est établie pour $l=2k+1$.
  22 En suivant les notations introduites à la section~\ref{anx:sccg}, soit
  23 $\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ les sous-graphes
  24 de $\textsc{giu}(f_{2k+1})$ induits par les ensembles $\Bool^{2k} \times\{0\}$
  25 et $\Bool^{2k} \times\{1\}$ de $\Bool^{2k+1}$ respectivement.
  26 Les graphes $\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ sont isomorphes à $\textsc{giu}(f_{2k})$.
  27 De plus, ils ne sont liés dans $\textsc{giu}(f_{2k+1})$ que par
  28 des arcs de la forme
  29 $(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ et
  30 $(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$.
  31 Dans $\textsc{giu}(f_{2k+1})$, deux sortes d'arcs pointent vers $(x_1,\dots,x_{2k},0)$.
  32 Ceux qui sont de la forme $(y_1,\dots,y_{2k},0)$, où un seul des $y_i$ est différent de $x_i$,
  33 et leur nombre est celui des arcs qui pointent vers $(x_1,\dots,x_{2k})$ dans $\textsc{giu}(f_{2k})$.
  34 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$.
  35 De même pour le nombre d'arcs dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$.
  36 Par hypothèse d'induction, la chaîne de Markov associée à $\textsc{giu}(f_{2k})$
  37 est doublement stochastique.
  38 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$.
  39
  40 Montrons à présent la double stochasticité pour $l=2k+2$.
  41 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
  42 $\textsc{giu}(f_{2k+2})^0$ et   $\textsc{giu}(f_{2k+2})^1$ qui sont isomorphes à  $\textsc{giu}(f_{2k+1})$.
  43 Parmi les configurations de  $\Bool^{2k+2}$, seuls  quatre suffixes de longueur 2 peuvent apparaître:
  44 $00$, $10$, $11$ et $01$.
  45 Puisque
  46 $f_{2k+2}(\dots,0,0)_{2k+2}=0$, $f_{2k+2}(\dots,1,0)_{2k+2}=1$,
  47 $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
  48 \begin{itemize}
  49 \item $(x_1,\dots,x_{2k},0,0)$
  50 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})$
  51  auquel on ajoute 1 (une boucle autour des configurations $(x_1,\dots,x_{2k},0,0)$);
  52 \item $(x_1,\dots,x_{2k},1,0)$
  53 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})$
  54  auquel on ajoute 1 (l'arc entre les configurations  $(x_1,\dots,x_{2k},1,1)$ et les  configurations
  55 $(x_1,\dots,x_{2k},1,0)$);
  56 \item $(x_1,\dots,x_{2k},0,1)$
  57 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})$
  58  auquel on ajoute 1 (une boucle autour des configurations $(x_1,\dots,x_{2k},0,1)$);
  59 \item $(x_1,\dots,x_{2k},1,1)$
  60 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})$
  61 auquel on ajoute 1 (l'arc entre les configurations
  62 $(x_1,\dots,x_{2k},1,0)$ et les configurations
  63 $(x_1,\dots,x_{2k},1,1)$).
  64 \end{itemize}
  65 Chacun des sommets $(x_1,\dots,x_{2k+2})$ a donc le même nombre d'arcs entrants,
  66 la preuve est donc établie pour $l=2k+2$.