Chaˆınes de Markov avancées PDF

Chaˆınes de Markov `a temps discret

Cours sur les Chaines de Markov à temps discret. TOUCHE Nassim. Département de Processus aléatoires à temps discret : cours exercices et problèmes corrigés.

Corrigé de lexamen du 26 avril 2012 (durée 2h)

26‏/04‏/2012 Les trois parties sont indépendantes. Exercice 1 : On considère une chaîne de Markov (Xn)n≥0 sur {1...

MAT2717 – Processus stochastiques Élise Davignon

23‏/05‏/2022 et exercices corrigés de Sabin Lessard (éditions Ellipses). Veuillez ... Figure 3.1 – Le graphe d'une chaîne de Markov à temps continu. Ici ...

CHAÎNES DE MARKOV

La partie “Rappels de probabilités” est basée sur des notes écrites en collaboration avec Frédérique. Petit pour la préparation au CAPES.

Processus aléatoires et applications

02‏/01‏/2019 Exemple 6.0.1 (Chaıne de Markov en temps continu). Soit Yn une chaıne de Markov de matrice de transition P et soit Nt la fonction de ...

MAT-3071 Processus Stochastiques

Processus de Markov continus : mouvement brownien. > Th`emes du cours. 1. Chaˆınes de Markov. Définition Matrice de transition

Polytech Lyon M2 Statistique des processus Examen du 10 février

Exercice 2. On considère une chaîne de Markov à temps continu sur E = 11 2

TD n° 1 STATISTIQUE DESCRIPTIVE 7 13 8 10 9 12 10 8 9 10 6 14

Exercices d'application directe du cours a) En Ile de France chaque véhicule B – PROCESSUS STOCHASTIQUES A TEMPS CONTINU. B1. On suppose que la durée de ...

Exercices corrigés

Calculer la moyenne et la variance de Y . Solution. 1) La variable aléatoire X est absolument continue à valeurs dans R. Elle admet une densité de probabilité

Corrigé de lexamen du 26 avril 2012 (durée 2h)

