Argthtjtr

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és 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.

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 Xn+1{displaystyle X_{n+1}} sachant le passé, i.e. sachant (Xk)0≤k≤n{displaystyle left(X_{k}right)_{0leq kleq n}} est une fonction de Xn{displaystyle X_{n}} seul :

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 :

∀n≥0,∀(i0,…,in−1,i,j)∈En+2,{displaystyle forall ngeq 0,forall (i_{0},ldots ,i_{n-1},i,j)in E^{n+2},}

P(Xn+1=j∣X0=i0,X1=i1,…,Xn−1=in−1,Xn=i)=P(X1=j∣X0=i).{displaystyle mathbb {P} {Big (}X_{n+1}=jmid ,X_{0}=i_{0},X_{1}=i_{1},ldots ,X_{n-1}=i_{n-1},X_{n}=i{Big )}=mathbb {P} left(X_{1}=jmid X_{0}=iright).}

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

∀n≥0,∀(i,j)∈E2,P(Xn+1=j∣Xn=i)=P(X1=j∣X0=i).{displaystyle forall ngeq 0,forall (i,j)in E^{2},qquad mathbb {P} left(X_{n+1}=jmid X_{n}=iright)=mathbb {P} left(X_{1}=jmid X_{0}=iright).}

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 :

Notons que les évènements passés {(X0,…,Xn)∈A}{displaystyle {(X_{0},dots ,X_{n})in A}} et futurs {(Xn,Xn+1,…)∈B}{displaystyle {(X_{n},X_{n+1},dots )in B}} prennent ici la forme la plus générale possible, alors que l'évènement présent {Xn=i}{displaystyle {X_{n}=i}} reste sous une forme particulière, et pas par hasard : si on remplace {Xn=i}{displaystyle {X_{n}=i}} par {Xn∈C}{displaystyle {X_{n}in C}} 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ù Xn{displaystyle X_{n}} peut-il bien se trouver, plus précisément, à l'intérieur de la partie C{displaystyle C} ?), et, partant de là, pour prévoir le futur.

Contrexemple de la marche aléatoire sur Z{displaystyle mathbb {Z} } :

