Plan du site  
pixel
pixel

Articles - Étudiants SUPINFO

Chaîne de Markov

Par Thibault HOARAU Publié le 27/09/2017 à 20:43:09 Noter cet article:
(0 votes)
Avis favorable du comité de lecture

Définition d'une chaîne de Markov à espaces d'états finis

Définition :

Une chaîne de Markov à espaces d’états finis est un processus qui se déroule dans un temps défini au préalable, et permettant la « prédiction » en termes de probabilités, de passer (ou non) * de l’état actuel à un nouvel état.

*Ce détail sera souligné par l’exemple illustrant la définition, présent un peu plus loin dans ces explications.

Il faut garder en tête que dans une chaîne de Markov, la probabilité de passer à un nouvel état est indépendante des états parcourus auparavant, et dépend uniquement de l’état actuel.

Exemple :

On part d’une liste d’états finis :

Etats finis : Heureux, Triste, Enervé, Indifférent

On définit par la suite un point de départ à notre chaîne :

Imaginons que lorsque notre expérience commence notre sujet est à l’état Heureux.

Lorsque le sujet est Heureux :

 Certain pourcentage de rester Heureux

 Certain pourcentage de devenir Triste

 Certain pourcentage de devenir Enervé

 Certain pourcentage de devenir Indifférent

Et il en va de même pour chacun de ses états finis, bien qu’ils ne soient pas obligés d’avoir un pourcentage de possibilités supérieurs à 0 en partant d’un état A vers un état B.

Pour mieux illustrer cela:

- Si notre sujet part de l'état Heureux, celui-ci aura :

60% de chances de rester Heureux,

20% de chances de devenir Triste,

20% de chances de devenir Enervé,

0% de chances de devenir Indifférent.

- Si notre sujet part de l'état Triste, celui-ci aura :

30% de chances de rester Triste,

20% de chances de devenir Heureux,

15% de chances de devenir Enervé,

35% de chances de devenir Indifférent.

Le coeur même du raisonnement d'une chaîne de Markov, part donc des différences de chances de passer d'un état à un autre, selon notre état de départ.

Ainsi : Une chaîne de Markov correspond donc à la probabilité en partant d’un état fini de varier ou non, à un autre état fini, et ce avec des pourcentages propres à chaque état, et définis avant le début de notre expérience.

Définition d’une matrice de transition

Définition

Une matrice de transition est une matrice représentative des probabilités à chaque état fini de passer vers un autre état fini. Ainsi, chaque ligne de cette matrice correspond aux probabilités, pour un état précis, de passer à un autre état fini.

Pour le dire plus clairement, la ligne 2 correspondra aux probabilités à l’état 2 de :

- Passer à l’état 1 à la première position ;

- Passer à l’état 2 à la seconde position (Soit rester la même) ;

- Passer à l’état 3 à la troisième position ;

- Etc…

Exemple

Illustrons cette définition avec un exemple des plus concrets :

L’exemple ci-dessus illustre le parcours d’un crapaud entre 7 nénuphars, et nous pouvons observer à la droite du schéma sa matrice de transition, ainsi que son graphe de transition.

Pour confirmer la compréhension de cette matrice, on note par exemple :

  • En partant de l’état 1, nous pouvons nous rendre uniquement à l’état 2 (Comme en P12 , soit ligne 1, colonne 2)

  • En partant de l’état 3, nous pouvons nous rendre à l’état 1 avec ½ (Comme en P31 , soit ligne 3, colonne 1), et à l’état 2 avec ½ (Comme en P32 , soit ligne 3, colonne 2)

  • Etc…

Source de cet exemple : http://www.statslab.cam.ac.uk/~rrw1/markov/M.pdf

Informations complémentaires sur les matrices de transitions

Une matrice de transition peut être qualifiée avec trois adjectifs différents : Stochastique, régulière, et ergodique.

Dans le but d’approfondir notre compréhension des matrices de transition, expliquons ces adjectifs :

Stochastique, se dit d’une matrice où pour n’importe quelle matrice vérifiant que :

- Pour tout (i, j) Pi,j ≥ 0 ;

- Pour tout i, la somme de toutes les probabilités pour tout j de Pi,j = 1.

« La matrice d'une chaîne de Markov est forcément stochastique et inversément, toute matrice stochastique est la matrice d'une chaîne de Markov. »,

Source de la phrase : http://dept-info.labri.fr/ENSEIGNEMENT/formation-a-distance/cibermiageprocessus/c1.7/ch01/seq02/sequence.htm

Régulière, se dit d’une matrice où l’on peut passer d’un état fini vers tous les autres états (même l’état lui-même) en une seule étape, soit une matrice où il n’y a aucun 0, et où la somme de toutes les probabilités partant d’un même état vaut 1.

Ergodique, se dit d’une matrice où il est possible en partant de n’importe quel état fini, d’atteindre tout autre état fini peu importe le nombre d’étapes à effectuer. Cette matrice sera donc constituée d’un circuit.

La représentation par un Graphe

Le but étant d’expliquer comment représenter par un graphe de chaînes de Markov, pour cela, nous nous sommes basés sur un exemple trouvé sur internet.

Source de l'exemple : http://www.di.ens.fr/~lelarge/proba09/ENSmarkov.pdf

Le graphe ci-dessus, comme l’indique son titre, est un graphe de transition avec 3 classes de communications. Ces 3 classes de communications sont :

  • - {1, 2, 3, 4} où il existe un chemin pour aller entre chacune des paires d’états finis.

  • {5, 7, 8} où il existe un chemin pour aller entre chacune des paires d’états finis.

  • {6} qui est seul, car il est isolé. On peut également dire de lui qu’il est fermé.

Dans une classe de communication, les composants sont connexes, c’est-à-dire qu’il existe un chemin en chaque sens entre chacun des sommets d’une même classe de communication.

Le graphe permet de mettre en avant chacune des transitions entre les différents états finis de notre chaîne de Markov. Grâce à cette représentation graphique, nous sommes capables de déduire les propriétés qualitatives de notre chaine de Markov.

Le rôle des puissances de la Matrice de Transition

Nous nous servirons d’une page web comme référence pour expliquer le rôle des puissances de la matrice de transition, et l’illustrer par un exemple. Toute cette démarche est basée et suit la logique du site cité en source.

Source de l'exemple : http://benhur.teluq.uquebec.ca/SPIP/inf6460/spip.php?article108

Exemple

« On pense qu’un individu non endetté a une possibilité sur 3 de devenir endetté. Un individu endetté a une possibilité sur 6 de régler ses dettes. », situation extraite de la source.

Pour illustrer ce cas, nous avons la matrice de l’individu endetté.

A partir de cette matrice, et en partant d’un individu qui n’est pas endetté.

On calcule au fur et à mesure, en commençant par ses risques d’être endetté le premier jour :

On constate donc que ses risques d’être endetté au bout du premier jour sont de 1/3.

Pour tester le rôle des puissances de la matrice de transition, nous testerons donc successivement jour après jour les risques que l’individu soit endetté.

Sur le long terme, nous constaterons que les probabilités en grandissant tendront vers une valeur, et au-delà restera à cette même valeur.

Dans ce cas précis, l’individu aura, au-delà de 100 jours et plus, un risque de 0,67 d’être endetté.

Ainsi, nous pouvons faire notre conclusion :

En regardant cette démonstration, on constate que les puissances dans les matrices de transitions nous permettent de calculer la valeur vers laquelle tend la probabilité de notre chaîne de Markov.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Toeic, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels