Markov Chains and Markov Chain Monte Carlo

Markov Model of English Text (*) •Download a large piece of English text, say “War and Peace” from Project Gutenberg •We will model the text as a sequence of characters •Write a programme to compute the ML estimate for the transition probability matrix •You can use the ﬁle markov_text R or markov_text m to help convert

MARKOV CHAINS: BASIC THEORY - University of Chicago

forth that fXngn 0 is a discrete-time Markov chain on a state space Xwith transition probabili-ties p(i,j) Deﬁne the transition probability matrix P of the chain to be the XX matrix with entries p(i,j), that is, the matrix whose ith row consists of the transition probabilities p(i,j)for j 2X: (4) P=(p(i,j))i,j 2X

Chaînes de Markov - Université Paris-Saclay

Chaînes de Markov Résumé Une chaîne de Markov est un processus aléatoire (Xn)n2N dont les transitions sont données par une matrice stochastique P(Xn,Xn+1) Ces processus vériﬁent la propriété de Markov, c’est-à-dire qu’observés àpartird’untemps(d’arrêt)T, (XT+n)n2N ne dépend que de XT et est de nouveau une chaîne de

Les chaînes de Markov - HEC Montréal

Markov Notation et notions de base Classi–cation des Øtats ProbabilitØs d™absorption Loi stationnaire RØfØrences Les chaînes de Markov 3-602-84 ModŁles probabilistes et stochastiques de la gestion

Chapitre 8 Chaˆınes de Markov

Chapitre 8 Chaˆınes de Markov 8 1 La matrice de transition Une suite de variables al·eatoires {Xn}n 0 ‘a valeurs dans l’espace d·enombrable E est appel·e processus stochastique (‘a temps discret) (‘a valeurs dans E)

Chaînes de Markov - imag

de Markov Il est naturel de se demander s’il existe des chaînes de Markov, au sens de la proposition 1 2, qui ne soient pas simulables Il n’en existe pas si E est dénombrable, ou si E est IRd, muni de sa tribu de boréliens On n’en rencontrera donc jamais en pratique Exemple : Marches aléatoires

Chapitre 4 Chaˆınes de Markov ﬁnies

1 Chaˆınes de Markov homog`enes ﬁnies 1 1 D´eﬁnition Nous verrons plus bas une d´eﬁnition g´en´erale des chaˆınes de Markov : (section 5) Pour l’instant, nous ne nous int´eresserons qu’au cas particulier des chaˆınes de Markov a valeurs dans un ensemble ﬁni E, qui sont homog`enes en temps

MAD M1 Actuariat/ES

Propriété de Markov simple Propriété de Markov forte I Dé nitions et premieres propriétés 1 Chaine de Markov homogène et matrice stochastique Soit (X n) 2N un processus stochastique, à valeurs dans un espace d'état ni ou dénombrable E Exemple 1 (A propos de l'espace d'état) E peut-être {a,b,c,d} N ou Z De nition 1 (Chaine de Markov)

Corrigé Une introduction aux chaînes de Markov

Cette chaîne de Markov n’est pas irréductible (les autres états ne sont pas accessibles à partir d’un état absorbant) et n’est pas apériodique (mis à part les états absorbants, les autres états sont de période 2) b) On déﬁnit la matrice P à l’aide du script suivant : P = np zeros((9, 9), dtype=float) P[0, 0] = 1 P[8, 8] = 1

Chaines de Markov et application au Pagerank

- L’espace d’ etats d’une chaine de Markov est identi e a E= f0;1;2;:::;N 1g: Ecrivez une fonction markov step(P, x) prenant en entr ee une matrice de transition P et un x2E La sortie est la r ealisation al eatoire d’un pas de la chaine de Markov - Ecrivez egalement une fonction markov steps(n, P, x) dont la sortie est la liste des r

[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] Markov Chains and Markov Chain Monte Carlo