\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint}
\usepackage[dvips]{color}
\usepackage[tikz]{bclogo}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\textwidth 19cm \textheight 25cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesection}{\textcolor{red}{\Alph{section}}} 
\renewcommand{\thesubsection}{\textcolor{blue}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
%\tableofcontents


\begin{center}\section*{\textcolor{red}{Graphes probabilistes}}\end{center}

\section{\textcolor{red}{Quelques exemples}}


\subsection{\textcolor{blue}{Une évolution de population}}


\subsubsection{\textcolor{blue}{Le problème}}

  Deux villes $X$ et $Y$ totalisent à elles deux une population d'un million d'habitants. \\
La ville $X$ est plus agréable, mais la ville $Y$ offre de meilleurs salaires. \\
20\,\% des habitants de $Y$ partent chaque année habiter $X$ pour avoir un meilleur cadre de vie, et 5\,\% des habitants de $X$ partent chaque année habiter $Y$ pour augmenter leur niveau de vie.\\
À l'année 0, un quart des habitants sont en $X$.\\

On se pose les questions suivantes :

\begin{itemize}
	\item Comment sera répartie la population, entre les villes $X$ et $Y$ au bout de 1, 2, 5, 10, 30, 40 ans ?
	\item Que se serait-il passé au bout de 1, 2, 5, 10, 30, 40 ans si 99\,\% des habitants avaient été initialement en $X$ (ou en $Y$) ?
	\item Que se serait-il passé au bout de 1, 2, 5, 10, 30, 40 ans si la population avait été également répartie entre les deux villes en l'année zéro ?
\end{itemize}


\subsubsection{\textcolor{blue}{Une solution}}

\begin{enumerate}
 \item L'énoncé nous dit que 95\,\% des gens qui sont en $X$ y restent, 5\,\% partent en $Y$, et que 80\,\% des gens qui sont en $Y$ y restent, 20\,\% partant en $X$.\\
En appelant $X_n$ la population de la ville $X$ à l'année $n$ et $Y_n$ celle de $Y$, expliquer pourquoi on peut représenter l'évolution par le système d'équations :
\[\left\{\begin{array}{rcl} X_{n+1}&=&0,95X_n+0,2Y_n \\ Y_{n+1}&=&0,05X_n+0,8Y_n\end{array}\right.\]
\item On peut représenter la situation par le graphe suivant, où l'on a marqué, sur chaque arête joignant le sommet $X$ au sommet $Y$, la proportion de population qui passe à chaque étape de $X$ à $Y$. Remarquons que, puisque la population ne peut disparaître ou apparaître, la somme des coefficients sur toutes les arêtes quittant un sommet doit être 1 :

\medskip
\begin{center}
\begin{psmatrix}[mnode=circle]
$X$ & $Y$
\end{psmatrix}
\psset{arrows=->,shortput=nab}
\nccircle[angleA=90]{1,1}{0.5cm}\nbput{0,95}
\ncarc[arcangle=15]{1,1}{1,2}^{0,05}
\ncarc[arcangle=15]{1,2}{1,1}^{0,2}
\nccircle[angleA=-90]{1,2}{0.5cm}\nbput{0,8}
\end{center}

\bigskip

Si l'on note, pour tout entier naturel $n$, $P_n=\begin{pmatrix} X_n & Y_n\end{pmatrix}$ le vecteur ligne qui décrit la population de $X$ et de $Y$ au bout de $n$ années, déterminer la matrice $M$ telle que le système déquation d'évolution trouvée précédemment peut se réécrire : \[P_{n+1} = P_n\times M\]
On appelera $M$ : \emph{matrice de transition du système}.

  \textbf{Attention !} Le produit ne se fait pas à droite de la matrice, comme on en a l'habitude, mais \textbf{\textcolor{red}{à gauche}}. Cela présente l'avantage de garder l'écriture des vecteurs en ligne, et c'est l'habitude en probabilité.


\begin{enumerate}
	\item Exprimer $P_1$ et $P_2$ en fonction de $M$ et de $P_0$.\\
	Généraliser pour obtenir $P_n$ en fonction de $P_0$, de $M$ et de $n$.
	\item à l'aide de cette formule, répondre aux questions qu'on se pose dans le problème.
	
\end{enumerate}
\item \begin{enumerate} \item Que constate-t-on, quand $n$ devient grand, quelle que soit la répartition de population à l'année 0 ?
	\item On suppose que $P_0=\begin{pmatrix}800\,000 & 200\,000\end{pmatrix}$.\\
	Calculer $P_1$, $P_2$, $P_3$, etc.\\
	Comment peut-on alors qualifier cette répartition, cet état ?
        \item On a vu que, quelle que soit la population de départ, le système converge vers cet état. Il peut donc être intéressant d'être en mesure de le déterminer dès le départ.\\
        On admet qu'une telle répartition existe et on appelle $x$ la population de $X$ et $y$ celle de $Y$ pour lesquelles la population de chaque ville est la même chaque année.
\begin{enumerate}
\item Que devient le système d'équations d'évolution si 
$\begin{pmatrix} X_n & Y_n \end{pmatrix} = \begin{pmatrix} x & y \end{pmatrix}$ ?
	\item En déduire que $x$ et $y$ sont solutions de :
			$\left\{ \begin{array}{rcl}
			0,2y&=&0,05x \\
			x+y&=&1\,000\,000
			\end{array}\right.$
	\item Déterminer alors $x$ et $y$.
\end{enumerate}
\end{enumerate}
\end{enumerate}



\subsection{\textcolor{blue}{Maladie}}

  Un individu vit dans un milieu où il est susceptible d'attraper une maladie par piqûre d'insecte. Il peut être dans l'un des trois états suivants : immunisé ($I$), malade ($M$), sain, c'est-à-dire non malade et non immunisé, ($S$). \\
D'un mois à l'autre, son état peut changer selon les règles suivantes :
\begin{itemize}
	\item étant immunisé, il peut le rester avec une probabilité 0,9 ou passer à l'état $S$ avec une probabilité 0,1 ;
	\item étant dans l'état $S$, il peut le rester avec une probabilité 0,5 ou passer à l'état $M$ avec une probabilité 0,5 ;
	\item étant malade, il peut le rester avec une probabilité 0,2 ou passer à l'état $I$ avec une probabilité 0,8.
\end{itemize}

\begin{enumerate}
	\item Tracer un graphe probabiliste pour décrire cette situation et écrire la matrice de transition.

	\item Calculer l'état de probabilité de l'individu au bout de trois mois, de six mois, d'un an, de deux ans pour chacune des situations suivantes :
\begin{itemize}
	\item au départ, il est immunisé ;
	\item au départ, il est non malade et non immunisé ;
	\item au départ, il est malade.
\end{itemize}
\item On note $\begin{pmatrix} i & m & s \end{pmatrix}$ l'état stable du système.
\begin{enumerate}
 \item Montrer que $i$, $m$, $s$ sont solutions du système :
 \[(S)=\left\{\begin{array}{rcl}
               0,8m-0,1i&=&0\\
               0,5s-0,8m&=&0\\
               0,1i-0,5s&=&0\\
               i+m+s&=&1
              \end{array}\right.\]
              
  \item En déduire l'état stable.

\end{enumerate}

\end{enumerate}





\section{\textcolor{red}{Cas général : graphes probabilistes à $p$ états}}

On considère un système qui peut se trouver dans $p$ états $\{1\,;\, 2\,;\,\ldots\,;\, p\}$, avec une certaine probabilité, variable au cours du temps, pour chaque état.

On s'intéresse à l'évolution de ce système au cours du temps, et on fait l'hypothèse que la probabilité de transition de l'état $i$ à l'état $j$ est indépendante du temps, et ne dépend pas de l'histoire antérieure, mais seulement de l'état dans lequel on se trouve.

De bons exemples de tels systèmes sont donnés par les jeux de hasard, tels que jeu de l'oie, Monopoly, jacquet, petits chevaux, etc. Pour de tels jeux, l'état est donné par la case sur laquelle on se trouve ; la façon dont on y est arrivé n'a pas d'importance pour la suite du jeu.

Les systèmes qu'on observe dans la vie réelle sont en général beaucoup plus complexes, mais l'approximation simple qu'on en fait ici donne souvent des indications utiles ; ce type de modèle est utilisé en pratique dans un grand nombre de situations, avec de bons résultats.

On peut représenter un tel système par un graphe orienté, dont les sommets sont les états du système, et où l'on associe à chaque transition, de l'état $i$ à l'état $j$, une arête orientée allant de $i$ vers $j$, étiquetée par la probabilité de transition, c'est-à-dire la probabilité conditionnelle d'être dans l'état $j$ à l'instant $n+ 1$ sachant que l'on est dans l'état $i$ à l'instant $n$. Remarquons que l'on peut rester dans un même état : le graphe peut avoir des boucles.



\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}}
On appelle \emph{graphe probabiliste} un graphe orienté, tel que pour chaque couple de sommets $(i\,;\,j)$ distincts ou confondus il existe au plus une arête de $i$ vers $j$, et où chaque arête est étiquetée par un réel $p_{ij}$ compris entre 0 et 1, la somme des poids des arêtes issues d'un même sommet étant égale à 1.
\end{bclogo}

De même qu'à un graphe (orienté ou non), on associe une matrice d'adjacence $A$, dont le terme $a_{ij}$ compte le nombre d'arêtes joignant le sommet $i$ au sommet $j$, on peut associer à un graphe probabiliste une matrice qui décrit les probabilités de transition :



\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}}
étant donné un graphe probabiliste à $p$ sommets, on appelle \emph{matrice de transition} associée la matrice carrée $M = (m_{ij})$ à $p$ lignes et $p$ colonnes, dont le coefficient $m_{ij}$ est l'étiquette de l'arête orientée de $i$ vers $j$ si elle existe (c'est-à-dire la probabilité de transition de $i$ à $j$), et 0 sinon.
\end{bclogo}

On veut étudier l'évolution d'un tel système au cours du temps ; on note $X_n$ le vecteur ligne à $p$ éléments dont l'élément d'ordre $j$ est la probabilité que le système se trouve à l'instant $n$ dans l'état $j$ (Attention aux indices ! on a ici une suite de vecteurs lignes, avec chacun $p$ composantes !).

La propriété fondamentale est la suivante :

\begin{minipage}{10cm}
\begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{Propriété}

Pour tout entier $n$, on a $X_{n+1} = X_n\times M$
\end{bclogo}
\end{minipage}

On admet ce résultat.

On en déduit immédiatement :

\begin{minipage}{10cm}
\begin{bclogo}[couleur = cyan!20, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{\textcolor{red}{Propriété}}}
Pour tout entier $n > 0$, on a : $X_n = X_0\times M^n$
\end{bclogo}

\end{minipage}
\bigskip

En effet : \\
$X_2=X_1M=\left(X_0M)M=X_0M^2\right)$\\
$X_3=X_2M=\left(X_0M^2)M=X_0M^3\right)$\\
$\cdots$\\
$X_{n}=X_{n-1}M=\left(X_0M^{n-1}\right)M=X_0M^n$\\
On admet que la propriété est vraie pour tout rang $n$.

