\chapterimage{markov}
\chaptertext{\foreignlanguage{russian}{Андрей Андреевич  МАРКОВ} (1856 -
1922), grand mathématicien  russe, initiateur des probabilités modernes,
grand amateur de poésie,   n'hésita pourtant pas à s'impliquer dans la
tumultueuse  histoire  de  son   pays.  Il  n'eut  pas  peur  d'affirmer
publiquement son  anti-tsarisme et fut  renvoyé de l'Université.  Il fut
réhabilité après la Révolution. 

Nous étudierons de manière élémentaire quelques résultats de ses travaux
sur   les   processus   aléatoires  (ou   stochastiques),   c'est-à-dire
l'évolution   dans   le   temps   d'une   variable   aléatoire   appelés
\textit{chaînes  de  \textsc{Markov}} dont  les  applications sont  très
nombreuses, notamment en informatique  (reconnaissance de la langue d'un
texte,  techniques  de  compression,  l'algorithme PageRank  de  Google,
files d'attente, bioinformatique,...)

La  présentation proposée  ici  est celle  du  célèbre mathématicien  et
pédagogue allemand Arthur \textsc{Engel}.

D'un point de vue plus probabiliste, les chaînes de \textsc{Markov} vont
nous permettre d'étudier des v.a.r. non indépendantes ce que nous ne pouvions
pas envisager jusqu'à maintenant.
}

\chapter{Initiation aux processus aléatoires}


\section{Vision dynamique des probabilités - Automates}
%


\subsection{Découverte}
Considérons  l'habituelle urne  et  ses  boules: on  y  trouve 3  boules
pervenche, 2 lila et 1 rose.  On tire successivement et sans remise deux
boules  de  l'urne:  quelle  est  la  probabilité  d'obtenir  une  boule
pervenche?

On peut représenter ce jeu par l'automate suivant:




\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=2.5cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 
                                                                                               
 \node[state,initial] (A)  {Départ};
 \node[state] (C) [ below of=A] {$L_1$};
 \node[state] (B) [ left of=C] {$P_1$};
 \node[state] (D) [ right of= C] {$R_1$}; 
 \node[state,accepting] (E) [below  of=C] {$P_2$};
 
 \path 
       (A) edge node[right] {1/6} (D)
       (A) edge node[right] {1/3} (C)
       (A) edge node[left] {1/2} (B)
       (B) edge node[left] {2/5} (E)
       (C) edge node[right] {3/5} (E)
       (D) edge node[right] {3/5} (E)
       ;
\end{tikzpicture}
\end{center}


Les      résultats       habituels      conduisent      au      résultat
attendu:   $$\bbp(P_2)=\frac{1}{2}\times   \frac{2}{5}+\frac{1}{3}\times
\frac{3}{5}+\frac{1}{6}\times \frac{3}{5}=\frac{1}{2}$$

L'orientation de l'automate nous permet  de dire que la probabilité de A
à B est égale à la somme  de tous les \textit{chemins} allant de A vers
B.


On  parle souvent  dans ce  cas  de \textit{processus  aléatoire} ou  de
\textit{marche  aléatoire}:  il  s'agit d'une  succession  d'expériences
aléatoires simples.   Une dimension temporelle vient  donc s'ajouter aux
outils statiques habituels et induit une vision
\textit{dynamique} des probabilités. L'utilisation d'automates apparaît
alors  naturelle  car  elle  est  associée aux  notions  d'états  et  de
changements d'états:





\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
\tikzstyle{every state}=[fill=white,draw=black,text=black]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting by arrow,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state] (A)  {$i$};
 \node[state] (B) [ right of=A] {$j$};
 
 \path (A) edge node[above] {$p_{ij}$} (B);
\end{tikzpicture}
\end{center}

Le nombre $p_{ij}$  représente la probabilité de passer  de l'état $i$ à
l'état $j$.


Parmi tous les processus aléatoires, un processus de \textsc{Markov} est
caractérisé par la connaissance:
\begin{itemize}
\item de l'état initial;
\item de tous les états;
\item de tous les $p_{ij}$.
\end{itemize}

\textbf{La particularité  des chaînes de \textsc{Markov} est  de représenter des
processus où la probabilité permettant de passer à un instant donné d'un
état présent à un état futur 
ne dépend du passé qu'à travers le présent soit: \og la probabilité du
futur  sachant présent  et passé  est égale  à la  probabilité  du futur
sachant le présent\fg{}.
} ou encore: \textbf{le présent contient toutes les données du passé...}.

