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

[PDF] Introduction aux chaînes de Markov - Département de

7 4 Simulation des premiers états d'une chaıne de Markov homog`ene Vous trouverez d'autres exercices ainsi des documents de cours sur les On peut déduire de la proposition 24 une façon simple de calculer la loi de Xn puisque

[PDF] CHAÎNES DE MARKOV - Institut de Mathématiques de Bordeaux

Dans l'évolution au cours du temps, l'état du processus à un instant futur ne Soit Xn est une chaîne de Markov de matrice de transition P, et soit ν0 la loi de X0 On considère la marche aléatoire simple sur Z Elle possède une seule classe, 

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

22 fév 2021 · Dans ce cours, toutes les chaîne de Markov sont supposées homogènes, Soit Q la matrice de transition d'une chaîne de Markov homogène Donnez un exemple simple de configuration permettant un minimum local

[PDF] Chaînes de Markov - Institut Camille Jordan

1 7 2 Chaîne de Markov en temps continu et espace discret 27 de ces notes, issues d'un cours de 2ème année de Master, suppose une connaissance Un exemple particulièrement simple de marche aléatoire est celui où toutes les

[PDF] CHAÎNES DE MARKOV - Ceremade

5 4 Exercices : Introduction aux chaînes de Markov De plus, le maniement des probabilités discrètes étant plus simple que celui des probabilités continues et unige ch/math/folks/velenik/Cours/2013-2014/ProbaStat/probastat pdf , 2014

[PDF] Introduction aux chaines de Markov - CERMICS

Il est facile de calculer des espérances ou des lois conditionnelles pour une chaıne de Markov `a l'aide des puissances de sa matrice de transition Nous 

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

Dans ce cours, toutes les chaîne de Markov sont supposées homogènes Remarque 1 Pour cela, le plus simple est de diagonaliser la matrice Comme c 'est 

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

Une façon très simple de construire une chaîne de Markov (Xn)n≥0 est de se donner Dans ce cours, une probabilité µ sur E sera toujours définie comme un  

[PDF] Introduction aux chaînes de Markov Lycée - Gradus ad Mathematicam

Mots-clefs : chaînes ou processus de Markov, espace des états, loi initiale, lois instantanées, matrice de transition, matrice stochastique, probabilité de passage d' 

[PDF] Chaînes de Markov - DI ENS

fait, les chaınes de Markov sont des processus stochastiques dont l'évolution est régie par une simple suffit `a générer une grande variété de comportements

[PDF] chaînes de markov cours exercices et corrigés détaillés

[PDF] chaine de markov application

[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

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

2

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

2

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

3

1 Chaînes de Markov homogènes 3

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

4

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

9

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

14

2 Temps d"absorption 18

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

18

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

20

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

21

3 Classification des états 25

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

25

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

28

4 Distributions invariantes 31

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

33

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

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

5 Convergence à l"équilibre 42

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

42

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

49

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

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

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

56

6 TP 1 - Moteur de recherche 56

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

56

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

56

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

56

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

57
raphael.lachieze-rey@parisdescartes.fr 1

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

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

57

7 TP2 Simulation de polymères 58

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

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

58

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

61

8 TP : Problème du voyageur de commerce 64

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

64

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

64

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

64

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

64

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

quotesdbs_dbs2.pdfusesText_4