Processus stochastiques

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

Bob Carpenter, Jennifer Chu-Carroll et plusieurs autres
 Processus stochastique
 Processus séquentiel dont chaque valeur est une variable
aléatoire.
 Caractérisé par ses différentes réalisations
Ex: Suite de lancers de dé (par ex., 1,3,2,5,3,6,2,4…
Signal radar,
réalisation
Écho de voix

V.A.

 Notation pour les processus chronologiques :

 Temps continu : x(t )
 Temps discret : X(tn) ; X(nTe) ; X(n) ; Xn
 Processus de Poisson
 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:
( T ) k
P( N (t  T )  N (t )  k )  e  T
k!
 Le délai entre deux signaux suit une loi exp. de paramètre 
Pt T  e  T
 Le temps d’attente entre « k » signaux suit une loi 
 Processus de renouvellement typique (c.à.d sans mémoire)
Exemple
 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 :

30 3
P(X 0) e 0.049
0!
• Probabilité qu’il y ait moins de 3 motifs recherchés dans 3 documents :
90 9
91 9
92
P ( X  3)  e  e  e 9  0.0062
0! 1! 2!
• Probabilité de fouiller plus d’un document avant de trouver un
3
motif recherché : P(T  1)  e  0.049
• Probabilité de fouiller plus de 3 documents avant de trouver un
motif recherché : P(T  3)  e  0.00012
9
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
 Processus de Markov
 L’évolution du processus dépend de son comportement
passé (processus à mémoire)
• 1er ordre : Si on observe on à l ’instant tn, alors
P( X (tn )  on X (tn1 )  on1 ,..., X (t1 )  o1 )  P( X (tn )  on X (tn1 )  on1 )
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.

Chaîne de Markov

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

Séquence : {Xn} = ACGCCTAGGCTAGCTTATCG

P{ X n1  j | X n  i, X n1  in1 , ..., X 0  i0 }  P{ X n1  j | X n  i }

P{ X n 1  j | X n  i }  Pij

Pij  0, P
j 0
ij 1

m
 i 0 ,  1
i 0
i
Représentation d’une chaîne de Markov
 Il faut définir:
 L’espace des observations ={o1,...,om}, où oi est un élément d’un
alphabet définissant la valeur possible de chaque état observé de X(t)
 La matrice des probabilités de transitions A={ai,j}, où ai,j = P(oj|oi)
est la probabilité d’observer oj après avoir observé oi à l’état précédent
 Le vecteur des probabilités initiales ={i}, où i=P(oi) est la
probabilité d’observer oi à l’état initial
Exemple: X(t) : Temps qu’il fait sur 3 jours Représentation Graphique
={‘ neige ’,‘ pluie ’, ’soleil ’} 0.4 0.6
 0.4 0.3 0.3  0.2
  Neige Pluie
 0.2 0.6 0.2  0.3
A=  0.1 0.1 0.8 
  0.3 0.1 0.2 0.1
0.02
= {0.02 , 0.4, 0.58} Soleil
0.58 0.4
m m 0.8
 aij  1
j 1
 i  1
i 1
 Probabilité d’une séquence d’états
Th. Bayes
P(on , on 1 ,..., o1 )  P(on on 1 ,..., o1 )  P(on 1 ,..., o1 )
 P(on on 1 )  P(on 1 on 2 ,..., o1 )  P(on  2 ,..., o1 )
Propriété de
 P(on on 1 )  P(on 1 on 2 )  ... P(o2 o1 ) P(o1 )
Markov
n
 P( o1 )   P( ot ot 1 )
t 2 Représentation Graphique
Application:
Quelle est la probabilité qu’il fasse ‘ Soleil ’, 0.4 0.6
5 jours de suite ? 0.2
Neige 0.3
Pluie
P(Soleil, Soleil, Soleil, Soleil, Soleil)=
0.58*0.8*0.8*0.8*0.8 =0.2375 0.3 0.1 0.2 0.1
0.02
Soleil
P(Neige, Neige, Pluie, Pluie, Soleil)= 0.58 0.4
0.02*0.4*0.3*0.6*0.2=0,000288 0.8
Et s’il y a plusieurs chemins ?
 Probabilité de faire une transition en n sauts
Pijn  P{ X n  m  j | X m  i}, n, m  0, i, j  0
P n
Noteij: P
est l’élément (i, j) de la matrice P ;
n
ij  P
n
n
  ij

 Les équations de Chapman-Kolmogorov permettent des « pauses »


P n m
ij   Pikn Pkjm , n, m  0, i, j  0
k 0

• Quelle est la probabilité qu’il fasse ‘ Soleil’ dans 2 jours sachant qu’il neige
aujourd’hui ?
P( X 3  S X 1  N ) 
0.4 N 0.3
P( S N )  P( N N )  P( S P)  P( P N )  P( S S )  P( S N )
0.3 0.2
N P S
 0.3 * 0.4  0.2 * 0.3  0.8 * 0.3  0.42
0.3
S 0.8 ou  
P( X 3  S X 1  N )  P 2 NS
système d’évènements complet
 On s’intéresse uniquement au résultat, en suivant
les chemins possibles sans se soucier de l’état de
départ : m
P( X t  j )   P( X t  j X t 1  i )  P( X t 1  i )
i 1

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

P( X (3)  S )  P( S N )  P( X (2)  N )  P( S P)  P( X (2)  P)  
P( S S )  P( X (2)  S ) 0.4 N 0.3
0.3
 N P 0.2 S

P( X (3)  S )  0.3 * (0.4 * 0.02  0.2 * 0.4  0.1* 0.58) 0.3

S 0.8

0.2 * (0.3 * 0.02  0.6 * 0.4  0.1* 0.58)

0.8 * (0.3 * 0.02  0.2 * 0.4  0.8 * 0.58)  0.5446
Exemple
• 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 ½ 0.50

aller à sp4 avec probabilité de ½ 1 2

0.50
De sp3 on peut : 0.50
0.25
aller à sp1 avec probabilité de ¼ 0.25
aller à sp2 avec probabilité de ¼ 6 3 4
aller à sp5 avec probabilité de ¼ 0.25 1.00
à sp6 avec probabilité de ¼
0.25
De sp4 on va à sp3
5
De sp5, on boucle
De sp6, on boucle
• 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 :
24312 avec une proba : 0.50x1x0.25x0.50=1/16
21212 avec une proba : 0.50x0.50x0.50x0.50=1/16
21112 avc une proba : 0.50x0.50x0.50x0.50=1/16
0.50
Soit une proba de 3/16=0.187
1 2
0.50
0.50
0.25
0.25

6 3 4

0.25 1.00

0.25

5
 Deuxième résolution : par matrice

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

on a P ( X 4  2 / X 0  2)  p22 4

0.50

0,50 0,5 0 0 0 0 1 2
Matrice 0,5 0 0 0,5 0 0
0.25
0.50
0.50
0,25 0,25 0 0 0,25 0,25
initiale P 0 0 1 0 0 0
0.25
4
6 3
0 0 0 0 1 0
0 0 0 0 0 1 0.25 1.00

0.25

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

0,3125 0,1875 0,125 0,125 0,125 0,125
P4 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
Distribution limite des états
 Probabilités des états en fonction du temps:
π nj  P{ X n  j}, π n  (π 0n , π1n ,...)
 
P{ X n  j}   P{ X n 1  i}P{ X n  j | X n 1  i}  π   π in 1Pij
n
j
i 0 i 0

• Sous forme matricielle:

π n  π n 1P  π n 2 P 2  ...  π 0 P n
 Si  n tend vers une valeur stationnaire  , on a :
π  lim π n
n
• et
π  πP (En partant de )
L’existence de  dépend de la structure de la chaîne
 La distribution stationnaire existe et est indépendante de
l’état initial si la chaîne est irréductible et apériodique
Irréductible : Apériodique :
• Deux états i et j communiquent si : • Une chaîne est apériodique si

n, m : Pijn  0, Pjim  0 aucun état n’est périodique

• Un état i est périodique si :
• La chaîne est irréductible si tous les
états communiquent  d  1: Piin  0  n   d

1 2
1 2

0
0
3 4
3 4
 Détermination de la distribution stationnaire

A. Nombre d’états fini B. Nombre d’états infini

Deux possibilités :
• Résoudre le système d’équations : • Méthodes précédentes non
m
π j   πi Pij , j  0,1,..., m applicables
i 0 • On doit deviner la solution, ou la
m
trouver par itération:
π i 1 
i 0
n
π j   πi Pij , j  0,1,...,
• Dériver  de lim P, sachant que i 0
n 
 j  PX n  j|X 0 i P n
ij π
i 0
i 1
et donc que Pn converge vers une
matrice dont les lignes valent 
Valable pour un petit nombre
d’états
Exemple • Modèle markovien
 Avec i le nombre de parapluies
 Une professeure possède disponibles à l’endroit présent, on
deux parapluies. S’il pleut obtient le diagramme de transition
et l’un d’eux est disponible, 1 p
elle le prend; sinon, elle
i=0 2 1 1 p
sort sans parapluie.
Si p est la probabilité qu’il 1 p p

pleuve à chaque fois  La mMatrice des probabilités de

transitions entre états
qu’elle se déplace, quelle
est la probabilité qu’elle  0 0 1
prenne une douche P 0 1 p p
 
involontaire alors? 1  p p 0 

1 p
P{gets wet}  π 0 p  p
Se mouiller
3 p
Ex.: chaîne Markov avec un nombre fini d’états

1 p
 0 0 1
0 2 1 1 p P 0 1 p p
 
1  p p 0 
1 p p

 π 0  (1  p )π 2
 π  πP  π  (1  p )π  pπ
 1 1 2 1 p 1 1
    π  , π  , π 

 i π i  1  2π  π 0  p π 1
0
3  p
1
3  p
2
3 p
 π 0  π1  π 2  1

1 p
P{gets wet}  π 0 p  p
Se mouiller
3 p
Ex.: chaîne Markov avec un nombre fini d’états

 Si on prend p = 0.1:
 1 p 1 1 
π
3  p
,
3  p
,
3  p   0.310, 0.345, 0.345 
 

 0 0 1
P   0 0.9 0.1 1 p
  P{gets wet}  π 0 p  p
Se mouiller

 0.9 0.1 0  3 p

 On peut aussi calculer  en évaluant lim Pn

numériquement
n
 0.310 0.345 0.345 
lim P n   0.310 0.345 0.345  ( n  150)
n   
 0.310 0.345 0.345 

 L’efficacité du calcul dépend de la structure de P

Exemple montrant l’indépendance de  des
états initiaux
0.6 0.6
0.4 0.6 0.4

1
À l’équilibre, on a : 2 3

=[1/4 1/2 1/4] 0.4 0.4

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

0,2 0,6 0,2
π 0a  [1,0,0] π b0  [0,1,0] π 0c  [0,0,1]
0 0,4 0,6
On obtient par simulation :
π1 0.6 0.4 0.0 0.2 0.6 0.2 0.0 0.4 0.6
π 20 0.25 0.50 0.25
0.25 0.50 0.25
0.25 0.50 0.25
Autres processus markoviens

 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