\subsection{Premier exemple - Règles de parcours}
Voyons  à  présent  un  exemple  plus précis  pour  introduire  quelques
définitions.


 Considérons le  jeu suivant: je  dispose d'un Zwjrsch  (monnaie syldave)
mais  je dois absolument  disposer de  5 Zwjrsch  pour inviter Pavlova 
à la patinoire. Je propose un jeu à mon riche voisin Ivan Ivanovitch: je
lance ma  pièce équilibrée de  1 Zwjrsch. Je  mise tout l'argent  que je
possède si j'ai 1 ou 2 Zwjrsch ou uniquement le complément à 5 si j'ai 3
ou  4   Zwjrsch  (je  ne   suis  pas  totalement  stupide   ayant  suivi
l'enseignement  du   célèbre  mathématicien  français   Konanovitch au
contraire de mon voisin).

On peut représenter ce jeu par l'automate suivant:





\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=2.5cm,semithick, bend angle=20]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting below,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A)  {$1$};
 \node[state,accepting] (Z) [ above left of=A] {$0$};
 \node[state] (B) [ above right of=Z] {$2$};
 \node[state] (C) [ right of=A] {$3$};
 \node[state] (D) [ right of=B] {$4$}; 
 \node[state,accepting] (E) [above right of=C] {$5$};
 
 \path 
       (A) edge node[right] {1/2} (B)
       (A) edge node[below left] {1/2} (Z)
       (B) edge node[above left] {1/2} (Z)
       (B) edge node[above] {1/2} (D)
       (C) edge node[below] {1/2} (A)
       (D) edge node[left] {1/2} (C)
       (D) edge node[above right] {1/2} (E)
       (C) edge node[below right] {1/2} (E)
       ;
\end{tikzpicture}
\end{center}


Un   état  $i$  est   dit  \textit{absorbant}   si,  et   seulement  si,
$p_{ii}=1$.  Ici,  les états  5  et 0  sont  absorbants  (j'y suis,  j'y
reste).  L'ensemble $\bigl\{0,5\bigr\}$ des états absorbants constituent
le \textit{bord}  de l'ensemble  des états. Les  autres états  sont dits
\textit{intérieurs}.

Une chaîne  de \textsc{Markov} est \textit{absorbante}  lorsque son bord
est non vide.

On peut  alors se  demander quelle est  la probabilité  que j'accompagne
Pavlova à la patinoire et quelle sera la durée moyenne du jeu.



Nous allons  donner trois règles  qui vont nous  guider tout au  long de
notre étude et  dont les deux premières reprennent  les résultats sur le
conditionnement.    Elles    concernent    les   \textit{parcours}    ou
\textit{promenades    aléatoires}   le    long    de   l'automate.    La
\textit{longueur}  d'un  parcours   désigne  le  nombre  de  transitions
séparant les deux extrémités.

\begin{enumerate}
\item la probabilité de réaliser un parcours donné à partir
  d'un point donné  est égale au produit de  toutes les probabilités
  de transition le long de ce parcours;
\item La probabilité d'atteindre  un sous-ensemble du bord
      à partir d'un état donné
      est égale à la somme  des probabilités de tous les parcours allant
      de cet élément aux éléments du sous-ensemble;
\item  la  durée   moyenne  des  parcours  allant  d'un   état  au  bord
      (le  \textit{temps   moyen  d'absorption})  est   la  moyenne  des
      longueurs  des parcours  de ce  sommet  au bord  pondérée par  les
      probabilités de  chaque transition.  Si on introduit  une variable
      aléatoire  égale   au  temps  de  parcours,  il   s'agit  donc  de
      l'espérance de cette v.a.r.
\end{enumerate}



Le  problème,  c'est  qu'il  peut  y  avoir  une  infinité  de  parcours
absorbants pour  un sommet donné  comme dans l'exemple proposé  que nous
allons pouvoir à présent étudier.


Nous  allons  étudier  tous   les  parcours  absorbants  partant  de  1,
c'est-à-dire tous  les parcours  allant de  1 à 5.  Il y  en a  bien une
infinité du fait  de la présence du  cycle $1\to 2\to 4 \to  3\to 1$. La
dernière partie du parcours peut être $1\to 2\to 4\to 5$ ou $1\to 2\to 4
\to 3 \to 5$ de longueurs respectives 3 et 4. Ainsi, la probabilité $p_1$ cherchée vaut:




\begin{eqnarray*}
p_1&=&\underbrace{\left(\frac{1}{2^3}+\frac{1}{2^4}\right)}_{0 \text{ boucle}}
+\underbrace{\left(\frac{1}{2^{3+4}}+\frac{1}{2^{4+4}}\right)}_{1
\text{ boucle}}
+\underbrace{\left(\frac{1}{2^{3+2\times
4}}+\frac{1}{2^{4+2\times 4}}\right)}_{2 \text{ boucles}}
+\underbrace{\left(\frac{1}{2^{3+3\times
4}}+\frac{1}{2^{4+3\times 4}}\right)}_{3 \text{ boucles}}
+\cdots\\
&=&         \left(\frac{3}{2}\times        \frac{1}{2^3}\right)        +
\left(\frac{3}{2}\times      \frac{1}{2^7}\right)+\left(\frac{3}{2}\times
\frac{1}{2^{11}}\right)+\left(\frac{3}{2}\times
\frac{1}{2^{15}}\right)+\cdots\\
&=&3 \displaystyle\sum_{k=0}^{+\infty}\left(\frac{1}{2^4}\right)^k\\
&=&3 \frac{1}{1-\frac{1}{16}}\\
&=&\frac{1}{5}
\end{eqnarray*}


Vous voici une nouvelle fois confronté au problème d'une somme infinie à
valeur finie...

\begin{recherche}
Faites  un calcul similaire  pour déterminer  la probabilité  de perdre:
vous connaissez déjà le résultat donc vous pourrez contrôler vos calculs...
\end{recherche}

Introduisons à  présent la  v.a.r. égale  au temps de  parcours. Il  y a
quatre \og familles\fg{} de parcours:
\begin{enumerate}
\item   $1\to    0$   précédé    de   $k$   cycles:    $X=4k+1$,   $\bbp
      \left(\left[X=4k+1\right]\right)=\left(\frac{1}{2^4}\right)^k\times
      \frac{1}{2}=\frac{1}{2^{4k+1}}$;
\item $1\to 2\to 0$ précédé de $k$ cycles: $X=4k+2$, $\bbp
      \left(\left[X=4k+2\right]\right)=\left(\frac{1}{2^4}\right)^k\times
      \left(\frac{1}{2}\right)^2=\frac{1}{2^{4k+2}}$;
\item $1\to 2\to 4\to 5$ précédé de $k$ cycles: $X=4k+3$, $\bbp
      \left(\left[X=4k+3\right]\right)=\left(\frac{1}{2^4}\right)^k\times
      \left(\frac{1}{2}\right)^3=\frac{1}{2^{4k+3}}$;
\item $1\to 2\to 4\to 3\to5$ précédé de $k$ cycles: $X=4k+4$, $\bbp
      \left(\left[X=4k+4\right]\right)=\left(\frac{1}{2^4}\right)^k\times \left(\frac{1}{2}\right)^4=\frac{1}{2^{4k+4}}$.
\end{enumerate}

Dans tous les cas, $\bbp([X=n])=\frac{1}{2^n}$ donc $\bbe(X)=\displaystyle\sum_{n=1}^{+\infty}\frac{n}{2^n}$.
 

\begin{recherche}
  Nous avons prouvé au module précédent que:

$$\forall   q\in\bbr,\   |q|<1  \Longrightarrow   S=\displaystyle\sum_{n
\geqslant 0}^{}q^n=\frac{1}{1-q}$$

Pour $|q|<1$, notons $T=\displaystyle\sum_{n \geqslant 1}^{}nq^{n-1}$ en
supposant que cette écriture a un sens. 

Calculer   $(1-q)T$    en   fonction    de   S   et    déduisez-en   que
$T=\frac{1}{(1-q)^2}$ puis que $\bbe(X)=2$.
\end{recherche}


\subsection{Deuxième exemple - Valeur moyenne}

Voyons à présent un nouveau jeu: je lance une pièce. Si j'obtiens quatre
fois  de suite \og  Pile\fg{}, mon voisin  Ivan Ivanitch  a
gagné. Si  j'obtiens deux  fois \og
Face\fg{} puis deux fois \og Pile\fg{}, j'ai gagné. 
Je présente ce jeu comme équitable à Ivan car la probabilité de
gagner à chaque fois est 
$\left(\frac{1}{2}\right)^4=\frac{1}{16}$. Suis-je malhonnête?


Représentons le jeu  à l'aide d'un automate. On  ne représentera pas les
probabilités  de   transitions  car   elles  valent  toutes   $1/2$:  ma
malhonnêteté éventuelle n'est pas due à l'emploi d'une pièce truquée...




\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=1.8cm,semithick, bend angle=25]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 3em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {Départ};
 \node[state] (B) [above right of =A] {P};
 \node[state] (C) [ right of =B] {PP};
 \node[state] (D) [right of =C] {PPP};
 \node[state,accepting] (E) [right of=D] {PPPP};
 \node[state] (F) [below right of =A] {F};
 \node[state] (G) [ right of =F] {FF};
 \node[state] (H) [ right of =G] {FFP};
 \node[state,accepting] (I) [right of=H] {FFPP};

 \path 
       (A) edge node[] {} (B)
       (A) edge node[] {} (F)
       (B) edge node[] {} (C)
       (B) edge[bend left] node[] {} (F)
       (C) edge node[] {} (D)
       (C) edge node[] {} (F)
       (D) edge node[] {} (E)
       (D) edge node[] {} (F)
       (F) edge node[] {} (G)
       (F) edge[bend left] node[] {} (B)
       (G) edge node[] {} (H)
       (G) edge[loop above] node[] {} (G)
       (H) edge node[] {} (I)
       (H) edge[bend left] node[] {} (F)
       ;
\end{tikzpicture}
\end{center}

Le problème,  c'est que cette fois, il  y a trop de  cycles pour pouvoir
utiliser  les simples  outils  de parcours  vus  précédemment mais  nous
allons partir  d'eux pour  trouver des résultats  plus puissants  en les
considérant par \og paquets\fg{}.

Soit une chaîne de \textsc{Markov} dont l'ensemble des états est $S=\bigl\{1,2,...,n\bigr\}$.

Nous allons tout d'abord nous  intéresser à la probabilité $p_i$ pour un
état $i$ d'être \og absorbé\fg{} dans un sous-ensemble SB du bord.

Sur le bord, $p_i=1$ si $i\in SB$ et 0 sinon.

À l'intérieur,  en utilisant la  règle des probabilités totales  ou bien
la deuxième règle du parcours pour obtenir que:

$$p_i=\displaystyle\sum_{k\in S}^{}p_{ik}p_k$$


Or les  $p_{ik}$ sont nuls s'il  n'existe pas de transition  de $i$ vers
$k$. Notons $\ER_i$ l'ensemble  des extrémités des transitions d'origine
$i$, alors:


$$p_i=\displaystyle\sum_{k\in \ER_i}^{}p_{ik}p_k$$


Appliquons ce résultat à notre jeu.

Appelons $x$  la probabilité que  je gagne au  départ. Il me  manque une
donnée  pour  appliquer  la  règle  précédente  donc  j'appelle  $y$  la
probabilité que je gagne depuis l'état F.


Je connais également $p_{PPPP}=0$ et $p_{FFPP}=1$ puisque je m'intéresse
au sous-ensemble du bord qui me fait gagner.



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=1.5cm,semithick, bend angle=25]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 2em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$x$};
 \node[state] (B) [above right of =A] {};
 \node[state] (C) [ right of =B] {};
 \node[state] (D) [right of =C] {};
 \node[state,accepting] (E) [right of=D] {0};
 \node[state] (F) [below right of =A] {$y$};
 \node[state] (G) [ right of =F] {};
 \node[state] (H) [ right of =G] {};
 \node[state,accepting] (I) [right of=H] {1};

 \path 
       (A) edge node[] {} (B)
       (A) edge node[] {} (F)
       (B) edge node[] {} (C)
       (B) edge[bend left] node[] {} (F)
       (C) edge node[] {} (D)
       (C) edge node[] {} (F)
       (D) edge node[] {} (E)
       (D) edge node[] {} (F)
       (F) edge node[] {} (G)
       (F) edge[bend left] node[] {} (B)
       (G) edge node[] {} (H)
       (G) edge[loop above] node[] {} (G)
       (H) edge node[] {} (I)
       (H) edge[bend left] node[] {} (F)
       ;
\end{tikzpicture}
\end{center}


Remplissons  alors de  proche en  proche l'automate  en  remplissant les
cercles avec les $p_i$.


Je    peux   remplir    les   deux    états   précédents    les   bords:
$p_{PPP}=\frac{1}{2}\times 0+\frac{1}{2}\times y$ et $p_{FFP}=\frac{1}{2}\times 1+\frac{1}{2}\times y$




\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=1.5cm,semithick, bend angle=25]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 2em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$x$};
 \node[state] (B) [above right of =A] {};
 \node[state] (C) [ right of =B] {};
 \node[state] (D) [right of =C] {$\frac{y}{2}$};
 \node[state,accepting] (E) [right of=D] {0};
 \node[state] (F) [below right of =A] {$y$};
 \node[state] (G) [ right of =F] {};
 \node[state] (H) [ right of =G] {$\frac{1+y}{2}$};
 \node[state,accepting] (I) [right of=H] {1};

 \path 
       (A) edge node[] {} (B)
       (A) edge node[] {} (F)
       (B) edge node[] {} (C)
       (B) edge[bend left] node[] {} (F)
       (C) edge node[] {} (D)
       (C) edge node[] {} (F)
       (D) edge node[] {} (E)
       (D) edge node[] {} (F)
       (F) edge node[] {} (G)
       (F) edge[bend left] node[] {} (B)
       (G) edge node[] {} (H)
       (G) edge[loop above] node[] {} (G)
       (H) edge node[] {} (I)
       (H) edge[bend left] node[] {} (F)
       ;
\end{tikzpicture}
\end{center}

Alors       $p_{PP}=\frac{1}{2}\times      \frac{y}{2}+\frac{1}{2}\times
y=\frac{3y}{4}$ et $p_{FF}=\frac{1+y}{4}+\frac{1}{2}p_{FF}=\frac{1+y}{2}$ 


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=1.8cm,semithick, bend angle=25]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 2em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$x$};
 \node[state] (B) [above right of =A] {};
 \node[state] (C) [ right of =B] {$\frac{3y}{4}$};
 \node[state] (D) [right of =C] {$\frac{y}{2}$};
 \node[state,accepting] (E) [right of=D] {0};
 \node[state] (F) [below right of =A] {$y$};
 \node[state] (G) [ right of =F] {$\frac{1+y}{2}$};
 \node[state] (H) [ right of =G] {$\frac{1+y}{2}$};
 \node[state,accepting] (I) [right of=H] {1};

 \path 
       (A) edge node[] {} (B)
       (A) edge node[] {} (F)
       (B) edge node[] {} (C)
       (B) edge[bend left] node[] {} (F)
       (C) edge node[] {} (D)
       (C) edge node[] {} (F)
       (D) edge node[] {} (E)
       (D) edge node[] {} (F)
       (F) edge node[] {} (G)
       (F) edge[bend left] node[] {} (B)
       (G) edge node[] {} (H)
       (G) edge[loop above] node[] {} (G)
       (H) edge node[] {} (I)
       (H) edge[bend left] node[] {} (F)
       ;
\end{tikzpicture}
\end{center}

Ici, $p_{P}=\frac{3y}{8}+\frac{y}{2}=\frac{7y}{8}$



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=1.8cm,semithick, bend angle=25]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 2em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$x$};
 \node[state] (B) [above right of =A] {$\frac{7y}{8}$};
 \node[state] (C) [ right of =B] {$\frac{3y}{4}$};
 \node[state] (D) [right of =C] {$\frac{y}{2}$};
 \node[state,accepting] (E) [right of=D] {0};
 \node[state] (F) [below right of =A] {$y$};
 \node[state] (G) [ right of =F] {$\frac{1+y}{2}$};
 \node[state] (H) [ right of =G] {$\frac{1+y}{2}$};
 \node[state,accepting] (I) [right of=H] {1};

 \path 
       (A) edge node[] {} (B)
       (A) edge node[] {} (F)
       (B) edge node[] {} (C)
       (B) edge[bend left] node[] {} (F)
       (C) edge node[] {} (D)
       (C) edge node[] {} (F)
       (D) edge node[] {} (E)
       (D) edge node[] {} (F)
       (F) edge node[] {} (G)
       (F) edge[bend left] node[] {} (B)
       (G) edge node[] {} (H)
       (G) edge[loop above] node[] {} (G)
       (H) edge node[] {} (I)
       (H) edge[bend left] node[] {} (F)
       ;
\end{tikzpicture}
\end{center}


Il nous  reste à déterminer  $y$ et $x$  mais nous n'avons  pas exploité
l'état F: 

  $y=p_F=\frac{1+y}{4}+\frac{7y}{16}=\frac{11y+4}{16}$  d'où
$y=\frac{4}{5}$.


Finalement,             $x=\frac{1}{2}y+\frac{7y}{16}=\frac{15}{16}\times
\frac{4}{5}=\frac{3}{4}$.

Je  gagne donc avec  une probabilité  de $\frac{3}{4}$:  avec un  peu de
mathématiques, je peux donc embrouiller mon voisin Ivan Ivanitch.