Cette formule, qui permet de calculer la répartition de probabilités au temps $n$ si on la connaît au temps 0, est fondamentale pour tous les exercices.

\medskip

Un cas particulièrement intéressant est celui où la répartition de probabilité est stable au cours du temps.


\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}}
On appelle \textbf{état stable} un vecteur ligne $X = \begin{pmatrix} x_1 & \ldots & x_p\end{pmatrix}$ à $p$ composantes  tel que $X = X\times M$ et $\sum_{i=1}^px_i=1$
\end{bclogo}

La dernière condition $\sum_{i=1}^px_i=1$ est due au fait que $X$ représente une répartition de probabilité.\\

\medskip

Remarquons que la recherche d'un état stable n'est pas difficile en pratique : il s'agit de résoudre l'équation $X = X\times M$, et d'en chercher une solution satisfaisant $\sum_{i=1}^px_i=1$, ce qui se fait sans problème pour une matrice $M$ donnée.

On peut interpréter cette équation de la manière suivante : pour obtenir un état stable, il faut que toutes les transitions s'équilibrent ; si l'on considère le problème comme une évolution de population, il faut que, pour tout état $i$, la quantité de personnes qui quittent l'état $i$ à chaque étape soit égale à la quantité de personnes qui y arrivent.

Ce qui est moins évident, c'est qu'un tel état existe, et qu'il soit unique. Ce qui se passe quand on ne part pas d'un état stable n'est pas évident non plus. Nous allons l'étudier en détail dans le cas d'un système à deux états, cas qui est accessible au niveau de la terminale.

