Processus de Markov

Processus de Markov

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 portent le nom de leur découvreur, Andreï Markov.

Un processus de Markov en temps discret est une séquence \scriptstyle\ X_1, \scriptstyle\ X_2, \scriptstyle\ X_3,\ \dots de variables aléatoires. L'ensemble de leurs valeurs possibles est appelé l’espace d'états, la valeur \scriptstyle\ X_n\ étant l'état du processus à l'instant \scriptstyle\ n. Selon les auteurs, le vocable « chaîne de Markov » désigne les processus de Markov à temps discret ou uniquement les processus de Markov à temps discret et à espace d'états discret, i.e. les processus de Markov à temps discret dont l'espace d'états est fini ou dénombrable.

Si la loi conditionnelle de \scriptstyle\ X_{n+1}\ sachant le passé, i.e. sachant \scriptstyle\ \left(X_k\right)_{0\le k\le n}\ est une fonction de \scriptstyle\ X_n\ seul, alors :

P(X_{n+1}=x\mid X_0, X_1, X_2, \ldots, X_n) = P(X_{n+1}=x\mid X_n). \,

où x est un état quelconque du processus. L'identité ci-dessus identifie la probabilité markovienne.

Andreï Markov a publié les premiers résultats de ces processus en 1906.

Une généralisation à un espace d'états infini dénombrable a été donnée par Kolmogorov en 1936.

Les processus de Markov sont liées au mouvement brownien et à l'hypothèse ergodique, deux sujets de physique statistique qui ont été très importants au début du XXe siècle.

Sommaire

Types de processus de Markov

Espace d'états discret

Lorsque les variables aléatoires successives sont des variables discrètes munies d'une fonction de probabilité, on parle de chaîne de Markov.

Bien que les chaînes de Markov s'appliquent à des phénomènes dont l'aspect temporel est généralement sans intérêt, on peut associer aux valeurs successives x_i\, les instants t_i\,. La propriété markovienne selon laquelle la probabilité d'un état du système ne dépend que de son état précédent à travers une probabilité conditionnelle appelée probabilité de transition s'exprime par :

P(x_n,t_n|x_{n-1},t_{n-1};x_{n-2},t_{n-2};...;x_1,t_1;x_0,t_0) = P(x_n,t_n|x_{n-1},t_{n-1}) \quad t_n>t_{n-1}>...>t_1>t_0\,.

Une chaîne de Markov est entièrement définie par la probabilité au premier ordre P(x,t)\, et la probabilité de transition. On obtient par exemple la probabilité au second ordre par :

P(x_1,t_1;x_2,t_2) = P(x_1,t_1) P(x_2,t_2|x_1,t_1) \quad t_2>t_1\,.

Elle est donc également définie par la probabilité au second ordre. Enfin, elle peut être définie par l'état initial et la probabilité de transition.

Espace d'états continu

Les chaînes de Markov trouvent des applications dans les domaines les plus divers mais les processus considérés dans les problèmes dynamiques, en particulier en vibrations, portent généralement sur des variables aléatoires continues.

Dans ces conditions, la probabilité d'obtenir une valeur donnée est généralement nulle et les probabilités d'apparition doivent être remplacées par des densités de probabilité dans la formule de la propriété markovienne :

p(x_n,t_n|x_{n-1},t_{n-1};x_{n-1},t_{n-1};...;x_1,t_1;x_0,t_0) = p(x_n,t_n|x_{n-1},t_{n-1}) \quad t_n>t_{n-1}>...>t_1>t_0\,

Temps discret et temps continu

Les considérations qui précèdent restent valables si les intervalles de temps deviennent infiniment petits. Cette remarque est particulièrement intéressante dans le cas d'une équation différentielle. Si elle est du premier ordre, la mise en différences finies fait apparaître un mécanisme markovien. Pour les ordres supérieurs et les systèmes différentiels, la décomposition en équations du premier ordre conduit à un système markovien à plusieurs dimensions.

Propriétés des processus de Markov à temps discret

Un processus de Markov est caractérisé par la distribution conditionnelle :

P(X_{n+1}\mid X_n)\,

qui est aussi appelée probabilité de transition d'un pas du processus. La probabilité de transition pour deux, trois pas ou plus se déduit de la probabilité de transition d'un pas, et de la propriété de Markov :

P(X_{n+2}\mid X_n) = \int P(X_{n+2},X_{n+1}\mid X_n)\,\mathrm dX_{n+1} = \int P(X_{n+2}\mid X_{n+1}) \, P(X_{n+1}\mid X_n) \, \mathrm dX_{n+1}

De même,

P(X_{n+3}\mid X_n) = \int P(X_{n+3}\mid X_{n+2}) \int P(X_{n+2}\mid X_{n+1}) \, P(X_{n+1}\mid X_n) \, \mathrm dX_{n+1} \, \mathrm dX_{n+2}

