[PDF] Chaînes de Markov : théorie et applications

matrice stochastique sur X Une chaîne de Markov de matrice de transition P est (c) Application : on considère la marche aléatoire sur l'hypercube X = {0,1}N

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] Processus de Markov, application `a la dynamique des populations

Chaˆınes de Markov 1 1 Introduction L'idée des chaınes de Markov est tr`es simple: il s'agit d'une suite (Xn)n∈IN de variables aléatoires `a valeurs dans un

[PDF] Chaînes de Markov : théorie et applications - Département de

matrice stochastique sur X Une chaîne de Markov de matrice de transition P est (c) Application : on considère la marche aléatoire sur l'hypercube X = {0,1}N

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

Chaînes de Markov (et applications) Raphael Lachieze-Rey∗ 26 janvier Si Q est la matrice de transition d'une chaîne de Markov, alors elle est stochastique

[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] Chaines de Markov et protocole de gestion des communications

meilleure compréhension ; et nous donnerons en fin du document un exemple d' application des chaines de Markov avec le système ALOHA La loi binomiale

[PDF] Chaînes de Markov

Φ l'application de E ×[0, 1] dans E qui au couple (i, u) associe l'inverse de la fonction de répartition de la loi (pij)j∈E, évalué en u L'algorithme calcule bien Xn+1

[PDF] Processus de Markov et applications - PAESTEL

11 sept 2006 · de Monte Carlo, le chapitre 2 sur les chaînes de Markov en temps discret à valeurs dans un ensemble fini ou dénombrable, et les chapitres 6 et

[PDF] Introduction aux chaines de Markov - CERMICS

Les applications des chaınes de Markov sont `a valeurs dans E est appelée chaıne de Markov de matrice de transition P si pour tous n ∈ N, x ∈ E, on a

[PDF] 3 Applications à létude de chaînes de Markov - Institut de

3 Applications à l'étude de chaînes de Markov 35 3 1 Convergence d'une chaîne de Markov vers une diffusion 35 3 1 1 Un peu d'intuition

[PDF] changement globaux pdf

[PDF] comment reduire le rechauffement climatique

[PDF] exercices corrigés changement d état d un corps pur

[PDF] chimie organique 1ere année biologie

[PDF] exercice de chimie 1ere année biologie

[PDF] cours préparatoire mp tunisie pdf

[PDF] cours de tce 1er année biologie pdf

[PDF] tp biologie végétale pdf

[PDF] les cours de geologie pdf

[PDF] cours de biologie cellulaire 1ere année snv

[PDF] cours physique l1 snv pdf

[PDF] cours biologie cellulaire usthb

[PDF] td physique 1ere année snv

[PDF] physique 1 annee snv

[PDF] chimie analytique cours pharmacie

[PDF] Chaînes de Markov : théorie et applications - Département de

[PDF] Chaînes de Markov : théorie et applications - Département de

Chaînes de Markov (et applications)

Raphael Lachieze-Rey

22 février 2021

M1 MM Paris Descartes, 2020 - 2021.

Table des matières

0.1 Espérances et probas conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

0.2 Familles sommables et théorème de Fubini . . . . . . . . . . . . . . . . . . . . . . . . . .

0.3 Formule des probabilités totales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 Chaînes de Markov homogènes 3

1.1 Exemples et définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Loi des marginales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

TD : Chaînes de Markov homogènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Temps d"absorption 18

2.1 Temps d"arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Probabilités et temps d"absorptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

TD : Temps d"arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Classification des états 25

3.1 Récurrence et transience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

TD : Classes d"équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Distributions invariantes 31

4.1 Théorème ergodique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35
TD : Mesures invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5 Convergence à l"équilibre 42

5.1 Périodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Algorithme de Metropolis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49
TD : Convergence et simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

TD : Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 TP 1 - Moteur de recherche 56

6.1 Construction du "Web" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2 Calcul de PageRank via les valeurs propres . . . . . . . . . . . . . . . . . . . . . . . . .

6.3 Estimation du PageRank avec un surfeur aléatoire . . . . . . . . . . . . . . . . . . . . .

6.4 Interprétation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57
raphael.lachieze-rey@parisdescartes.fr 1

6.5 Construction du moteur de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57

6.6 Raffinements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 TP2 Simulation de polymères 58

7.1 Packagegeometry. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .58

7.2 Evolution libre du polymère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.3 Test de polymères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 TP : Problème du voyageur de commerce 64

8.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.2 Algorithme d"optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.3 Etude de la convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8.4 Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CODE COULEUR

En noir : l"essentiel

En magenta : exemples, explications, exercices, commentaires, preuves,...

Rappels

0.1 Espérances et probas conditionnelles

On rappelle la formule de probabilités conditionnelles :P(AjB) =P(A\B)=P(B), pourP(B)6= 0.

On note parfoisPB(A) =P(AjB), rappelons quePB()est une mesure de probabilités à part entière.

Le double conditionnement se traite ainsi :

