Un graphepondéréest un graphe où chaque arête est associée à un nombre réel, appelépoidsde l’arête. Un grapheprobabilisteest un graphe orienté et pondéré, où le poids de chaque arrête est positif et où la somme des arêtes partant d’un sommet est toujours égale à 1.
Exemple
Graphe probabiliste
Matrice de transition
Chaque ligne et chaque colonne de la matrice de transition représente un sommet du graphe probabiliste.
La valeur du coefficientai,jest égal au poids de l’arête partant du sommetI(ligne) et allant au sommetj(colonne).
Exemple
Sommet
A
B
C
Ligne/colonne
1
2
3
00,20,4000,610,80
Note : La somme des coefficients d’une ligne est toujours égale à 1.
Chaîne de Markov
Imagine une expérience que tu répètes plusieurs fois. La variable aléatoireXnassocie à chaque élément de l’universΩla valeur qu’il prend dansE⊆Rà la n-ième répétition. On peut ainsi construire une suiteX0,X1,X2,…de variables aléatoires.
Note : L’ensembleEs’appelle l’espace des états.
Unechaîne de Markovest une suite de variables aléatoiresXntelle que chaque événementXndépend uniquement de l’état deXn−1, c’est-à-dire qu’il dépend de l’état antérieur mais pas des états qui précèdent et pas de l’étapenà laquelle on se trouve.
Exemple
Dans un village, chaque famille part tous les étés en vacances, soit à la mer, soit à la montagne. La décision du lieu de vacances dépend uniquement de l’endroit où la famille est allée l’année précédente. L’ensemble des états est{mer(1),montagne(2)}(on associe arbitrairementmerau nombre 1etmontagneau nombre 2).
Si une famille est allée à la mer l’année précédente, il y a25%de chance qu’elle y retourne, etde chance qu’elle choisisse la montagne.
Si une famille est allée à la montagne l’année précédente, il y a60%de chance qu’elle y retourne, et40%de chance qu’elle aille au bord de la mer à la place.
Chaquereprésente la destination choisie par la famille l’année. Il s’agit d’une chaîne de Markov puisque la décision ne dépend que de la valeur prise parXn−1. Le graphe suivant représente cette situation:
Tu peux aussi construire la matrice de transition de ce graphe:
(0,250,40,750,6)
Note : On appelle ce graphe le graphe probabiliste associé et cette matrice la matrice de transition de la chaîne de Markov.
Distribution initiale
La loi de probabilité deest appelée la distribution initiale de la chaîne de Markov. Elle est généralement représentée par une matrice ligne notée.
AVEC DEUX ÉTATS
π0=(p(X0=1)p(X0=2))
AVEC TROIS ÉTATS
π0=(p(X0=1)p(X0=2)p(X0=3))
De manière analogue, la loi de probabilité deXnest appelée la distribution aprèsntransitions de la chaîne de Markov. Elle est généralement représentée par une matrice ligne notéeπn.
AVEC DEUX ÉTATS
πn=(p(Xn=1)p(Xn=2))
AVEC TROIS ÉTATS
πn=(p(Xn=1)p(Xn=2)p(Xn=3))
On dit que la distribution estinvariantesi tous lesπnsont les mêmes.
PROPRIÉTÉ
Une propriété des distributions d’une chaîne de Markov est que :
πn=π0×Tn
oùTest la matrice de transition de la chaîne de Markov.
Exemple
Reprends l’exemple précédent. Imagine que l’an 0,30% des familles sont allées à la mer et70%à la montagne. Calcule la distribution après 2ans:
Une chaîne de Markov est une suite de variables aléatoires X_n telle que chaque événement X_n dépend uniquement de l’état de X_(n-1), c’est-à-dire qu’il dépend de l’état antérieur mais pas des états qui précèdent et pas de l’étape n à laquelle on se trouve.
Qu'est qu'une matrice de transition ?
Chaque ligne et chaque colonne de la matrice de transition représente un sommet du graphe probabiliste.
La valeur du coefficient a_(i,j) est égal au poids de l’arête partant du sommet i (ligne) et allant au sommet j (colonne).
Qu'est-ce qu'un graphe pondéré ?
Un graphe pondéré est un graphe où chaque arête est associée à un nombre réel, appelé poids de l’arête.