Processus aleatoires et applications

Nils Berglund

Description

Niveau: Supérieur, Master
Processus aleatoires et applications Master 2 Pro de Mathematiques Universite d'Orleans Nils Berglund Version de Septembre 2011

• loi exponentielle


• application aux algorithmes mcmc


• chaınes de markov


• exemples de chaınes de markov


• generalites sur les processus stochastiques


• distributions stationnaires


• processus ponctuel de poisson


• construction par les temps d'attente

Sujets

• Berglund
• Loi exponentielle
• Chaîne de Markov

Informations

• Publié par: profil-mupheg-2012
• Publié le: 01 septembre 2011
• Nombre de lectures: 62
• Langue: Français

Extrait

Processus aleatoires
et applications
Master 2 Pro de Mathematiques
Universite d’Orleans
Nils Berglund
Version de Septembre 2011Table des matieres
I Cha^ nes de Markov 1
1 Cha^ nes de Markov sur un ensemble ni 3
1.1 Exemples de cha^ nes de Markov . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Cha^ nes de Markov absorbantes . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Cha^ nes de Markov irreductibles . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Cha^ nes de Markov reversibles . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Cha^ nes de Markov sur un ensemble denombrable 29
2.1 Marches aleatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Generalites sur les processus stochastiques . . . . . . . . . . . . . . . . . . . 33
2.3 Recurrence, transience et periode . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4 Distributions stationnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5 Convergence vers la distribution stationnaire . . . . . . . . . . . . . . . . . 45
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Application aux algorithmes MCMC 53
3.1 Methodes Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Algorithmes MCMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3 L’algorithme de Metropolis . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4 Le recuit simule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
II Processus de sauts et les d’attente 63
4 Rappels de probabilites 65
4.1 Loi binomiale et loi de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2 Loi normale et loi exponentielle . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5 Le processus ponctuel de Poisson 73
5.1 Construction par la fonction de comptage . . . . . . . . . . . . . . . . . . . 74
5.2 par les temps d’attente . . . . . . . . . . . . . . . . . . . . . . 76
5.3 Generalisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
-10 TABLE DES MATIERES
6 Processus markoviens de sauts 81
6.1 Taux de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2 Generateur et equations de Kolmogorov . . . . . . . . . . . . . . . . . . . . 84
6.3 Distributions stationnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7 Files d’attente 91
7.1 Classi cation et notation de Kendall . . . . . . . . . . . . . . . . . . . . . . 91
7.2 Cas markoviens : Files d’attente M/M/s . . . . . . . . . . . . . . . . . . . . 92
7.3 Cas general : Files d’attente G/G/1 . . . . . . . . . . . . . . . . . . . . . . 96
7.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99Partie I
Cha^ nes de Markov
1Chapitre 1
Cha^ nes de Markov sur un
ensemble ni
1.1 Exemples de cha^ nes de Markov
Les cha^ nes de Markov sont intuitivement tres simples a de nir. Un systeme peut admettre
un certain nombre d’etats di erents. L’etat change au cours du temps discret. A chaque
changement, le nouvel etat est choisi avec une distribution de probabilite xee au prealable,
et ne dependant que de l’etat present.
Exemple 1.1.1 (La souris dans le labyrinthe). Une souris se deplace dans le labyrinthe
de la gure 1.1. Initialement, elle se trouve dans la case 1. A chaque minute, elle change
de case en choisissant, de maniere equiprobable, l’une des cases adjacentes. Des qu’elle
atteint soit la nourriture (case 4), soit sa taniere (case 5), elle y reste.
On se pose alors les questions suivantes :
1. Avec quelle probabilite la souris atteint-elle la nourriture plut^ ot que sa taniere?
2. Au bout de combien de temps atteint-elle sa taniere ou la nourriture?
On peut essayer de repondre a ces questions en construisant un arbre decrivant les chemins
possibles. Par exemple, il est clair que la souris se retrouve dans sa taniere au bout d’une
minute avec probabilite 1=3. Sinon, elle passe soit dans la case 2, soit dans la case 3, et
depuis chacune de ces cases elle a une chance sur deux de trouver la nourriture. Il y a donc
une probabilite de 1=6 que la souris trouve la nourriture au bout de deux minutes. Dans
les autres cas, elle se retrouve dans la case de depart, ce qui permet d’etablir une formule
de recurrence pour les probabilites cherchees.
2 4
5 1 3
Figure 1.1. Le labyrinthe dans lequel vit la souris.
3^4 CHAPITRE 1. CHAINES DE MARKOV SUR UN ENSEMBLE FINI
1=2
1=2 1=2
PP PF B
1=2 1=2
1=2
AFP FF
1=2 1=2
Figure 1.2. Graphe associe au jeu de Pile ou Face. Chaque symbole de deux lettres
represente le resultat des deux derniers jets de piece. Anatole gagne si la piece tombe trois
fois de suite sur Face, Barnabe gagne si la piece tombe sur Pile-Face-Pile.
Cette maniere de faire est toutefois assez compliquee, et devient rapidement impos-
sible a mettre en oeuvre quand la taille du labyrinthe augmente. Dans la suite, nous
allons developper une methode plus e cace pour resoudre le probleme, basee sur une
representation matricielle.
Exemple 1.1.2 (Jeu de Pile ou Face). Anatole et Barnabe jouent a la variante suivante de
Pile ou Face. Ils jettent une piece de monnaie (parfaitement equilibree) de maniere repetee.
Anatole gagne des que la piece tombe trois fois de suite sur Face, alors que Barnabe gagne
des que la suite Pile-Face-Pile appara^ t.
On se pose les questions suivantes :
1. Avec quelle probabilite est-ce Anatole qui gagne le jeu?
2. Au bout de combien de jets de la piece l’un des deux joueurs gagne-t-il?
La situation est en fait assez semblable a celle de l’exemple precedent. Un peu de re exion
montre que si personne n’a gagne au bout den jets de la piece, la probabilite que l’un des
deux joueurs gagne au coup suivant ne depend que des deux derniers resultats. On peut
alors decrire le jeu par une cha^ ne de Markov sur l’ensemble
X =fPP; PF; FP; FF; A gagne; B gagneg; (1.1.1)
ou par exemple PP signi e que la piece est tombee sur Pile lors des deux derniers jets.
On determine alors les probabilites de transition entre les cinq etats, et on retrouve un
probleme semblable a celui de la souris.
Exemple 1.1.3 (Modele d’Ehrenfest). C’est un systeme motive par la physique, qui a ete
introduit pour modeliser de maniere simple la repartition d’un gaz entre deux recipients.
N boules, numerotees de 1 aN, sont reparties sur deux urnes. De maniere repetee, on tire
au hasard, de fa con equiprobable, un numero entre 1 et N, et on change d’urne la boule
correspondante.
On voudrait savoir comment ce systeme se comporte asymptotiquement en temps :
1. Est-ce que la loi du nombre de boules dans chaque urne approche une loi limite?
2. Quelle est cette loi?
3. Avec quelle frequence toutes les boules se trouvent-elles toutes dans la m^eme urne?^1.1. EXEMPLES DE CHAINES DE MARKOV 5
1 2=3 1=3
1=3 2=3 1
Figure 1.3. Le modele d’urnes d’Ehrenfest, dans le cas de 3 boules.
On peut a nouveau decrire le systeme par une cha^ ne de Markov, cette fois sur l’espace
des etatsX =f0; 1;:::;Ng, ou le numero de l’etat correspond au nombre de boules dans
l’urne de gauche, par exemple.
Exemple 1.1.4 (Texte aleatoires). Voici trois \textes" generes de maniere aleatoire :
A. YxUV,luUqHCLvE?,MRiKaoiWjyhg nEYKrMFD!rUFUy.qvW;e:F N.udbBdo!,
ZpGwTEOFcA;;RrSMvPjA’Xtn.vP?JNZA;xWP, Cm?;i’MzLqVsAnlqHyk,ghDT
:PwSwrnJojRhVjSe?dFkoVRN!MT FeemBXITdj m.h d’ea;Jkjx,XvHIBPfFT
s I’SLcSX;’X!S, ODjX.eMoLnQttneLnNE!qGRgCJ:BuYAauJXoOCCsQkLcyPO
MulKLRtSm;PNpFfp’PfgvIJNrUr t l aXtlA?;TPhPxU:,ZmVGr,,’DIjqZDBY
DrkPRiKDYRknDhivt;, LYXDuxNKpjegMvrtfz:JpNTDj’LFmHzXxotRM u.iya
UUrgZRcA QmCZ wsNWhddBUPAhJIFJvs.CkKFLJoXef;kCnXrv’uWNcpULYsnl
Kg OURmysAnxFjHawwsSpM H;PWPsMaFYLMFyvRWOjbdPlLQIaaspNZkuO’Ns.l
jEXO,lxQ’GS;n;H:DH:VWJN :t’JMTUVpKCkVZ’NyKJMGiIbQFXEgDEcWxMBiyo
ybRIWIAC deMJnnL;SBAZ?:.UuGnC:B.!lBUT,pT?tyHHLlCvN, mKZgwlMJOJd
HHobua;KU.;kADVM?jr’v.SCq:hZLR;lqkmLkhn:ajhBM,gKexDAro,HlczWTv
cFmNPt.MudUWPO, sTrWlJdgjoiJd.:d;CpJkJCW;FIRnpMGa;umFysOMAqQtmT
pPaYZKtOFYppeE.KFX?SuvcbaDrQ XECelD;cfoQKf?’jCTUaISS;fV:gqoWfSq
k:Tf!YuPBANtKhewiNg’ImOFs:UhcExmBjsAaMhBf UVP, ’dcFk;gxJMQGyXI;
nVwwfWxS:YXQMELEIObTJiilUYSlOsg.gCqlrN:nEU:irHM’nOLXWUbJLTU re’
kk vAwMgt’KgWSxwxqJe,z’OBCrnoIshSCDlZirla,rWNPkc?UgZm GOBX.QylY
jOtuF
B. nsunragetnetelpnlac. pieln tJmends d e.imnqu caa aneezsconns re.tc oml d e c, paeisfuaul
irt ssna l df.ieulat a ese t hre edn ro m eeel slsplotasstp etuoMeiiseeaenemzeaeuqpeer
enuoco sfehnnir p ts ’mpisu qrd iraLp nFetesa,opQeey rieeaduset MuuisecG il e m ru
daeiafasousfnircot i eeedracev ever.nsn iaeulu!,mtel lpa rdbjdide tolr’murunlr bteaaua
ieasilureseuavrmoce ntvqm qnurnaunsa.mraayVarinanr eumsu cnponf ciuo .pssre elreeY
snrrq aani psu oqoddaiaaomrssloe’avia,loei va eroltrsurdeduuoe usir ’th’niIt has,slluoooe
tee ?eoxaea slsii i u edtvsear e,Mesatnd o o rvdocaeagiua apugiqn rclt smtee.te, gceade