2_Processus stochastiques

8/6/2019 2_Processus stochastiques

http://slidepdf.com/reader/full/2processus-stochastiques 1/22

Processus stochastiques

Adapté de Yannis Korilis, Christian St-Jean, Dave DeBarr,

Bob Carpenter, Jennifer Chu-Carroll et plusieurs autres



Phénomène temporel où intervient le hasard

Caractérisé par ses réalisation successives

Les valeurs instantanées sont des variables aléatoires

Ex: Suite de lancers de dé 1,3,2,5,3,6,2,4

Signal radar

Écho de voix

Temps continu : X(t)

Temps discret : X(tn) ; X(n) ; Xn

réalisation

V.A.

Processus stochastique



Les signaux observés sont « rares » et ne dépendent que

du temps d¶attente et d¶un paramètre P :

Le nombre de signaux entre le temps t et le temps t+

T suit P(PT)

? A T

k

e!k

)t ( )k )t ( N )T t ( N ( P P

P

!!

Le temps d¶attente entre deux signaux suit une

loi exponentielle de paramètre P

? A T eT t P P!"

Le temps d¶attente entre « k » signaux suit une loi Gamma.

Processus de Poisson



Le nombre de pannes dun composant est de 3 par jour.

Probabilité qu¶il y ait aucune panne en 1 jour :

Probabilité qu¶il y ait moins de trois pannes en 3 jours:

049.0!0

3)0( 3

0

!!! e X P

0062.0!2

9

!1

9

!0

9)0( 9

29

19

0

!!! eee X P

Probabilité pour que le temps d¶attente de la première panne soit

supérieure à 24 heures : 049.0e ) j1T ( P 3!!"

Probabilité pour que le temps d¶attente de la première panne soit

supérieure à 72 heures : 00012.0e ) j3T ( 9!!"

Temps moyen d¶attente d¶une panne : 1/3 de journée

Nombre moyen de pannes par jour : 3 pannes

Exemple



Le nombre de clients entrant dans un magasin un jour donné suit une

loi de Poisson, X, de paramètre P = 12. Quelle est la probabilité de nepas tomber en-dessous de 250 entrées de clients durant un mois de

22 jours ouvrables ?

On a P8 = 12·22 = 264.

La probabilité recherchée est donc

P ( X u 250) = 1 - P ( X < 250) = 1 - exp(-264)·7i=0..249 264i/i! = 0.8133788672..

On peut acccéler les calculs en approchant la distribution de la variable de

Poisson X par celle d'une variable normale Y de moyenne Q = P8= 264 et devariance W2 = P8 = 264. Cela donne

P ( X u 250) = P ( X - Q u -14) $ P ((Y - Q)/W u 250/W) = P ( Z u -14/264½)

et Z est une variable normale standard. Donc

P ( X u 250) $ ½·[1 + erf (7·33½/66)] = 0.8055572942..

Exemple



Processus stochastique dont l¶évolution ne dépend que d¶un

nombre limité d¶états antérieurs

1er ordre : Si à l ¶instant ti, on a observé la réalisation oi de X(t) alors

)o )t ( o )t ( ( )o )t ( ,...,o )t ( o )t ( ( 1n1nnn111n1nnn ee!eee

L¶état courant du système suffit pour prédire son état futur.

2nd

ordre : L¶état courant du système et celui le précédant suffisent pour prédireson état futur.

Andrei Markov (1856-1922) : statisticien russe spécialisé dans les modèles

probabilistes temporels.

Processus de Markov





Exemple: X(t) : Temps qu¶il fait

7={µ neige ¶,µ pluie ¶, ¶soleil ¶}

A=

4 = {0.02 , 0.4, 0.58}

¹

¹¹

º

¸

©

©©

ª

¨

8.01.01.0

2.06.02.0

3.03.04.0

Il faut définir: L¶espace d¶états: alphabet 7={o1,...,om} des réalisations

possiblesde X(t)

La matrice de transition A={ai,j= P(o j|oi)}

Les probabilités de départ 4={Ti=P(oi)}

Représentation Graphique

Neige Pluie

Soleil

0.4

0.1 0.1

0.2

0.6

0.3

0.8

0.3

0.2

0.02

0.40.58

§ §! !

!!m

j

ii ja

1

m

1i

1 1 T

Représentation d¶une chaîne de Markov



Représentation Graphique

Neige Pluie

Soleil

0.4

0.1 0.1

0.2

0.6

0.3

0.8

0.3

0.2

0.02

0.40.58

)o( P )oo( P ... )oo( P )oo( P

... )o ,...,o( P )o ,...,oo( P )oo( P

)o ,...,o( P )o ,...,oo( P )o ,...,o ,o( P

1122n1n1nn

12n12n1n1nn

11n11nn11nn

vvvv!

vv!

v!

�!

v!n

2t 1t t 1 )oo( P )o( P

Application:

Quelle est la probabilité qu¶il fasse µ Soleil ¶,

5 jours de suite ? P(Soleil, Soleil, Soleil, Soleil, Soleil )=

0.58*0.8*0.8*0.8*0.8 =0.2375

P(Neige, Neige, Pluie, Pluie, Soleil )=

0.02*0.4*0.3*0.6*0.2=0,000288

Th. Bayes

Probabilité d¶une séquence d¶états



� Probabilité de transition en n sauts

Note : est l¶élément (i, j) de la matrice P n

� Équations de Chapman-Kolmogorov

{ }, , 0, , 0ni j n m m P P X j X i n m i j

! ! ! u u

ni j P

0

, , 0, , 0n m n m

i j ik kj

k

P P P n m i jg

!

! u u§

Quelle est la probabilité qu¶il fasse µ Soleil¶ dans 2 jours sachant qu¶il

neige au jourd¶hui ?

2))1()3((

42.03.0*8.03.0*2.04.0*3.0

)()()()()()(

))1()3((

S

P N X S X P ou

N S P S S P N P P P S P N N P N S P

N X S X P

!!!

!!

vvv

!!!

N SP

N

S

0.4

0.3

0.3 0.8

0.2

0.3

Et sil y a plusieurs chemins ?



Quelle est la probabilité qu ¶il fasse µ Soleil ¶ dans 3 jours ?

0.5446 0.58 )*0.80.4*0.20.02*(0.3*0.80.58 )*.100.4*0.6

...0.02*(0.3*0.20.58 )*0.10.4*0.20.02*(0.4*0.3 )S )3( X ( P

)S )2( X ( P )S S ( P

) P )2( X ( P ) P S ( P ) N )2( X ( P ) N S ( P )S )3( X ( P

!

!!

!v

!v!v!!

.

.

? A§!

!v!!!!

m

1i1t 1t t t )i X ( P )i X j X ( P ) j X ( P

Système d événements complet :

Prévision suivant un système

d¶évènements complet



Un programme informatique est composé de 5 sous programmes

indépendants, sp1, .., sp5, et un sous-programme de sortie sp6.

De sp1 on peut aller à sp2 avec une proba de ½

on peut boucler avec une proba de ½

De sp2 on peut aller à sp1 avec une proba de ½on peut aller à sp4 avec une proba de ½

De sp3 on peut aller à sp1 avec une proba de ¼

on peut aller à sp2 avec une proba de ¼

on peut aller à sp5 avec une proba de ¼

on peut aller à sp6 avec une proba de ¼De sp4 on va à sp3

Quand on arrive à sp5, on boucle

Quand on arrive à sp6, on boucle

1 2

3 4

5

6

0.50

0.50

0.50

1.000.25

0.25

0.25

0.25

Exemple



Partant de sp2, quelle probabilité d¶y être à nouveau au

temps « 4 » ?

Première solution : graphique

Il existe 3 chemins pour aller de 2 à 2 en quatre temps :

24312 avec une proba : 0.50x1x0.25x0.50=1/16

21212 avec une proba : 0.50x0.50x0.50x0.50=1/16

21112 avc une proba : 0.50x0.50x0.50x0.50=1/16

Soit une proba de 3/16=0.1871 2

3 4

5

6

0.50

0.50

0.50

1.000.25

0.25

0.25

0.25



Si on pose les probabilités pij sous forme de matrice P,

on anik

n pi X k X P !!! )/( 0

Deuxième résolution : par matrice

0,50 0,5 0 0 0 0

0,5 0 0 0,5 0 0

0,25 0,25 0 0 0,25 0,25

0 0 1 0 0 0

0 0 0 0 1 0

0 0 0 0 0 1

Matriceinitiale P

P4

0,375 0,25 0,125 0,125 0,0625 0,0625

0,3125 0,1875 0,125 0,125 0,125 0,125

0,1875 0,125 0,0625 0,0625 0,28125 0,28125

0,1875 0,125 0,125 0,0625 0,25 0,25

0 0 0 0 1 0

0 0 0 0 0 1

1 2

3 4

5

6

0.50

0.500.50

1.000.25

0.25

0.25

0.25



� Probabilités des états (dépendant du temps)

� Sous forme matricielle:

� Si T n tend vers une distribution stationnaire T , on a :

� et(En partant de )

L¶existence de T dépend de la structure de la chaîne

n n

n n n n j i ij

i i

P X j P X i P X j X i P g g

! !

! ! ! ! ! !§ §

0 1 { }, ( , ,...)n n n n

j n P X j! ! !

1 2 2 0 ... n n n n P P P

! ! ! !

lim n

np ¡

P !1 2 2 0

...n n n

P P

Distribution limite des états



Apériodique :

� Une chaîne est apériodique si

aucun état n¶est périodique

� Un état i est périodique si :

� La distribution stationnaire existe et est indépendante de

l¶état initial si la chaîne est irréductible et apériodique

Irréductible :

� Les états i et j communiquent si :

� La chaîne est irréductible si tous les

états communiquent

, : 0, 0n m

i j jin m P P " "

1: 0n

iid P n d E" " !

0

3 4

21

0

3 4

21



Détermination de la distribution stationnaire

A. Nombre d¶états fini

Deux possibilités :

� Résoudre le système d¶équations :

� Dériver T de , sachant que

et donc que P n converge vers une

matrice dont les lignes valent T

Valable pour un petit nombre

d¶états

B. Nombre d¶états infini

� Méthodes précédentes non applicables

� On doit deviner la solution, ou la

trouver par itération:, , ,...,m

j i ij

i

m

i

i

j m!

!

! !

!

§

§0

0

, 0,1,...,

1

j i ij

i

i

i

P jg

!g

!

! !

!

§

§n

n

P limgp

_ a n

ij0n j P i X | j X P !!!!T



� Modèle markovien ± i est le nombre de parapluies

disponibles à l¶endroit présent

± Matrice des probabilités detransitions entre états

� Un professeur distrait

possède deux parapluies.

S¶il pleut et l¶un d¶eux est

disponible, elle le prend;

sinon, elle sort sans parapluie.

Si p est la probabilité qu¶il pleuve à chaque fois qu¶elle

se déplace, quelle est la probabilité qu¶elle prenneune douche involontaire àchaque fois ?

0 2 1 1 p

p1 p

1 p

0 0 10 1

1 0

P p p

p p

« »¬ ¼!

¬ ¼¬ ¼½

Exemple

0

1{gets wet}

3

p P p p

p

! !

Se mouiller



Ex.: chaîne Markov avec un nombre fini d¶états

0 2 1 1 p

p1 p

1 p0 0

0

0

p p

p p

« »¬ ¼! ¬ ¼¬ ¼½

2 0

0 2

1 1 2

0 1 2

1 2

1

0

(1 )

(1 ) 1 1 1 , ,

1 3 3 3

1

i i

p

P p p p

p p p p

! ®±! ! ® ±� � ! ! !¯ ¯! ° ±± !

!

°

§

0{gets wet}

3

p P p p

p

! !

Se mouiller



Ex.: chaîne Markov avec un nombre fini d¶états

� Si on prend p = 0.1:

� On peut aussi calculer T en évaluant numériquement

± L¶efficacité du calcul dépend de la structure de P

0 0 1

0 0 9 0 1

0 9 0 1 0

P

« »¬ ¼¬ ¼¬ ¼½

1 1 1 , , 0.310, 0.345, 0.345

3 3 3

p

p p p

¨ ¸© ¹ª º

0.3 0 0.345 0.345

lim 0.3 0 0.345 0.345 ( 50)

0.3 0 0.345 0.345

n

n

P npg

« »¬ ¼ }¬ ¼¬ ¼½

0

1{gets wet}

3

p P p p

p

! !

Se mouiller

n

n

P limgp



À l¶équilibre, on a :

T=[1/4 1/2 1/4]

Ainsi, si on part de trois états différents :

]1,0,0[]0,1,0[]0,0,1[ 000 !!! cba T T T

On obtient par simulation :

? A ? A ? A6.04.00.02.06.02.00.04.06.01T

? A

? A

? A25.050.025.0

25.050.025.0

25.050.025.020T

1 2 3

0.60.4 0.6

0.6

0.4 0.4

0.4

0,6 0,4 0

0,2 0,6 0,2

0 0,4 0,6

Exemple montrant lindépendance de T des

états initiaux



� Chaînes de Markov généralisées (ou Semi-Markov) :

± Le prochain état dépend de l¶état présent, plus la durée de temps passée

dans ce dernier.

� Chaînes de Markov à temps continu :

± Cas spécial des processus semi-markoviens.

� Champs de Markov

± Modèle de Markov s¶appliquant à une distribution spatiale de variablesaléatoires

� Chaînes de Markov cachées :

± Elles sont accessibles uniquement à travers des observations indirectes

Autres processus markoviens

Documents

2_Processus stochastiques