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