Propriété de Markov

En probabilité un processus stochastique vérifie la propriété de Markov si et uniquement si la distribution conditionnelle de probabilité des états futurs, compte tenu de les états passés...



Catégories :

Probabilités - Processus stochastique

Page(s) en rapport avec ce sujet :

  • Markov fort. Une chaˆıne de Markov (Mn) (Poly. page 94) vérifie toujours la propriété de Markov fort : Si T temps d'arrêt :... (source : cmap.polytechnique)
  • (" propriété de Markov forte "). - Soit T un temps d'arrêt; et soit. S une variable aléatoire FT-mesurable, à valeurs dans R+, et telle que T... (source : archive.numdam)
  • qui est un temps d'arrêt et porte alors le nom de propriété de Markov forte. On débute par énoncer un lemme qui assure que les formules écrites ont un... (source : proba.jussieu)

En probabilité un processus stochastique vérifie la propriété de Markov si et uniquement si la distribution conditionnelle de probabilité des états futurs, compte tenu de 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 nommé 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 semblable à la meilleure prévision qu'on puisse faire du futur, connaissant seulement 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.

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

\begin{align}\mathbb{P}\Big(X_{n+1}=j&\mid\, X_0=i_0, X_1=i_1,\ldots, X_{n-1}=i_{n-1},X_n=i\Big) &= \mathbb{P}\left(X_{n+1}=j\mid X_n=i\right).
\end{align}

On suppose le plus fréquemment 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 :

\forall n\ge 0, \forall (i_0,\ldots,i_{n-1},i,j) \in Eˆ{n+2},
\mathbb{P}\Big(X_{n+1}=j \mid\, X_0=i_0, X_1=i_1,\ldots, X_{n-1}=i_{n-1},X_n=i\Big) = \mathbb{P}\left(X_{1}=j\mid X_0=i\right).

Cette forme de la propriété de Markov faible est plus forte que la forme précédente, et entraîne surtout que

\forall n\ge 0, \forall (i,j)\in Eˆ{2},\qquad\mathbb{P}\left(X_{n+1}=j\mid X_n=i\right) = \mathbb{P}\left(X_{1}=j\mid X_0=i\right).

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, bien plus générale que la précédente, mais néenmoins équivalente à la précédente :

Propriété de Markov faible «générale» —  Pour n'importe quel choix de

{\mathbb P}((X_{n}, X_{n+1}, \dots ) \in B\,|\,(X_0,\dots,X_{n}) \in A,  X_n=i)
\;=\;{\mathbb P}((X_{0}, X_{1}, \dots )\in B\,|\, X_0=i).

Notons que les évènements passés et futurs prennent ici la forme la plus générale envisageable, tandis que l'évènement présent reste sous une forme spécifique, et pas par hasard : si on remplace par dans l'énoncé ci-dessus, alors l'énoncé devient faux généralement, car l'information sur le passé devient utile pour prévoir le présent (où peut-il bien se trouver, plus exactement, au sein 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,

\mathbb{P}_{\mu}(X_{n+1}=1\ |\ X_n\in\{0,1\}\text{ et }X_{n-1}=0)=0,\

tandis qu'on peut aisément trouver et tels que

<img class=propriété de Markov forte, liée à la notion de temps d'arrêt : cette propriété de Markov forte est principale 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

{\mathbb P}((X_{n}, X_{n+1}, \dots ) \in B\text{ et } (X_0,\dots,X_{n}) \in A\ |\ X_n=i)
=\;{\mathbb P}((X_{n}, X_{n+1}, \dots ) \in B\ |\ X_n=i)\times{\mathbb P}((X_0,\dots,X_{n}) \in A\ |\  X_n=i).

Cette égalité exprime l'indépendance conditionnelle entre le passé et le futur, sachant le présent (sachant que). Cependant, si 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

{\mathbb P}((X_{n}, X_{n+1}, \dots ) \in B\text{ et } (X_0,\dots,X_{n}) \in A\ |\ X_n=i)
 =\; {\mathbb P}((X_{0}, X_{1}, \dots )\in B\ |\ X_0=i)\times{\mathbb P}((X_0,\dots,X_{n}) \in A\ |\  X_n=i).

Critère

Critère essentiel — 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 :

\forall n\ge 0,\qquad X_{n+1}=f\left(X_n,Y_{n}\right),

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 au sein 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

 X_{n+1}=X_n\cup\{Y_n\},

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 indispensable 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. A titre d'exemple, tablettes de chocolat.

Remarques :
  • La propriété de Markov découle de l'indépendance des elle reste vraie quand les ont des lois différentes, et quand la «relation de récurrence» dépend de Les hypothèses faites en sus de l'indépendance sont là seulement pour assurer l'homogénéité de la chaîne de Markov.
  • Le critère est essentiel en cela que toute chaîne de Markov homogène peut être simulée précisément via une récurrence de la forme pour une fonction bien choisie. Plus exactement, si est une chaîne de Markov homogène, il existe un quintuplet où sert à désigner 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
 Xˆ{\prime}_{n+1}=f(Xˆ{\prime}_n,Y_n)
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 génèrée ensuite Dans le cas de variables aléatoires à valeurs dans un espace d'états fini ou dénombrable, une partie appartient à si et uniquement si il existe tel que

\begin{align}
A
&=
\left\{(X_0,X_1,\dots,X_n)\in B\right\}
\\
&=
\left\{\omega\in\Omega\ |\ \left(X_k(\omega)\right)_{0\le k\le n}\in B\right\}.
\end{align}

Définition — Une variable aléatoire T : \Omega \rightarrow \mathbb N \cup \{ \infty \} est un temps d'arrêt de la chaîne de Markov si,

\forall n \in \mathbb N,\quad\{T=n\} \in \mathcal{F}_n,

ou bien, équivalemment, si,

\forall n \in \mathbb N,\quad\{T\le n\} \in \mathcal{F}_n.

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 suivant les 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 :


\{T=n\}\quad \Leftrightarrow\quad\left\{(X_0,X_1,\dots,X_n)\in B_n\right\}.

Cela interdit au joueur de prendre sa décision suivant les résultats des parties futures : cela revient à faire l'hypothèse que don de double vue et tricherie sont exclus.

Pour une définition d'un temps d'arrêt en situation générale on pourra regarder

Article détaillé : Temps d'arrêt.
Exemples :

Les variables aléatoires ci-dessous sont des temps d'arrêt :

  • Soit un état de la chaîne de Markov ; on nomme instant de premier retour en et on note la variable aléatoire définie ci-dessous :
<img class=
  • L'instant de -ème retour en noté et défini par récurrence par :
<img class=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 nommé évènement antérieur à si :

\forall n \in \mathbb N,\qquad \ A \cap (T=n) \in \mathcal{F}_n.

La totalité des évènements antérieurs à forme une sous-tribu de nommée tribu antérieure à et notée

Interprétation. On sait que pour tout il existe un sous ensemble tel que :


\{T=n\}\quad \Leftrightarrow\quad\left\{(X_0,X_1,\dots,X_n)\in B_n\right\}.

Si de plus cela veut dire que pour tout il existe un sous ensemble tel que


\left\{A\cap \{T=n\}\right\}\quad \Leftrightarrow\quad\left\{(X_0,X_1,\dots,X_n)\in D_n\right\}.

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 quelquefois 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


\begin{align}
{\mathbb P}_{\mu}\Big(\big(X_{T+n}\big)_{n\ge 0}\in B\text{ et }A\ &\vert\ T<+
\infty \text{ et }X_T=i\Big)\\
&={\mathbb P}_i\left(\left(X_{n}\right)_{n\ge 0}\in B\right){\mathbb P}_{\mu}\left(A\ \vert\ T<+
\infty\text{ et }X_T=i\right).
\end{align}

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


\begin{align}
{\mathbb P}_{\mu}\Big(\big(X_{T+n}\big)_{n\ge 0}\in B\ \vert\ T<+
\infty \text{ et }X_T=i\Big)
&={\mathbb P}_i\left(\left(X_{n}\right)_{n\ge 0}\in B\right)
\end{align}

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


\begin{align}
{\mathbb P}_{\mu}\Big(\big(X_{T+n}\big)_{n\ge 0}\in B&\text{ et }A\ \vert\ T<+
\infty \text{ et }X_T=i\Big)\\
&={\mathbb P}_{\mu}\Big(\big(X_{T+n}\big)_{n\ge 0}\in B\ \vert\ T<+
\infty \text{ et }X_T=i\Big){\mathbb P}_{\mu}\left(A\ \vert\ T<+
\infty\text{ et }X_T=i\right).
\end{align}

Cas spécifique 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 reconnu est l'instant de k-ème retour en noté plus haut on constate que, par récurrence de l'état


{\mathbb P}_{\mu}\Big(T<+\infty\Big)=1,

et que, par définition de


{\mathbb P}_{\mu}\Big(X_T=i\Big)=1.

Ainsi les conditions apparaissant dans la propriété de Markov forte sont presque certaines. Or, dès que on a Ici cela donne que


\begin{align}
{\mathbb P}_{\mu}\Big(\big(X_{T+n}\big)_{n\ge 0}\in B\text{ et }A\Big)
&={\mathbb P}_{\mu}\Big(\big(X_{T+n}\big)_{n\ge 0}\in B\Big){\mathbb P}_{\mu}\left(A\right)
\\
&={\mathbb P}_i\left(\left(X_{n}\right)_{n\ge 0}\in B\right){\mathbb P}_{\mu}\left(A\right).
\end{align}

Pour tout k, il y a par conséquent indépendance (inconditionnelle) entre les évènements qui précèdent le k-ème passage en et les 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 jusque là. On dit tandis 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 peut-être 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 aussi 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 :

<img class=temps, et Y un processus tel que chaque état de Y représente un intervalle de temps de X :

Y(t) = \big\{ X(s) : s \in [a(t), b(t)] \, \big\}.

Si Y est markovien, alors c'est la représentation markovienne de X et X qui est alors nommé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 :

<img class=Références
  1. Norris, J.  : Markov Chains.
  2. (en) Y. K. Lin, Probabilistic Theory of Structural Dynamics, Robert E. Krieger Publishing Company, New York, juillet 1976, 368 p. (ISBN 0882753770)  
  1. Philippe A. Martin, Introduction aux processus stochastiques en physique
  2. Ch. Ancey, Simulations stochastiques - Applications aux écoulements géophysiques et la turbulence

Voir aussi

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Propri%C3%A9t%C3%A9_de_Markov.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.