\section{\textcolor{red}{Un cas particulier : les graphes probabilistes à 2 états}}

On suppose qu'il n'y a que deux états, notés 1 et 2. On note $U_n$ (resp. $V_n$) la probabilité qu'à l'instant $n$, le système se trouve dans l'état 1 (resp. 2).

Pour tout entier $n$, on note $X_n$ le vecteur-ligne à deux colonnes, $X_n = \begin{pmatrix} U_n & V_n\end{pmatrix}$. Remarquons que l'on a toujours $U_n + V_n = 1$.

On note $a$ la probabilité de transition de l'état 1 à l'état 2, c'est-à-dire la probabilité que le système passe à l'état 2 à l'étape $n+1$ sachant que le système est à l'état 1 à l'étape $n$
et $b$ la probabilité de transition de l'état 2 à l'état 1.

Les probabilités de demeurer dans l'état 1 ou dans l'état 2 sont donc $1 - a$ et $1 - b$.

Le système peut donc être représenté par le graphe probabiliste suivant :

\bigskip

\begin{center}
\begin{psmatrix}[mnode=circle]
$1$ & $2$
\end{psmatrix}
\psset{arrows=->,shortput=nab}
\nccircle[angleA=90]{1,1}{0.5cm}\nbput{$1-a$}
\ncarc[arcangle=15]{1,1}{1,2}^{$a$}
\ncarc[arcangle=15]{1,2}{1,1}^{$b$}
\nccircle[angleA=-90]{1,2}{0.5cm}\nbput{$1-b$}
\end{center}

