[PDF] [PDF] Graphes probabilistes A Quelques exemples - Blog Ac Versailles

[PDF] Graphes probabilistes et matrices de transitions Quest-ce quun

La déterminer La matrice de transition a pour éléments les probabilités du graphe probabiliste lorsqu'il n'y a rien de précisé , on considère que les événements 

[PDF] GRAPHES - maths et tiques

Par exemple, la somme des poids issus de A est égal à 2 3 + 1 3 = 1 3) Matrice de transition Définition : Soit G un graphe probabiliste d'ordre n dont les  

[PDF] Graphes probabilistes - LaBRI

ENSM - Éléments de Théorie des Graphes 7 Matrices de transition À un tel graphe probabiliste, on associe une matrice de transition M permettant de retrouver

[PDF] Graphe probabiliste et matrice de transition - Free

Graphe probabiliste et matrice de transition Commentaire sur le document d' accompagnement de Terminale ES sur les graphes probabilistes (cf p 3 et 4)

[PDF] Graphes probabilistes - Meilleur En Maths

Construire un graphe probabiliste pour décrire cette situation b Donner la matrice de transition M complétée de ce graphe : M=( 0,05 0,05 0,8 0,1 0045

[PDF] Les graphes - IREM de la Réunion - Université de La Réunion

Graphes probabilistes 35 8 b Matrice de transition 36 8 c État probabiliste à la ne étape 36 8 d État stable 37 8 e Cas particulier de la recherche d'un état 

[PDF] CHAPITRE 3 GRAPHES PROBABILISTES 1 Graphe probabiliste

Définition : la matrice de transition d'un graphe probabiliste d'ordre n est la matrice carrée d'ordre n telle que le coefficient ai, j est égal au poids de l'arête 

[PDF] Ch 04 Les graphes probabilistes - APMath

Soit G un graphe probabiliste d'ordre n dont les sommets sont numérotés de 1 à n La matrice de transition M du graphe G est la matrice carrée d'ordre n telle 

[PDF] Graphes probabilistes A Quelques exemples - Blog Ac Versailles

Tracer un graphe probabiliste pour décrire cette situation et écrire la matrice de transition 2 Calculer l'état de probabilité de l'individu au bout de trois mois, 

[PDF] origine de la querelle des anciens et des modernes

[PDF] matrice de transition markov

[PDF] matrice de transition d'état

[PDF] journal anne frank résumé

[PDF] querelle des anciens et des modernes dates

[PDF] wikipedia la querelle des anciens et des modernes

[PDF] matrice de transition exercices corrigés

[PDF] definition generale des coefficients techniques de production

[PDF] fiche technique café

[PDF] intensité du café

[PDF] modèle fermé de leontief

[PDF] tableau intensité café nespresso

[PDF] exercices corrigés de comptabilité nationale sur le tableau entrée sortie pdf

[PDF] principales étapes transformation café pdf

[PDF] arômes du café

Graphes probabilistes

A Quelques exemples

I Une évolution de population

I .1 Le problème Deux villesXetYtotalisent à elles deux une populationd"un million d"habitants. La villeXest plus agréable, mais la villeYoffre de meilleurs salaires.

20% des habitantsdeYpartent chaque année habiterXpour avoir un meilleur cadre de vie, et 5% des habi-

tants deXpartent chaque année habiterYpour augmenter leur niveau de vie. À l"année 0, un quart des habitantssont enX.

On se pose les questions suivantes :

— Comment sera répartie la population,entre les villesXetYau bout de 1, 2, 5, 10, 30, 40 ans?

— 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 enY)?

— Quese serait-ilpasséau boutde 1,2,5,10,30,40 anssilapopulationavait étéégalementrépartieentre

les deux villes en l"année zéro?

I.2 Une solution

1. L"énoncé nous dit que 95% des gens qui sont enXy restent, 5% partent enY, et que 80% des gens qui

sont enYy restent, 20% partant enX. En appelantXnla population de la villeXà l"annéenetYncelle deY, expliquer pourquoi on peut représenter l"évolution par le système d"équations : ?Xn+1=0,95Xn+0,2Yn Y n+1=0,05Xn+0,8Yn

