Processus de Markov

M1 LOGISTIQUE ET SUPPLY CHAIN MANAGEMENT 2013/2014

Azouz Menel Bergaoui Malek

Gharbi Nour Moumni Sarra Somrani Imèn

Zhar Fatma

2

I- Présentation des chaines de Markov :

1. Historique :

En mathématiques, un processus de Markov est un processus stochastique possédant la

propriété de Markov. Dans un tel processus, la prédiction du futur à partir du présent n'est pas

rendue plus précise par des éléments d'information concernant le passé. Les processus de

Markov (1906) portent le nom de leur inventeur, Andreï Markov (mathématicien russe-

2 juin 1856 - 20 juillet 1922).

2. Définitions :

Une chaine de Markov est une suite de variables aléatoires (Xn, n ∈ N) qui permet de

modéliser l´évolution dynamique d’un système aléatoire : Xn représente l’état du système à

l’instant n.

Pour une chaîne de Markov on fait l’hypothèse qu’il y a plusieurs évolutions possibles

(états) à partir de la situation présente, chacune d’elles ayant une certaine probabilité de se

réaliser. C’est cette incertitude sur l’avenir qui est prise en compte par les modèles

markoviens que l’on appelle pour cette raison dynamiques aléatoires ou stochastiques.

Il existe bien d’autres dynamiques aléatoires que les chaines de Markov mais celles-ci ont une

propriété bien spéciale, que l’on appelle absence de mémoire (ou simplement propriété de

Markov) que nous allons indiquer à présent.

Lorsqu’un système a plusieurs avenirs possibles à partir de son état présent, il se pourrait que

la probabilité que l’un ou l’autre de ces avenirs se réalise dépende non seulement de son état

présent mais aussi de son histoire récente. (L’évolution future ne dépend du passé qu’au

travers de sa valeur actuelle).

Une chaine de Markov est dite irréductible lorsque tous ses états communiquent, c’est-à-dire

lorsque, pour toute paire d’états (xi, xj) la probabilité d’aller de l’un `a l’autre est strictement

positive.

Un état xi ∈ S tel que, lorsque la chaine est issue de ce point, elle y retourne en un temps fini

avec une probabilité strictement positive, s’appelle un état récurrent (sinon l’état est dit

transitoire).

3

Lorsqu’un état est récurrent, chaque trajectoire issue de ce point y revient presque

certainement une infinité de fois.

Par contre, lorsqu’il est transitoire, chaque trajectoire issue de ce point n’y revient

presque surement qu’un nombre fini de fois.

Soit X = (Xn, n ∈ N) une chaine de Markov de matrice de transition P. On dit que x

est un état absorbant de la chaine X si P(x, x) = 1.

On représente une chaîne de Markov avec une matrice de transition. Chaque rangée de la

matrice correspond à un état et donne la probabilité de passer à un autre état.

Une matrice P = (P(x, y), x, y ∈ E) est dite matrice stochastique si ses coefficients sont

positifs et la somme sur une ligne des coefficients est égale à 1

Une matrice de transition se reconnaît parce que toutes les valeurs sont entre 0 et 1

inclusivement et que la somme de chaque rangée est 1.

Naturellement, pour avoir une chaîne de Markov, il faut répéter le nombre de transitions

possibles.

Une matrice de transition est dite régulière si elle ne contient aucun zéro.

Une matrice de transition est dite ergodique si elle permet de passer de n’importe quel état à

n’importe quel autre (mais pas nécessairement en une seule étape).

Observez que si la matrice de transition n’a aucun zéro, alors, dans une seule étape, il est

possible de passer de n’importe quel état à n’importe quel autre.

Les applications des chaînes de Markov sont très nombreuses (réseaux, génétique des

populations, mathématiques financières, gestion de stock, algorithmes stochastiques

d’optimisation, simulation ...).

3. Exemple (chaîne de Markov à deux états) :

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.

Comme dit précédemment, on représente une chaîne de Markov avec une matrice de

transition. Chaque rangée de la matrice correspond à un état et donne la probabilité de passer

à un autre état.

4

Dans le cas de notre individu endetté, la matrice de transition est :

Pour avoir une chaîne de Markov, il faut répéter le nombre de transitions possibles. Dans

notre cas, supposons qu’à chaque jour qui passe, la matrice de transition s’applique. Si

l’individu n’est pas endetté au départ, après un jour il y aura une probabilité de 1/3 qu’il soit

endetté :

Après deux jours, il aura autant de possibilités d’être endetté que de ne pas l’être :

Et ainsi de suite. On peut se demander ce qui se passera après un très long délai, disons un

an ?

Il suffit alors de savoir calculer les puissances de la matrice de transition.

Dans tous les cas qui nous concernent, ces puissances convergent rapidement vers une matrice

fixe : cela signifie qu’après avoir calculé 2, 3, 10 ou 20 puissances, la matrice ne change

pratiquement plus :

5

On voit, par ces matrices, qu’après un an, 2 ans ou 10 ans, un individu, qu’il débute avec une

dette ou sans dette, aura une probabilité de 2/3 d’être endetté !

II- Etude théorique :

Une chaine de Markov est une suite de variables aléatoires toutes définis sur un même

ensemble. On prend l’exemple de cette chaine où 0 et 1 sont deux états vrai faux, sécurité et

insécurité. Le système peut basculer d’un état a l’autre avec les probabilité p et q .

L’arc qui va de l’état 0 à l’état 1 auquel est associée à une probabilité p, c’est la probabilité de

se retrouver à l’état 1 au temps n+1 étant donné qu’au temps précédent n il été a l’état 0.

C’est une probabilité conditionnelle.

- Le passage de l’état 1 à l’état 0 est donné par la probabilité q.

- La probabilité de rester dans le même état 1 est de 1-q.

- La probabilité de rester dans le mm état 0 est de 1-p.

Ceci est illustré par les formules suivantes :

6

La chaine de Markov nous permet de calculer la probabilité de trouver ma chaine dans un

certain état c-à-d si on arrive a un moment inconnu t et que la chaine tourne, quelle est la

probabilité qu’à ce moment t on est à l’état 0.

On cherche donc la probabilité Xn+1 =0 au temps n+1 en ignorant la valeur de n.

Donc on distingue 2 cas : je me retrouve a l’état 0 au temps n+1 soit je viens de Xn=0 ou

Xn=1 au temps n.

Je fais l’intersection avec 2 évènements Xn=0 et Xn=1, qui sont disjoint et complémentaire

Je peux reformuler en faisant apparaitre les probabilités conditionnelles.

Je remplace par les probabilités définit précédemment .

Et maintenant je me retrouve avec 2 termes ou apparait la probabilité que Xn=0 .

On calcule P(Xn+1=0) qui dépend de la probabilité de Xn =0

Et si je résonne de la même manière je vais voir que ça dépend de P(Xn-1=0) ainsi de suite

puis Xn-2 et Xn-3 et finalement je vais dérouler cette récurrence pour faire apparaitre la

probabilité que X0 =0

7

Et lorsqu’on rassemble les termes la probabilité s’exprime en fonction de la probabilité de

X0=0 plus une somme géométrique

on obtient finalement cette expression

III- Etude empirique : Etude de cas

1. Présentation du cas :

- Cadre de la recherche :

La sécheresse constitue un fléau redoutable pour l'économie tunisienne fondée

essentiellement sur la production agricole pluviale. L'analyse de la récurrence et de la

persistance de ce phénomène par des méthodes scientifiques cherche à établir une estimation

des probabilités qui pourrait contribuer à la planification de stratégies de mobilisation et de

gestion des ressources en eau.

La Tunisie se situe dans une zone de transition entre la zone tempérée et la zone

subtropicale. De par cette position, elle subit alternativement les influences des perturbations

tempérées, d'une part, et les influences sahariennes qui avancent plus ou moins profondément

à l'intérieur du pays, d'autre part. Elle possède également deux façades maritimes : l'une

septentrionale et l'autre orientale. Les perturbations de nord-ouest et les situations de retour

d'est constituent la principale source de pluie.

Par ailleurs, l'économie du pays, fondée sur l'agriculture, reste tributaire de la pluviométrie.

Pour cela, des ouvrages hydrauliques ont été aménagés afin de lutter contre la sécheresse.

Mais, si la sécheresse perdure deux ou trois années successives, les autorités doivent faire face

à cette éventualité en planifiant les priorités de satisfaction des demandes en eau (eau potable,

eau domestique, industrie, irrigation, etc.) et en adaptant la capacité des réservoirs de stockage

de l'eau.

Or, la fréquence relative d'un événement comme la sécheresse annuelle peut être étudiée en

termes de probabilité. Pour décrire la persistance de la sécheresse, nous allons appliquer la

méthode des chaînes de Markov à des données pluviométriques annuelles.

8

Nous voulons donc, par cette étude, établir une estimation des probabilités d'avoir des années

sèches successives. Cette estimation peut servir à la planification et à la gestion des ressources

en eau.

- Données et méthodes

L'information pluviométrique utilisée pour cette étude provient de la Direction générale

des ressources en eau, principal gestionnaire de réseau et de fichiers pluviométriques en

Tunisie. Elle se compose de données pluviométriques annuelles (les années disponibles pour

les mêmes stations s'étendent de 1909 à 1996) relatives à 22 postes pluviométriques répartis

sur l'ensemble du territoire tunisien (soit 1 936 années-stations). Nous avons réduit ces valeurs

à 528 valeurs régionales en groupant les stations par grande région naturelle (figure 1).

9

.

Fig.1. Isohyètes moyennes annuelles - Principales stations pluviométriques des grandes

régions naturelles de Tunisie.

10

Les postes pluviométriques retenus pour l'analyse sont des stations principales du réseau

national dont le suivi est très régulier et la répartition spatiale assez proportionnée. Ils ont été

sélectionnés pour la fiabilité de leurs données, la longueur de leur série et leur représentativité

spatiale. L'élaboration d'une moyenne arithmétique régionale permet d'atténuer les disparités,

de modérer les particularités de chaque station et de réduire la masse de données afin de

présenter une estimation globale et synthétique de la pluviométrie dont l'impact sur la vie

agricole n'est pas ponctuel mais régional.

Définition de la sécheresse :

La sécheresse se définit par un déficit des disponibilités en eau par rapport à une situation

considérée comme normale pour une période donnée et une région déterminée. En réalité, il

existe différents types de sécheresse :

- la sécheresse climatologique essentiellement liée au déficit pluviométrique

- la sécheresse agronomique qui fait appel au déficit de la réserve hydrique du sol et à

l'état d'avancement de la végétation

- la sécheresse hydrologique ou hydrogéologique qui se manifeste par des étiages

anormaux et un abaissement prononcé des nappes

C'est la sécheresse climatologique qui nous semble déterminer les autres types de sécheresse.

La réduction des précipitations se répercute nécessairement sur le milieu environnant. La

sécheresse est « une décroissance des disponibilités en eau pour une époque particulière et sur

une région particulière ». Éphémère, la sécheresse peut affecter un mois, une saison ou une

année. Elle devient redoutable quand elle persiste deux ou trois années successives. C'est pour

cela que nous avons choisi d'axer notre étude sur la persistance de la sécheresse à l'échelle

annuelle.

En l'absence d'indicateur officiel de la sécheresse, nous avons adopté comme méthode de

définition des années sèches, et après plusieurs essais au moyen de différents indices, la

méthode de l'analyse fréquentielle.

Cette méthode, indépendante des valeurs centrales (moyennes ou médianes), est fondée sur un

classement des valeurs des plus faibles vers les plus fortes, des années les plus sèches aux

années les plus humides, les années du milieu étant considérées comme années normales. Une

répartition quasiment équitable attribue 35 % des valeurs aux années extrêmes (sèches ou

humides) et 30 % aux années normales. La distinction des classes se présente ainsi :

11

- les années dont la fréquence est inférieure à 0,35 correspondent aux années sèches

(parmi lesquelles on peut distinguer les années très sèches, de fréquence inférieure à

0,15)

- les années dont la fréquence est comprise entre 0,35 et 0,65 sont considérées comme

années normales

- les années dont la fréquence dépasse 0,65 correspondent aux années humides (celles

dont la fréquence est supérieure à 0,85 sont considérées comme des années très

humides)

La méthode est simple et nous l'avons simplifiée davantage en ne considérant que les années

sèches de fréquence inférieure à 0,35 et les années non sèches pour le reste des années.

2. Application du processus de Markov :

Le processus de Markov exprimera des probabilités conditionnelles de passage de l'état de

la veille (année précédente) à l'état de l'année en cours.

L'état de l'année k ne dépend que de l'état k-1 pour le processus de Markov d'ordre 1. Il

dépend des états k-1 et k-2 pour le processus de Markov d'ordre 2.

Une année peut être caractérisée du point de vue pluviométrique par deux états :

- un état 0 : présence de la sécheresse (sèche ou très sèche) ; i = 0

- un état 1 : absence de la sécheresse (normale, humide, très humide) ; i = 1

Dans ce qui suit, nous présentons dans un premier temps la chaine de Markov d’ordre 1

appliquée à notre cas puis nous présentons la chaine de Markov d’ordre 2 :

Chaine de Markov d’ordre 1 :

Etat de l’an k

Etat de l’an k-1 0 1

0 A00 A01

1 A10 A11

Tableau 1: Processus de Markov d'ordre 1

12

La probabilité marginale s’écrit sous la forme :

Pour chaque région, la quantité de pluie est suivie pour 90 ans. Les données sont collectées

dans le graphe qui suit :

La matrice de Markov d'ordre 1 est déterminée à partir de ce qui précède en donnant plus

d'importance aux coefficients A00, A01, A10. L'application nous donne les résultats

regroupés dans ce tableau

13

Régions A00 A01 A10 A11

Nord-Ouest 40% 60% 31% 69%

Nord-est 23% 77% 40% 60%

Centre-Ouest 37% 63% 33% 67%

Centre-est 33% 67% 35% 65%

Sud-ouest 30% 70% 36% 64%

Sud-est 23% 77% 40% 60%

Tableau 2: Processus d'ordre 1 pour chaque région

Résultats & Interprétations :

À la suite de l'application de l'hypothèse d'un processus de Markov d'ordre 1, nous

constatons que, pour l'ensemble du pays et quelle que soit l'année de départ (sèche ou

non sèche), la probabilité d'avoir une année « sèche » l'année suivante est partout plus

faible que celle d'avoir une année « non sèche », c'est-à-dire normale ou humide. Les

probabilités oscillent entre 23 et 40 %.

On remarque également que le Nord-Est et le Sud-Est se comportent de la même

façon et présentent les mêmes valeurs de probabilité, valeurs relativement les plus

faibles en cas d'année de début sèche et les plus fortes en cas d'année de début « non

sèche ».

À l'échelle régionale, les probabilités se présentent ainsi :

* Si une année est sèche, la probabilité pour qu'elle soit suivie d'une année « sèche » est plus

importante au nord qu'au sud.

* Si une année n'est pas sèche, la probabilité d'avoir une année sèche l'année suivante est plus

faible au nord qu'au sud et à l'ouest qu'à l'est. Cette probabilité augmente en allant du nord

vers le sud. À l'est, le Sahel se distingue par une probabilité plus faible qu'au nord-est et qu'au

sud-est.

* À l'ouest, la probabilité d'avoir deux années successives sèches diminue progressivement du

nord vers le sud. Réciproquement, si une année est sèche, la probabilité pour qu'elle soit

suivie d'une année non sèche est plus importante au sud qu'au nord.

14

* À l'est, la probabilité d'avoir deux années successives sèches est beaucoup plus faible qu'à

l'ouest et le Centre a une probabilité plus forte que le Nord-Est et le Sud-Est.

Enfin, la probabilité d'avoir deux années sèches successives est la plus forte au Nord-Ouest,

que la partie orientale du pays a des probabilités plus faibles que la partie occidentale et que le

Nord-Est et le Sud-Est présentent les mêmes probabilités plus faibles que celles du Sahel. La

proximité des sources d'humidité nous semble fournir une explication vraisemblable à cet état

de fait, mais elle n'est pas suffisante étant donné que le Sahel est également exposé à la mer.

Chaine de Markov d’ordre 2

Dans ce cas, l'état de l'année k dépend de l'état de l'année k-1 et de l'état de l'année k-2. La

matrice de passage de la chaîne de Markov d'ordre 2 s'écrit comme indiqué dans le Tableau où

Bijk représente la probabilité conditionnelle d'obtenir un doublet de classe (j, k) succédant à

un doublet de classe (i, j) avec :

Apparaissions de certains zéros, contrairement à l'ordre 1, à cause de l'impossibilité de

certaines successions de doublets.

Etat au jour k-

1 et k-2

Etat au jour k-1 et k

00 01 10 11

00 B000 B001 0 0

01 0 0 B010 B011

10 B100 B101 0 0

11 0 0 B110 B111

Tableau 3: Le processus de Markov d’ordre 2

Application :

Pour chaque région, la matrice de Markov d'ordre 2 a été calculée en s’intéressant

essentiellement aux années sèches successives (B000, B001, B100 et B101) :

S-S-S (trois années sèches successives),

15

S-S-NS (deux années sèches successives),

NS-S-S (deux années sèches successives),

NS-S-NS (une année sèche isolée).

L'application de l'hypothèse des chaînes de Markov donne les probabilités indiquées dans

le tableau ci dessous.

Régions S-S-S SS-NS NS-S-S NS-S-NS

Nord-Ouest 43% 57% 39% 61%

Nord-Est 43% 57% 17% 83%

Centre-Ouest 45% 55% 32% 68%

Centre-Est 40% 60% 30% 70%

Sud-Ouest 11% 89% 38% 62%

Sud-Est 14% 86% 26% 74%

Tableau 4: Processus de Markov d’ordre 2 pour chaque région

Résultats & Interprétations :

Comme pour l'ordre 1, ce que l’on constate à la suite de l'application de l'hypothèse d'un

processus de Markov d'ordre 2, c’est que la probabilité d'avoir l'année suivante une année «

sèche » est partout plus faible que celle d'avoir une année « non sèche » (Les probabilités

oscillent entre 11 et 45 %). Ceci est vrai pour l'ensemble du pays et quelle que soit la

composition de la séquence.

À l'échelle régionale, les conclusions suivantes ont pu être dégagées :

Si deux années successives sont sèches, la probabilité d'avoir une troisième année

sèche est importante au nord et au centre où elle varie de 40 à 45 %. Par contre, cette

probabilité est très faible au sud où elle ne dépasse pas les 14 %.

D’une manière réciproque, la probabilité d'avoir deux années sèches successives

suivies d'une année « non sèche » est importante au Sud : elle dépasse les 85 %. En

revanche, elle est moins importante au nord et au centre où elle varie de 55 à 60 %.

La probabilité d'avoir deux années sèches successives faisant suite à une année « non

sèche », est plus importante à l'ouest qu'à l'est : à l'ouest, elle varie de 32 à 39 % alors

que, à l'est, elle varie de 17 à 30 %.

16

Réciproquement, la probabilité d'avoir une année sèche isolée au milieu de deux

années « non sèches » est plus importante à l'est qu'à l'ouest : à l'est, elle varie de 70 à

83 % tandis que, à l'ouest, elle varie de 61 à 68 %.

Ainsi, on peut dire que le Sud (Est et Ouest) est la région qui risque le moins la

persistance de la sécheresse. Le Centre-Ouest est, par contre, la région la plus menacée par

la succession de trois années sèches.

Pour ce qui est de la probabilité d'avoir deux années sèches à la suite d'une année non sèche,

la répartition des probabilités ressemble à celle relative à deux années sèches successives

(processus de Markov d'ordre 1) indépendamment de l'année qui précède, on note :

- Une opposition très nette entre l'Ouest (P= 39% pour le Nord Ouest) et l'Est (P=17%

pour le Nord Est)

- Probabilité au Sahel (P = 32%) est plus importante que celle au Sud-Est (P =26%).

Conclusion:

Les chaînes de Markov sont un outil mathématique issu des probabilités dont leur

utilisation n’a pas cessé d’augmenter depuis son apparition et ce pour les avantages qu’elles

présentent.

En fait, la structure mathématique des chaines de Markov extrêmement simple et qui est

indépendantes de l’état initial du processus suffit à générer une très grande variété de

comportements. C’est pour cela que les chaines de Markov trouvent des applications dans des

domaines pluridisciplinaire comme, par exemple, la biologie pour modéliser les relations

entre symboles successifs d'une même séquence (de nucléotides par exemple), en allant au

delà du modèle polynomial, la physique en particulier dans la physique statistique, la

sociologie, la météorologie, l’intelligence artificielle, la recherche opérationnelle et les

sciences de l’ingénieur, où elles donnent des réponses qualitatives aussi bien que quantitatives

aux problèmes posés.

Outre leur cadre théorique solide, les chaines de Markov ont l’avantage de permettre une

modélisation explicite des données.

La matrice de transition de la chaine de Markov est généralement obtenue à partir des

données historiques. Nous pouvons donc constater que la chaine de Markov peut autant être

17

utilisée dans un contexte de probabilité historique (réaliste) que dans un contexte plus

théorique.

Par ailleurs, une « explosion » combinatoire du nombre d’états susceptible d’être occupés

par le système dont on souhaite de modéliser le comportement peut rendre difficile

l’utilisation des modèles markoviens. Ceci présente un inconvénient dans l’utilisation de

processus de Markov.