Processus stochastiques Adapté de Yannis Korilis, Christian St-Jean, Dave DeBarr, Bob Carpenter,...

Processus stochastiques

Adapté de Yannis Korilis, Christian St-Jean, Dave DeBarr, Bob Carpenter, Jennifer Chu-Carroll et plusieurs autres

Phénomène chronologique où intervient le hasard Caractérisé par ses différentes réalisations Les valeurs instantanées sont des variables aléatoires

Ex: Suite de lancers de dé (par ex., 1,3,2,5,3,6,2,4…

Signal radar,

Écho de voix

Notation : Temps continu : X(t ) Temps discret : X(tn) ; X(nTe) ; X(n) ; Xn

réalisation

V.A.

Processus stochastique

Les signaux observés sont « rares » et leur survenue dépend du temps d’attente T et d’un paramètre Le nombre de signaux durant T est:

Tk

ek

TktNTtNP

!

)())()((

Le délai entre deux signaux suit une loi exp. de paramètre

TeTtP

Le temps d’attente entre « k » signaux suit une loi Processus de renouvellement typique (c.à.d sans mémoire)

Processus de Poisson

Dans un ensemble de documents analysés, le nombre moyen de motifs remarquables est 3 par document : Temps moyen d’attente : 1/3 de document Nombre moyen de motifs par document : 3

• Probabilité qu’il n’y ait aucun motif recherché dans 1 document :

• Probabilité qu’il y ait moins de 3 motifs recherchés dans 3 documents : 049.0

!03

)0( 30

eXP

0062.0!2

9

!1

9

!0

9)3( 9

29

19

0

eeeXP

• Probabilité de fouiller plus d’un document avant de trouver un motif recherché : 049.0)1( 3 eTP

• Probabilité de fouiller plus de 3 documents avant de trouver un motif recherché : 00012.0)3( 9 eTP

Exemple

Le nombre quotidien de personnes qui visitent une bibliothèque suit une loi de Poisson de paramètre = 12. Quelle est la probabilité que plus de 250 personnes viennent durant 22 jours ouvrables ?

• On a = 12·22 = 264.• La probabilité recherchée est donc

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

• On peut accélérer les calculs en faisant l’approximation de la distribution de Poisson par une gaussienne de moyenne = et de variance 2, valant toues les deux = 264. Cela donne :

P(X 250) = P(X - -14) P((Y - )/ 250/) = P(Z -14/264½) où Z est une variable normale standard. Donc

P(X 250) ½·[1 + erf(7·33½/66)] = 0.806

Exemple

L’évolution du processus dépend de son comportement passé (processus à mémoire)

• 1er ordre : Si on observe on à l ’instant tn, alors

))()(())(,...,)()(( 111111 nnnnnnnn otXotXPotXotXotXP

L’état courant du système suffit pour prédire son prochain état

• 2nd ordre : L’état courant du système et celui le précédant suffisent pour prédire le prochain état.

Andrei Markov (1856-1922) : statisticien russe spécialisé en modèles probabilistes temporels.

Processus de Markov

0

0, 1ij ijj

P P

Exemple: Alphabet : = {‘A’,’C’,’G’,’T’}

Séquence : {Xn} = ACGCCTAGGCTAGCTTATCG

}|{},...,,|{ 100111 iXjXPiXiXiXjXP nnnnnn

ijn1n P}iX|jX{P

1,0m

0iii

Chaîne de Markov

Il faut définir: L’espace des observations ={o1,...,om} Alphabet définissant la valeur possible de chaque état observé de X(t)

La matrice des probabilités de transitions A={ai,j} ai,j = P(oj|oi) : probabilité d’observer oj pour un état après avoir

observé oi pour l’état précédent Le vecteur des probabilités initiales ={i} i=P(oi) : Probabilité d’observer oi à l’état initialExemple: X(t) : Temps qu’il fait sur 3 jours

={‘ neige ’,‘ pluie ’, ’soleil ’}

A=

= {0.02 , 0.4, 0.58}

8.01.01.0

2.06.02.0

3.03.04.0

Représentation Graphique

Neige Pluie

Soleil

0.4

0.1 0.1

0.2

0.6

0.3

0.8

0.3

0.20.02

0.40.58

m

jiija

1

m

1i

1 1

Représentation d’une chaîne de Markov

Probabilité d’une séquence d’états

Représentation Graphique

Neige Pluie

Soleil

0.4

0.1 0.1

0.2

0.6

0.3

0.8

0.3

0.20.02

0.40.58

)()(...)()(

),...,(),...,()(

),...,(),...,(),...,,(

112211

121211

111111

oPooPooPooP

ooPoooPooP

ooPoooPoooP

nnnn

nnnnn

nnnnn

n

2t1tt1 )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

Propriété de Markov

Probabilité de faire une transition en n sauts

Note : est l’élément (i, j) de la matrice Pn ;

Les équations de Chapman-Kolmogorov pemettent des « stopover »

{ | }, , 0, , 0nij n m mP P X j X i n m i j

nijP

0

, , 0, , 0n m n mij ik kj

k

P P P n m i j

• Quelle est la probabilité qu’il fasse ‘ Soleil’ dans 2 jours sachant qu’il neige aujourd’hui ?

NSNXSXPou

NSPSSPNPPPSPNNPNSP

NXSXP

213

13

)(

42.03.0*8.03.0*2.04.0*3.0

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

)(

P

N SP

N

S

0.4

0.3

0.3 0.8

0.2

0.3

Et s’il y a plusieurs chemins ?

ijnnijP P

• Quelle est la probabilité qu’il fasse ‘ Soleil ’ dans 3 jours ?

0.54460.58)*0.80.4*0.20.02*(0.3*0.8

0.58)*.100.4*0.60.02*(0.3*0.2

0.58)*0.10.4*0.20.02*(0.4*0.3))3((

))2(()(

))2(()())2(()())3((

SXP

SXPSSP

PXPPSPNXPNSPSXP

m

1i1t1ttt )iX(P)iXjX(P)jX(P

On y suit tous les chemins possibles sans se soucier de l’etat de départ :

système d’évènements complet

N SP

N

S

0.4

0.3

0.3 0.8

0.2

0.3

• Un programme informatique comprend 5 modules indépendants, sp1, .., sp5, et un module de sortie sp6

De sp1 on peut :aller à sp2 avec probabilité de ½boucler avec probabilité de ½

De sp2 on peut :aller à sp1 avec probabilité de ½aller à sp4 avec probabilité de ½

De sp3 on peut :aller à sp1 avec probabilité de ¼aller à sp2 avec probabilité de ¼aller à sp5 avec probabilité de ¼à sp6 avec probabilité de ¼

De sp4 on va à sp3De sp5, on boucle De sp6, on boucle

1 2

3 4

5

6

0.50

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

1.000.25

0.25

0.25

0.25

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

2204 )2/2( pXXP

Deuxième résolution : par matrice

0,50 0,5 0 0 0 00,5 0 0 0,5 0 0

0,25 0,25 0 0 0,25 0,250 0 1 0 0 00 0 0 0 1 00 0 0 0 0 1

Matrice initiale P

P4

0,375 0,25 0,125 0,125 0,0625 0,06250,3125 0,1875 0,125 0,125 0,125 0,1250,1875 0,125 0,0625 0,0625 0,28125 0,281250,1875 0,125 0,125 0,0625 0,25 0,25

0 0 0 0 1 00 0 0 0 0 1

1 2

3 4

5

6

0.50

0.500.50

1.000.25

0.25

0.250.25

Probabilités des états en fonction du temps:

• Sous forme matricielle:

Si n tend vers une valeur stationnaire , on a :

• et(En partant de )

L’existence de dépend de la structure de la chaîne

11 1

0 0

{ } { } { | } π πn nn n n n j i ij

i i

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

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

j nP X j

1 2 2 0π π π ... πn n n nP P P

π lim πn

n

π πP

Distribution limite des états

nπ

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 :• Deux états i et j communiquent si :

• La chaîne est irréductible si tous les états communiquent

, : 0, 0n mij jin m P P

1: 0niid P n d

0

3 4

21

0

3 4

21

Détermination de la distribution stationnaire

A. Nombre d’états finiDeux possibilités :• Résoudre le système d’équations :

• Dériver de , sachant que

et donc que Pn converge vers une matrice dont les lignes valent 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:

0

0

π π , 0,1,...,

π 1

m

j i iji

m

ii

P j m

0

0

π π , 0,1,...,

π 1

j i iji

ii

P j

n

nPlim

nij0nj PiX|jXP

La mMatrice des probabilités de transitions entre états

Une professeure 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 prenne une douche involontaire alors?

i=0 2 1 1 p

p1 p

1 p

0 0 1

0 1

1 0

P p p

p p

Exemple

0

1{gets wet} π

3

pP p p

p

Se mouiller

• Modèle markovien Avec i le nombre de parapluies

disponibles à l’endroit présent, on obtient le diagramme de transition

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

0 2 1 1 p

p1 p

1 p0 0 1

0 1

1 0

P p p

p p

2 0

0 2

1 1 20 1 2

1 2

1

0

π π π

π (1 )π

π π π (1 )π π 1 1 1π , π , π

π 1 3 3 3

π π π 1i i

p

P p p p

pp p p

0

1{gets wet} π

3

pP 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 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.310 0.345 0.345

lim 0.310 0.345 0.345 ( 150)

0.310 0.345 0.345

n

nP n

0

1{gets wet} π

3

pP p p

p

Se mouiller

n

nPlim

À l’équilibre, on a : =[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

On obtient par simulation :

6.04.00.02.06.02.00.04.06.0π1

25.050.025.0

25.050.025.0

25.050.025.0π20

1 2 3

0.60.4 0.6

0.6

0.4 0.4

0.4

0,6 0,4 00,2 0,6 0,2

0 0,4 0,6

Exemple montrant l’indépendance de 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 variables aléatoires

Chaînes de Markov cachées : Elles sont accessibles uniquement à travers des observations

indirectes

Autres processus markoviens