Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Graphe probabiliste [spé]

I. Étude d'un exemple

On étudie la propagation d'une maladie dans une population.

On choisit au hasard une personne dans cette population.

On note :

On suppose que :

Au début de l'étude, la maladie touche 5 % de la population. On a donc p0=0,05p_0=0,05 et q0=0,95q_0=0,95.

a. Utilisation d'un arbre

On peut représenter la situation au jour 0 et au jour 1 par l'arbre ci-dessous :

arbre pondéré

La formule des probabilités totales permet de calculer les probabilités p1p_1 et q1q_1 :

p1=0,05×0,7+0,95×0,2=0,225p_1=0,05\times 0,7 + 0,95\times 0,2 = 0,225

q1=0,05×0,3+0,95×0,8=0,775q_1 =0,05\times 0,3 + 0,95\times 0,8 = 0,775

De même, on peut représenter l'évolution du jour nn au jour n+1n+1 grâce à l'arbre ci-dessous :

arbre pondéré

On obtient, en utilisant à nouveau la formule des probabilités totales :

pn+1=0,7pn+0,2qnp_{n+1}=0,7 p_n + 0,2 q_n

qn+1=0,3pn+0,8qnq_{n+1}=0,3 p_n + 0,8 q_n.

b. Graphe probabiliste

À une date donnée, un individu se trouve dans l'un ou l'autre des deux états suivants :

  • la personne est malade (état noté M)

  • la personne est saine (état noté S)

Un graphe probabiliste représente ces deux états sous la forme de sommets et les probabilités de passer d'un état à l'autre sous la forme d'arcs orientés.

Dans notre exemple, on obtient le graphe suivant :

graphe probabiliste d'ordre 2

On remarque que la somme des probabilités issues d'un même sommet (en bleu pour M et en rouge pour S) est toujours égale à 1.

c. Matrice de transition

Les relations trouvées grâce à l'arbre :

pn+1=0,7pn+0,2qnp_{n+1}=0,7 p_n + 0,2 q_n

qn+1=0,3pn+0,8qnq_{n+1}=0,3 p_n + 0,8 q_n

peuvent s'écrire sous forme matricielle :

A=(pn+1qn+1)=(pnqn)×(0,70,30,20,8)A=\begin{pmatrix} p_{n+1} & q_{n+1} \end{pmatrix} = \begin{pmatrix} p_{n} & q_{n} \end{pmatrix} \times \begin{pmatrix} 0,7 & 0,3 \\ 0,2 & 0,8 \end{pmatrix}

N.B. Vérifier le en effectuant le calcul : (pnqn)×(0,70,30,20,8)\begin{pmatrix} p_{n} & q_{n} \end{pmatrix} \times \begin{pmatrix} 0,7 & 0,3 \\ 0,2 & 0,8 \end{pmatrix}.

En notant T=(0,70,30,20,8)T = \begin{pmatrix} 0,7 & 0,3 \\ 0,2 & 0,8 \end{pmatrix} et pour tout entier naturel nn, Pn=(pnqn)P_n = \begin{pmatrix} p_{n} & q_{n} \end{pmatrix}, la relation précédente s'écrit :

pn+1=Pn×T p_{n+1}=P_n \times T

La matrice TT s'appelle matrice de transition et les matrices lignes PnP_n, états probabilistes.

On a alors :

p1=P0×T p_{1}=P_0 \times T P0P_0 est l'état initialP0=(p0q0)=(0,050,95)P_0=\begin{pmatrix} p_{0} & q_{0} \end{pmatrix}=\begin{pmatrix} 0,05 & 0,95 \end{pmatrix}

p2=P1×T=P0×T×T=P0×T2 p_{2}=P_1 \times T=P_0 \times T \times T = P_0 \times T^2

p3=P2×T=P0×T2×T=P0×T3 p_{3}=P_2 \times T=P_0 \times T^2 \times T = P_0 \times T^3

et ainsi de suite...

pn=P0×Tn p_{n}= P_0 \times T^n

Par exemple, l'état probabiliste au cinquième jour sera :

p5=P0×T5 p_{5}= P_0 \times T^5

À la calculatrice, on trouve p5=(0,3890,611) p_{5}=\begin{pmatrix} 0,389 & 0,611 \end{pmatrix} (au millième près).

Le cinquième jour, 38,9% de la population sera malade.

II. Graphe probabiliste - Matrice de transition

Dans toute cette partie, on considère un système possédant nn états possibles notés A1A_1, A2A_2, ... AnA_n. Ce système peut changer d'état au cours du temps et on suppose que la probabilité de passer de l'état AiA_i à l'état AjA_j reste constante.

Définition

Un graphe probabiliste est un graphe orienté et pondéré dans lequel :

  • Les sommets du graphe représentent les différents états possibles d'un système

  • Les poids des arcs indiquent les probabilités de passage d'un état à l'autre

Dans un graphe orienté, la somme des poids des arcs issus d'un même sommet est égale à 1.

Exemples

a. Graphe probabiliste d'ordre 2

graphe probabiliste d'ordre 2

Graphe probabiliste à 2 états A1A_1 et A2A_2

b. Graphe probabiliste d'ordre 3

graphe probabiliste d'ordre 3

Graphe probabiliste à 3 états A1A_1, A2A_2 et A3A_3

Définition

Soit un graphe probabiliste d'ordre nn.