\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=1.8cm,semithick, bend angle=25]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 2em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state,initial] (A) {$\frac{3}{4}$};
 \node[state] (B) [above right of =A] {$\frac{7}{10}$};
 \node[state] (C) [ right of =B] {$\frac{3}{5}$};
 \node[state] (D) [right of =C] {$\frac{2}{5}$};
 \node[state,accepting] (E) [right of=D] {0};
 \node[state] (F) [below right of =A] {$\frac{4}{5}$};
 \node[state] (G) [ right of =F] {$\frac{9}{10}$};
 \node[state] (H) [ right of =G] {$\frac{9}{10}$};
 \node[state,accepting] (I) [right of=H] {1};

 \path 
       (A) edge node[] {} (B)
       (A) edge node[] {} (F)
       (B) edge node[] {} (C)
       (B) edge[bend left] node[] {} (F)
       (C) edge node[] {} (D)
       (C) edge node[] {} (F)
       (D) edge node[] {} (E)
       (D) edge node[] {} (F)
       (F) edge node[] {} (G)
       (F) edge[bend left] node[] {} (B)
       (G) edge node[] {} (H)
       (G) edge[loop above] node[] {} (G)
       (H) edge node[] {} (I)
       (H) edge[bend left] node[] {} (F)
       ;
\end{tikzpicture}
\end{center}


Je peux maintenant me demander combien de fois en moyenne je vais lancer
la pièce avant d'atteindre un état absorbant.

\begin{recherche}
  Démontrez que $m_i=\displaystyle\sum_{k\in\ER_i}^{}p_{ik}(1+m_k)$.

Déduisez-en que la durée moyenne  d'une partie avec Ivan Ivanitch est de
12 lancers.
\end{recherche}

\section{Comportement asymptotique des chaînes de \textsc{Markov}}


Zlot, Brzxxz  et Morzgniouf sont trois villes  situées respectivement en
Syldavie, Bordurie et Bouzoukstan.  Des trafiquants de photos dédicacées
du  groupe  ABBA  prennent  leur  marchandise le  matin  dans  n'importe
laquelle de  ces villes  pour l'apporter le  soir dans  n'importe quelle
autre. On  notera pour  simplifier $V_1$, $V_2$  et $V_3$ ces  villes et
$p_{ij}$ la probabilité qu'une marchandise  prise le matin dans la ville
$V_i$   soit  rendue   le  soir   dans  la   ville  $V_j$.   La  matrice
$P=(p_{ij})_{{1\leqslant   i   \leqslant  3}\atop   {1\leqslant   j\leqslant   3}}$  est   appelée
\textit{matrice de transition} de la chaîne de \textsc{Markov}.


\begin{definition}[Matrice stochastique]
  Une matrice dont  tous les coefficients sont positifs  ou nuls et dont
  la  somme  des  coefficients  de  chaque  ligne  vaut  1  est  appelée
  \textbf{matrice stochastique}.

Si, de plus, la somme des colonnes vaut 1, la matrice est dite \textbf{bistochastique}.
\end{definition}

Que peut-on dire d'une matrice de transition?



Voici le diagramme de transition des trafiquants suédophiles:


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=5cm,semithick, bend angle=10]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 2em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state] (A) {$V_1$};
 \node[state] (C) [below right of =A] {$V_3$};
 \node[state] (B) [below left of =A] {$V_2$};

 \path 
       (C) edge[bend left] node[below left] {0,2} (A)
       (A) edge[bend left] node[above right] {0,1} (C)
       (A) edge[loop above] node[above] {0,8} (A)
  (B) edge[bend left] node[above left] {0,3} (A)
       (A) edge[bend left] node[below right] {0,1} (B)
       (B) edge[loop below ] node[below ] {0,2} (B)
(C) edge[bend left] node[below] {0,6} (B)
       (B) edge[bend left] node[above] {0,5} (C)
       (C) edge[loop below ] node[below ] {0,2} (C)
       ;
\end{tikzpicture}
\end{center}



Il n'y a pas d'état absorbant a priori. Il faut donc changer notre fusil
d'épaule. Nous allons en fait utiliser le calcul matriciel.
La matrice de transition est:


$$
\begin{pmatrix}
0,8&0,1&0,1\\
0,3&0,2&0,5\\
0,2&0,2&0,6
\end{pmatrix}
$$


On notera  $x_i^{(k)}$ la proportion  de trafiquants qui se  trouvent au
matin du jour $k$ dans la ville $V_i$.