\bigskip

  et la matrice correspondante est :
\[M=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}\]

Les nombres $a$ et $b$ sont tous deux compris entre 0 et 1.

Il y a quelques \textbf{cas triviaux} que l'on peut traiter à part :
\begin{itemize}
	\item \emph{Si $a$ et $b$ sont nuls}, $M$ est la matrice identité, et \textbf{tous les états sont stables}. Ce n'est pas étonnant, puisqu'il est impossible de changer !
	\item \emph{Si l'un des deux seulement est nul}, par exemple $a$, on voit que l'on finit toujours par arriver dans l'état 1. C'est le cas d'une population qui ne se renouvelle pas, et dont les individus peuvent être dans deux états, vivants (état 2) ou morts (état 1) : à long terme, la population ne sera plus composée que de morts. On parle alors d'état absorbant (pour l'état 1). Il y a donc \textbf{un état stable}.
	\item Enfin, \emph{si les deux coefficients $a$ et $b$ sont égaux à 1}, le système clignote : il oscille sans se stabiliser entre l'état 1 et l'état 2, et se retrouve tous les deux coups dans le même état. \textbf{Il n'y a pas d'état stable}.
\end{itemize}

\medskip

Ces cas particuliers étant faciles à étudier, et peu intéressants, \textbf{on supposera désormais que $a$ et $b$ sont strictement positifs, et ne sont pas tous deux égaux à 1}.

\bigskip

On admettra alors le résultat général suivant :

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Théorème (admis)}}
Considérons un graphe probabiliste à deux états, de matrice de transition $M=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}$ telle que $0 < a < 1$ et $0<b<1$.
Alors, le système admet un unique état stable, indépendamment de l'état initial.
\end{bclogo}

%\bigskip
%
%  On peut généraliser, sous certaines conditions à un graphe à $n$ états :
%
%\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Théorème (admis)}}
%Soit un graphe probabiliste à $n$ états, de matrice de transition $M$. S'il existe une puissance $M^k$ de $M$ dont tous les coefficients sont \emph{strictement} positifs, alors il existe un seul état stable $X$, vérifiant $X = XM$, et quel que soit l'état initial, le système converge exponentiellement vite vers l'état stable.
%\end{bclogo}
%

Liens Internet : \\

On peut consulter les cours suivants sur Internet :

\begin{enumerate}[$\bullet$]
\item \href{}{https://www.maths-cours.fr/cours/graphe-probabiliste-spe/}}

\item \href{}{https://www.maths-et-tiques.fr/telech/GraphesTESL2.pdf}

\item vidéo : \href{}{https://www.youtube.com/watch?v=rHylCtXtdNs}

\item \href{}{https://www.youtube.com/watch?v=P39RdSm5aZE}


\end{enumerate}
\label{fin}
\end{document}  