P(A\B\C) =P(A\BjC)P(C) =PC(A\B)P(C) =PC(AjB)PC(B)P(C) =P(AjB;C|{z} i:e:B\C)P(BjC)P(C): Etant donné des variables aléatoiresXetYà valeurs réélles,

E(XjY) ='(Y)

est une variable aléatoire qui est entièrement déterminée parY. Par exemple, siX;Ysont des variables

de Bernoulli de paramètre1=2indépendantes, E((X+Y)2jY) =E(X2jY) + 2E(XYjY) +E(Y2jY) =EX2+ 2YEX+Y2=12 +Y+Y2='(Y):

0.2 Familles sommables et théorème de Fubini

Etant donné un espace mesuré(

;)et une fonctionf: !R, l"intégrale Z f(x)(dx); n"a de sens que sifest intégrable Z jf(x)j(dx)<1 2 (exemple dex7!sin(x)x surR). Par contre, sif>0, alors Z f(x)(dx)2R+[ f+1g est défini sans ambiguité. De même, étant donné une série(an;n2N), 1 X n=0a n n"a de sens que sian>0ou si(an;n>0)est sommable, c"est-à-dire 1 X n=0janj<1:

Pour ce qui est de l"interversion, le théorème de Fubini nous dit que pour une fonction bi-mesurable

f(x;y)sur un produit d"espaces mesurés 0, Z Z

0f(x;y)(dx)

0(dy) =Z

0 Z f(x;y)0(dy) (dx) sif(x;y)>0ou si Z

0jf(x;y)j(dx)0(dy)<1

ou si, de manière équivalente, Z Z

0jf(x;y)j(dx)

(dy)<1:

Les fonctions positives peuvent être intégrées dans l"ordre qu"on veut. SiXnsont des variables aléatoires

sur l"espace probabilisé( ;P),

0=Net0est la mesure de comptage, ça nous donne avecf(!;n) =

X n(!); E X n2NX n=X n2NEXn sans besoin de justification sif(!;n)>0, ou si E X n2NjXnj=X n2NEjXnj<1:

0.3 Formule des probabilités totales

SoitU;Vdeux variables à valeurs dans un espace dénombrableE. Alors pourx2E;

P(U=x) =X

y2EP(U=x;V=y) =X y2Supp(Y)P(U=xjV=y)P(V=y):

1 Chaînes de Markov homogènes

;P)est un espace probabilisé. 3

1.1 Exemples et définitions

Idée: Une chaîne de Markov est une suite de variables aléatoires dans le temps ouconditionnel-

lement au présent, le futur ne dépend pas du passé, ou autrement dit le futur ne dépend du

passé que par le présent. Formellement, soitEun espace fini ou dénombrable. Ce sera l"espace d"états. Définition 1.SoitX=fXn;n0gune suite de variables aléatoires à valeurs dansE. On dit que Xest une chaîne de Markov si, pour toutx0;:::;xn+12E, on a

P(Xn+1=xn+1|{z}

Le futurjX0=x0;X2=x2;:::;Xn=xn|{z}

Le passé (et le présent)) =P(Xn+1=xn+1|{z}

Le futurjXn=xn|{z}

Le présent)

Cette propriété des chaînes de Markov est aussi connue commepropriété de Markov. On peut formuler cette propriété en termes de lois conditionnelles :

La loi conditionnelle deXn+1sachant(X0;:::;Xn)est égale à la loi conditionnelle deXn+1sachantXnExercice 1.

Parmi les exemples suivants, lesquels peuvent correspondre a une chaîne de Markov?

Les records du monde du 100m

La p opulationmondiale

La p ositiond"une v oiture( le passé nous renseigne sur sa vitesse, et donc sur sa p ositionfuture )

Le nom brede p ersonnesdans une file d"atten te

Un marc heuraléatoire qui ne revien tjamais su rses pas. Le couple (p osition,vitesse) d"une v oiturede course une marc healéatoire

Exemple 1.

Mo délisation

Séquence d"ADN : A CGGTAACTC...p eut-êtrevue en première appro ximationcomme une chaîne de Markov Ev olutionde p opulation: Chaque jour, un individu nait ou un individu meurt

Généalogie/Epidémiologie : Chaque jour, un individu donne naissance (ou con tamine)un nom bre

aléatoire d"individu, ou meurt (guérit)

In telligenceartificielle

Sim ulation.Exemple : jeu de cartes mélangé. On part d"un jeu de cartes (fictif )dans l"ordre, e t

à chaque coup on applique l"interversion de 2 cartes tirées au hasard. La "loi" du jeu de cartes