2. On peut représenter la situation par le graphe suivant, oùl"on a marqué, sur chaque arête joignant le

sommetXau sommetY, la proportion de population qui passe à chaque étape deXà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 :

XY0,95

0,05 0,2 0,8 Si l"on note, pour tout entier natureln,Pn=?XnYn?le vecteur ligne qui décrit la population deXet

deYau bout denannées, déterminer la matriceMtelle que le système déquation d"évolution trouvée

précédemment peut se réécrire : P n+1=Pn×M

On appeleraM:matrice de transition du système.

Attention!Le produit ne se fait pas à droite de la matrice, comme on en a l"habitude, mais

à gauche.

Cela présente l"avantage de garder l"écriture des vecteursen ligne, et c"est l"habitudeen probabilité.

(a) ExprimerP1etP2en fonction deMet deP0. Généraliser pour obtenirPnen fonction deP0, deMet den. (b) à l"aide de cette formule, répondre aux questions qu"on se pose dans le problème.

Page 1/

5

3. (a) Que constate-t-on, quandndevient grand, quelle que soit la répartition de populationà l"année

0? (b) On suppose queP0=?800000 200000?.

CalculerP1,P2,P3, etc.

Comment peut-on alors qualifier cette répartition,cet état?

(c) Onavu que, quelle quesoit la populationdedépart,le systèmeconverge verscet é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 appellexla population deXetycelle deYpour lesquelles la populationde chaque ville est la même chaque année. i. Que devient le système d"équations d"évolution si?XnYn?=?x y?? ii. En déduire quexetysont solutionsde :?0,2y=0,05x x+y=1000000 iii. Déterminer alorsxety.

II Maladie

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 :

— étant immunisé, il peut le rester avec une probabilité0,9 ou passer à l"étatSavec une probabilité0,1;

— étant dans l"étatS, il peut le rester avec une probabilité 0,5 ou passer à l"étatMavec une probabilité

0,5;

— étant malade, il peut le rester avec une probabilité0,2 ou passer à l"étatIavec une probabilité0,8.

1. Tracer un graphe probabiliste pour décrire cette situation et écrire la matrice de transition.

2. 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 situationssuivantes :

— au départ, il est immunisé;

— au départ, il est non malade et non immunisé;

— au départ, il est malade.

3. On note?i m s?l"état stable du système.

(a) Montrer quei,m,ssont solutions du système : (S)=???????0,8m-0,1i=0

0,5s-0,8m=0

0,1i-0,5s=0

i+m+s=1 (b) En déduire l"état stable. B Cas général: graphes probabilistesàpétats

On considère un système qui peut se trouver danspétats {1; 2; ... ;p}, avec une certaine probabilité, va-

riable 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"étatià l"étatjest indépendante du temps, et ne dépend pas de l"histoire antérieure, mais

seulement de l"état dans lequel on se trouve.

Page 2/

5

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éralbeaucoup plus complexes, mais l"approxi-

mationsimplequ"on en fait ici donne souventdes indicationsutiles;ce type de modèleest 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"étatià l"étatj, une arête orientée allant deiversj, étiquetée par la

probabilitéde transition,c"est-à-dire la probabilitéconditionnelled"être dans l"étatjà l"instantn+1 sachant

que l"on est dans l"étatià l"instantn. Remarquons que l"on peut rester dans un même état : le graphepeut

avoir des boucles.

ou confondus il existe au plus une arête deiversj, et où chaque arête est étiquetée par un réelpi j

compris entre 0 et 1, la somme des poids des arêtes issues d"unmême sommet étant égale à 1.

Définition

De même qu"à un graphe (orienté ou non), on associe une matrice d"adjacenceA, dont le termeai j

compte le nombre d"arêtes joignant le sommetiau sommetj, on peut associer à un graphe probabiliste

une matrice qui décrit les probabilités de transition:

étant donné un graphe probabiliste àpsommets, on appellematrice de transitionassociée la matrice

carréeM=(mi j) àplignes etpcolonnes, dont le coefficientmi jest l"étiquette de l"arête orientée dei

versjsi elle existe (c"est-à-dire la probabilitéde transitiondeiàj), et 0 sinon.

Définition

On veut étudier l"évolution d"un tel système au cours du temps; on noteXnle vecteur ligne àpéléments

dont l"élément d"ordrejest la probabilité que le système se trouve à l"instantndans l"étatj(Attention aux

indices! on a ici une suite de vecteurs lignes, avec chacunpcomposantes!).

La propriété fondamentale est la suivante :

Pour tout entiern, on aXn+1=Xn×M

Propriété

On admet ce résultat.

On en déduit immédiatement:

Pour tout entiern>0, on a :Xn=X0×Mn

Propriété

En effet :

X

2=X1M=?X0M)M=X0M2?

X

3=X2M=?X0M2)M=X0M3?

X n=Xn-1M=?X0Mn-1?M=X0Mn On admet que la propriété est vraie pour tout rangn.

Page 3/

5

Cette formule, qui permet de calculer la répartition de probabilités au tempsnsi on la connaît au temps

0, est fondamentale pour tous les exercices.

Un cas particulièrementintéressant est celui où la répartitionde probabilitéest stable au cours du temps.

On appelleétatstableun vecteur ligneX=?x1...xp?àpcomposantestel queX=X×Metp? i=1x i=1

Définition

La dernière conditionp?

i=1x i=1 est due au fait queXreprésente une répartitionde probabilité. X=X×M, et d"en chercher une solutionsatisfaisantp? i=1x i=1, ce qui se fait sans problème pour une matrice

Mdonnée.

transitions s"équilibrent; si l"on considère le problème comme une évolution de population, il faut que, pour

tout étati, la quantité de personnes qui quittent l"étatià 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. C Un cas particulier: les graphes probabilistesà 2 états

On suppose qu"il n"y a que deux états, notés 1 et 2. On noteUn(resp.Vn) la probabilité qu"à l"instantn, le

système se trouve dans l"état 1 (resp. 2). Pour tout entiern, on noteXnle vecteur-ligne à deux colonnes,Xn=?UnVn?. Remarquons que l"on a toujoursUn+Vn=1.

Onnoteala probabilitéde transitionde l"état 1 à l"état 2, c"est-à-dire la probabilitéque le système passe à

l"état 2 à l"étapen+1 sachant que le système est à l"état 1 à l"étapenetbla 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-aet 1-b. Le système peut donc être représenté par le graphe probabilistesuivant : 121-a
a b 1-b et la matrice correspondante est :

M=?1-a a

b1-b? Les nombresaetbsont tous deux compris entre 0 et 1. Il y a quelquescas triviauxque l"on peut traiter à part :

—Si a et b sont nuls,Mest la matrice identité, ettous les états sont stables. Ce n"est pas étonnant, puis-

qu"il est impossiblede changer!

Page 4/

5

—Si l"un des deux seulement est nul, par exemplea, 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

On parle alors d"état absorbant (pour l"état 1). Il y a doncun étatstable.

— Enfin,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 lemême état.Il n"y a pas d"état stable.

Ces cas particuliers étant faciles à étudier, et peu intéressants,on supposera désormais queaetbsont

strictement positifs, etne sont pas tousdeux égauxà 1. On admettra alors le résultat général suivant : Considérons un graphe probabiliste à deux états, de matricede transitionM=?1-a a b1-b? telle que

0

Théorème (admis)

Liens Internet :

On peut consulter les cours suivants sur Internet : •https ://www.maths-cours.fr/cours/graphe-probabiliste-spe/ •https ://www.maths-et-tiques.fr/telech/GraphesTESL2.pdf •vidéo : https ://www.youtube.com/watch?v=rHylCtXtdNs •https ://www.youtube.com/watch?v=P39RdSm5aZE

Page 5/

5quotesdbs_dbs30.pdfusesText_36