[PDF] Chapitre 8 Graphes probabilistes

View - Download Chapitre 8 Graphes probabilistes

Previous PDF

Next PDF

Chapitre 8Graphes probabilistesSommaire

8.1 Quelques exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

8.1.1 Une évolution de population. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

8.1.2 Maladie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

8.2 Casgénéral : graphes probabilistes àpétats. . . . . . . . . . . . . . . . . . . . . . . 65

8.3 Uncas particulier : les graphes probabilistes à 2 états. . . . . . . . . . . . . . . . . 66

8.4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.4.1 État stable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8.4.2 Démonstrations à l"aide de suites. . . . . . . . . . . . . . . . . . . . . . . . . . . 72

8.4.3 Démonstrations à l"aide de matrices. . . . . . . . . . . . . . . . . . . . . . . . . . 74

8.1 Quelques exemples

8.1.1 Une évolution de population

Le problème

Deux villesXetYtotalisent à elles deux une populationd"un milliond"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 habitantsdeXpartent 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épartiela population,entre les villesXetYau bout de 1, 2, 5, 10, 30, 40 ans?

•Que se serait-il passé au bout de 1, 2, 5, etc. ans si 99%des habitantsavaient été initialement

enX(ou enY)?

•Que se serait-il passé au bout de 1, 2, 5, etc. ans si la population avait été également répartie

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

Une solution

1. L"énoncé nousdit que 95%des gens qui sont enXy restent,5%partentenY, et que 80%des

gens qui sont enYy restent, 20% partant enX. 63

8.1 Quelques exemplesTerminale ES spécialité

En appelantXnla populationde la villeXà l"annéenetYncelle deY, expliquer pourquoi on peut représenter l"évolutionpar 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

joignantlesommetXau sommetY, la proportionde populationqui passeà chaqueétapede XàY. Remarquons que, puisque la population ne peut disparaîtreou 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 lignequi 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 vecteurs en ligne, et c"est l"habitude

en 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.

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) On a vu que, quelle que soit la populationde départ,le système converge vers cet état. Il

peut donc être intéressant d"être en mesure de le déterminerdès le départ. On admet qu"une telle répartitionexiste et on appellexla population deXetycelle de Ypour lesquelles la populationde chaque ville est la même chaque année. i. Que devient le système d"équations d"évolutionsi?XnYn?=?x y?? ii. En déduire quexetysont solutionsde :?0,2y=0,05x x+y=1000000 iii. Déterminer alorsxety.

8.1.2 Maladie

Un individu vit dans un milieu où il est susceptible d"attraper une maladie par piqûre d"insecte. Il

peutêtredansl"undestroisétatssuivants:immunisé(I),malade(M), sain,c"est-à-direnonmalade et non immunisé,(S). D"un mois à l"autre, son état peut changer selon les règles suivantes : 64
http://perpendiculaires.free.fr/ Terminale ES spécialité8.2 Cas général : graphes probabilistes à p états

•étant immunisé, il peut le rester avec une probabilité0,9 oupasser à l"étatSavec une proba-

bilité 0,1;

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

probabilité 0,5; 0,8.

1. Tracer un graphe probabiliste pour décrire cette situationet é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 solutionsdu 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.

8.2 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 probabi-

lité, 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 proba-

bilité 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.

De bons exemples de tels systèmes sont donnés par les jeux de hasard, tels que jeu de l"oie, Mo-

nopoly, 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"importancepour la suite du jeu.

Les systèmes qu"on observe dans la vie réelle sont en généralbeaucoup plus complexes, mais l"ap-

proximation 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, avecde bons résultats.

On peut représenter un tel système par un graphe orienté, dont les sommets sont les états du sys-

tème, et où l"onassocie àchaque transition,del"étatiàl"étatj, unearêteorientéeallantdeiversj,

étiquetéepar laprobabilitéde transition,c"est-à-dire laprobabilitéconditionnelled"êtredansl"état

jà 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 graphe peut avoir des boucles. Définition 8.1.On appellegraphe probabilisteun graphe orienté, tel que pour chaque couple de sommets(i;j)distinctsouconfondusil existeau plusunearêtedeiversj,et où chaquearêteest

étiquetée par un réelpi jcompris entre 0 et 1, la somme des poids des arêtes issues d"unmême

sommet étant égale à 1. De même qu"à un graphe (orienté ou non), on associe une matrice d"adjacenceA, dont le terme a i jcompte le nombre d"arêtes joignant le sommetiau sommetj, on peut associer à un graphe probabiliste une matrice qui décrit les probabilitésde transition:

David ROBERT65

8.3 Un cas particulier : les graphes probabilistes à 2 étatsTerminale ES spécialité

associéelamatricecarréeM=(mi j)àplignesetpcolonnes,dontlecoefficientmi jestl"étiquette

de l"arête orientée deiversjsi elle existe (c"est-à-dire la probabilité de transition deiàj), et 0

sinon.

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

élémentsdont l"élément d"ordrejest laprobabilitéquele système se trouveà l"instantndansl"état

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

La propriété fondamentaleest la suivante :

Propriété 8.1.Pour tout entier n, on a Xn+1=Xn×M

On l"admettra.

On en déduit immédiatement:

Propriété 8.2.Pour tout entier n>0, on a : Xn=X0×Mn

On l"admettra.

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

temps 0, est fondamentalepour tous les exercices.

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

temps. Définition 8.3.On appelle état stable un vecteur ligneX=?x1...xp?àpcomposantes tel que

X=X×Metp?

i=1x i=1

La dernière condition

?p i=1xi=1 est due au fait queXreprésente une répartitionde probabilité.

Remarquons que la recherche d"un état stable n"est pas difficile en pratique : il s"agit de résoudre

l"équationX=X×M, et d"en chercher une solution satisfaisant?p i=1xi=1, ce qui se fait sans problème pour une matriceMdonnée.

On peut interpé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 leproblème comme une évolution de popula-

tion, 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 quiest moinsévident, c"est qu"un tel état existe,et qu"il soit unique. Cequi sepasse quandonne

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.

8.3 Un cas particulier: les graphes probabilistesà 2 états

Onsupposequ"il n"y a que deuxétats, notés1 et 2. OnnoteUn(resp.Vn) laprobabilitéqu"à l"instant

n, 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.

On noteala probabilité de transition de 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

transitionde l"état 2 à l"état 1. 66
http://perpendiculaires.free.fr/ Terminale ES spécialité8.3 Un cas particulier : les graphes probabilistes à 2 états 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 éton-

nant, puisqu"il est impossiblede changer! •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 états, vivants (état 2) ou morts (état1) : à 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 doncun étatstable.

•Enfin,si les deux coefficients a et b sont égaux à 1, le système clignote : il oscille sans se stabi-

liser entre l"état 1 et l"état 2, et se retrouve tous les deux coups dans le même état.Il n"y a pas

d"état stable.

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

sont strictement positifs, etne sont pas tousdeux égauxà 1. On admettra alors le résultat général suivant :

Théorème 8.3.Considérons un graphe probabiliste à deux états, de matricede transition M=?1-a a

b1-b? telle que0Théorème 8.4.Soit un graphe probabiliste à n états, de matrice de transition M. S"il existe une

puissance M kde M dont tous les coefficients sontstrictementpositifs, 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.

On l"admettra.

David ROBERT67

8.4 ExercicesTerminale ES spécialité

8.4 Exercices

8.4.1 État stable

EXERCICE8.1(Liban, juin 2003).

Un théâtre propose deux types d"abonnements pour une année :un abonnement A donnant droit à six spectacles ou un abonnement B donnant droit à trois spectacles. On considère un groupe de 2 500 personnes qui s"abonnent tousles ans.nétant un entier naturel, on note : a nla probabilitéqu"une personne ait choisi un abonnement A l"annéen; b nla probabilitéqu"une personne ait choisi un abonnement B l"annéen; P nla matrice?anbn?traduisant l"état probabilisteà l"annéen. Tousles ans85%des personnesquiont choisil"abonnementA et 55%des personnesquiont choisi d"abonnement.

1. On suppose que, l"année zéro, 1500 personnes ont choisi l"abonnement A et 1000 l"abonne-

ment B.

Déterminer l"état initialP0=?a0b0?.

2. (a) Tracer un graphe probabilistetraduisant les donnéesde l"énoncé.

(b) Déterminer la matrice de transitionM de ce graphe. (c) En déduire le nombre d"abonnés pour chaque type d"abonnement l"année un.

3. SoitP=?x y?l"état stable, oùxetysont deux nombres réels positifs tels quex+y=1.

Justifier quexetyvérifient l"équationx=0,85x+0,45y.

Déterminerxety.

En déduire la limitede la suite (an) quandntend vers plus l"infini. Interpréter le résultat précédent en terme de nombre d"abonnements de type A.