26 avr. 2012 Les trois parties sont indépendantes. Exercice 1 : On considère une chaîne de Markov (Xn)n?0 sur {1...

Chaˆ?nes de Markov avancées

21 déc. 2012 Markov `a temps continu et en particulier `a la modélisation de ... Exercice IV (Simuler un processus de Poisson avec un nombre de sauts.

Sciences de gestion - Synthèse de cours exercices corrigés

de cours exercices corrigés. Éric DOR. &. Économétrie. Cours et exercices adaptés constantes dans le temps et les covariances entre des composantes de ...

TD n° 1 STATISTIQUE DESCRIPTIVE 7 13 8 10 9 12 10 8 9 10 6 14

la variable est quantitative si elle est continue ou discrète. Exercices d'application directe du cours ... une loi uniforme continue calculer :.

MAT-3071 Processus Stochastiques

Séance d'exercices : Jeudi 10h30-12h30 (local SH-2420) Chaˆ?nes de Markov `a temps continu ... Deuxi`eme test de 10% et un examen final de 40%.

Introduction aux probabilités et à la statistique Jean Bérard

ainsi que des exercices dans lesquelles des hypothèses très simplificatrices sont posées. Comment travailler ce cours. Le volume de ce document vous affole

Chaînes de Markov

1.7.2 Chaîne de Markov en temps continu et espace discret . . . . 27 Exercice 3 Considérons une famille de variables aléatoires X0...

Processus aléatoires et applications

2 janv. 2010 2 Chaˆ?nes de Markov sur un ensemble dénombrable ... A Solution de quelques exercices ... L'état change au cours du temps discret. A chaque.

Recherche Opérationnelle:

Programmation dynamique chaînes de Markov

Introduction à la théorie des graphes

D'après le résultat établi dans l'exercice précédent un tel graphe doit Chaîne : suite finie de sommets reliés entre eux par une arête.

Cha^nes de Markov avancees

M2 Genie Biologique et Informatique { Premier semestre 2012{2013Mikael Falconnet mikael.falconnet@genopole.cnrs.frTable des matieres

1 Processus de Poisson 2

1.1 Rappels sur la loi exponentielle . . . . . . . . . . . . . . . . . .

1.2 Processus de Poisson : denition et propriete principale . . .

1.3 Processus de Poisson et loi exponentielle . . . . . . . . . . . .

1.4 Proprietes supplementaires . . . . . . . . . . . . . . . . . . . . .

2 Modeles d'evolution de sequences biologiques 10

2.1 Modeles markoviens de substitution de nucleotides . . . . . .

2.2 Distance phylogenetique . . . . . . . . . . . . . . . . . . . . . .

2.3 Modeles Markoviens de substitution de codons . . . . . . . . .

A Correction des exercices 22

B Sujets d'examen 49

B.1 Premiere Session 2012{2013 . . . . . . . . . . . . . . . . . . . . 49
B.2 Seconde Session 2012{2013 . . . . . . . . . . . . . . . . . . . . . 62
1 L'objectif de ce cours est de familiariser les etudiants avec les cha^nes de Markov a temps continu et en particulier a la modelisation de l'evolution de sequences biologiques. On introduira la loi exponentielle et les processus de Poisson, la notion de generateur innitesimal sera abordee a travers les modeles markoviens de substitutions de nucleotides et nous evoquerons egalement les modeles de substitution de codons. La simulation sous le logicielRoccupera une part importante du module.

1 Processus de Poisson

1.1 Rappels sur la loi exponentielle

La loi exponentielle joue un r^ole fondamental dans les processus de Poisson et les cha^nes de Markov a temps continu. Nous en exposons ici les proprietes principales.

Denition 1.1

(loi exponentielle).La loi exponentielle de parametre¸, (avec

¸È0), noteeExp(¸)est la loi de densite

x7!¸e¡¸x,x>0. En particulier,Csuit une loi exponentielle de parametre¸si et seulement si

P(CÈt)AEe¡¸t,pour toutt>0.

La notationCest un choix personnel et provient de la premiere lettre declock signianthorlogeen anglais. En eet, dans la majorite des situations rencon- trees, les variables aleatoires suivant des lois exponentielles representeront des temps d'attente entre deux arrivees. On peut donc se representerCcomme le temps de sonnerie d'une horloge aleatoire suivant une loi exponentielle. La notationTsera reservee aux temps d'arrivee. Proposition 1.2.La loi exponentielle satisfait les proprietes suivantes. (i)P(CÈtÅujCÈu)AEP(CÈt)AEe¡¸t, pour toust,uÈ0. (ii)P(C6tÅsjCÈt)AE¸s[1Å"(s)], ou"(s)!0quands!0. (iii) SoientC1,C2,...,Cndes variables aleatoires independantes distribuees suivant des lois exponentielles de parametres¸1,¸2,...,¸n. AlorsCAEmin(C1,...,Cn)suit une loi exponentielle de parametrePn iAE1¸i. La propriete(i), appeleeabsence de memoire, caracterise la loi exponentielle, c'est a dire que c'est la seule loi continue qui possede cette propriete. La demonstration est un elegant exercice sur les equations fonctionnelles. Plus 2 important est l'interpretation de(i). Elle signie que si l'horloge n'a pas sonne jusqu'au tempsu, la probabilite qu'elle sonne dans l'intervalle(u,tÅu] ne depend que detet pas deu. L'horloge a "oublie" qu'elle n'avait pas sonne jusqu'au tempsuet s'est reinitialisee. Cette propriete peut sembler perturbante quand on pense queCpeut representer le temps de panne d'une machine. En eet, l'absence de memoire dans ce cas revient a oublier l'usure de la machine. Le propriete(ii)signie que si une horloge suit une loi exponentielle de parametre¸, la probabilite qu'elle sonne dans un petit intervalle de longueur sest approximativement¸s. La propriete(iii)signie que si je regardenhorloges independantes alors le temps d'attente de la premiere sonnerie parmi cesnhorloges est aussi une loi exponentielle. Preuve de la proposition 1.2.Montrons(i). Nous avons

¡¸uAEe¡¸t.

Montrons(ii). Nous avons

Montrons(iii). Nous avons par denition deC

P(CÈt)AEP(C1Èt,...CnÈt),

puis gr^ace a l'independance des variables aleatoiresC1,C2,...,Cn

P(CÈt)AEnY

iAE1P(CiÈt)AEnY iAE1e¡¸itAEe¡tPn iAE1¸i.Exercice I(Illustration de la propriete (iii) de la proposition 1.2). 1. Rappeler la fonction de densite d'une loi exponentielle de parametre ¸AE2et tracer sa courbe a l'aide deR. On pourra utiliser les fonctions plotetdexp. 2. Simuler unn-echantillon d'une loi exponentielle de parametre¹È0 avecnAE500et¹AE1. On pourra utiliser la fonctionrexp. 3. Simuler unn-echantillon du minimum de deux lois exponentielles independantes de parametres¹1AE¹2AE1avecnAE500. On pourra utiliser la fonctionpmin. 4. Tracer l'histogramme d'unn-echantillon du minimum de deux exponen- tielles independantes de parametre¹1AE¹2AE1, avecnAE500. On pourra utiliser la fonctionhist. 3

5.Tracer sur le m^eme graphique la fonction de densite d'une loi expo-

nentielle de parametre¸AE2et l'histogramme d'unn-echantillon du minimum de deux exponentielles independantes de parametre¹1AE¹2AE1 avecnAE500. On pourra utiliser l'optionbreaksdans la fonctionhist pour aner l'histogramme. 6.

R eprendrel aq uestion4. a vecnAE1000.

7. ^Etes-vous convaincu quant a la propriete (iii) de la proposition 1.2? Plut^ot que d'utiliser un histogramme pour representer unn-echantillon et se demander si il correspond a la \bonne" loi de densite, nous allons utiliser un autre outil : la fonction de repartition empirique.

Denition.

SoitXune variable aleatoire reelle. La fonction de repartitionF deXest donnee par

F(x)AEP(X6x).

Denition.

En statistique, la fonction de repartition empiriqueFn(¢)d'un n-echantillonX1,...,Xnest une fonction aleatoire en escalier denie par F n(x)AEnombre d'elements6xdans l'echantillonn AE1n n X iAE11{Xi6x}.

Theoreme

(Theoreme de Glivenko-Cantelli).SoitX1,...,Xnunn-echantillon ou chaqueXia pour fonction de repartitionF. Alors presque s^urement, la fonction de repartition empiriqueFn(¢)converge uniformement versFquandn tend vers l'inni.

Exercice II

(Une meilleure illustration de la propriete (iii) de la proposi- tion 1.2). 1. On suppose queX1AE2,X2AE1,X3AE2.5etX4AE3.5. Tracer a la main puis a l'aide deRla fonction de repartition empirique de cet echantillon. On pourra utiliser la fonctionecdf. Dans un souci esthetique, on utilisera les optionsverticals=TRUEetdo.points=FALSE. 2. Donner la fonction de repartition d'une loi exponentielle de parametre

¸AE2et tracer sa courbe a l'aide deR.

3. Tracer sur le m^eme graphique la fonction de repartition d'une loi exponentielle de parametre¸AE2et la fonction de repartition empirique d'unn-echantillon du minimum de deux exponentielles independantes de parametre¹1AE¹2AE1avecnAE500. 4.

R eprendrel aq uestion3. a vecnAE1000.

5. ^Etes-vous convaincu quant a la propriete (iii) de la proposition 1.2? 4

1.2 Processus de Poisson : denition et propriete principaleParmi les processus stochastiques a temps continu, le processus de Poisson

occupe une place privilegiee. Il est utilise pour decrire la realisation dans le temps d'evenements aleatoires d'un type donne. Classiquement, on retrouve l'arrivee de clients a un guichet, l'arrivee de demandes de t^aches sur une im- primante, l'occurrence d'accidents dans une entreprise, etc. Schematiquement, ceci revient a modeliser les temps de sonnerie d'une horloge aleatoire.

Denition 1.3

(Processus de comptage).La description mathematique d'un ux d'evenements aleatoires peut se faire de deux manieres dierentes. 1. O nc onsiderel enom bred' evenementsN(t)se produisant dans l'inter- valle de temps[0,t]et on cherche a determiner la distribution de cette variable aleatoire discrete. Le processus stochastique{N(t) :t>0}est appeleprocessus de comptage, ses realisations sont des fonctions en escalier croissantes (gure 1). Notons queN(uÅt)¡N(u)indique le nombre aleatoire d'evenements se produisant dans l'intervalle]u,tÅu].

2.On considere les intervalles de temps qui separent les instants d'appa-

rition de deux evenements consecutifs. Ce sont des variables aleatoires continues et positives dont on admettra generalement qu'elles sont independantes et identiquement distribuees. La connaissance de leur distribution commune permettra alors de determiner les proprietes du processus de comptage correspondant. Soit{N(t) :t>0}un processus de comptage et designons parCnla duree separant le(n¡1)-ieme evenement dun-ieme pourn>1. La variable aleatoire Cn, appeletemps d'attente, represente le temps pendant lequel le processus demeure dans l'etatn¡1. Posons ensuite T nAEC1ÅC2Å¢¢¢ÅCn, qui est le temps ecoule jusqu'a la realisation dun-ieme evenement. On verie aisement que

Denition 1.4

(Processus de Poisson).On dit qu'un processus de comptage {N(t) :t>0}est unprocessus de Poissons'il satisfait aux quatre conditions suivantes. (H1) Le processusN(t)est homogene dans le temps. Ceci veut dire que la probabilite d'avoirkevenements dans un intervalle de longueur donnee 5

N(t)012345

tT 1T 2T 3T 4T 5C 1C 2C 3C 4C

5Figure1 { Realisation d'un processus de comptage

tne depend que detet non pas de la position de l'intervalle par rapport a l'axe temporel. En d'autres termes pour toussÈ0,tÈ0etkAE0,1,.... (H2) Le processusN(t)est a accroissements independants, ce qui signie que pour tout systeme d'intervalles disjoints, les nombres d'evenements s'y produisant sont des variables aleatoires independantes. En particulier, (H3) La probabilite qu'un evenement se produise dans un petit intervalle de temps est proportionnelle a la longueur de cet intervalle, le coecient de proportionnalite etant¸. Autrement dit, p

1(s)AE¸sÅs"(s),ou"(s)!0quands!0.

Le coecient¸est appeleintensitedu processus poissonien. (H4) La probabilite que deux evenements ou plus se produisent dans un petit intervallesest negligeable par rapport a la probabilite qu'il n'y ait qu'un seul evenement. En termes plus precis p k(s)AEs"(s),ou"(s)!0quands!0etk>2. Cette condition exclut la possibilite d'une realisation simultanee de deux evenements ou plus. 6 Theoreme 1.5.Si un processus de comptage satisfait aux conditions (H1)- (H4), alors

P(N(t)AEk)AEpk(t)AEe¡¸t(¸t)kk!,

E[N(t)]AE¸t, Var[N(t)]AE¸t.

La variable aleatoireN(t)suit une donc une loi de Poisson de parametre¸t.

La demonstration de ce resultat est admise.

1.3 Processus de Poisson et loi exponentielle

Soit{N(t) :t>0}un processus de Poisson de parametre¸etCnla duree separant le(n¡1)-ieme evenement dun-ieme.

Theoreme 1.6.

Les temps d'attente d'un processus de Poisson de parametre ¸sont des variables aleatoires independantes et identiquement distribuees selon une loi exponentielle de parametre¸.

Heuristique de la preuve.

Considerons d'abordC1, le temps d'attente du

premier evenement. Nous avons P(C1Èt)AEP(aucun evenement dans[0,t])AEP(N(t)AE0)AEe¡¸t. La variable aleatoireC1suit donc bien une loi exponentielle. Ensuite P(C2ÈtjC1AEs)AEP(aucun evenement dans]s,sÅt]jC1AEs) En utilisant la condition (H2), on peut supprimer le conditionnement et il vient P(C2ÈtjC1AEs)AEP(aucun evenement dans]s,sÅt])AEe¡¸t.quotesdbs_dbs18.pdfusesText_24

[PDF] Chaˆınes de Markov avancées

Cha^nes de Markov avancees

1 Processus de Poisson 2

1.1 Rappels sur la loi exponentielle . . . . . . . . . . . . . . . . . .

1.2 Processus de Poisson : denition et propriete principale . . .

1.3 Processus de Poisson et loi exponentielle . . . . . . . . . . . .

1.4 Proprietes supplementaires . . . . . . . . . . . . . . . . . . . . .

2 Modeles d'evolution de sequences biologiques 10

2.1 Modeles markoviens de substitution de nucleotides . . . . . .

2.2 Distance phylogenetique . . . . . . . . . . . . . . . . . . . . . .

2.3 Modeles Markoviens de substitution de codons . . . . . . . . .

A Correction des exercices 22

B Sujets d'examen 49

1 Processus de Poisson

1.1 Rappels sur la loi exponentielle

Denition 1.1

¸È0), noteeExp(¸)est la loi de densite

