%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8,fourier]{preambuleTrm}
%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}
\usepackage{tkz-graph,tkz-berge}
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning}
\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}

\newcommand\nor{\downarrow}
\newcommand\nand{\mid}

\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}


\graphicspath{{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}}




\lstset{numbers=none,language=scilab,xleftmargin=10pt,%
keywordstyle =\color{orange!40}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{black!90!red},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}





\setcounter{tocdepth}{2} %\setcounter{page}{0}


\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}
\usepackage{elephantbird}



\begin{document}


\title[] % (optional, use only with long paper titles)
{Chaînes de Markov: une initiation}

\subtitle{INFO1 - Semaine 22}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{IUT} de Nantes - Dpt d'informatique }% (optional, but mostly needed)

\logo{\includegraphics[scale=0.15]{logo_iut}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{Dernière mise à jour: \today}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

\AtBeginSubsubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}




\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection,currentsubsection]
       \end{multicols}
}

  \end{frame}
}





\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
 {\scriptsize
\begin{multicols}{2}
    \tableofcontents[currentsection]
       \end{multicols}
}

  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{multicols}{2} 
 \tableofcontents
\end{multicols}
}

 
 \end{frame}




 \begin{frame}
 
\begin{figure}
\begin{center}
  \includegraphics{markov}
\caption{\foreignlanguage{russian}{Андрей Андреевич  МАРКОВ} (1856 -
1922)}
\end{center}
\end{figure}



 \end{frame}





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




\subsection{Découverte}

\begin{frame}
Les boules dans l'urne, deux tirages successifs sans remise...
\end{frame}


\begin{frame}



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

\pause

 \textbf{Le présent contient toutes les données du passé...}
\end{frame}



\subsection{Premier exemple - Règles de parcours}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{rouble}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{patin}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{tatiana}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}
  \begin{itemize}
  \item état absorbant
  \item bord
  \item états intérieurs
  \item chaîne absorbante
  \item parcours (promenade) aléatoire
  \item longueur d'un parcours
  \end{itemize}
\end{frame}



\begin{frame} \frametitle{Les règles}
  \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}
\end{frame}


\begin{frame}
  

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


\pause

\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\\
\end{eqnarray*}

\end{frame}

\begin{frame}
\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}



  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{frame}




\begin{frame} \frametitle{Temps 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}

\end{frame}




\begin{frame} \frametitle{Rappel}
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}$$

\pause

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

\pause

Calculer   $(1-q)T$    en   fonction    de   S
\end{frame}







\subsection{Deuxième exemple - Valeur moyenne}





\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.9\textheight]{rouble}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  

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

\end{frame}



\begin{frame}
  \begin{itemize}
  \item  probabilité $p_i$ pour un
état $i$ d'être \og absorbé\fg{} dans un sous-ensemble SB du bord;
\item $p_i=1$;
\item $p_i=0$
\item $p_i=\displaystyle\sum_{k\in S}^{}p_{ik}p_k$
\item $p_i=\displaystyle\sum_{k\in \ER_i}^{}p_{ik}p_k$
  \end{itemize}
\end{frame}







\begin{frame}
  

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

\end{frame}



\begin{frame}
  
\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}
\end{frame}



\begin{frame}
  
\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}
\end{frame}




\begin{frame}


\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}
\end{frame}







\begin{frame}

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

\end{frame}

\begin{frame}{Durée moyenne}
 La valeur  du délai d'absorption  est égal à  1 augmenté de  la moyenne
 pondérée des délais d'absorption en les états voisins.


\pause 


$$ m_i=1+\sum_{k \geqslant 1}p_{ik}m_k$$
\end{frame}

\begin{frame}
  $$X_i=\displaystyle\sum_{k \geqslant 1}\indi{ik}(1+Y_k)$$
\end{frame}


\begin{frame}
\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}

\end{frame}



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


\begin{frame}

%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{mafia}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\textwidth]{abba}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}
\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}
\end{frame}





\begin{frame}
  matrice de transition
\end{frame}


\begin{frame}

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?).


\pause

 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{frame}





\begin{frame}

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)$.

\pause


Nous allons utiliser SCILAB pour les longs calculs.


\end{frame}



\begin{frame}


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

\end{frame}


\begin{frame}
  

\begin{theorem}[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{theorem}

\end{frame}


\end{document}
%%% Local Variables: 
%%% TeX-master: t
%%% End: 
