Problème de compilation beamer

\documentclass[9pt,handout]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[all]{xy}
\usepackage{ucs}
\usefonttheme[onlymath]{serif}
\usepackage{tikz}
\usepackage{algorithm}
\usepackage{color}
\usetheme{Warsaw}
\newtheorem{thm}{\textsl{Théorème}}[section]
\newtheorem*{dfn}{\textsl{Définition}}
\newtheorem*{prp}{\textsl{Proposition}}
\newtheorem{cor}[thm]{\textsl{Corollaire}}
\newtheorem*{lem}{\textsl{Lemme}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newtheorem*{rmq}{\textsl{Remarque}}
\newtheorem*{ex}{\textsl{Exemple}}
\newtheorem*{rap}{\textsl{Rappel}}
\setbeamercovered{transparent}
\usetheme{CambridgeUS}
\title[titre]{\structure{\textbf{\textsl{titre }}}}
\author{ E}
\institute[]
{
\large Master Mathématiques Appliquées\\\vspace{2\baselineskip}Faculté Polydisciplinaire de l \normalsize \\
Encadré par : T
  }

\date{27 juin 2016}
% Optionnel. La date, généralement celle du jour de la conférence

\subject{Sujet de votre diaporama}
% C'est utilisé dans les métadonnes du PDF
\begin{document}
\frame{\titlepage}
\tableofcontents
\begin{frame}{Introduction}
\begin{description}
  \item[*] La méthode de Monte Carlo est une méthode numérique, qui utilise des tirages
aléatoires pour réaliser le calcul d’une quantité déterministe.
  \item[*] La simulation parfaite(1996): il s'agit d'un algorithme qui fournit un échantillon de la distribution stationnaire d'une chaîne finie basé sur la méthode couplage.
\end{description}
\end{frame}
\section{Les Modèles Markoviens}
\begin{frame}
\begin{block}{Définition:Chaîne de Markov a temps discret}
Soit $(X_{n})_{n \geq 0 }$  un processus aléatoire d'espace d'état $\chi$, fini ou dénombrable. On dit que $(X_{n})_{n \geq 0}$ est une chaîne de Markov si:$$\forall x\in \chi,
                         \mathbb{P}(\underbrace{X_{n+1}=x}_{\text{Le futur}}\mid,\underbrace{X_0=x_0, X_1=x_1,\ldots, X_{n}=x_{n}}_{\text{Le passé (et le présent)}} )=\mathbb{P}(\underbrace{X_{n+1}=x}_{\text{Le futur}}\mid,\underbrace{X_{n}=x_{n}}_{\text{Le présent}} ).$$\\

si de plus la quantité$\mathbb{P}(X_{n+1}=x^{'}\mid, X_{n}=x)$ ne dépend pas de $n$,i.e
                                                                                          $$\forall n\in \mathbb{N}  , \mathbb{P}(X_{n+1}=x^{'}\mid, X_{n}=x)=\mathbb{P}(X_{1}=x^{'}\mid, X_{0}=x).$$
                                                                                         alors la cha\^{\i}ne de Markov est dite homogène.


 \end{block}
\begin{block}{\textcolor[rgb]{0.00,0.00,0.69}{.}}
Une chaîne de Markov à temps discret est définie par :\begin{itemize}
                                                       \item $\chi$: un ensemble d'états fini ou infini dénombrable,
                                                       \item Une matrice  de transition P\begin{itemize}
  \item Positive: $\forall x,x^{'}\in \chi, P(x,x^{'})\geq 0$
  \item Stochastique: $\forall x\in \chi,\sum_{x^{'}\in \chi}P(x,x^{'})=1 $
\end{itemize}
\item Un vecteur $\Pi :\chi\rightarrow [0,1]$ :  appelé distribution initiale, tel que :
$\sum_{n\in\chi}\Pi[n]=1$
                                                     \end{itemize}
\end{block}
\end{frame}
\begin{frame}
\begin{block}{Loi de probabilité de chaîne de Markov}
\begin{itemize}
  \item la DTMC est définie par une distribution stationnaire (si elle existe)(comportement à $\infty $)
  \item la DTMC est définie par des distributions transitoires $\Pi(n)=(\Pi_{1}(n),\Pi_{2}(n)),\ldots,\Pi_{n}(n),\ldots$ ( avec $\Pi_{i}(n)=P(X_{n}=i) ou i\in \chi$)(comportement à $n$) .
\end{itemize}
\begin{equation}
\boxed{
$$ \Pi(n)=\Pi(n-1)P=\Pi(0)P^{n} $$
}
\end{equation}

\end{block}
\begin{block}{Distribution limite :}
 si la limite $\lim_{n\rightarrow\infty}\Pi(n) $ existe, nous la  notons $\Pi$ et elle vérifiera $\Pi=\Pi P$. Dans ce cas, on dit que $\Pi$ est une distribution stationnaire de la chaîne $X=(X_{n})_{n\geq 0}$
\end{block}
\begin{alertblock}{ Remarque }
Il faut toutefois constater que le calcul explicite du régime
transitoire s'avère pénible, parfoi impossible, pour la plupart des
modèles considérés.
\end{alertblock}
\end{frame}
\begin{frame}{Classification des DTMCs}
\begin{block}{ Définition}
      On définit la période d'un état $i\in\chi$ par $\delta_{i}=pgcd(n\geq 1,p_{ii}(n)>0)$
\end{block}


\begin{figure}[!h]

\xymatrix {
 & États \ar[dl] \ar[dr] &&&  États \ar[dl] \ar[dr] \\
Periodiques && Aperiodiques & Transitoires && Recurrents \ar[dl] \ar[dr] \\
&&&& Nuls && Non{-}nuls
}

\caption{Double classification des états d'une DTMC}
\end{figure}
\end{frame}

\begin{frame}
\emph{Dans notre recherche nous nous intéressons principalement du  chaîne de Markov à temps discret homogène, irréductible(tous les états communiquent entre eux) et à espace d'état fini.}
\end{frame}

\begin{frame}
\begin{block}{ chaîne de Markove continu}
\begin{itemize}
  \item  Une chaîne de Markov à temps continu  $\{X_{t},t\geq0\}$, prend des valeurs dans un espace d’états $\chi$ discret ( qui peut être fini ou infini) et le temps est continu,$t\in\mathbb{R}_{\geq0}$. La matrice des probabilités de transition de la chaîne $\{X_{t},t\geq0\}$ à l'instant t est définie pour tout instant $t\geq0$ par:
\begin{equation}
\boxed{
$$ \forall x,x^{'}\in\chi,P^{t}(x,x^{'})=\mathbb{P}(X_{t}=x^{'}\mid X_{0}=x)  $$
}
\end{equation}
  \item Une CTMC $\{X_{t},t\geq0\}$ est homogène dans le temps si pour tout $x,x^{'}\in\chi$ :
$$ \forall t,v \geq0,\mathbb{P}(X_{t+v}=x^{'}\mid X_{t}=x)=\mathbb{P}(X_{v}=x^{'}\mid X_{0}=x) $$
\end{itemize}
\end{block}
\end{frame}

\begin{frame}
\begin{block}{Génerateur infinitésimal}
  Le générateur infinitésimal $Q=\lim_{t\rightarrow0}\frac{1}{t}(P^{t}-I)$ d’une CTMC possède les propriétés suivantes :
  \begin{itemize}
    \item 	Les éléments non diagonaux sont positifs ou nuls :
    $$ Q(x,x^{'})\geq0, \forall x\neq x^{'} $$
    \item 	Les éléments diagonaux sont négatifs :
    $$Q(x,x^{'})<0 $$
    \item 	La somme des éléments de chacune des lignes est nulle :
    $$ Q(x,x)=-\sum_{x\neq x^{'}}Q(x,x^{'})$$
  \end{itemize}
  \end{block}
\end{frame}
\section{Ordres stochastiques}
\begin{frame}
\begin{block}{ Définition }
Un ordre stochastique est un ordre partiel sur un espace des fonctions de répartition.
\end{block}
\xymatrix {
 & Ordre \hspace*{0.1cm}stochastique \ar[dl] \ar[dr]  \\
ordre\hspace*{0.1cm} stochastique\hspace*{0.1cm} integral \ar[d]^{exemple} && ordre\hspace*{0.1cm} stochastique\hspace*{0.1cm} ensembliste  \ar[d]^{exemple} \\
l^{'}ordre fort ST,\hspace*{0.1cm} l'ordre ICX... && ST,\hspace*{0.1cm}WK...
}
\end{frame}

\begin{frame}
\begin{block}{ Ordre stochastique integral }
Un ordre stochastique  est dit intégral si il existe une famille de fonctions (mesurables) $\Theta$ telle que:\\
\begin{center}
$ X\preceq_{\Theta}Y$ $si et seulement si$ $E[f(X)]\leq E[f(Y)], \forall f\in \Theta$
\end{center}
Quand les espérances existent, est appelé un ordre intégral, et sera noté par$\preceq_{\Theta}$.
\end{block}
\begin{block}{ Ordre stochastique ensembliste }
$X\preceq_{\Theta}Y$ si et seulement si :
  $$\mathbb{P}(X\in\Gamma)\leq \mathbb{P}(Y\in\Gamma),\forall\Gamma\in\gamma(\chi)$$
avec $\gamma$ est un ensemble croissante.
\end{block}
  L’ordre stochastique le plus connu et qui sera utilisé dans notre travail est l’ordre stochastique fort notée par $\preceq_{st}$.
\end{frame}

\begin{frame}
\begin{block}{ Ordre stochastique forte }
La relation d’ordre stochastique fort a été initialement considérée pour la comparaison des fonctions de répartition, comme une généralisation de la comparaison des nombres réels. Ainsi, définir l’ordre $\preceq_{st}$ entre deux fonctions de répartition, revient à faire la comparaison par point
de ces deux fonctions.
\end{block}
\begin{block}{$\preceq_{st}$sur un espace fini totalement ordonne}
Caractérisation sur $\chi=\{1,2,\cdots,n\}$ (x et y deux vecteurs de probabilité)
\begin{center}
$X \preceq_{st} Y \Rightarrow  $ $\sideset{}{}\sum_{k\geq i}^{n}  {x_{k}} \leq \sideset{}{}\sum_{k\geq i}^{n}  {y_{k}} $ $i=1,\ldots,n$
\end{center}
\end{block}
\textbf{ exemple:\\}
 $x=(0,0.1,0.1,0.1,0.3)$ et $y=(0.1,0,0.3,0.1,0.4)$ et $z=(0.2,0,0.6,0.1,0.1)$ nous avons:
$$x=(0,0.1,0.1,0.1,0.3)\preceq_{st}y=(0.1,0,0.3,0.1,0.4)$$
$$car\left\{
  \begin{array}{ll}
    0.3   & \hbox{$\leq$ O.4;} \\
    0.1+0.3   & \hbox{$\leq$ 0.1+O.4;} \\
    0.1+0.1+0.3   & \hbox{$\leq$ 0.3+0.1+O.4;} \\
    0.1+0.1+0.1+0.3   & \hbox{$\leq$ 0+0.3+0.1+O.4;} \\
    0+0.1+0.1+0.1+0.3  & \hbox{$\leq$ 0.1+0+0.3+0.1+O.4.}
  \end{array}
\right.
$$
 $y=(0.1,0,0.3,0.1,0.4)\npreceq_{st}z=(0.2,0,0.6,0.1,0.1)$ car$0.4 \nleq 0.1$
\end{frame}
\section{La comparaison et monotonie des chînes de Markov}
\begin{frame}
\textcolor[rgb]{1.00,0.00,0.00}{\textbf{Caractérisation algébrique de la monotonie:}}
L'espace fini, totalement ordonne $\chi=\{1,2,\cdots,n\}$
\hspace*{1cm}[Rappel :$X \preceq_{st} Y \Rightarrow  $ $\sideset{}{}\sum_{k\geq i}^{n}  {x_{k}} \leq \sideset{}{}\sum_{k\geq i}^{n}  {y_{k}} $ $i=1,\ldots,n$]
\begin{center}
\textcolor[rgb]{0.00,0.59,0.00}{\textbf{ Comparaison :}}
\end{center}
\begin{minipage}{6cm}
 $K_{st}= \begin{bmatrix}
   1 & 0 & 0 & \cdots & 0 \\
   1 & 1 & 0& \cdots & 0 \\
   1 & 1 & 1 & \cdots& 0\\
   \vdots & \vdots & \vdots & \ddots & \vdots\\
  1 & 1 & 1 & \cdots & 1 \\
 \end{bmatrix}$
\end{minipage}
\begin{minipage}{6cm}
  \textcolor[rgb]{1.00,0.00,0.00}{Vecteurs}:$X \preceq_{st} Y\Leftrightarrow XK_{st}\leq YK_{st}$\\
                              \textcolor[rgb]{1.00,0.00,0.00}{Matrices}:$P \preceq_{st} Q\Leftrightarrow PK_{st}\leq QK_{st}$.
\end{minipage}
 \begin{center}
\textcolor[rgb]{0.00,0.59,0.00}{\textbf{ Monotonie :}}
\end{center}
P est $\preceq_{st}$-monotone $\Leftrightarrow$ $P(x,.) \preceq_{st} P(y,.)$ $\forall x \leq y$ \\
\hspace*{2.9cm}$\Leftrightarrow$ les colonnes de la matrice $PK_{st}$  sont croissantes.\\
On note par $P(x, .)$ la ligne $x$ de la matrice.
\end{frame}
\begin{frame}
\begin{center}
\textcolor[rgb]{1.00,0.00,0.00}{Comparaison des chaînes de Markov}
\end{center}
\begin{block}{Monotonie d'une DTMC}

Nous dirons qu'une DTMC est $\preceq_{st}-monotonie$ si sa matrice de transition est $\preceq_{st}-monotonie$.
\end{block}
\begin{block}{Comparaison de DTMC}
Soient $\{X_{n},n\geq 0\}$ et $\{Y_{n},n\geq 0\}$ deux DTMCs homogènes, leurs matrices de transition respectives sont $P$ et $Q$, si:\\
\begin{itemize}
  \item $X_{0}\preceq_{st}Y_{0}$
  \item $P\preceq_{st}Q$
  \item $P$ ou $Q$ est $\preceq_{st}-monotone$
\end{itemize}
alors:\\
$$\{X_{n}\}\preceq_{st}\{Y_{n}\}$$
\end{block}
\end{frame}
\section{Construction algorithmique des bornes stochastiques}
\begin{frame}
la caractérisation de la comparaison stochastique dans l'ordre total a ouvert une voie
pour la construction algorithmique des bornes $\preceq_{st}-monotonie$.
\end{frame}
\begin{frame}
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}\\
\textcolor[rgb]{0.78,0.47,0.86}{\textbf{Algorithme 1}}(algorithme de Vincent) construction d'une borne supérieure st-monotone $P^{sup}$ pour une matrice stochastique $P$ d'ordre $n$\\
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}\\
\begin{enumerate}
  \item: \textbf{Entrée}:$P$
  \item:\textbf{Sortie}: $P^{sup}$
  \item: $P^{sup}(1,n)=P(1,n)$
  \item: \textbf{Pour}$i=1,2,\cdots,n$ \textbf{faire}
  \item: \space\space\space\space\space $P^{sup}(i,n)=\max(P^{sup}(i-1,nn),P(i,n));$
  \item: \textbf{fin pour}
  \item: \textbf{Pour} $j=n-1,\cdots,2$ \textbf{faire}
  \item: \space\space\space\space\space$P^{sup}(1,j)=P(1,j)$
  \item: \space\space\space\space\space\textbf{pour} $i=2,3,\cdots,n$  \textbf{faire}

  \item: \space\space\space\space\space\space\space\space\space\space$P^{sup}(i,j)=\max(\sum_{k=j}^{n}P^{sup}(i-1,k),\sum_{k=j}^{n}P(i,k))-\sum_{k=j+1}^{n}P^{sup}(i,k)$
  \item: \space\space\space\space\space$\textbf{fin pour}$
  \item: \textbf{fin pour}
  \item: \textbf{pour}$i=2,3,\cdots,n$ \textbf{faire}
  \item: \space\space\space\space\space$P^{sup}(i,1)=1-\sum_{k=2}^{n}P^{sup}(i,k)$
  \item: \textbf{fin pour}
  \item: \textbf{retourner} $P^{sup}$

\end{enumerate}
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}
\end{frame}
\begin{frame}
\textcolor[rgb]{1.00,0.00,0.00}{Propriétés de l'algorithme}\\
\begin{itemize}
  \item \textcolor[rgb]{0.00,0.59,0.00}{\textbf{Optimalité :}}\\    Soit $P$ une matrice stochastique et $P^{sup}$ la matrice obtenue par l'algorithme $1$. La matrice $P^{sup}$ est la plus petite matrice $\preceq_{st}-monotone$, telle que $P\preceq_{st}P^{sup}$. Formellement, s'il existe une matrice $R$ telle que:\\
    \begin{itemize}
      \item $R est \preceq_{st}-monotone $
      \item $P\preceq_{st}R$
      alors, $P^{sup}\preceq_{st}R$
    \end{itemize}

  \item \textcolor[rgb]{0.00,0.59,0.00}{\textbf{Inconvénient:}}\\    \begin{itemize}
      \item Supression de transitions dans la matrice $P^{sup}(irréductibilité)$
      \item Complexité
    \end{itemize}
\end{itemize}
\end{frame}
\begin{frame}
\textcolor[rgb]{1.00,0.00,0.00}{Amélioration de l'algorithme de Vincet(IMSUB)}\\
Forneau et al ont proposé un algorithme qui construit une borne supérieure $\preceq_{st}-monotone$ irréductible  pour une matrice initial irréductible vérifiant les conditions suivantes:\\
\begin{itemize}
  \item $P(1,1)>0$
  \item Chaque ligne du triangle inférieur (sans la diagonale principale) possède un élément strictement positif.
\end{itemize}
$\underline{solution:}$algorithme  de IMSUB( Irreductible Monotonne Strong Stochastiq Upper Bound)
\end{frame}
\begin{frame}
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}\\
\textcolor[rgb]{0.78,0.47,0.86}{\textbf{Algorithme 2}}(algorithme IMSUB) construction d'une borne irréductible\\
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}\\
\begin{enumerate}
  \item:\textbf{Notation:}$\varepsilon$ constante $0<\varepsilon<1$
  \item:\textbf{Entrée}:$P$
  \item:\textbf{Sortie}: $P^{sup}$
  \item:$P^{sup}(1,n)=P(1,n)$
  \item:\textbf{Pour}$i=1,2,\cdots,n$ \textbf{faire}
  \item: \space\space\space\space\space$P^{sup}(i,n)=\max(P^{sup}(i-1,nn),P(i,n));$
  \item:\textbf{fin pour}
  \item:\textbf{Pour} $j=n-1,\cdots,2$ \textbf{faire}
  \item: \space\space\space\space\space$P^{sup}(1,j)=P(1,j)$
  \item: \space\space\space\space\space\textbf{pour} $i=2,3,\cdots,n$  \textbf{faire}
  \item:\space\space\space\space\space\space\space\space\space\space$P^{sup}(i,j)=\max(\sum_{k=j}^{n}P^{sup}(i-1,k),\sum_{k=j}^{n}P(i,k))-\sum_{k=j+1}^{n}P^{sup}(i,k)$
   \item: \space\space\space\space\space\space\space\space\space\space\textbf{si}$(i>j)$ \textbf{et} $(P^{sup}(i,j)=0)$\textbf{alors}
  \item:\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space $ P^{sup}(i,j)=$ $\varepsilon(1-\sum_{k=j+1}^{n}P^{sup}(i,k))$
  \item:\space\space\space\space\space\space\space\space\space\space$\textbf{fin si}$
  \item: \space\space\space\space\space$\textbf{fin pour}$
  \item:\textbf{fin pour}
  \item:\textbf{pour}$i=2,3,\cdots,n$ \textbf{faire}
  \item: \space\space\space\space\space$P^{sup}(i,1)=1-\sum_{k=2}^{n}P^{sup}(i,k)$
  \item:\textbf{fin pour}
  \item:\textbf{retourner} $P^{sup}$
\end{enumerate}
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}
\end{frame}
\begin{frame}
\begin{alertblock}{Remarque}
Remarquons que la seule différence avec l'algorithme 1 est dans la ligne  12 de l'algorithme
2.Cette ligne permet de garder les transition de la matrice borne positives.
\end{alertblock}
\textcolor[rgb]{0.00,0.59,0.00}{\textbf{Exemple:}}\\
\begin{center}
$P$=
$
\begin{pmatrix}
  0.5 & 0.2 & 0.1 & 0.2 & 0.0 \\
  0.1 & 0.7 & 0.1 & 0.0 & 0.1 \\
  0.2 & 0.1 & 0.5 & 0.2 & 0.0 \\
  0.1 & 0.0& 0.1 & 0.7 & 0.1 \\
  0.0 & 0.2 &0.2 & 0.1 & 0.5 \\
\end{pmatrix}$
\end{center}
\end{frame}
\begin{frame}
\begin{itemize}
  \item $\rightarrow \textcolor{cyan}{P^{sup}(1,n)=P(1,n)}$ avec $n=1,2,3,4,5$
  \item $\textcolor{violet}{P^{sup}=\max(P^{sup}(i-1,5),P(i,5))}$ avec $i={2,3,4,5}$ et $j={1,2,3,4,5}$
  \end{itemize}
  \begin{center}
$\begin{pmatrix}
  \textcolor{cyan}{0.5} & \textcolor{cyan}{0.2} & \textcolor{cyan}{0.1} & \textcolor{cyan}{0.2} & \textcolor{cyan}{0.0} \\
  \textcolor{violet}{0.1} & \textcolor{violet}{0.7} & \textcolor{violet}{0.1} & \textcolor{violet}{0.2} & \textcolor{violet}{0.1} \\
  \textcolor{violet}{0.5} & \textcolor{violet}{0.7}& \textcolor{violet}{0.5}& \textcolor{violet}{0.2} & \textcolor{violet}{0.1}  \\
  \textcolor{violet}{0.5} & \textcolor{violet}{0.7}& \textcolor{violet}{0.5} & \textcolor{violet}{0.7} & \textcolor{violet}{0.1} \\
  \textcolor{violet}{0.5} & \textcolor{violet}{0.7} &\textcolor{violet}{0.5} & \textcolor{violet}{0.7} & \textcolor{violet}{0.5} \\
\end{pmatrix} $
\end{center}
\begin{itemize}
  \item Pour $j=4,3,2$ et $i=2,3,4,5$  \\
$\textcolor{purple}{P^{sup}(i,j)=\max(\sum_{k=j}^{5}P^{sup}_{x}(i-1,k), \sum_{k\geq j}^{5}P(i,k))-\sum_{k=j+1}^{5}P^{sup}(i,k)}$\\
et pour $\textcolor{blue}{P^{sup}(i,1)}$ va recevoir $1-\sum_{k=2}^{5}P^{sup}(i,k)$
\end{itemize}
$$\begin{pmatrix}
   \textcolor{cyan}{0.5} & \textcolor{cyan}{0.2} & \textcolor{cyan}{0.1} & \textcolor{cyan}{0.2} & \textcolor{cyan}{0.0} \\
    \textcolor{blue}{0.1} &  \textcolor{purple}{0.6} & \textcolor{purple}{0.1} & \textcolor{purple}{0.1} & \textcolor{violet}{0.1}\\
    \textcolor{blue}{0.1} & \textcolor{purple}{0.2} & \textcolor{purple}{0.5} & \textcolor{purple}{0.1} & \textcolor{violet}{0.1} \\
    \textcolor{blue}{0.1} &\textcolor{purple}{0.0}  & \textcolor{purple}{0.1} & \textcolor{purple}{0.7} &\textcolor{violet}{0.1} \\
    \textcolor{blue}{0.0} & \textcolor{purple}{0.1} & \textcolor{purple}{0.1} & \textcolor{purple}{0.3} &\textcolor{violet}{0.5} \\
  \end{pmatrix}
  $$
  \end{frame}
  \begin{frame}
  \begin{itemize}
  \item si $(i>j)$ $ P^{sup}(i,j)=$ $\varepsilon(1-\sum_{k=j+1}^{n}P^{sup}(i,k))$
  \begin{center}
  $P^{sup}=\begin{pmatrix}
                           0.5 & 0.2 & 0.1 & 0.2 & 0.0 \\
                           0.1 & 0.6 & 0.1 & 0.1 & 0.1 \\
                           0.0 & 0.3 & 0.5 & 0.1 & 0.1 \\
                           0.0 & 0.0 & 0. & 0.7 & 0.1 \\
                           0.0 & 0.0 & 0.0 & 0.5 & 0.5 \\
                         \end{pmatrix}$
\end{center}
\end{itemize}
\end{frame}
\section{La simulation de Monte-Carlo}
\begin{frame}{Introduction}
\begin{itemize}
\item La simulation parfaite a été introduite par Propp et Wilson, il s’agit d’un algorithme de simulation qui fournit un échantillon non-biaisé de la distribution stationnaire d’une chaîne  de Markov finie.\\
\item sa complexité dépend donc de la cardinalité de l’espace d’états Dans  ce cas, l’utilisation de l’algorithme de simulation parfaite n’est pas toujours envisageable\\
\item Cette technique de simulation a été améliorée dans le cas des chaînes de Markov monotones.
\end{itemize}
\end{frame}
\begin{frame}
\textcolor[rgb]{1.00,0.00,0.00}{Description de la simulation parfaite:}\\
\begin{itemize}
  \item La simulation parfaite est basée sur l’algorithme de couplage dans le passé (CFTP).
  \item Cete méthode a été utilisée avec succès dans la simulation de
grands systèmes Markoviens.
\end{itemize}
Pour décrire l'algorithme CFTP:\\
\begin{itemize}
  \item Nous supposons que notre chaîne de Markov est homogène et irréductible
  \item Nous notons aussi $\mathbb{U}$ l'ensemble des variables aléatoires uniformes sur $]0,1[$
  \item $\Phi_{r}$ fonction de transition
\end{itemize}
\end{frame}
\begin{frame}
\begin{block}{Fonction de transition d'une DTMC}
\begin{equation}
\boxed{
$$X_{n+1}=\Phi_{r}(X_{n},U_{n+1})$$
}
\end{equation}
où $U_{n}$ appartient à la séquence des entrées du système, généralement une séquence d'une variable aléatoire prenant ses valeurs dans l'espace de probabilités $\mathbb{U}=]0,1[$
\end{block}
\begin{alertblock}{Remarque}
Généralement, lorsque nous disposons d'un espace d'état totalement ordonné, nous utilisons l'inverse de la fonction de répartition comme fonction de transition du systéme.
\end{alertblock}
\end{frame}
\begin{frame}
\textcolor[rgb]{0.00,0.59,0.00}{\textbf{Exemple:\\}}
Soit $X$ une DTMC ayant comme matrice de transition $P$ définie sur l'espace d'états totalement ordonné $\chi=\{a,b,c\}$\\
$$P=\begin{pmatrix}
      0.7 & 0.2 & 0.1\\
      0.5 & 0.5 & 0 \\
      0.6 & 0.1 & 0.3 \\
    \end{pmatrix}
$$
Nous pouvons considérer l'inverse de la fonction de répartition de $X$ comme fonction de transition du sytème. Elle sera égale à:\\
\begin{center}
$\Phi_{r}(a,u) =\left\{
                 \begin{array}{ll}
                   a  &  \hbox{ si $0\leq u<0.7$;} \\
                   b  &  \hbox{si $0.7\leq u<0.9$;} \\
                   c  &  \hbox{si $0.9\leq u\leq 1$.}
                 \end{array}
               \right.$\\
 $\Phi_{r}(b,u) =\left\{
                 \begin{array}{ll}
                   a  &  \hbox{ si $0\leq u<0.5$;} \\
                   b  &  \hbox{si $0.5\leq u\leq 1$.}
                 \end{array}
               \right.$\\
 $\Phi_{r}(c,u) =\left\{
                 \begin{array}{ll}
                   a  &  \hbox{ si $0\leq u<0.6$;} \\
                   b  &  \hbox{si $0.6\leq u<0.7$;} \\
                   c  &  \hbox{si $0.7\leq u\leq 1$.}
                 \end{array}
                 \right.$
\end{center}
\end{frame}
\begin{frame}
\textbf{\textcolor[rgb]{1.00,0.00,0.00}{Couplage depuis le passé (CFTP)\\}}
\begin{itemize}
  \item L'idée de l'algorithme CFTP consiste à lancer simultanément, depuis un instant $T <0$dans le passée jusqu'à l'instant $0$, $N$ copies de la chaîne de Markov étudiée $X$.
  \item  Chaque copie démarre à l'instant $T$ dans un état différent, en suivant la même fonction de transition $\Phi_{r}$ ,et en utilisant la même suite de nombres aléatoires $u_{1},u_{2},\cdots$ pour la fonction transition.
  \item  On cherche le couplage de toutes ces chaînes, c'est-à-dire qu'elles aient atteint le même état à un instant $T_{c}$ entre $T$ et $0$. Deux chaînes ou trajectoires qui se rencontrent, suivent exactement le même chemin après.
\end{itemize}
\end{frame}
\begin{frame}
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}\\
\textcolor[rgb]{0.78,0.47,0.86}{\textbf{Algorithme 3}}(Algorithme CFTP) Coupling From The Past\\
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}\\
\begin{enumerate}
  \item \textbf{ \textcolor[rgb]{0.73,0.33,0.83}{Etape 1:}} Initialisation :\\
  \hspace*{2cm}$ T\leftarrow -1$
 \item \textbf{ \textcolor[rgb]{0.73,0.33,0.83}{Etape 2:}} Générer des variables aléatoires indépendantes\\
 \hspace*{2cm} $u_{T+1},\cdots,u_{\lceil T/2 \rceil}$\\
\hspace*{2cm}$u\leftarrow (u_{T+1},\cdots,u_{0})$
 \textcolor[rgb]{0.73,0.33,0.83}{ \item \textbf{ Etape 3:}}Lancer N chaînes de Markov identiques à $X$, chacune dans un état\\
 \hspace*{2cm}différent et laisser évoluer ces chaînes depuis $T$ jusqu'à  l'instant $0$.\\ \hspace*{2cm} Puis calculer ${\Phi_{r}}_{0}^{T}(i,u)$ pour tout $i\in\chi$
  \textcolor[rgb]{0.73,0.33,0.83}{\item \textbf{ Etape 4:}}Si $\exists i_{0}\in\chi,$ $\forall i\in\chi$, $i_{0}={\Phi_{r}}_{0}^{T}(i,u)$\\
\hspace*{2cm} on retourne $i_{0}$ et on arrête.\\
\hspace*{2cm}  Sinon $T\leftarrow2T$et on revient àl'étape 2.
\end{enumerate}
\begin{tikzpicture}
\draw (0,0) plot coordinates {(0,0) (17,0)};
\end{tikzpicture}
\end{frame}
\begin{frame}
\textcolor[rgb]{0.00,0.59,0.00}{\textbf{Exemple:}}\\
l'espace d'états $\chi=\{1,2,3,4\}$
$$P=\begin{pmatrix}
      0.4 & 0.3 & 0.3 & 0 \\
      0.5 & 0 & 0.5 & 0 \\
      0 & 0.35 & 0.1 & 0.55 \\
      0 & 0.25 & 0.3 & 0.45 \\
    \end{pmatrix}$$
Soit $u$ une variable aléatoire à valeur dans l'intervalle $]0,1[$, et soit $\mathbb{U}=(0.31, 0.38, 0.65, 0.94, 0.71,0.1, 0.85, 0.51, 0.02,
0.66)$ une séquence de tirages aléatoires de la variable $u$.\\
initialement, tous les états sont potentiellement des états d'arrivée des trajectoires.
\end{frame}
\begin{frame}
\textcolor[rgb]{0.50,0.00,0.00}{\textbf{A l'itération 1 }}:nous générons une transition pour chacun des états de $\chi$ donc:\\

\begin{itemize}
  \item On commence à l'instant $T_{0}=-1$
  \item On génère $u_{0}=0.47$
  \item On calcule ${\Phi_{r}}_{0}^{T_{0}}(i,u_{0})$ pour tout $i\in\chi$:
  \end{itemize}
\begin{minipage}{6cm}
  $${\Phi_{r}}_{0}^{T_{0}}(1,u_{0})=2$$
  $${\Phi_{r}}_{0}^{T_{0}}(2,u_{0})=1$$
  $${\Phi_{r}}_{0}^{T_{0}}(3,u_{0})=4$$
  $${\Phi_{r}}_{0}^{T_{0}}(4,u_{0})=3$$
\end{minipage}
\begin{minipage}{6cm}
\begin{figure}[!h]
\begin{tikzpicture}[x=1.5cm,>=latex]
\draw [->] (-5.5,-1)--(1.5,-1);
\foreach \i in {-1,...,0} {
  \draw (\i,-.9)--(\i,-1.1) node[below] {\i};
}
\foreach \i/\j in {-1/1,-1/2,-1/3,-1/4,0/1,0/2,0/3,0/4} {\node[draw,circle](\i_\j) at (\i,4-\j) {$\j$};
}
\draw[->](-1_4)--(0_3);
\draw[->](-1_3)--(0_4);
\draw[->](-1_2)--(0_1);
\draw[->](-1_1)--(0_2);
\draw (-0.5,3.7) node [scale=0.7] {$u_0=0.47$};
\end{tikzpicture}
\end{minipage}
\end{frame}
\end{document}