converge vers la loi d"un jeu de cartes mélangé selon une permutation uniforme Les questions auxquelles on va tenter de répondre dans ce cours : Conaissan tla loi de X0, quelle est la loi deXn;n2N? La loi deXnconverge-t-elle? P artantd"un certain x2E, et poury2E, quelle est la proba que la chaîne passe pary, i.e. qu"il existe un tempsT <1, aléatoire, pour queXT=y? Quel est l"espérance deT? Exercice 2.SoitRn;n0des variables indépendantes à valeurs dansE=N. Montrer queSn=Pn i=1RietPn=Qn i=1Risont des chaînes de Markov. Une chaîne de Markov peut être vue comme unsystème dynamique, ce qui veut dire que X n+1=fn(Xn), oufnest une "transformation aléatoire" indépendante du passé. Dans l"exemple précédent,fn(Xn)est la somme (ou le produit) deXnavecRn+1. 4 Si la transformation aléatoirefnne dépend pas den, i.e.Xn+1=f(Xn)pour toutnpour une certaine transformationf, on dit queXest unechaîne de Markov homogène.

Cela veut dire que si à un certain instantn0la chaîne se trouve à l"étatx(Xn=x), alors la

probabilité qu"elle se trouve à l"étatyau tempsn+ 1est la même que si l"on était au temps initial.

Définition 2.Une chaîne de Markov(Xn)esthomogènesi pour toutn0,xetydansE

P(Xn+1=yjXn=x) =P(X1=yjX0=x):

Dans ce cas, on pose

Q(x;y) =P(X1=yjX0=x); x;y2E:

Qest lamatrice de transitionde la chaîneX, on dit aussinoyau de transitionquandEest infini.

Dans ce cours, toutes les chaîne de Markov sont supposées homogènes, ce ne sera pas forcément

explicitement écrit. Remarque 1.Qest éventuellement une matrice infinie

Une chaîne de Markov homogène "saute" donc aléatoirement d"états en états, et la probabilité de

chaque saut est donnée par la matriceQ. En général, on montre queXest une chaîne de Markov en

même temps que l"on expliciteQ. Notation: CommeEest un espace dénombrable, une mesuresurEest défini par sa valeur sur les atomes : (fxg);x2E: Réciproquement, si(fxg)>0pourx2E,définit bien une mesure surEvia (A) =X x2A(fxg);AE: On abrège parfois cette notation en(x) =(fxg).est alors une mesure de probabilité si X x2E(x) = 1: On peut également noter cette mesure comme un vecteur siE=fx1;x2;:::gest ordonné := ((x))x2E= (1;2;3;:::)est équivalent à(xi) =i. Exemple 2.La mesure= (k2)k>1est définie par(fkg) =k2;k2N, ou par (A) =X k2Ak 2;AN:

C"est une mesure finie car

2est une série CVG, mais pas une mesure de probabilités. Par contre la

mesure =n2P 1 k=11k 2 n>1 en est une. 5

Définition 3.SoitQla matrice de transition d"une chaîne de Markov homogène. Etant donné un état

x2E, la mesure Q x(y) =Q(x;y) est une distribution (i.e. une mesure de probabilité) surE, appelée mesure de saut depuisx.

Démonstration:

En effet, pourx2E,

X y2EQ x(y) =X y2EQ(x;y) =X y2EP(X1=yjX0=x) =E(X y2E1

fX1=ygjX0=x) =E(1jX0=x) = 1:Exercice 3.Markov lui-même a analysé la succession de voyelles et de consonnes dans le livreEugene

Onekinde Pushkin sous l"angle des chaînes de Markov. Il est parti des données suivantes :A. Markov,

studied the sequence of 20,000 letters in A. S. Pushkin"s poem "Eugeny Onegin" discovering that the

stationary vowel probability isp= 0:432, that the probability of a vowel following a vowel isp1= 0:128,

and that the probability of a vowel following a consonant isp2= 0:663. 1. Quel est l"espace d"état ?La Matrice de transition ? 2. Mêmes questions a vec"The Childho odof Bagro v,the G randson": Markov also gave the results of his other tests; he studied the sequence of 100,000 letters in S. T. Aksakov"s novel. For that novel, the probabilities were p = 0.449, p1 = 0.552, and p2 = 0.365. 6 Exemple 3.Une grenouille monte sur une échelle. Chaque minute, elle peut monter d"un barreau

avec probabilité1=2, ou descendre d"un barreau avec probabilité1=2. L"échelle a5barreaux. Si la

grenouille arrive tout en haut, elle saute en bas de l"échelle avec probabilité1=2ou redescend d"un

7 barreu.

On appelleXnla position de la grenouille sur l"échelle. L"espace d"états est doncE=f0;1;2;:::;5g.

Si a un instantnla grenouille est au niveaux2 f1;2;3;4gde l"échelle, alors à l"instantn+1elle sera

au barreaux+ 1avec probabilité1=2; au barreaux1avec probabilité1=2; ce qui se traduit par

P(Xn+1=x+ 1jXn=x) = 1=2 (=P(X1=x+ 1jX0=x));

P(Xn+1=x1jXn=x) = 1=2 (=P(X1=x1jX0=x)

Comme les probabilités ne dépendent pas den, il semble que l"on tienne le bon bout pour avoir une

chaîne de Markov homogène. Si c"est le cas, on peut écrire une partie de la matrice de transition :

[PDF] [PDF] Chaînes de Markov : théorie et applications - Département de