Si E=Z{displaystyle E=mathbb {Z} } et pi,i+1=1−pi,i−1=p,{displaystyle p_{i,i+1}=1-p_{i,i-1}=p,} on parle de marche aléatoire sur Z.{displaystyle mathbb {Z} .} Supposons que p∈]0,1[.{displaystyle pin ]0,1[.} Alors, par exemple,

Pμ(Xn+1=1 | Xn∈{0,1} et Xn−1=0)=0,{displaystyle mathbb {P} _{mu }(X_{n+1}=1 | X_{n}in {0,1}{text{ et }}X_{n-1}=0)=0,}

alors qu'on peut facilement trouver μ{displaystyle mu } et n{displaystyle n} tels que

Pμ(Xn+1=1 | Xn∈{0,1})>0.{displaystyle mathbb {P} _{mu }(X_{n+1}=1 | X_{n}in {0,1})>0.}

Ainsi, du fait d'une connaissance imprécise ({Xn∈{0,1}} {displaystyle {X_{n}in {0,1}} }) du présent, certaines informations concernant le passé permettent d'améliorer le pronostic : sachant que X_n-1 = 0, on en déduit que X_n n'est pas nul, donc que X_n est égal à 1, puis on conclut que X_n+1 ne peut être égal à 1. Par contre, sans l'information X_n-1 = 0, on ne peut exclure que X_n+1 soit égal à 1.

Pourtant, la marche aléatoire sur Z{displaystyle mathbb {Z} } 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 (X_n = 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

Cette égalité exprime l'indépendance conditionnelle entre le passé et le futur, sachant le présent (sachant que Xn=i{displaystyle X_{n}=i}). 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

Critère |

Propriété de Markov forte (temps discret, espace discret) |

Temps d'arrêt |

Notons Fn{displaystyle {mathcal {F}}_{n}} la tribu engendrée par la suite (Xk)0≤k≤n.{displaystyle (X_{k})_{0leq kleq n}.} Dans le cas de variables aléatoires à valeurs dans un espace d'états E{displaystyle E} fini ou dénombrable, une partie A⊂Ω{displaystyle Asubset Omega } appartient à Fn{displaystyle {mathcal {F}}_{n}} si et seulement s'il existe B⊂En+1{displaystyle Bsubset E^{n+1}} tel que

A={(X0,X1,…,Xn)∈B}={ω∈Ω | (Xk(ω))0≤k≤n∈B}.{displaystyle {begin{aligned}A&=left{(X_{0},X_{1},dots ,X_{n})in Bright}\&=left{omega in Omega | left(X_{k}(omega )right)_{0leq kleq n}in Bright}.end{aligned}}}

Définition — Une variable aléatoire T:Ω→N∪{∞}{displaystyle T:Omega rightarrow mathbb {N} cup {infty }} est un temps d'arrêt de la chaîne de Markov (Xn)n≥0{displaystyle (X_{n})_{ngeq 0}} si

∀n∈N,{T=n}∈Fn,{displaystyle forall nin mathbb {N} ,quad {T=n}in {mathcal {F}}_{n},}

ou bien, ce qui est équivalent, si

∀n∈N,{T≤n}∈Fn.{displaystyle forall nin mathbb {N} ,quad {Tleq n}in {mathcal {F}}_{n}.}

Interprétation. Imaginons que les variables aléatoires Xk{displaystyle X_{k}} représentent les résultats d'un joueur lors des parties successives d'un jeu, et que T{displaystyle T} représente la partie après laquelle le joueur décide d'arrêter de jouer : T{displaystyle T} 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 n{displaystyle n} il existe un sous ensemble Bn⊂En+1{displaystyle B_{n}subset E^{n+1}} tel que :

{T=n}⇔{(X0,X1,…,Xn)∈Bn}.{displaystyle {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 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 j{displaystyle j} un état de la chaîne de Markov ; on appelle instant de premier retour en j,{displaystyle j,} et on note Rj,{displaystyle R_{j},} la variable aléatoire définie ci-dessous :

Rj={inf{n>0|Xn=j}si{n>0|Xn=j}≠∅,+∞sinon.{displaystyle R_{j}=left{{begin{array}{lll}inf left{n>0,vert ,X_{n}=jright}&&{textrm {si}}quad left{n>0,vert ,X_{n}=jright}neq emptyset ,\+infty &&{textrm {sinon.}}end{array}}right.}

On arrête donc de jouer dès qu'on arrive à l'état j,{displaystyle j,} mais sans compter l'état initial. Si on remplace {n>0}{displaystyle {n>0}} par {n≥0}{displaystyle {ngeq 0}} dans la définition, on parle de temps d'entrée, plutôt que de temps de retour.

• De même pour C{displaystyle C} une partie de E,{displaystyle E,} on appelle instant de première entrée dans C,{displaystyle C,} et on note TC,{displaystyle T_{C},} la variable aléatoire ci-dessous définie :

TC={inf{n≥0|Xn∈C}si{n≥0|Xn∈C}≠∅,+∞sinon.{displaystyle T_{C}=left{{begin{array}{lll}inf left{ngeq 0,vert ,X_{n}in Cright}&&{textrm {si}}quad left{ngeq 0,vert ,X_{n}in Cright}neq emptyset ,\+infty &&{textrm {sinon.}}end{array}}right.}

• L'instant de k{displaystyle k}-ème retour en i,{displaystyle i,} noté Ri(k){displaystyle R_{i}^{(k)}} et défini par récurrence par :

Ri(k)={inf{n>Ri(k−1)|Xn=i}si{n>Ri(k)|Xn=i}≠∅,+∞sinon.,{displaystyle R_{i}^{(k)}=left{{begin{array}{lll}inf left{n>R_{i}^{(k-1)},vert ,X_{n}=iright}&&{textrm {si}}quad left{n>R_{i}^{(k)},vert ,X_{n}=iright}neq emptyset ,\+infty &&{textrm {sinon.}}end{array}}right.,}

ou encore l'instant de k{displaystyle k}-ème entrée dans C,{displaystyle C,} sont des t.a..

Définition et propriété — Soit T{displaystyle T,} un temps d'arrêt et A∈A : A{displaystyle Ain {mathcal {A}} : A,} est appelé évènement antérieur à T{displaystyle T,} si:

∀n∈N, A∩(T=n)∈Fn.{displaystyle forall nin mathbb {N} ,qquad Acap (T=n)in {mathcal {F}}_{n}.}

L'ensemble des évènements antérieurs à T{displaystyle T,} forme une sous-tribu de A{displaystyle {mathcal {A}}} appelée tribu antérieure à T{displaystyle T,} et notée FT.{displaystyle {mathcal {F}}_{T}.}

Interprétation. On sait que pour tout n{displaystyle n} il existe un sous ensemble Bn⊂En+1{displaystyle B_{n}subset E^{n+1}} tel que :

{T=n}⇔{(X0,X1,…,Xn)∈Bn}.{displaystyle {T=n}quad Leftrightarrow quad left{(X_{0},X_{1},dots ,X_{n})in B_{n}right}.}

Si de plus A∈FT,{displaystyle Ain {mathcal {F}}_{T},} cela signifie que pour tout n{displaystyle n} il existe un sous ensemble Dn⊂Bn{displaystyle D_{n}subset B_{n}} tel que

{A∩{T=n}}⇔{(X0,X1,…,Xn)∈Dn}.{displaystyle left{Acap {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 A{displaystyle A} se produit ou pas en observant le comportement de la suite (Xk)0≤k≤n{displaystyle (X_{k})_{0leq kleq n}} jusqu'au temps T :{displaystyle T :} par abus de langage, on dit parfois que l'évènement A{displaystyle A} porte sur la suite (X0,X1,…,XT).{displaystyle (X_{0},X_{1},dots ,X_{T}).}

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, T,{displaystyle T,} pourvu que T{displaystyle T} soit un temps d'arrêt :

Propriété de Markov forte —  Pour un temps d'arrêt T{displaystyle T} de X,{displaystyle X,} et un élément A{displaystyle A} de FT,{displaystyle {mathcal {F}}_{T},}
on a

Pμ((XT+n)n≥0∈B et A | T<+∞ et XT=i)=Pi((Xn)n≥0∈B)Pμ(A | T<+∞ et XT=i).{displaystyle {begin{aligned}{mathbb {P} }_{mu }{Big (}{big (}X_{T+n}{big )}_{ngeq 0}in B{text{ et }}A &vert T<+infty {text{ et }}X_{T}=i{Big )}\&={mathbb {P} }_{i}left(left(X_{n}right)_{ngeq 0}in Bright){mathbb {P} }_{mu }left(A vert T<+infty {text{ et }}X_{T}=iright).end{aligned}}}

Cela peut s'interpréter comme une forme d'indépendance (une indépendance conditionnelle ) entre le passé, A,{displaystyle A,} et le futur, (XT+n)n≥0∈B,{displaystyle {big (}X_{T+n}{big )}_{ngeq 0}in B,} de T,{displaystyle T,} sachant ce qui se passe à l'instant T,{displaystyle T,} à savoir {T<+∞ et XT=i}.{displaystyle {T<+infty {text{ et }}X_{T}=i}.} En effet, en particularisant A=Ω,{displaystyle A=Omega ,} on obtient que

Pμ((XT+n)n≥0∈B | T<+∞ et XT=i)=Pi((Xn)n≥0∈B){displaystyle {begin{aligned}{mathbb {P} }_{mu }{Big (}{big (}X_{T+n}{big )}_{ngeq 0}in B vert T<+infty {text{ et }}X_{T}=i{Big )}&={mathbb {P} }_{i}left(left(X_{n}right)_{ngeq 0}in Bright)end{aligned}}}

puis, en revenant à un élément général A{displaystyle A} de FT{displaystyle {mathcal {F}}_{T}}, on obtient la formulation suivante :

Indépendance conditionnelle — Pour un temps d'arrêt T{displaystyle T} de X,{displaystyle X,} et un élément A{displaystyle A} de FT,{displaystyle {mathcal {F}}_{T},}
on a

Pμ((XT+n)n≥0∈B et A | T<+∞ et XT=i)=Pμ((XT+n)n≥0∈B | T<+∞ et XT=i)Pμ(A | T<+∞ et XT=i).{displaystyle {begin{aligned}{mathbb {P} }_{mu }{Big (}{big (}X_{T+n}{big )}_{ngeq 0}in B&{text{ et }}A vert T<+infty {text{ et }}X_{T}=i{Big )}\&={mathbb {P} }_{mu }{Big (}{big (}X_{T+n}{big )}_{ngeq 0}in B vert T<+infty {text{ et }}X_{T}=i{Big )}{mathbb {P} }_{mu }left(A vert T<+infty {text{ et }}X_{T}=iright).end{aligned}}}

Cas particulier des temps de retour |

Dans le cas où la chaîne de Markov est irréductible, où l'état i{displaystyle i} est récurrent, et où le temps d'arrêt T{displaystyle T} considéré est l'instant de k-ème retour en i,{displaystyle i,} noté plus haut Rik,{displaystyle R_{i}^{k},} on constate que, par récurrence de l'état i,{displaystyle i,}

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

et que, par définition de Rik,{displaystyle R_{i}^{k},}

Pμ(XT=i)=1.{displaystyle {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 Pμ(C)=1,{displaystyle {mathbb {P} }_{mu }(C)=1,} on a Pμ(D|C)=Pμ(D).{displaystyle {mathbb {P} }_{mu }(D,|,C)={mathbb {P} }_{mu }(D).} Ici cela donne que

Pμ((XT+n)n≥0∈B et A)=Pμ((XT+n)n≥0∈B)Pμ(A)=Pi((Xn)n≥0∈B)Pμ(A).{displaystyle {begin{aligned}{mathbb {P} }_{mu }{Big (}{big (}X_{T+n}{big )}_{ngeq 0}in B{text{ et }}A{Big )}&={mathbb {P} }_{mu }{Big (}{big (}X_{T+n}{big )}_{ngeq 0}in B{Big )}{mathbb {P} }_{mu }left(Aright)\&={mathbb {P} }_{i}left(left(X_{n}right)_{ngeq 0}in Bright){mathbb {P} }_{mu }left(Aright).end{aligned}}}

Pour tout k, il y a donc indépendance ( inconditionnelle ) entre les évènements qui précèdent le k-ème passage en i{displaystyle i} et les évènements qui suivent le k-ème passage en i.{displaystyle i.} Qui plus est, la trajectoire de la chaîne de Markov après le k-ème passage en i, (XT+n)n≥0,{displaystyle i, (X_{T+n})_{ngeq 0},} a même loi que la trajectoire d'une chaîne de Markov partant de i{displaystyle i} à 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 i{displaystyle i} à 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 :

P[X(t+h)=y|X(s)=x(s),s≤t]=P[X(t+h)=y|X(t)=x(t)],∀h>0.{displaystyle mathrm {P} {big [}X(t+h)=y,|,X(s)=x(s),sleq t{big ]}=mathrm {P} {big [}X(t+h)=y,|,X(t)=x(t){big ]},quad forall h>0.}

Généralement, on utilise une hypothèse d'homogénéité dans le temps, c'est-à-dire :

P[X(t+h)=y|X(t)=x(t)]=P[X(h)=y|X(0)=x(0)],∀t,h>0.{displaystyle mathrm {P} {big [}X(t+h)=y,|,X(t)=x(t){big ]}=mathrm {P} {big [}X(h)=y,|,X(0)=x(0){big ]},quad forall t,h>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 :

Y(t)={X(s):s∈[a(t),b(t)]}.{displaystyle Y(t)={big {}X(s):sin [a(t),b(t)],{big }}.}

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 :

p(x3,t3|x1,t1)=∫p(x3,t3|x2,t2)p(x2,t2|x1,t1)dx2t3>t2>t1{displaystyle p(x_{3},t_{3}|x_{1},t_{1})=int p(x_{3},t_{3}|x_{2},t_{2})p(x_{2},t_{2}|x_{1},t_{1})dx_{2}quad t_{3}>t_{2}>t_{1}}.

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 |

1. Norris, J. : Markov Chains.


2. (en) Y. K. Lin, Probabilistic Theory of Structural Dynamics, New York, Robert E. Krieger Publishing Company, 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 |

• Andrei Markov


• Chaîne de Markov


• Couverture de Markov

• Portail des probabilités et de la statistique