[PDF] Chaînes de Markov 2 Matrice de transition. Dé

View - Download Chaînes de Markov

Previous PDF

Next PDF

Chaînes de Markov

Table des matières

1 Définitions2

2 Matrice de transition3

3 Étude d"une chaîne de Markov homogène 4

3.1 Étude mathématique d"une chaîne de Markov homogène . . . . . . . . . . . . . . . . . . . . .

4

3.2 Simulation des premiers états d"une chaîne de Markov avec Scilab . . . . . . . . . . . . . . . .

5

3.3 États stables d"une chaîne de Markov homogène . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.4 Convergence vers l"état stable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 1

Les chaînes de Markov donnent un exemple de suites de variables aléatoires non indépendantes, ce qui

est le cas dans beaucoup de situations.

1 DéfinitionsDéfinition 1.1 :Chaîne de Markov

On appellechaîne de Markov, toute suite(Xn)n?Nde variables aléatoires (définies sur le même espace pro-

babilisé) à valeurs dans un ensembleEtelles que pour toutn?Net pour tout(i0,i1,...,in-1,i,j)?En+2,

on a P [Xn=i]∩[Xn-1=in-1]∩...[X0=i0](Xn+1=j) =P[Xn=i](Xn+1=j).

La loi deXn+1sachantX0,X1,...,Xn-1est égale à la loi deXn+1sachantXn.Remarque 1.2 :Interprétation

Intuitivement, si on interprète la variablencomme étant le temps, cette définition signifie que sachant

le présent (l"instantn), le futur (l"instantn+ 1) est indépendant du passé (les instant1àn-1). Un

processus de Markov est aussi dit "processus sans mémoire".Définition 1.3 :Ensemble des états de la chaîne

On dit que la chaîne est dansl"étatiau tempsnsi l"événement[Xn=i]est réalisé. L"ensembleEest

donc l"ensemble des états de la chaîne.

Définition 1.4 :Probabilités de transitionLes probabilitésP[Xn=i](Xn+1=j), notéespi,j(n), sont appelées probabilités de transition.

Définition 1.5 :Chaîne de Markov homogène

Une chaîne de Markov est ditehomogènelorsque les probabilitéspi,j(n)ne dépendent pas den, mais

seulement deietj. Elles sont alors notéespi,j. On a alors ?(i,j)?E2,P[Xn=i](Xn+1=j) =P[X0=i](X1=j) =pi,j.Remarque 1.6 :Interprétation

Intuitivement, cela signifie que la "loi d"évolution" d"un instantnà l"instant suivantn+1reste toujours la

même au cours du temps.

Dans la suite nous n"étudierons que le cas où(Xn)n?Nest une chaîne de Markov homogène à valeurs

dans un espace d"étatsEqui est un ensemble fini. 2

2 Matrice de transition

Définition 2.1 :Matrice de transitionSi la chaîne de Markov(Xn)n?Nest homogène et siEest fini, par exempleE= [[1,N]], on appelle

matrice de transitionde la chaîne, la matrice deMN(R)suivante : M=( ((((p

1,1p1,2... p1,N

p

2,1p2,2... p2,N............

p

N,1pN,2... pN,N)

))))Définition 2.2 :Matrice stochastique

Une telle matrice, dont les coefficients sont positifs et tels que la somme des coefficients de chaque ligne

est égale à1, est dite stochastique.

Définition 2.3 :Vecteur ligne stochastique

Un vecteur ligne, dont les coefficients sont positifs et tels que la somme des coefficients est égale à1, est

dit stochastique.

Méthode 2.4 :Diagramme de transition

On représente une chaîne de Markov homogène(Xn)n?Npar ungraphe orienté pondéré, appelé

diagramme de transitiondont les sommets sont les éléments deE.

Deux élémentsxetysont reliés par une flèche dexàylorsque la probabilité de passer dexàyest

strictement positive (la probabilité est précisée au-dessus de la flèche), et sans flèche dexàylorsque la

probabilité de passer dexàyest nulle.Exemple 1. La marche aléatoire sur{1,2,...,N}semi-réfléchie en1et enN. On choisit au hasard une position initiale entre1etNpuis : •On se déplace de façon équiprobable de+1ou-1.

