Présentation

Article

1 - ÉVOLUTION MARKOVIENNE

  • 1.1 - Matrices de transition
  • 1.2 - Définition des chaînes de Markov
  • 1.3 - Dynamique associée à une fonction de transition
  • 1.4 - Exemples

2 - CLASSIFICATION DES CHAÎNES DE MARKOV

  • 2.1 - Récurrence et transience
  • 2.2 - Décomposition en classes irréductibles
  • 2.3 - Récurrence positive et récurrence nulle
  • 2.4 - Quelques outils issus de la théorie du potentiel
  • 2.5 - Étude d'exemples

3 - COMPORTEMENT ASYMPTOTIQUE DES CHAÎNES DE MARKOV

  • 3.1 - Théorème ergodique
  • 3.2 - Stabilisation des chaînes de Markov
  • 3.3 - Chaînes de Doeblin
  • 3.4 - Coalescence. Méthode de Propp & Wilson

4 - APPLICATIONS DES CHAÎNES DE MARKOV

  • 4.1 - Algorithme de Hastings-Metropolis
  • 4.2 - Contrôle stochastique
  • 4.3 - Chaînes de Markov cachées

Article de référence | Réf : AF612 v1

Applications des chaînes de Markov
Chaînes de Markov

Auteur(s) : Jean LACROIX

Date de publication : 10 oct. 2008

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

RÉSUMÉ

La notion de chaîne a été introduite en 1902 par Andrei Markov dans le but de formaliser des problèmes d'épistémologie et de cryptage. Plus tard, vers 1940-1950, est apparu un formalisme beaucoup mieux adapté, proposant des modes opératoires effectifs s'inspirant de la théorie générale des processus stochastiques et de la théorie du potentiel. Cette présentation est élémentaire et ne nécessite que des connaissances de base en probabilités. Des exemples illustrent la théorie débouchant sur des procédures algorithmiques génériques : algorithmes de recherche de mesures invariantes, de la programmation dynamique et des chaînes de Markov cachées.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

ABSTRACT

The concept of the chain was introduced in 1902 by Andrei Markov in order to formalize epistemologic and encryption issues. Later, around the years 1940-1950, a much better and adapted formalism appeared, offering effective operating modes inspired by the general theory of stochastic processes and the potential theory. This presentation is basic and only requires a basic knowledge in probabilities. Examples illustrate the theory leading to generic algorithmic approaches: algorithms for invariant measures, dynamic programming and hidden Markov chains.

Auteur(s)

INTRODUCTION

La notion de chaîne a été introduite en 1902 par Andrei Markov dans le but de formaliser des problèmes d'épistémologie et de cryptage.

L'espace d'états est alors fini et, durant une longue période, beaucoup d'utilisateurs se sont contentés de manipulations matricielles qui trouvent rapidement leurs limites, même avec les moyens informatiques actuels. Ce n'est que vers les années 1940-1950 qu'est apparu un formalisme beaucoup mieux adapté, proposant des modes opératoires effectifs qui s'inspirent de la théorie générale des processus stochastiques et de la théorie du potentiel. La présentation qui en est faite ici est volontairement élémentaire et ne nécessite que des connaissances de base en probabilités. En effet, l'on se restreint ici à un espace d'états dénombrable et l'on ne fait pas usage de concepts plus élaborés comme les filtrations ou la théorie des martingales. La notion de dépendance markovienne est très intuitive ; par contre, les techniques de calcul demandent plus de dextérité et d'entraînement. C'est pourquoi un grand nombre de preuves et d'exemples sont fournis, pour permettre au lecteur de s'exercer à la manipulation d'outils nouveaux. Quelques preuves sont aussi rédigées pour pallier la lourdeur de certaines présentations, principalement en ce qui concerne celles décrites dans le paragraphe . En ce qui concerne les applications, qui sont extrêmement nombreuses, le choix s'est porté sur quelques exemples qui débouchent sur des procédures algorithmiques génériques, relativement récentes et d'un usage très répandu : algorithmes de recherche de mesures invariantes (Propp-Wilson, Metropolis), de la programmation dynamique (Bellman) et des chaînes de Markov cachées (E.M.).

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af612


Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Présentation

4. Applications des chaînes de Markov

Les applications des chaînes de Markov sont extrêmement variées et il n'est bien sûr pas question de toutes les évoquer (voir, par exemple, et ). On se restreint donc à quelques exemples permettant de mettre l'accent sur des procédures algorithmiques largement utilisées.

4.1 Algorithme de Hastings-Metropolis

Soit E un espace dénombrable. On désire trouver un procédé de simulation d'une variable aléatoire de loi λ que l'on peut toujours supposer strictement positive, cette loi étant connue à une constante multiplicative près, par exemple une mesure de Gibbs de la forme . Pour cela, on se donne une probabilité de transition R (x,y) vérifiant et l'on construit Q par la formule :

Il est facile de constater que λ est réversible pour Q, c'est-à-dire que . Il s'ensuit que λ est invariante pour Q. On doit donc s'assurer que Q admet une seule probabilité invariante et trouver ensuite un procédé de simulation de celle-ci.

L'algorithme du « recuit simulé », correspond au cas d'une mesure de Gibbs. On se donne un ensemble fini de « voisins » de chaque point xE, de telle sorte que la mesure R(x,.) uniformément distribuée sur les « voisins » de x, définisse un noyau symétrique et irréductible. Le noyau Qβ admet donc l'unique probabilité invariante λ β. Celle-ci converge vers la loi uniforme sur l'ensemble des minimums de la fonction H lorsque β → +∞, ce qui donne donc un moyen de déterminer ceux-ci, en évitant les minimums locaux.

Pour construire une variable aléatoire de loi λ, on fait la construction suivante : on se donne une loi de probabilité de base μ que l'on suppose facilement simulable et strictement...

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Lecture en cours
Applications des chaînes de Markov
Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - BREMAUD (P.) -   Chaînes de Markov  -  Springer-verlag, New-York (2001).

  • (2) - DELMAS (J.F.), JOURDAIN (B.) -   Modéles aléatoires  -  Mathématiques et applications (57) Springer-verlag, Berlin (2006).

  • (3) - DURRETT (R.) -   Probability : Theory and examples  -  Wadsworth and Brooks, Pacific Grove (1991).

  • (4) - LACROIX (J.) -   Chaînes de Markov et processus de Poisson  -  Cours en ligne de l’université de Paris VI http://www.proba.jussieu.fr/supports.php.

  • (5) - LACROIX (J.), PRIOURET (P.) -   Probabilités approfondies  -  Cours en ligne de l’université de Paris VI http://www.proba.jussieu.fr/supports.php.

  • (6) - MAZLIAK (L.), PRIOURET (P.), BALDI (P.) -   Martingales et chaînes de Markov  -  Hermann, (2001).

  • ...

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS