- Propriété de Markov
-
En probabilité, un processus stochastique vérifie la propriété de Markov si et seulement si la distribution conditionnelle de probabilité des états futurs, étant donné les états passés et l'état présent, ne dépend en fait que de l'état présent et non pas des états passés (absence de « mémoire »). Un processus qui possède cette propriété est appelé processus de Markov. Pour de tels processus, la meilleure prévision qu'on puisse faire du futur, connaissant le passé et le présent, est identique à la meilleure prévision qu'on puisse faire du futur, connaissant uniquement le présent : si on connait le présent, la connaissance du passé n'apporte pas d'information supplémentaire utile pour la prédiction du futur.
Sommaire
Propriété de Markov faible (temps discret, espace discret)
Définition
C'est la propriété caractéristique d'une chaîne de Markov : en gros, la prédiction du futur à partir du présent n'est pas rendue plus précise par des éléments d'information supplémentaires concernant le passé, car toute l'information utile pour la prédiction du futur est contenue dans l'état présent du processus. La propriété de Markov faible possède plusieurs formes équivalentes qui reviennent toutes à constater que la loi conditionnelle de
sachant le passé, i.e. sachant
est une fonction de
seul :
Propriété de Markov faible « élémentaire » — Pour tout
pour toute suite d'états
On suppose le plus souvent les chaînes de Markov homogènes, i.e. on suppose que le mécanisme de transition ne change pas au cours du temps. La propriété de Markov faible prend alors la forme suivante :
Cette forme de la propriété de Markov faible est plus forte que la forme précédente, et entraîne en particulier que
Dans la suite de l'article on ne considèrera que des chaînes de Markov homogènes. Pour une application intéressante des chaînes de Markov non homogènes à l'optimisation combinatoire, voir l'article Recuit simulé.
La propriété de Markov faible pour les chaînes de Markov homogènes a une autre forme, beaucoup plus générale que la précédente, mais pourtant équivalente à la précédente :
Propriété de Markov faible « générale » — Pour n'importe quel choix de
Notons que les évènements passés
et futurs
prennent ici la forme la plus générale possible, alors que l'évènement présent
reste sous une forme particulière, et pas par hasard : si on remplace
par
dans l'énoncé ci-dessus, alors l'énoncé devient faux en général, car l'information sur le passé devient utile pour prévoir le présent (où
peut-il bien se trouver, plus précisément, à l'intérieur de la partie
?), et, partant de là, pour prévoir le futur.
Contrexemple de la marche aléatoire sur:
Si
et
on parle de marche aléatoire sur
Supposons que
Alors, par exemple,
alors qu'on peut facilement trouver
et
tels que
0.\ " border="0">
Ainsi, du fait d'une connaissance imprécise (
) du présent, certaines informations concernant le passé permettent d'améliorer le pronostic : sachant que Xn-1 = 0, on en déduit que Xn n'est pas nul, donc que Xn est égal à 1, puis on conclut que Xn+1 ne peut être égal à 1. Par contre, sans l'information Xn-1 = 0, on ne peut exclure que Xn+1 soit égal à 1.
Pourtant, la marche aléatoire sur
est une chaîne de Markov, et possède bien la propriété de Markov. Il n'y a pas de contradiction, ici : la propriété de Markov stipule que, lorsque l'on a une connaissance précise (Xn = i ) du présent, aucune information concernant le passé ne permet d'améliorer le pronostic.
Il existe une propriété de Markov forte, liée à la notion de temps d'arrêt : cette propriété de Markov forte est cruciale pour la démonstration de résultats importants (divers critères de récurrence, loi forte des grands nombres pour les chaînes de Markov).
Indépendance conditionnelle
La propriété de Markov faible « générale » entraine que
Indépendance conditionnelle — Pour n'importe quel choix de
Cette égalité exprime l'indépendance conditionnelle entre le passé et le futur, sachant le présent (sachant que
). Cependant, si l'on compare avec la propriété de Markov faible « générale » telle qu'énoncée plus haut, on constate qu'on a perdu la propriété d'homogénéité : la propriété de Markov faible « générale » est en fait équivalente à la propriété plus forte
Indépendance conditionnelle et homogénéité — Pour n'importe quel choix de
Critère
Critère fondamental — Soit une suite
de variables aléatoires indépendantes et de même loi, à valeurs dans un espace
, et soit
une application mesurable de
dans
Supposons que la suite
est définie par la relation de récurrence :
et supposons que la suite
est indépendante de
Alors
est une chaîne de Markov homogène.
Collectionneur de vignettes (coupon collector) :Petit Pierre fait la collection des portraits des onze joueurs de l'équipe nationale de football, qu'il trouve sur des vignettes à l'intérieur de l'emballage des tablettes de chocolat Cémoi ; chaque fois qu'il achète une tablette il a une chance sur 11 de tomber sur le portrait du joueur n°
(pour tout
). On note
l'état de la collection de Petit Pierre, après avoir ouvert l'emballage de sa
-ème tablette de chocolat.
est une chaîne de Markov partant de
, car elle rentre dans le cadre précédent pour le choix
puisque
où les variables aléatoires
sont des variables aléatoires indépendantes et uniformes sur
: ce sont les numéros successifs des vignettes tirées des tablettes de chocolat. Le temps moyen nécessaire pour compléter la collection (ici le nombre de tablettes que Petit Pierre doit acheter en moyenne pour compléter sa collec') est, pour une collection de
vignettes au total, de
où
est le
-ème nombre harmonique. Par exemple,
tablettes de chocolat.
Remarques :- La propriété de Markov découle de l'indépendance des
elle reste vraie lorsque les
ont des lois différentes, et lorsque la « relation de récurrence »
dépend de
Les hypothèses faites en sus de l'indépendance sont là uniquement pour assurer l'homogénéité de la chaîne de Markov.
- Le critère est fondamental en cela que toute chaîne de Markov homogène peut être simulée exactement via une récurrence de la forme
pour une fonction
bien choisie. Plus précisément, si
est une chaîne de Markov homogène, il existe un quintuplet
où
désigne un espace de probabilité,
est une variable aléatoire à valeurs dans
et où
est une suite de variables aléatoires i.i.d. à valeurs dans
et
étant définies sur
et indépendantes, et il existe une application
définie de
dans
telles que la suite
définie par
- ait même loi que la suite
- On peut même choisir
et choisir des variables
indépendantes et uniformes sur l'intervalle [0,1], ce qui est commode pour l'étude de chaînes de Markov via des méthodes de Monte-Carlo, i.e. par simulation de trajectoires « typiques » de chaînes de Markov.
Propriété de Markov forte (temps discret, espace discret)
Temps d'arrêt
Notons
la tribu engendrée par la suite
Dans le cas de variables aléatoires à valeurs dans un espace d'états
fini ou dénombrable, une partie
appartient à
si et seulement s'il existe
tel que
Définition — Une variable aléatoire
est un temps d'arrêt de la chaîne de Markov
si,
ou bien, équivalemment, si,
Interprétation. Imaginons que les variables aléatoires
représentent les résultats d'un joueur lors des parties successives d'un jeu, et que
représente la partie après laquelle le joueur décide d'arrêter de jouer :
est un temps d'arrêt si la décision d'arrêter est prise en fonction des résultats des parties déjà jouées au moment de l'arrêt, i.e. si pour tout
il existe un sous ensemble
tel que :
Cela interdit au joueur de prendre sa décision en fonction des résultats des parties futures : cela revient à faire l'hypothèse que tricherie et don de double vue sont exclus.
Pour une définition d'un temps d'arrêt en situation générale on pourra regarder
Exemples :Les variables aléatoires ci-dessous sont des temps d'arrêt :
- Soit
un état de la chaîne de Markov ; on appelle instant de premier retour en
et on note
la variable aléatoire définie ci-dessous :
0\,\vert\,X_n = j\right\}& &\textrm{si }\quad\left\{n > 0\,\vert\,X_n = j\right\} \neq\emptyset,\\ +\infty& &\textrm{sinon.} \end{array} \right. " border="0">
- On arrête donc de jouer dès qu'on arrive à l'état
mais sans compter l'état initial. Si on remplace
0\}\ " border="0"> par
dans la définition, on parle de temps d'entrée, plutôt que de temps de retour.
- De même pour
une partie de
on appelle instant de première entrée dans
et on note
la variable aléatoire ci-dessous définie :
- L'instant de
-ème retour en
noté
et défini par récurrence par :
R^{(k-1)}_i\,\vert\,X_n = i\right\}& &\textrm{si }\quad\left\{n > R^{(k)}_i\,\vert\,X_n = i\right\} \neq\emptyset,\\ +\infty& &\textrm{sinon.} \end{array} \right., " border="0">
ou encore l'instant de
-ème entrée dans
sont des t.a..
Contrexemple :Pour
et
dans
on pose
On peut montrer que
n'est pas un temps d'arrêt, mais que, par contre,
est un temps d'arrêt.
Définition et propriété — Soit
un temps d'arrêt et
est appelé évènement antérieur à
si:
L'ensemble des évènements antérieurs à
forme une sous-tribu de
appelée tribu antérieure à
et notée
Interprétation. On sait que pour tout
il existe un sous ensemble
tel que :
Si de plus
cela signifie que pour tout
il existe un sous ensemble
tel que
En quelque sorte, on teste si l'évènement
se produit ou pas en observant le comportement de la suite
jusqu'au temps
par abus de langage, on dit parfois que l'évènement
porte sur la suite
Propriété de Markov forte
Dans l'énoncé général de la propriété de Markov faible, l'instant « présent », n, peut-être remplacé par un instant « présent » aléatoire,
pourvu que
soit un temps d'arrêt :
Propriété de Markov forte — Pour un temps d'arrêt
de
et un élément
de
on a
Cela peut s'interpréter comme une forme d'indépendance (une indépendance conditionnelle ) entre le passé,
et le futur,
de
sachant ce qui se passe à l'instant
à savoir
En effet, en particularisant
on obtient que
puis, en revenant à un élément général
de
, on obtient la formulation suivante :
Indépendance conditionnelle — Pour un temps d'arrêt
de
et un élément
de
on a
Cas particulier des temps de retour
Dans le cas où la chaîne de Markov est irréductible, où l'état
est récurrent, et où le temps d'arrêt
considéré est l'instant de k-ème retour en
noté plus haut
on constate que, par récurrence de l'état
et que, par définition de
Ainsi les conditions apparaissant dans la propriété de Markov forte sont presque certaines. Or, dès que
on a
Ici cela donne que
Pour tout k, il y a donc indépendance ( inconditionnelle ) entre les évènements qui précèdent le k-ème passage en
et les évènements qui suivent le k-ème passage en
Qui plus est, la trajectoire de la chaîne de Markov après le k-ème passage en
a même loi que la trajectoire d'une chaîne de Markov partant de
à l'instant 0 : elle redémarre comme neuve, indépendamment de ce qui a pu se passer auparavant. On dit alors que les temps de retour successifs sont des instants de renouvellement ou bien des instants de régénération.
Les morceaux de trajectoires entre deux régénérations consécutives forment alors une suite de variables aléatoires i.i.d. (sauf le premier morceau, indépendant, mais éventuellement de loi différente, si la chaîne de Markov ne part pas de
à l'instant 0). Cela conduit à une démonstration de la loi forte des grands nombres pour les chaînes de Markov déduite de la loi forte des grands nombres pour les v.a.r. i.i.d.. Cela donne également une méthode pour construire des intervalles de confiance pour les paramètres intéressants de la chaîne de Markov.
Propriété de Markov faible (temps continu, espace discret)
Mathématiquement, si X(t), t > 0, est un processus stochastique, et si x(t), t > 0, est une fonction, la propriété de Markov est définie ainsi :
0." border="0">
Généralement, on utilise une hypothèse d'homogénéité dans le temps, c'est-à-dire :
0." border="0">
Dans certains cas, un processus à première vue non-markovien peut tout de même avoir des représentations markoviennes en modifiant le concept d'état actuel et futur. Soient X un intervalle de temps, et Y un processus tel que chaque état de Y représente un intervalle de temps de X :
Si Y est markovien, alors c'est la représentation markovienne de X et X qui est alors appelée processus de Markov du second ordre. Les processus d'ordre supérieur sont définis de la même manière.
Équation de Chapman-Kolmogorov-Smoluchowski
C'est une équation intégrale qui assure la cohérence du processus :
t_2>t_1 " border="0">.
Elle se transforme en une équation aux dérivées partielles, plus facile à manipuler, qui prend le nom d'équation de Fokker-Planck.
Références
- Norris, J. : Markov Chains.
- (en) Y. K. Lin, Probabilistic Theory of Structural Dynamics, New York, Robert E. Krieger Publishing Company, juillet 1976, 368 p. (ISBN 0882753770)
- Philippe A. Martin, Introduction aux processus stochastiques en physique
- Ch. Ancey, Simulations stochastiques - Applications aux écoulements géophysiques et la turbulence
Voir aussi
- Portail des probabilités et des statistiques
Wikimedia Foundation. 2010.