Sur les états1etN, on peut soit rester sur la même position, soit repartir vers l"état voisin, de

manière équiprobable. 3

La matrice de transition associée est

M=( ((((((((((1/2 1/2 0 0...0 0

1/2 0 1/2 0...0 0

0 1/2 0 1/2...0 0

0 0 1/2 0...0 0

0 0 0 0...0 1/2

0 0 0 0...1/2 1/2)

et la loi deX0est?1N 1N ...1N (on choisit au hasard une position initiale).

3 Étude d"une chaîne de Markov homogène

3.1 Étude mathématique d"une chaîne de Markov homogène

On suppose queE= [[1,N]].Méthode 3.1 :Comment calculer la loi d"une chaîne de Markov homogène?SoitMla matrice de transition de la chaîne(Xn)n?N. On pose le vecteur ligne

U n=?

P(Xn= 1)P(Xn= 2)...P(Xn=N)?

•La formule des probabilités totales associée au système complet d"événements(Xn=i)i?[[1,N]]donne

?j?[[1,N]],P(Xn+1=j) =N? i=1P(Xn=i)P(Xn=i)(Xn+1=j) =N? i=1P(Xn=i)pi,j. •La relation précédente est équivalente à ?n?N, Un+1=UnM. •Par récurrence, on montre que ?n?N, Un=U0Mn.

La loi deXnne dépend que de la matriceMet de la loi deX0.Remarque 3.2 :Définition par récurrence

Les chaînes de Markov sont le pendant aléatoire des suites récurrentes d"ordre1xn+1=f(xn). La

différence avec les suites récurrentes étant queXn+1est une fonction aléatoire deXn.

Les chaînes de Markov sont un objet essentiel des probabilités modernes; elles sont utilisées avec succès

en théorie des jeux, physique, biologie, sciences sociales, finance, informatique. 4

Méthode 3.3 :CasMdiagonalisableAyant trouvé les valeurs propres deM, et dans le cas oùMest diagonalisable, on sait qu"il existe une

matrice inversiblePet une matrice diagonaleDtelles queM=PDP-1.On a alors ?n?N, Mn=PDnP-1.

On peut alors calculer

?n?N, Un=U0PDnP-1.

On en déduit alors la loi deXnen déterminantU0,P,DetP-1.Remarque 3.4 :ConseilDans les cas oùMn"est pas diagonalisable, il faut se laisser guider par l"énoncé.3.2 Simulation des premiers états d"une chaîne de Markov avec Scilab

Définition 3.5 :Commande grand(.,"markov",.,.)

La commandegrand(n,"markov",M,x0)simule une chaîne de Markov de matrice de transition

M? MN(R)et d"état initialx0.

Cette commande renvoie lesnpremiers états de la chaîne (trajectoire) suivant l"état initial.Méthode 3.6 :Comment simuler une chaîne de Markov?On utilise la fonctiongrand(n,"markov",M,x0), oùMdésigne la matrice de transition de la chaîne.Remarque 3.7

Si l"ensemble des états est[[1,N]],x0doit être un entier compris entre1etN.Exemple 2.

On considère le jeu suivant : un mobile se déplace par sauts sur les points alignésA(état1),

O(état2) etB(état3). Le voyage s"effectue selon la règle suivante : •Le mobile démarre enO.

Si le mobile est enOà l"instantn, il sera de façon équiprobable, soit enAsoit enBà l"instantn+ 1.

•Si le mobile est enAà l"instantn, il y reste à l"instantn+ 1ou il retourne enOet ceci de façon

équiprobable.

Si le mobile est enBà l"instantn, il passe enOl"instantn+ 1avec la probabilité1(le pointBest dit réfléchissant).

On obtient le diagramme de transition suivant :

5

On souhaite simuler le trajet de ce mobile durant les10premiers sauts. Ce jeu est une chaîne de Markov à3

états :1(pointA),2(pointO) et3(pointB) dont la matrice est M=( (1/2 1/2 0

1/2 0 1/2

0 1 0)

Comme le mobile démarre enOon ax0=2, on peut alors proposer la commande suivante : --> X=grand(10,"markov",[1/2 1/2 0; 1/2 0 1/2; 0 1 0],2) X =

1. 2. 3. 2. 1. 2. 3. 2. 1. 1.

3.3 États stables d"une chaîne de Markov homogèneDéfinition 3.8 :Distribution stationnaire

Soit une chaîne de Markov homogène de matrice de transitionM. Une loi de probabilité définie par un

vecteur ligne stochastiqueΠqui satisfait l"équationΠM= Πest appeléedistribution stationnaire(ou

loi stationnaire) de la chaîne de Markov.

Propriété 3.9 :Distribution stationnairet

Πest vecteur propre detMpour la valeur propre1.Remarque 3.10 :Chaîne de Markov invariante

Si l"état initialX0a pour loi de probabilitéΠ, alors la chaîne de Markov est stationnaire (elle ne change

jamais d"état).Exemple 3.Déterminer un état stable pour une chaîne de Markov dont la matrice de transition est

M=?1/2 1/2

1/4 3/4?

Solution.On a le diagramme de transition suivant.

6

SoitΠ =?

x y? avecx+y= 1(c"est un vecteur ligne stochastique) telle que

ΠM= Πetx+y= 1??

??x/2 +y/4 =x, x/2 + 3y/4 =y, x+y= 1.?? ??-x/2 +y/4 = 0, x/2-y/4 = 0, x+y= 1.??y= 2/3, x= 1/3.

DoncΠ =?

1/3 2/3?

3.4 Convergence vers l"état stableProposition 3.11 :Convergence vers l"état stable

On suppose queUn(la loi deXn) converge vers une limiteL? M1,N(R). CommeUn+1=UnM, par passage à la limite on a : L=LM

La limite de la loi deXnest donc forcément l"état stableL= Π(vers lequel le système converge en temps

long).

Dans ce cas, on remarque que quelle que soit la position initialex0de la chaîne de Markov, sa loi se

stabilise vers la même loi limite.Remarque 3.12 :Attention !

La réciproque est fausse : il peut y avoir un état stable mais les lois de la chaîne de Markov peuvent ne

pas converger vers l"état stable.Exemple 4.Reprenons l"exemple précédent d"une chaîne de Markov dont la matrice de transition est

M=?1/2 1/2

1/4 3/4?

On a calculé l"état stableΠ =?

1/3 2/3?

Solution.Nous pouvons vérifier cela avecScilab

--> n=10000; --> X=grand(n,"markov",[1/2 1/2; 1/4 3/4],1); --> s1=sum(X==1) // nombre des états 1 de la chaîne s1 = 7 3291.
--> f1=sum(X==1)/n // proportion des états 1 de la chaîne f1 =

0.3291

--> s2=sum(X==2) // nombre des états 2 de la chaîne s2 = 6709.
--> f2=sum(X==2)/n // proportion des états 2 de la chaîne f2 =

0.6709Cela semble vouloir dire que, sur le long terme, il y a une chance sur3pour que le système soit dans l"état1

et deux chances sur3pour que le système soit dans l"état2. On a bien lim n→+∞Un= limn→+∞?

P(Xn= 1)P(Xn= 2)?

1/3 2/3?

Donc lim n→+∞P(Xn= 1) =13 etlimn→+∞P(Xn= 2) =23 8quotesdbs_dbs13.pdfusesText_19

[PDF] matrice de transition exemple

[PDF] matrice de transition terminale s

[PDF] matrice des coefficients techniques

[PDF] matrice diagonalisable exemple

[PDF] Matrice et variable aléatoire

[PDF] matrice identité d'ordre 3

[PDF] matrice inverse de leontief definition

[PDF] matrice inversible exercice corrigé

[PDF] matrice nilpotente exercice corrigé

[PDF] Matrice probabiliste, terminale

[PDF] matrice spe maths es

[PDF] Matrice spécialité maths (ES)

[PDF] matrice terminale es exercice

[PDF] matrice trigonalisable exercice corrigé

[PDF] matrice xcas