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:
Après deux ans, environ35%des familles partiront à la mer et65%iront à la montagne.
En savoir plus
Apprenez avec les Bases
Apprenez les bases avec des unités théoriques et mettez en pratique ce que vous avez appris à l'aide d'ensembles d'exercices !
Durée:
Unité 1
Matrices : graphes
Test Avancé
Obtenez un score de 80 % pour accéder directement à l'unité finale.
Ceci est la leçon dans laquelle vous vous trouvez actuellement et l'objectif du parcours.
Unité 2
Matrices : chaînes de Markov
Test final
Testez la révision de toutes les unités pour réclamer une planète de récompense.
Créer un compte pour commencer les exercices
Questions fréquemment posées sur les crédits
Qu'est-ce qu'une chaîne de Morkov ?
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.