\begin{definition}[Vecteur d'état]
 On appelle
\textit{vecteur d'état}  tout élément $(x_1,...,x_n)$  de $\bbr^{n}$ tel
que $x_1+\cdots+x_n=1$. 
\end{definition}

Ainsi,  $x^{(k)}=\left(   x_1^{(k)},x_2^{(k)},x_3^{(k)}\right)$  est  un
vecteur d'état (pourquoi?).


\begin{recherche}
 Démontrez que: 
$$\forall k \in \llbracket 1,n\rrbracket,\quad x^{(k)}= x^{(k-1)}\cdot P$$

puis que:

$$\forall k \in \llbracket 1,n\rrbracket,\quad x^{(k)}=x^{(0)}\cdot P^k$$

\end{recherche}


Supposons que le chef de la mafia locale dispose de 1000 trafiquants qui partent tous le matin du jour 0 de la ville de Zlot. Quelle sera la proportion de trafiquants dans chacune des villes au bout d'une semaine ? d'un an ?

Il s'agit donc de calculer  des puissances successives de P.

On obtient les proportions au bout d'une semaine en 
calculant $ x^{(0)}\cdot p^7$ avec $x^{(0)}=\left(1000,0,0 \right)$.


Nous allons utiliser \Python pour les longs calculs en lançant \shell
\lstinline+$ ipython --pylab+ la suite 



\pythonc

\begin{lstlisting}[caption={}]
In [1]: A = matrix ([[0.8,0.1,0.1],[0.3,0.2,0.5],[0.2,0.2,0.6]])
In [2]: X = matrix ([[1000,0,0]])
In [3]: X*A
Out[3]: matrix([[ 800.,  100.,  100.]])
In [4]: X*(A**7)
Out[4]: matrix([[ 546.9038,  144.5711,  308.5251]])
In [5]: X*(A**365)
Out[5]: matrix([[ 536.58536585,  146.34146341,  317.07317073]])
\end{lstlisting}


Il semble que la proportion reste stable au bout d'un certain temps:


\begin{lstlisting}[caption={}]
In [6]: A**1000
Out[6]: 
matrix([[ 0.53658537,  0.14634146,  0.31707317],
        [ 0.53658537,  0.14634146,  0.31707317],
        [ 0.53658537,  0.14634146,  0.31707317]])
In [7]: A**10000
Out[7]: 
matrix([[ 0.53658537,  0.14634146,  0.31707317],
        [ 0.53658537,  0.14634146,  0.31707317],
        [ 0.53658537,  0.14634146,  0.31707317]])
\end{lstlisting}


On  observe  que  cette  matrice  \og à  l'infini\fg{}  a  trois  lignes
identiques.   Étudions   le   produit   d'un  vecteur   ligne   de   \og
$A_{\infty}$\fg{} par A:

\begin{lstlisting}[caption={}]
In [8]: Ainfini = A**(10000)
In [9]: v = Ainfini[0]
In [10]: v
Out[10]: matrix([[ 0.53658537,  0.14634146,  0.31707317]])
In [11]: v*A
Out[11]: matrix([[ 0.53658537,  0.14634146,  0.31707317]])
\end{lstlisting}


Troublant....En fait, ce résultat se généralise.


\begin{definition}[Matrice de transition régulière]
Une matrice de transition A est dite régulière si, et seulement si, il
existe  un entier  naturel $r$  tel que  $A^r$ a  ses  coefficients tous
\textbf{strictement} positifs.
\end{definition}


\begin{theoreme}[Théorème des chaînes de \textsc{Markov} régulières]
Soit A une matrice régulière. Il existe une matrice stochastique:

$$
A_{\infty}=\begin{pmatrix}
  a_1&a_2&\cdots&a_n\\
  a_1&a_2&\cdots&a_n\\
  \vdots&\vdots&\vdots&\vdots\\
  a_1&a_2&\cdots&a_n\\
\end{pmatrix}
$$

telles que $ \displaystyle\lim_{n \to +\infty} A^n =A_{\infty}$.


De plus, $v=(a_1,a_2,\cdots,a_n)$ est l'unique vecteur d'état stationnaire
(tel que $v\cdot A=v$).
\end{theoreme}


Nous démontrerons ce résultat après un peu de pratique du calcul matriciel.
\vfill

\eject

\section{Exercices}


\subsection{Chaînes absorbantes - automates}


\begin{exercice}[Ascension]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{plexy_gladz}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-4.45cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
  

  Vaclav veut faire l'ascension du mont Plexy-Gladz, plus haut sommet de
  Bordurie (1808  m). Il décide  de passer une  nuit au refuge  du Guide
  Suprême (1010 m)  et également au refuge de  La Grande Moustache (1507
  m).  Chaque  matin il  écoute  le bulletin  météo.  S'il  est bon,  il
  poursuit son  ascension jusqu'à l'étape suivante,  sinon, il redescend
  d'une étape. On suppose que Vaclav est initialement au refuge du Guide
  Suprême et que s'il est  obligé de redescendre au refuge de Szprinkoth
  (778 m),  il abandonne son  projet d'ascension. Enfin, il  faut savoir
  qu'en Bordurie, la météo est donnée en fonction d'un lancer de dé: on annonce du
  beau temps si la face marque V ou VI, et de la pluie si la face marque
  I, II, III ou IV.

Calculez la probabilité que Vaclav  arrive au sommet et la durée moyenne
de son ascension en jours.
\end{exercice}





\begin{exercice}[Tennis]
Deux joueurs s'affrontent  dans une partie de tennis.  Chaque point joué
est gagné par le joueur A avec une probabilité de 3/5, sinon c'est B qui
gagne. On  suppose que  l'issue de chaque  échange est  indépendante des
autres.

Initialement, les joueurs sont à 40 partout. Calculez la probabilité que
A gagne le jeu et la durée moyenne du jeu en nombre d'échanges.
\end{exercice}


\begin{exercice}[Palindrome]
On  dispose d'une  roue  de foire  non  truquée qui  affiche  1 avec  la
probabilité $p$ et 0  sinon. On lance la roue et on  note le résultat en
continuant tant qu'on  n'a pas obtenu un mot  symétrique (un palindrome)
comme 11, 101,  110010011, etc. Attention! 01010 ne  convient pas car la
roue s'arrête à 010.

On supposera que 1 et 0 ne sont pas des
palindromes.  Quelle est  la  durée moyenne  d'attente  pour obtenir  un
palindrome?
\end{exercice}



\begin{exercice}[Jeu]
   Vladimir
  choisit un mot constitué de 0 et de 1 et Anastasia un autre mot. 
  On lance ensuite une pièce de monnaie équilibrée (P=1, F=0)
  jusqu'à ce  qu'un des  deux mots choisis  apparaisse.  Le  gagnant est
  celui dont  le mot apparaît en  premier. Ce jeu  est-il équilibré dans
  les cas suivants:
\begin{multicols}{3}
  \begin{enumerate}
  \item $v=00$, $a=111$;
  \item $v=000$, $a=111111$;
  \item $v=00$, $a=101$;
  \item $v=1101$, $a=0101$;
  \item $v=1010$, $a=0011$;
  \item $v=101$, $a=1001$;
  \item $v=111$, $a=0011$;
  \item $v=010$, $a=1001$;
  \item $v=010$, $a=111$.
  \end{enumerate}
\end{multicols}
\end{exercice}


\begin{exercice}[Contrôle des naissances]
Pour  lutter  contre la  surpopulation,  le  gouvernement bordure  teste
plusieurs mesures.  Il est  décrété que les  parents auront  des enfants
jusqu'à ce que:
\begin{enumerate}
\item ils aient une fille;
\item les deux sexes soient représentés;
\item les deux sexes soient représentés deux fois;
\item  les  deux  sexes  soient  représentés  et  que  le  premier  sexe
      réapparaisse (5 filles, 8 garçons puis une fille par exemple).
\end{enumerate}
\end{exercice}


\begin{exercice}[Craps]
  
%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3.2cm]{craps}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
  

Le craps, ou la passe anglaise, est  le jeu de dés le plus populaire des
États-Unis. On jette deux dés et on additionne les numéros sortis. Si on
obtient 7 ou 11 on gagne, si on obtient 2, 3 ou 12 on perd.


Dans les autres  cas, on rejoue jusqu'à obtenir à  nouveau la même somme
sans obtenir 7.


Dressez l'automate  du craps en  distinguant 6 états:  \og défaite\fg{},
\og victoire\fg{},  \og début\fg{}, \og 5  ou 9\fg{}, \og  4 ou 10\fg{},
\og 6 ou 8\fg{}.

Calculez la probabilité de gagner et la durée moyenne d'une partie.





\end{exercice}



\subsection{Avec le calcul matriciel}





\begin{exercice}[Matrice bistochastique]
  Déterminez  un  vecteur d'état  simple  stationnaire  pour toutes  les
  distributions bistochastiques.
\end{exercice}

\begin{exercice}[LMD]
Voici  la matrice  de  transition des  passages $S_1\leftrightarrow  S_2
  \leftrightarrow S_3$ des promos de l'IUT d'informatique de Klow:

$$
\begin{pmatrix}
0,45&0,48&0,07\\
0,05&0,70&0,25\\
0,01&0,50&0,49
\end{pmatrix}
$$

Calculez la probabilité  de passer de $S_3$ en $S_1$  en 2 semestres, et
celle de passer de $S_1$ en $S_3$ en deux semestres.

Calculez   également  les   probabilités  stationnaires   (l'IUT,  c'est
tellement bien, on voudrait y passer sa vie...).



\end{exercice}


\begin{exercice}[Reprise]
Résolvez les  exercices précédents à  l'aide du calcul matriciel  (on ne
traitera pas les questions sur les durées moyennes).
\end{exercice}



%%% Local Variables: 
%%% TeX-master: "Poly_Probas_Stats_13"
%%% End: 