P(CÈt)AEe¡¸t,pour toutt>0.

¡¸uAEe¡¸t.

Montrons(ii). Nous avons

Montrons(iii). Nous avons par denition deC

P(CÈt)AEP(C1Èt,...CnÈt),

P(CÈt)AEnY

5.Tracer sur le m^eme graphique la fonction de densite d'une loi expo-

R eprendrel aq uestion4. a vecnAE1000.

Denition.

F(x)AEP(X6x).

Denition.

Theoreme

Exercice II

¸AE2et tracer sa courbe a l'aide deR.

R eprendrel aq uestion3. a vecnAE1000.

1.2 Processus de Poisson : denition et propriete principaleParmi les processus stochastiques a temps continu, le processus de Poisson

Denition 1.3

2.On considere les intervalles de temps qui separent les instants d'appa-

Denition 1.4

N(t)012345

5Figure1 { Realisation d'un processus de comptage

1(s)AE¸sÅs"(s),ou"(s)!0quands!0.

P(N(t)AEk)AEpk(t)AEe¡¸t(¸t)kk!,

E[N(t)]AE¸t, Var[N(t)]AE¸t.

La demonstration de ce resultat est admise.

1.3 Processus de Poisson et loi exponentielle

Theoreme 1.6.

Heuristique de la preuve.

Considerons d'abordC1, le temps d'attente du