Les états probabilistes PkP_k sont des matrices à une ligne à nn colonnes qui indiquent pour chacun des nn sommets, la probabilité de se trouver dans cet état à l'étape kk.

La somme des coefficients d'un état probabiliste est égale à 1.

Remarques

  • L'état probabiliste P0P_0 s'appelle l'état probabiliste initial.

  • Pour un système à deux états A et B, les états probabilistes seront de la forme Pk=(pkqk)P_k = \begin{pmatrix} p_k & q_k \end{pmatrix} pkp_k et qkq_k sont les probabilités de se trouver respectivement dans les états A et B à l'étape kk.

    Le système se trouvant, à chaque étape, soit dans l'état A soit dans l'état B, on aura, pour tout entier naturel kk, pk+qk=1p_k + q_k = 1

  • Pour un système à trois états, les états probabilistes seront de la forme Pk=(pkqkrk)P_k = \begin{pmatrix} p_k & q_k & r_k\end{pmatrix} avec, pour tout entier naturel kk, pk+qk+rk=1p_k + q_k + r_k = 1 .

Définition

Soit un graphe probabiliste d'ordre nn dont les états sont notés A1A_1, A2A_2, ... AnA_n.

La matrice de transition associée un graphe probabiliste d'ordre nn est une matrice carrée n×nn \times n dont le terme pi,jp_{i,j} situé à l'intersection de la ii-ème ligne et de la jj-ème colonne représente la probabilité de passer de l'état AiA_i à l'état AjA_j.

Dans une matrice de transition, la somme des coefficients situés sur une même ligne est égale à 1.

Exemples

a. Graphe probabiliste d'ordre 2

Considérons le graphe probabiliste suivant :

graphe probabiliste d'ordre 2

La matrice de transition associée à ce graphe est :

matrice de transition 2x2

b. Graphe probabiliste d'ordre 3

Dans l'exemple du graphe d'ordre 3 :

graphe probabiliste d'ordre 3

La matrice de transition est :

matrice de transition 3x3

Théorème

Soit un système dont la matrice de transition est notée TT, d'état initial P0P_0 et d'état probabiliste PkP_k à l'étape kk.

Alors, pour tout entier naturel kk :

  • Pk+1=Pk×TP_{k+1}=P_k \times T

  • Pk=P0×TkP_{k}=P_0 \times T^k

Démonstration

Ce résultat se démontre en utilisant la formule des probabilités totales (voir partie {I. Étude d'un exemple } )

Remarque

On peut rapprocher ces formules de celles obtenues pour les suites géométriques : un+1=un×qu_{n+1}=u_n \times q et un=u0×qnu_n=u_0 \times q^n.

Mais attention à l'ordre des matrices : le produit de matrices n'est pas commutatif !

III. États stables

Définition

Soit un graphe probabiliste de matrice de transition TT.

Un état stable est un état probabiliste PP qui vérifie P=P×TP=P \times T.

Remarque

En pratique pour trouver un état stable :

  • On pose P=(xy)P= \begin{pmatrix} x & y \end{pmatrix} si le graphe possède 2 états ( ou P=(xyz)P= \begin{pmatrix} x & y & z \end{pmatrix} si le graphe possède 3 états)

  • On écrit le système correspondant à l'égalité matricielle P=P×TP=P \times T

  • On ajoute au système l'équation x+y=1x+y=1 ( ou x+y+z=1x+y+z=1 si le graphe possède 3 états ) qui caractérise les états probabilistes ( la somme des coefficients est égale à 1)

  • On résout le système obtenu...

Exemple

Reprenons le graphe :

graphe probabiliste d'ordre 2

La matrice de transition associée est T=(0,10,90,40,6)T= \begin{pmatrix} 0,1 & 0,9 \\ 0,4 & 0,6 \end{pmatrix}.

En posant P=(xy)P= \begin{pmatrix} x & y \end{pmatrix} on obtient le système

{x=0,1x+0,4yy=0,9x+0,6yx+y=1 \begin{cases} x = 0,1x+0,4y \\ y = 0,9x+0,6y \\ x+y=1\end{cases}

qui est équivalent à :

{0,9x0,4y=00,9x0,4y=0y=1x \begin{cases} 0,9x-0,4y=0 \\ 0,9x-0,4y=0 \\ y=1-x \end{cases}

Les deux premières équations sont identiques et en remplaçant yy par 1x1-x dans la première équation on obtient :

{0,9x0,4(1x)=0y=1x \begin{cases} 0,9x-0,4(1-x)=0 \\ y=1-x \end{cases}

{x=413y=913 \begin{cases} x=\dfrac{4}{13} \\ \\ y=\dfrac{9}{13} \end{cases}

Il y a donc un état stable P=(413913)P = \begin{pmatrix} \dfrac{4}{13} & \dfrac{9}{13} \end{pmatrix}

Propriété

Si la matrice de transition d'un graphe probabiliste d'ordre 2 ou 3 ne comporte pas de coefficient nul, alors :

  • le graphe possède un état stable PP

  • les états probabilistes PnP_n tendent vers l'état stable PP quand nn devient grand.

Remarques

  • Cette propriété donne une condition suffisante mais non nécessaire. Il est possible qu'une matrice de transition comporte des coefficients nuls mais que le système converge malgré tout vers un état stable.

  • Le résultat précédent est également valable si le degré du graphe est supérieur à 3 (mais n'est pas au programme dans ce cas). Il s'agit d'un cas particulier du théorème de Perron-Frobenius

Dans ce chapitre :