Ces formules se généralisent à un futur arbitrairement lointain n + k en multipliant les probabilités de transition et en intégrant k − 1 fois.

La loi de distribution marginale P(Xn) est la loi de distribution des états au temps n. La distribution initiale est P(X0). L'évolution du processus après un pas est décrite par :

P(X_{n+1}) = \int P(X_{n+1}\mid X_n)\,P(X_n)\,\mathrm dX_n

Ceci est une version de l'équation de Frobenius-Perron. Il peut exister une ou plusieurs distributions d'états π telles que :

\pi(X) = \int P(X\mid Y)\,\pi(Y)\,\mathrm dY

où Y est un nom arbitraire pour la variable d'intégration. Une telle distribution π est appelée une distribution stationnaire. Une distribution stationnaire est une fonction propre de la loi de distribution conditionnelle, associée à la valeur propre 1.

Dans le cas des chaînes de Markov à espace d'états discret, certaines propriétés du processus déterminent s'il existe ou non une distribution stationnaire, et si elle est unique ou non.

  • une Chaîne de Markov est irréductible si tout état est accessible à partir de n'importe quel autre état.
  • un état est récurrent positif si l'espérance du temps de premier retour en cet état, partant de cet état, est finie.

Quand l'espace des états d'une chaîne de Markov n'est pas irréductible, il peut être partitionné en un ensemble de classes communicantes irréductibles. Le problème de la classification a son importance dans l'étude mathématique des chaînes de Markov et des processus stochastiques.

Si une chaîne de Markov possède au moins un état récurrent positif, alors il existe une distribution stationnaire.

Si une chaîne de Markov est récurrente positive et irréductible, alors :

  • il existe une unique distribution stationnaire ;
  • et le processus construit en prenant la distribution stationnaire comme distribution initiale est ergodique.

Donc, la moyenne d'une fonction f sur les instances de la chaîne de Markov est égale à sa moyenne selon sa distribution stationnaire :

\lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}^{n-1} f(X_k) = \int f(X)\,\pi(X)\,\mathrm dX

C'est vrai en particulier lorsque f est la fonction identité.

La moyenne de la valeur des instances est donc, sur le long terme, égale à l'espérance de la distribution stationnaire.

De plus, cette équivalence sur les moyennes s'applique aussi si f est la fonction indicatrice d'un sous-ensemble A de l'espace des états :

\lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}^{n-1} \chi_A(X_k) = \int_A \pi(X)\,\mathrm dX = \mu_{\pi}(A)

où μπ est la mesure induite par π.

Cela permet d'approximer la distribution stationnaire par un histogramme d'une séquence particulière.

Si l'espace des états est fini, alors la distribution de probabilité peut être représentée par une matrice stochastique appelée matrice de transition, dont le (i,j)ème élément vaut :

P(X_{n+1}=j\mid X_n=i) \,

Applications

  • Les systèmes Markoviens sont très présents en physique particulièrement en physique statistique. Ils interviennent en particulier à travers l'équation de Fokker-Planck. Plus généralement l'hypothèse markovienne est souvent invoquée lorsque des probabilités sont utilisées pour modéliser l'état d'un système, en supposant toutefois que l'état futur du système peut être déduit du passé avec un historique assez faible.
  • Le célèbre article de 1948 de Claude Shannon, A mathematical theory of communication, qui fonde la théorie de l'information, commence en introduisant la notion d'entropie à partir d'une modélisation Markovienne de la langue anglaise. Il montre ainsi le degré de prédictibilité de la langue anglaise, muni d'un simple modèle d'ordre 1. Bien que simples, de tels modèles permettent de bien représenter les propriétés statistiques des systèmes et de réaliser des prédictions efficaces sans décrire complètement la structure complète des systèmes.
  • En compression, la modélisation markovienne permet la réalisation de techniques de codage entropique très efficaces, comme le codage arithmétique. De très nombreux algorithmes en reconnaissance des formes ou en intelligence artificielle comme par exemple l'algorithme de Viterbi, utilisé dans la grande majorité des systèmes de téléphonie mobile pour la correction d'erreurs, font l'hypothèse d'un processus markovien sous-jacent.
  • L'indice de popularité d'une page Web (PageRank) tel qu'il est utilisé par Google est défini par une chaîne de Markov. Il est défini par la probabilité d'être dans cette page à partir d'un état quelconque de la chaine de Markov représentant le Web. Si N est le nombre de pages Web connues, et une page i a ki liens, alors sa probabilité de transition vers une page liée (vers laquelle elle pointe) est p_i^l= \tfrac{1-q}{k_i}+\tfrac qN et p_i^{nl}=\tfrac qN pour toutes les autres (pages non liées). Notons qu'on a bien k_i p_i^l+(N-k_i) p_i^{nl}=1. Le paramètre q vaut environ 0,15.
  • Les chaînes de Markov sont un outil fondamental pour modéliser les processus en théorie des files d'attente et en statistiques.
  • Les chaînes de Markov sont également utilisées en bio-informatique 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. Les modèles markoviens cachés ont également diverses utilisations, telles que la segmentation (définition de frontières de régions au sein de séquences de gènes ou de protéines dont les propriétés chimiques varient), l'alignement multiple, la prédiction de fonction, ou la découverte de gènes (les modèles markoviens cachés sont plus « flexibles » que les définitions strictes de type codon start + multiples codons + codons stop et ils sont donc plus adaptés pour les eucaryotes (à cause de la présence d'introns dans le génome de ceux-ci) ou pour la découverte de pseudo-gènes).

Voir aussi

Articles connexes

Liens externes

v · Probabilités et statistiques
Théorie des probabilités Axiomes des probabilités • Espace probabilisable • Probabilité • Événement • Tribu • Indépendance
Probabilités élémentaires Moyenne • Espérance • Médiane • Variance • Écart type
Loi de probabilité Variable aléatoire • Loi de Poisson • Loi normale • Loi de Student • Loi de Fisher • Variables iid
Convergence de variables aléatoires Théorème central limite • Loi des grands nombres
Processus stochastique Marche aléatoire • Chaîne de Markov • Processus de Markov • Mouvement brownien • Équation différentielle stochastique
Statistiques
Statistique descriptive Échantillon • Quantile • Intervalle de confiance • Représentations de données • Histogramme • Diagramme circulaire • Boîte à moustaches • Régression linéaire • Méthode des moindres carrés
Statistique mathématique Fonction de répartition empirique • Théorème de Glivenko-Cantelli • Inférence bayésienne
Tests statistiques Test d'hypothèse • Hypothèse statistique • Estimateur • Test du χ² • Test t • Test de Fisher
Applications Économétrie • Mécanique statistique • Jeu de hasard • Biomathématique • Mathématiques financières

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Processus de Markov de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • MARKOV (A. A.) — MARKOV ANDREÏ ANDREÏEVITCH (1856 1922) Mathématicien russe né à Riazan et mort à Petrograd. Andreï Andreïevitch Markov est connu comme un spécialiste de la théorie des nombres, de la théorie des probabilités et de l’analyse mathématique. Issu… …   Encyclopédie Universelle

  • processus — [ prɔsesys ] n. m. • 1541; lat. processus « progrès » I ♦ Anat. Prolongement d un organe. ⇒ diverticule, procès (I), saillie. Processus ethmoïdal du sphénoïde. II ♦ 1 ♦ (1865) Didact. Ensemble de phénomènes, conçu comme actif et organisé dans le… …   Encyclopédie Universelle

  • Processus de poisson — Pour les articles homonymes, voir Poisson (homonymie). Un processus de Poisson, nommé d après le mathématicien français Siméon Denis Poisson et la loi du même nom, est un processus de comptage classique dont l équivalent discret est le processus… …   Wikipédia en Français

  • Processus stochastique — Pour les articles homonymes, voir Processus. Le calcul classique des probabilités concerne des épreuves où chaque résultat possible (ou réalisation) est mesuré par un nombre, ce qui conduit à la notion de variable aléatoire. Un processus… …   Wikipédia en Français

  • Processus stationnaire — Pour accéder aux propriétés essentielles d un signal physique il peut être commode de le considérer comme une réalisation d un processus aléatoire (voir quelques précisions dans Processus continu). Le problème est largement simplifié si le… …   Wikipédia en Français

  • Processus continu — Pour les articles homonymes, voir Processus. La notion de processus continu correspond à un type de processus stochastique utilisé dans la description des signaux physiques, fonctions généralement régulières du temps. Le présent article aborde en …   Wikipédia en Français

  • Processus de Gauss — Cette notion se rencontre dans des domaines variés allant des vibrations mécaniques aux vagues de la mer. De même que le théorème de la limite centrale permet de considérer une somme de variables aléatoires indépendantes comme une variable de… …   Wikipédia en Français

  • Processus de Cox — Un Processus de Cox (nommé d après le statisticien Britannique Sir David Cox)), connu aussi sous le nom de double processus stochastique de Poisson, est un processus stochastique généralisant le processus de Poisson dans lequel la moyenne n est… …   Wikipédia en Français

  • Processus de comptage — Un processus de comptage, autrement appelé processus de dénombrement, est un processus stochastique à valeurs dans , l espace des entiers naturels. Il a pour vocation à modéliser un nombre entier aléatoire évoluant dans le temps. Le processus de… …   Wikipédia en Français

  • Processus — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Processus », sur le Wiktionnaire (dictionnaire universel) Le mot processus vient du latin pro (au sens …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”