2. CHAÎNES DE MARKOV



CALCUL DES PROBABILITÉS

1. Univers des événements

1.1. Axiomes

1.2. Probabilités conditionnelles

1.3. Martingales

2. Analyse combinatoire

1.1. Arrangements avec répétition

1.2. Permutations simples

1.3. Permutations avec répétitions

1.4. Arrangements simples sans répétitions

1.5. Combinaisons simples

1.5.1. Binômiale

1.5.2. Formule de Pascal

3. Chaînes de Markov

Les chaînes de Markov sont des outils statistiques et probabilistes simples et puissants mais dont la forme de présentation mathématique prête parfois à l'horreur. Nous allons tenter ici de simplifier un maximum les notations pour introduire cet outil formidable très utilisé au sein des entreprises pour gérer la logistique, les files d'attentes aux centrales d'appel ou aux caisses de magasins jusqu'à la théorie de la défaillance pour la maintenance préventive, en physique statistique ou en génie biologique (et la liste est encore longue et pour plus de détails le lecteur pourra se reporter aux chapitres concernés disponibles sur le site...).

Définition: Nous noterons equation un processus probabiliste fonction du temps (c'est donc un processus stochastique) dont la valeur à chaque instant dépend de l'issue d'une expérience aléatoire. Ainsi, à chaque instant t, X(t) est donc une variable aléatoire.

Si nous considérons un temps discret, nous notons alors equation un processus stochastique à temps discret. Si nous supposons que les variables aléatoires equation ne peuvent prendre qu'un ensemble discret de valeurs. Nous parlons alors de "processus à temps discret et à espace discret".

Remarque: Il est tout à fait possible comme dans l'étude du télétrafic d'avoir un processus à temps continu et à espace d'état discret.

Définition : equation est une "chaîne de Markov" si et seulement si:

equation   (6.65)

en d'autres termes (c'est très simple!) la probabilité pour que la chaîne soit dans un certain état à la n-ème étape du processus ne dépend que de l'état du processus à l'étape n - 1 et pas des étapes précédentes!

Remarque: En probabilité un processus stochastique vérifie la propriété markovienne si et seulement si la distribution conditionnelle de probabilité des états futurs, étant donné l'instant présent, ne dépend que de ce même état présent et pas des états passés. Un processus qui possède cette propriété est donc appelé "processus de Markov".

Définition: Une "chaîne de Markov homogène" est une chaîne telle que la probabilité qu'elle a pour passer dans un certain état à la n-ème soit indépendante du temps. En d'autres termes, la loi de probabilité caractérisant la prochaine étape ne dépend pas du temps (de l'étape précédente), et en tout temps la loi de probabilité à tout moment de la chaîne est toujours la même pour caractériser la transition à l'étape en cours.

Nous pouvons alors définir la (loi) de "probabilité de transition" d'un état i vers un état j par :

equation   (6.66)

Il est alors naturel de définir la "matrice de transition" ou "matrice stochastique":

equation   (6.67)

Les chaînes de Markov peuvent être représentées graphiquement sous la forme d'un graphe orienté G (cf. chapitre de Théorie Des Graphes) ayant pour sommet les point i et pour arêtes les couples orientés (i, j). Nous associons alors à chaque composante un arc orienté et sa de probabilité de transition.

exempleExemple:

equation
  (6.68)

Ainsi, les seules transitions permises par les 4 états (matrice 4x4) sont celles indiquées par les flèches. Ce qui fait que la matrice de transition s'écrit alors :

equation   (6.69)

où le lecteur remarquera que nous avons la propriété triviale (par construction!) que la somme des termes d'une colonne de la matrice transposée de P est toujours unitaire:

equation   (6.70)

et que la matrice est positive (ce qui signifie que tous ces termes sont positifs ou nuls).

Remarque: Se rappeler que la somme des probabilités des colonnes T obtenues est toujours égale à 1 pour la transposée de la matrice stochastique!!

L'analyse du régime transitoire (ou promenade aléatoire) d'une chaîne de Markov consiste à déterminer (ou à imposer!) la matrice-colonne (vecteur) p(n) d'être dans un état j à l'étape n (ou en la n-ème étape autrement dit...) :

equation   (6.71)

avec la somme des composantes qui vaut évidemment toujours 1 (car la somme des probabilités de se trouver dans un quelconque des sommets du graphe à un moment/étape donné(e) doit être égale à 100%).

Démonstration:

Si p(n) est un vecteur stochastique, alors son image:

equation   (6.72)

l'est aussi. Effectivement, equation car:

equation   (6.73)

est une somme de termes positifs ou nul. De plus, nous trouvons:

equation   (6.74)

equationC.Q.F.D.

Nous appelons fréquemment cette matrice colonne "vecteur stochastique" ou "mesure de probabilité sur le sommet i".

Ce vecteur de probabilités, dont les composantes sont positives ou nulles, dépend (c'est assez intuitif) de la matrice de transition P et du vecteur de probabilités initiales p(0).

Bien que cela soit démontrable (théorème de Perron-Frobenius) le lecteur pourra vérifier par un cas pratique (informatisé ou non!) que si nous choisissons un vecteur d'état p(n) quelconque alors il existe pour toute matrice stochastique P un vecteur unique de probabilité noté traditionnellement equation tel que:

equation   (6.75)

Une telle mesure de probabilité equation vérifiant la relation précédente est appelée une "mesure invariante" ou "mesure stationnaire" ou encore "mesure d'équilibre" qui représente l'état d'équilibre du système. En termes d'algèbre linéaire, pour la valeur propre 1, equation est un vecteur propre de P (cf. chapitre d'Algèbre Linéaire).

Nous en verrons un exemple trivial dans le chapitre de Théorie des Graphes qui sera redéveloppé sous forme détaillée et complète ainsi que dans le chapitre de Théorie Des Jeux Et De La Décision dans le cadre de la pharmaco-économie. Mais signalons également que les chaînes de Markov sont également utilisées en météorologie par exemple:

equation
  (6.76)

ou dans le domaine médical, financier, des transports du marketing, etc.