[PDF] Chaînes de Markov (et applications) PDF Markov.pdf

22 fév 2021 · Il est clair que si deux chaîne de Markov X = (Xn) et Y = (Yn) ont la même loi initiale µ0 et la même matrice de transition Q, alors elles ont la même

Ainsi l'évolution de la loi de Xn se ramène en fait à de l'algèbre linéaire A toute matrice de transition, on peut associer un graphe dirigé, éventuellement infini Les

[PDF] Chaînes de Markov et Processus markoviens de sauts Applications

La probabilité µ est appelé loi initiale de la chaîne et la matrice P matrice de transition Proposition 1 (Xn)n≥0 est une chaîne de Markov si et seulement si ∀ n

[PDF] Introduction aux chaines de Markov - CERMICS

Soit P une matrice stochastique sur E Une suite de variables aléatoires (Xn,n ∈ N) `a valeurs dans E est appelée chaıne de Markov de matrice de transition P

[PDF] Chaînes de Markov (et applications)

22 fév 2021 · Il est clair que si deux chaîne de Markov X = (Xn) et Y = (Yn) ont la même loi initiale µ0 et la même matrice de transition Q, alors elles ont la même

[PDF] Chaînes de Markov - DI ENS

Chaˆınes de Markov 8 1 La matrice de transition Une suite de variables aléatoires {Xn}n≥0 `a valeurs dans l'espace dénombrable E est appelé processus

[PDF] Chaines de Markov : compléments

Il n'y aurait plus moyen alors de définir de matrice de transition En réalité, lorsqu' on adopte une modélisation par une chaıne de Markov, on suppose de fait que

[PDF] Dynamiques aléatoires : chaines de Markov

C'est une caractéristique importante des chaınes de Markov que la matrice de transition P élevée `a la puissance k contient les probabilités de transitions de

[PDF] Chaînes de Markov - UQAM

22 mai 2014 · Si P est une matrice de transition d'une chaîne de Markov, alors la matrice N = (I − Q)−1, appelée matrice fondamentale de P, indique le

[PDF] Chaˆınes de Markov 1

Une chaıne de Markov de matrice de transition P et de loi initiale µ est une suite de v a (Xn) n∈N , définie sur un espace probabilisé (Ω,A,P), `a valeurs dans E

[PDF] exercice corrigé chaine de markov a etat absorbante

[PDF] chaine d'acquisition de données

[PDF] chaine de mesure audioprothèse

[PDF] acquisition de données du capteur ? l ordinateur

[PDF] chaine de mesure pdf

[PDF] chaine d'acquisition capteur

[PDF] les capteurs exercices corrigés

[PDF] chaine de markov apériodique

[PDF] chaine de markov apériodique exemple

[PDF] chaine de markov reversible

[PDF] chaine de markov récurrente

[PDF] chaine de markov exemple

[PDF] chaine de markov irreductible exemple

[PDF] chaine de markov exercice corrigé

[PDF] chaine énergétique barrage hydraulique

Chaînes de Markov : théorie et applications

Pierre-Loïc Méliot

Chapitre 1

Propriété de Markov

Les premiers résultats classiques de la théorie des probabilités (la loi des grands nombres, le

théorème central limite,etc.) concernent les suites(Xn)n∈Nde variables aléatoires indépendantes :

ce qui se passe si l"on relaxe un peu cette hypothèse, en demandant par exemple que

"Xn+1ne dépend du passé (les variablesX0,...,Xn) qu"au travers de la dernière variableXn».

L"objectif de ce premier chapitre est de formaliser cette idée, et d"étudier les premières propriétés

des suites de variables aléatoires correspondantes, qu"on appellerachaînes de Markov.

1. Matrices de transition et chaînes de Markov

On fixe dans tout ce chapitre un ensembleXfini ou dénombrable, donc en bijection avec une partie de l"ensemble des entiersN. On dit queXest unespace d"états. Nos suites de variables

aléatoires prendront leurs valeurs dansX; cette restriction interdit par exemple de considérer des

chaînes de Markov à valeurs dans l"ensemble non dénombrable des réelsR, mais elle peut être levée

sans grandes difficultés si l"on approfondit un peu la théorie qui sera développée ici. L"avantage de

cette restriction est qu"elle ôte la plupart des subtilités de théorie de la mesure. Uneprobabilitésur

Xest une famille de nombres réels positifs(p(x))x∈Xtelle que X x∈Xp(x) = 1. Étant donnée une telle probabilitép, la probabilité d"une partieA⊂Xestp(A) =P x∈Ap(x). Définition1.1 (Matrice stochastique).Une matrice stochastique, ou matrice de transition surX est une famille(P(x,y))x,y∈Xde nombres réels positifs telle que, pour toutx∈X, X y∈XP(x,y) = 1. Autrement dit, pour toutx∈X,P(x,·)est une probabilité surX. Exemple1.2.SurX={1,2,3}, la matrice suivante est une matrice stochastique :

P=

0 13 23
12 16 13 14 034

En effet, les entrées de la matrice sont positives (au sens large), et la somme sur chaque ligne vaut1.

donnée par un vecteur ligne; par exemple,π= (13 ,13 ,13 )est la probabilité uniforme sur l"espace

{1,2,3}. Si l"espace d"états est infini, il faut s"imaginer un vecteur ligne de longueur infinie. Cette

convention d"écriture permet l"observation suivante : Proposition1.3.SoitPune matrice stochastique sur un espace d"étatsX. 1

2 1. PROPRIÉTÉ DE MARKOV

(1)

P ourt outepr obabilitéπ= (π(x))x∈XsurX, le produit matricielπPest une nouvelle proba-

bilité surX. (2) P ourt outeautr ematr icest ochastiqueQsurX, le produit matricielPQest encore une matrice stochastique. Démonstration.Supposons pour commencer queXest un ensemble fini de tailleN: une probabilité surXest un vecteur ligne de tailleN, et une matrice stochastique surXest une matrice

de tailleN×N. Siπest une probabilité surXet siPest une matrice stochastique surX, alors pour

toutx∈X, (πP)(x) =X w∈Xπ(w)P(w,x).

Cette quantité est positive en tant que somme de nombres positifs, et on obtient bien une nouvelle

probabilité, carX x∈X(πP)(x) =X (w,x)∈X2π(w)P(w,x) =X w∈Xπ(w) = 1

en utilisant la propriété de matrice stochastique pour la seconde identité, et le fait queπest une

probabilité pour la dernière identité. Ceci prouve le premier point, et le second point s"en déduit

immédiatement, car pour toutx∈X, (PQ)(x,·) =P(x,·)|{z} ligne d"une matrice stochastique×Q|{z} matrice stochastique =probabilité×matrice stochastique=probabilité.

considérées peuvent maintenant être des séries de nombres positifs. Notons qu"en règle générale,

on ne peut pas définir correctement le produit matriciel pour des matrices de taille infinie, à cause

de problèmes de sommabilité; mais il n"y a pas de problème si tous les coefficients des matrices sont

positifs, et ce sera toujours le cas dans nos calculs.□ Fixons une matrice de transitionPsur un espace d"étatsX. Une chaîne de Markov de matrice

PsurXest une suite(Xn)n∈Nd"éléments aléatoires deX, dont la loi, qui est une probabilité sur

l"ensembleXN, vérifie certaines propriétés qui seront décrites ci-dessous(voir Définition1.5 ).L "une

des difficultés de la théorie des chaînes de Markov est que l"on doit manipuler des probabilités sur

l"ensembleXNde toutes les suites à valeurs dansX; or, dès quecard(X)≥2, cet ensemble est non

dénombrable, et manipuler des probabilités sur un tel ensemble pose des problèmes de théorie de

la mesure. Le paragraphe suivant donne des définitions et des résultats qui vont nous permettre de

surmonter ces obstacles théoriques. Par souci de rigueur, certains énoncés dans ce qui suit utilisent

les notions usuelles de théorie de la mesure (tribu, partie mesurable,etc.), mais c"est à peu près

le seul endroit du cours où on en aura besoin, et on peut sans doute comprendre tout le reste indépendamment de ces arguments.

On appelletrajectoireune suite(xn)n∈Nd"états de l"espaceX. Uncylindre à horizonN≥0est

un ensemble de trajectoires de la forme C(y0,y1,...,yN) ={trajectoires(xn)n∈N|x0=y0,x1=y1,...,xN=yN}; c"est donc une partie deXN. On noteFNla plus petite tribu sur l"ensembleXNqui contient tous les cylindres à horizonN(on rappelle qu"une tribu est un ensemble de parties qui contient∅et X

N, qui est stable par union dénombrable, par intersection dénombrable et par complémentaire).

Il est facile de voir que les événements deFNsont toutes les unions dénombrables de cylindres à

1. MATRICES DE TRANSITION ET CHAÎNES DE MARKOV 3

horizonN: F

N=

G (y0,...,yN)∈AC(y0,...,yN), Apartie deXN+1 Chaque cylindre à horizonNest une union disjointe de cyclindres à horizonN+ 1:

C(y0,y1,...,yN) =G

N+1∈XC(y0,y1,...,yN,yN+1).

Ceci implique que les tribusFNsont croissantes pour l"inclusion : F

0⊂ F1⊂ F2⊂ ··· ⊂ FN⊂ FN+1⊂ ···

Lorsqu"on observe des trajectoires dansXN, il faut comprendreFNcomme l"ensemble des événe- ments qu"on peut mesurer en se fondant uniquement sur ce que l"on peut voir jusqu"au tempsN. Théorème1.4 (Kolmogorov).SoitFla plus petite tribu surXNqui contient toutes les tribusFN. (1)

La donnée d"une pr obabilitépsurS

N∈NFNest équivalente à la donnée de toutes les probabi- lités de cylindresp(C(y0,...,yN)), avec la règle de compatibilité p(C(y0,...,yN)) =X y

N+1∈Xp(C(y0,...,yN,yN+1))

pour toute famille finie(y0,...,yN). (2) Supposons donnée une t ellef onctionp. Alors, il existe un unique prolongement depà toute la tribuF, qui en fait une mesure de probabilité sur cette tribu.

Le théorème ci-dessus indique que, pour définir correctement une probabilitépsur l"ensembleXN

de toutes les trajectoires, il suffit de la définir sur les cylindres. Notons que la tribuFest en général

strictement plus grande que l"unionS N∈NFN. En effet, six∈X, alors l"événement

E={(xn)n∈N|xn=xpournassez grand}

n"est pas dansS N∈NFN(on ne peut pas décider si une suite est stationnaire àxà partir d"observa- tions à horizon fini), mais il est bien dans la tribuF, car E=[

N∈N

M≥N{(xn)n∈N|xM=x}!

c"est donc l"union dénombrable d"intersections dénombrables d"événements dans les tribusFM.

Nous admettrons le théorème

1.4 sans démons tration;la pr emièrepar tiees ttr èsf acile,e tla se-

conde peut par exemple être prouvée en utilisant le lemme de classe monotone. Tout ceci n"est pas

vraiment important pour la suite, mais rend rigoureux la définition suivante. Définition1.5 (Chaîne de Markov).SoitXun espace d"états (fini ou dénombrable), etPune (Xn)n∈N∈XN, dont la loi est donnée sur les cylindres par la formule suivante : P[X0=x0,X1=x1,...,XN=xN] =π0(x0)P(x0,x1)P(x1,x2)···P(xN-1,xN),

0étant une certaine mesure de probabilité surX. On dit alors queπ0est la loi initiale de la chaîne de

Markov;P[X0=x0] =π0(x0)pour toutx0∈X.

Si la loi initialeπ0est donnée, alors la fonction définie sur les cylindres par p(C(x0,...,xN)) =π0(x0)P(x0,x1)···P(xN-1,xN)

4 1. PROPRIÉTÉ DE MARKOV

est bien une probabilité, et elle vérifie bien la condition de compatibilité du premier point du

théorème 1.4 . En effet, pour voir quepest une probabilité, notons qu"elle prend bien ses valeurs dans[0,1]pour tout cylindre, et qu"on a bien p(XN) =p G x

0∈XC(x0)!

=X x

0∈Xπ

0(x0) =π0(X) = 1.

Pour la compatibilité, on utilise le caractère stochastique de la matrice de transitionP: X y

N+1∈Xp(C(y0,...,yN+1)) =X

N+1∈Xπ

X y =π0(y0)P(y0,y1)···P(yN-1,yN) =p(C(y0,...,yN)).

Par conséquent, si on se donneπ0etP, alors par le théorème de Kolmogorov1.4 il e xisteune

unique probabilité sur les trajectoires dansXNqui vérifie la formule de la définition1.5 . On notera

cette probabilitéP(P,π0)ou plus simplementPπ0, la matricePétant sous-entendue. La théorie des

chaînes de Markov est l"étude des propriétés des suites de variables aléatoires(Xn)n∈Nqui suivent

une loiP(P,π0). Pour l"instant, siPestπ0sont données, alors il n"est pas tout à fait clair qu"il existe

bien des suites de variables aléatoires(Xn)n∈Nqui sont des chaînes de Markov de loiP(P,π0); cette

question sera résolue dans le prochain paragraphe. Nous donnerons aussi dans la prochaine section

des exemples importants de chaînes de Markov. Voyons d"abord quelques conséquences immédiates

de la définition 1.5 . Soit(Xn)n∈Nune chaîne de Markov de loiP(P,π0)sur un espace d"étatsX. Pour n≥1, on noteπnla loi deXn(diteloi marginale) :πn(x) =P[Xn=x]. Cette loi se calcule facilement à l"aide dePetπ0: Proposition1.6 (Lois marginales).Soit(Xn)n∈Nune chaîne de Markov de loi initialeπ0et de

matrice de transitionP. Pour toutn≥0, la loi marginaleπnest donnée par le produit matriciel :

n=π0Pn. Démonstration.Pour calculerπn(x), on peut sommer sur toutes les possibilités pour les va- riablesX0,X1,...,Xn-1: n(x) =X (x0,x1,...,xn-1)∈XnP

π0[X0=x0,X1=x1,...,Xn-1=xn-1,Xn=x]

X (x0,x1,...,xn-1)∈Xnπ On reconnaît la somme sur les indices qui donne le produit matriciel(π0Pn)(x).□ Proposition1.7 (Chaînes de Markov et probabilités de transition).Soit(Xn)n∈Nune chaîne

de Markov de loi initialeπ0et de matrice de transitionP. Pour toutn≥0, la loi conditionnelle de

X n+1sachant(X0,...,Xn)estP(Xn,·). Autrement dit, pour tout vecteur(x0,x1,...,xn)tel que P

π0[X0=x0,...,Xn=xn]̸= 0, on a

π0[Xn+1=x|X0=x0,...,Xn=xn] =P(xn,x).

1. MATRICES DE TRANSITION ET CHAÎNES DE MARKOV 5

Démonstration.Par définition d"une probabilité conditionnelle, P π0[Xn+1=x|X0=x0,...,Xn=xn] =Pπ0[X0=x0,...,Xn=xn,Xn+1=x]P

π0[X0=x0,...,Xn=xn]

0(x0)P(x0,x1)···P(xn-1,xn)

=P(xn,x).

Notons que réciproquement, si(Xn)n∈Nest une trajectoire aléatoire dansXNqui vérifieP[X0=

x] =π0(x)pour toutx∈Xet qui vérifie la conclusion de la proposition, alors c"est une chaîne

de Markov de loi initialeπ0et de matrice de transitionP. En effet, raisonnons par récurrence et

supposons établie jusqu"au rangNla formule pour les probabilités des cylindres. Alors, au rang N+ 1,

P[X0=x0,...,XN+1=xN+1]

d"où la formule au rangN. Ainsi, la proposition1.7 es tune définition alt ernativedes c haînesde

Markov.□

Remarque1.8.La proposition1.7 im pliquepour une c haînede Mar kov(Xn)n∈Nde matriceP la formule

P[Xn+1=x|Xn=xn] =P(xn,x).

Remarquons néanmoins que ceci ne suffit pas pour avoir une chaîne de Markov : on veut que la loi

deXn+1conditionnellement à tout le début de la trajectoire{X0=x0,...,Xn=xn}ne dépende que de l"état au tempsn, et soit la loi de transitionP(xn,·). La proposition précédente montre que la définition 1.5 coïncide a vecl" objectifde dépar t: é tant

donnée une chaîne de Markov(Xn)n∈N, la loi deXn+1conditionnellement àXnest indépendante

du passé(X0,...,Xn-1), et elle est donnée par la matrice de transitionP(Xn,·). Pour conclure

cette introduction des chaînes de Markov, expliquons comment calculer l"espérance d"une fonction

f(Xn)d"une chaîne de Markov. Dans tout ce qui suit, une fonctionfsur l"espace d"étatsXsera

toujours représentée par un vecteur colonne, sauf si cette fonction est une mesure de probabilité

(dans ce cas, on a convenu précédemment d"utiliser des vecteurs lignes). Par exemple, la fonction

f(x) = 2xsurX={1,2,3}est représentée par le vecteur f= 2 4

Avec ces conventions d"écriture :

Proposition1.9 (Espérance d"une fonction d"une chaîne de Markov).Soit(Xn)n∈Nune chaîne

de Markov de loi initialeπ0et de matrice de transitionP, etfune fonction positive ou bornée surX.

(1) L "espéranceconditionnelle de f(Xn+1)sachantXn=xvaut E

π0[f(Xn+1)|Xn=x] = (Pf)(x),

oùPfest le produit matriciel de la matricePpar le vecteurf. (2)

L "espérancede f(Xn)est

π0[f(Xn)] =π0Pnf.

6 1. PROPRIÉTÉ DE MARKOV

Démonstration.Notons pour commencer que siPπ0[Xn=x]̸= 0, alors pour touty∈X, P

π0[Xn+1=y|Xn=x] =P(x,y). En effet,

π0[Xn+1=y|Xn=x]

=X (x0,...,xn-1)∈XnP X (x0,...,xn-1)∈XnP

π0[X0=x0,...,Xn-1=xn-1]P(x,y) =P(x,y).

La première partie de la proposition s"en déduit immédiatement :

E[f(Xn+1)|Xn=x] =X

y∈XP[Xn+1=y|Xn=x]f(y) =X y∈XP(x,y)f(y) = (Pf)(x). La seconde partie de la proposition est une conséquence triviale de la proposition 1.6

E[f(Xn)] =X

x∈XP[Xn=x]f(x) =πnf=π0Pnf.□

2. Construction et exemples de chaînes de Markov

Nous avons défini précédemment les chaînes de Markov en précisant la forme de leurs lois

trajectorielles, mais ce n"est sans doute pas très intuitif. Dans cette section, nous allons expliquer

comment construire explicitement une chaîne de Markov de loi initiale et matrice de transition

données, et présenter des exemples. Une notion utile est celle degraphe d"une matrice de transition.

Supposons donnés un espace d"étatsXet une matrice de transitionPsurX. Le graphe dePest le graphe dirigéGP: -dont l"ensemble des sommets estX; -avec une arête dirigée dex∈Xversy∈XsiP(x,y)>0; dans ce cas, on accole une

étiquetteP(x,y)à cette arête.

Par exemple, le graphe de la matrice stochastique de l"exemple 1.2 es tdessiné sur la figur e 1.1 .123 1 32
3 1 2 1 61
33
4 1 4 Figure 1.1.Graphe de la matrice de transition de l"exemple1.2 .

2. CONSTRUCTION ET EXEMPLES DE CHAÎNES DE MARKOV 7

Définition intuitive.SoitPunematricestochastiquesurunespaced"étatsX,etπ0unemesurede comme suit : (1) On c hoisitun pr emieré tataléat oireX0suivant la loiπ0. (2) Supposons constr uitsles é tatsX0,...,Xn. SiXn=x, alors pour obtenirXn+1, on tire au

hasard une variable aléatoire de loiP(x,·)et indépendante de tous les choix précédemment

effectués. d"un saut(Xn=x)→(Xn+1=y)étant donnée parP(x,y).

Le point délicat de la définition intuitive ci-dessus est l"" indépendance de la transitionXn→

n+1de tous les choix précédemment effectués ». Le théorème ci-dessous rend rigoureux cette idée,

et démontre également l"existence d"une chaîne de Markov(Xn)n∈Nde loiP(P,π0)pour n"importe

quelle matrice stochastique et n"importe quelle loi initiale sur un espace d"étatsX.

Théorème1.10 (Représentation des chaînes de Markov).SoitXun espace d"états,π0une proba-

bilité surX. (1)

Supposons données :

-une variableX0de loiπ0surX; -une suite de variables aléatoires(ξn)n∈Nà valeurs dans un espace mesurable(E,E), ces variables étant identiquement distribuées, indépendantes entre elles et indépendantes de la variableX0; -une fonction mesurablef:X×E→X. On définit par récurrence la suite(Xn)n∈Nen posant pourn≥0: X n+1=f(Xn,ξn). Alors,(Xn)n∈Nest une chaîne de Markov surXde loi initialeπ0et de matriceP(x,y) =

P[f(x,ξ0) =y].

(2) R éciproquement,pour t outematr icest ochastiqueP, on peut effectuer la construction ci-dessus, etonpeutmêmesupposerqueE= [0,1)etque(ξn)n∈Nestunesuitedevariablesindépendantes et de loi uniforme sur[0,1).

Démonstration.Pour la première partie de la proposition, il suffit de vérifier que(Xn)n∈Na

les lois trajectorielles de la définition 1.5 . Soit(x0,x1,...,xN)des états dansX. On calcule :

P[X0=x0,X1=x1,X2=x2...,XN=xN]

=P[X0=x0,f(X0,ξ0) =x1,f(X1,ξ1) =x2,...,f(XN-1,ξN-1) =xN] =P[X0=x0,f(x0,ξ0) =x1,f(x1,ξ1) =x2,...,f(xN-1,ξN-1) =xN] =P[X0=x0]P[f(x0,ξ0) =x1]P[f(x1,ξ1) =x2]···P[f(xN-1,ξN-1) =xN] =P[X0=x0]P[f(x0,ξ0) =x1]P[f(x1,ξ0) =x2]···P[f(xN-1,ξ0) =xN]

en utilisant à la troisième ligne l"indépendance deX0et des variablesξn≥0, et à la quatrième ligne

le fait que toutes les variablesξnont la même loi. Ainsi,(Xn)n∈Nest bien une chaîne de Markov de

loiP(P,π0).

8 1. PROPRIÉTÉ DE MARKOV

Pour la seconde partie, fixonsX,π0etP, ainsi qu"une suite(ξn)n≥-1de variables i.i.d. (in- dépendantes identiquement distribuées) de loi uniforme sur[0,1): pour toutnet tout intervalle [a,b)⊂[0,1), CommeXest fini ou dénombrable, on peut numéroter ses élémentsx1,x2,...Notons alors que, pour toute probabilitépsurX, la suite de nombres réels(Pk i=1p(xi))k≥0est croissante, commence

à0et se termine par1siXest fini, ou tend vers1siXest infini dénombrable. On utilise la variable

-1pour choisir au hasardX0de loiπ0: X

0=xk,oùkest l"unique indice tel quek-1X

i=1π i=1π

0(xi).

On obtient bien une variable de loiπ0, car

P[X0=xk] =P"

k-1X i=1π i=1π

0(xi)#

=kX i=1π

0(xi)-k-1X

i=1π

0(xi) =π0(xk).

Définissons maintenant la fonctionf:X×[0,1]→Xà peu près de la même façon : f(x,ξ) =xk,oùkest l"unique indice tel quek-1X i=1P(x,xi).

Alors, on a bien

P[f(x,ξ0) =xk] =P"

k-1X i=1P(x,xi)# =kX i=1P(x,xi)-k-1X i=1P(x,xi) =P(x,xk)

pour toutxk∈X, donc par la première partie de la proposition, la suite(Xn)n∈Ndéfinie par la

récurrenceXn+1=f(Xn,ξn)est une chaîne de Markov de loiP(P,π0).□ point de vue pratique, si l"on veut simuler une variableξde loi uniforme sur[0,1)(par exemple

avec un ordinateur), il suffit de disposer d"une suite de lancers de pile ou face indépendants(bn)n≥1

avecP[bn= 0] =P[bn= 1] =12 pour toutn. En effet, le réel aléatoire dont l"écriture en base2est

ξ= 0.b1b2···bn···

suit alors une loi uniforme sur[0,1). Donc, on peut très facilement simuler une chaîne de Markov à

l"aide d"un ordinateur; dansPythonpar exemple, pour obtenir un réel aléatoire uniforme sur[0,1),

on utilise la commande import random random random()

Exemple1.12 (Suites de variables i.i.d.).Soitπune mesure de probabilité sur un espace d"états

X, et(Xn)n∈Nune suite de variables i.i.d. à valeurs dansX, avecP[Xn=x] =π(x)pour toutn∈N

et toutx∈X. Alors,(Xn)n∈Nest une chaîne de Markov de matrice de transition

P(x,y) =π(y).

En effet, on peut utiliser le théorème de représentation avecE=X,Xn+1=ξnetf(x,y) =y. Ce

n"est pas un exemple très intéressant (la probabilité d"une transition(Xn=x)→(Xn+1=y)ne

dépend pas dex), mais ceci montre que la théorie des chaînes de Markov généralise celle des suites

de variables indépendantes.

2. CONSTRUCTION ET EXEMPLES DE CHAÎNES DE MARKOV 9

Exemple1.13 (Ruine du joueur).SoitMun entier plus grand que1, etp∈(0,1)un nombre réel. On considère la chaîne de Markov d"espace d"étatsX={0,1,2,...,M}= [[0,M]], et de probabilités de transition ∀k≥1, P(k,k-1) = 1-p;

P(0,0) = 1-p;P(M,M) =p.

Le graphe de cette chaîne de Markov est :012M-1M···pppp

1-p1-p1-p1-p1-pp

Cette chaîne de Markov modélise la quantité d"argent d"un joueur qui participe à chaque tempsnà

un jeu où il a une probabilitépde gagner et d"augmenter ses fonds d"une unité, et une probabilité

1-pde perdre et de voir ses fonds diminuer d"une unité. Le nombreMest la quantité totale

d"argent mise en jeu et que le joueur peut remporter. On parle de lachaîne de Markov de la ruine

du joueur; l"un des problèmes importants que nous résoudrons dans ce chapitre est le calcul de la

probabilité de ruine P[la chaîne atteint l"état0avant l"étatM|X0=k].

Il existe un certain nombre de variantes de cette chaîne, avec les mêmes probabilités de transition

sauf pourP(0,·)etP(M,·). En particulier, une alternative assez fréquemment étudiée est le cas

oùP(0,1) =P(M,M-1) = 0etP(0,0) =P(M,M) = 1; si l"on imagine un jeu au casino,

cette modification implique que le jeu s"arrête lorsque le joueur est ruiné et atteint0, ou lorsqu"il a

remporté tout l"argent de la banque en atteignant l"étatM.

Exemple1.14 (File d"attente).Modifions légèrement l"exemple précédent en prenant l"espace

d"étatsX=N, avec essentiellement les mêmes probabilités de transition que précédemment :

∀k≥1, P(k,k+ 1) =p; ∀k≥1, P(k,k-1) = 1-p;

P(0,1) = 1.

C"est le casM= +∞dans le modèle de la ruine du joueur, avec également une modification de la

probabilité de transitionP(0,·).012···1pp

1-p1-pLa chaîne de Markov avec ces probabilités de transition modélise le nombre de personnes dans une

file d"attente avec un seul guichet :

-si la file d"attente est vide à l"étapen(Xn= 0), l"étape suivante correspond à l"arrivée d"un

nouveau client et on a doncXn+1= 1avec probabilité1.

-si la file d"attente est non vide à l"étapen(Xn=k≥1), l"étape suivante correspond soit

à l"arrivée d"un nouveau client (Xn+1=k+ 1), soit au départ du client au guichet dont la demande a été traitée (Xn+1=k-1). Certaines hypothèses de modélisation mènent aux valeurs de probabilités de transitionP(k,k+ 1) =petP(k,k-1) = 1-ppour un

certain paramètrepmesurant la différence entre la fréquence d"arrivée de nouveaux clients

et la fréquence de traitement des demandes (voir les exercices en fin de chapitre pour plus de détails).

10 1. PROPRIÉTÉ DE MARKOV

Des questions importantes pour ce modèle sont : est-ce qu"on a avec probabilité non nulleXn→

+∞(explosion de la chaîne)? Quel est le nombre moyen de personnes dans la file au cours d"un long intervalle de temps? Partant deX0=k, combien de temps en moyenne faut-il attendre pour que la file d"attente se vide? en retirant les deux bornes inférieure et supérieure de l"espace d"états : on prendX=Zet

P(k,k+ 1) =p;P(k,k-1) = 1-p

pour toutk∈Z. C"est lamarche aléatoire surZde paramètrep: à chaque étape, on fait un saut vers

le haut avec probabilitépet vers le bas avec probabilité1-p. Une construction possible de cette

chaîne est à partir de variables de Bernoulli indépendantes(ξn)n∈Navec

P[ξn= +1] =p;P[ξn=-1] = 1-p.

Alors,Xn=X0+ξ1+···+ξnest une chaîne de Markov surZavec matrice de transition donnée

par les formules ci-dessus. On étudie très souvent le cas oùX0= 0presque sûrement; autrement

dit,π0=δ0est le Dirac en0, avec

0(k) =(

1sik= 0,

0sinon.

On notera la loi de chaîne de MarkovP0au lieu dePδ0; plus généralement, étant donnée une chaîne

de Markov sur un espace d"étatsX, si la loi initiale est le Dirac en un pointδx, on notera toujours

xau lieu dePδxla loi associée surXN. Pour la marche aléatoire surZ, le cas le plus intéressant est

sans doute celui oùp= 1-p=12 (marche aléatoiresymétrique). Une trajectoire de cette marche aléatoire sous la loiP0est dessinée ci-dessous.100200n0510 -5Figure 1.2.Marche aléatoire symétrique surZ. La loi des grands nombres et le théorème central limite donnent des informations sur la dis-

tribution deXn=ξ1+ξ2+···+ξnànfixé (grand), mais pas sur l"aspect de toute la trajectoire

(X1,X2,...,Xn). En particulier, voici quelques questions importantes que l"on pourra résoudre

avec la théorie des chaînes de Markov (les réponses dépendent de la valeur du paramètrep) :

-combien de fois la trajectoire passe-t-elle par0? quel est la durée moyenne entre deux passages en0? quelle est la loi du temps aléatoire séparant deux passages en0? -la trajectoire reste-t-elle bornée? peut-elle tendre vers+∞ou-∞? combien de temps faut-il attendre pour atteindre un niveauk∈Z, partant deX0= 0? Exemple1.16 (Marche aléatoire sur un graphe).On a expliqué précédemment comment asso-

cier à une matrice stochastiquePun graphedirigéGP, de sorte que la chaîne de Markov de matrice

Pest une marche aléatoire sur ce graphe avec des probabilités de saut données parP. Il y a aussi une

façon canonique d"associer à un graphenon dirigéGune matrice stochastiquePGd"espace d"états

2. CONSTRUCTION ET EXEMPLES DE CHAÎNES DE MARKOV 11

l"ensemble des sommets deG. Considérons ainsi un grapheG= (X,E), c"est-à-dire un ensemble dénombrable de sommetsXet un ensemble d"arêtes E⊂ {paires{x,y}d"éléments distincts deX}.

On supposera que pour tout sommetx∈X,

degx= card({y∈X|{x,y} ∈E})est fini et supérieur à1. ceci n"implique pas queGsoit un graphe connexe. La matrice de transition canoniquement associée au grapheGest : P

[PDF] [PDF] Chaînes de Markov (et applications)