EXERCICE8.2(Amérique du sud, novembre 2004).

Au cours de la première semaine de l"année scolaire, un professeur propose aux élèves de sa classe

le choix entre deux sorties pédagogiques une sortie A et une sortie B.

20% des élèves de la classe sont favorables à la sortie A et tous les autres élèves sont favorables à la

sortie B. Les arguments des uns et des autres font évoluer cette répartitionen cours d"année. la semaine suivante.

On note :

a nla probabilitéqu"un élève soit favorable à la sortie A la semainen; b nla probabilitéqu"un élève soit favorable à la sortie B la semainen; P nla matrice?anbn?traduisant l"état probabilistela semainen.

1. Déterminer l"état initialP1.

2. Représenter la situationpar un graphe probabiliste.

3. En déduire quePn+1=Pn×M où M est la matrice?0,7 0,30,2 0,8?

4. Déterminer l"état probabilisteP3et en déduire la probabilité qu"un élève soit favorable à la

sortie A la troisième semaine.

5. Déterminer le réelxtel que?x1-x?×M=?x1-x?.

On admet que la suite

(an)est croissante. La sortie A finira-t-elle par être préférée àla sortie B? 68
http://perpendiculaires.free.fr/

Terminale ES spécialité8.4 Exercices

EXERCICE8.3(Antilles-Guyane, juin 2004).

On s"intéresse aux performances réalisées par des étudiantscourant le 200 mètres dans les compé-

titions universitaires. Lors d"une compétition, lescored"un(e) étudiant(e) est son meilleur temps

en secondes obtenu aux 200 m. Une enquête a permis d"établir le comportement général suivant,

qu"on supposera valable pour les filles et les garçons dans toute la suite :

•Lors de la première compétition,le score d"un(e) étudiant(e)est toujourssupérieur ou égal à

25 secondes.

•Si, lors de lan-ième compétition, l"étudiant(e) a réalisé un score strictement inférieur à 25

lors de la (n+1)-ième compétitionest de2 5.

•Si, lors de lan-ième compétition, l"étudiant(e) a réalisé un score supérieur ou égal à 25 se-

condes, la probabilité qu"il (elle) réalise encore un scorestrictement inférieur à 25 secondes

est 1 5. On représente les données précédentes par un graphe probabilisteG à deux états.

On note A tout score strictement inférieur à 25 secondes et B tout score supérieur ou égal à 25

secondes. Onnoteanlaprobabilitéd"obtenirunscore A lorsdela compétitionnetbnlaprobabilitéd"obtenir un score B lors de la compétitionn.

L"état probabilistelors de la compétitionnest donc représenté par la matrice ligne?anbn?.

1. Représenter G et donner sa matrice.

2. Jamalia, jeune étudiante, se présente à sa première compétition universitaire.

(a) Calculer la probabilité qu"elle réalise un score strictement inférieur à 25 secondes aux

200 mètres lors de cette compétition.

(b) Calculer la probabilité qu"elle réalise un score strictement inférieur à 25 secondes aux

200 mètres lors de sa troisième compétition.

3. Déterminer l"état stable du graphe G.

4. Julien a déjà de nombreuses compétitionsuniversitairesdans les jambes.

Montrer que, pour sa prochaine compétition, il a environ unechance sur quatre de réaliser un score strictement inférieur à 25 secondes aux 200 mètres.

EXERCICE8.4(Polynésie, juin 2004).

Étude de l"évolution météorologique d"un jour à l"autre dans une localité. Tous les résultats seront donnés sous forme de fractions rationnelles.

Partie A

•S"il fait sec aujourd"hui, alors il fera encore sec demain avec la probabilité5quotesdbs_dbs30.pdfusesText_36

[PDF] le mystère de la chambre jaune questionnaire lecture

[PDF] le mystère de la chambre jaune reponse

[PDF] le mystère de la chambre jaune audio

[PDF] qu'est qu'un diviseur

[PDF] exemple de diviseur

[PDF] qu est ce qu un multiple de 9

[PDF] qu est ce qu un divisible

[PDF] qu'est ce qu'un diviseur de 6

[PDF] trigonaliser une matrice dordre 4

[PDF] trigonaliser une matrice exemple

[PDF] trigonalisation méthode de jordan

[PDF] trigonalisation matrice 3x3

[PDF] qu'est ce qu'internet definition

[PDF] diagonalisation et trigonalisation des endomorphismes

[PDF] qu'est ce qu'internet pdf