Bibliographie & annexes
Présentation
En anglais
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’articleABSTRACT
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)
-
Jean LACROIX : Professeur à l'université Paris VI
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.).
L'expertise technique et scientifique de référence
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Mathématiques
(166 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
Présentation
Comportement asymptotique des chaînes de Markov
En anglais
2. Classification des chaînes de Markov
Une des caractéristiques les plus remarquables des chaînes de Markov est très proche de la loi du 0 ou 1 pour les variables aléatoires indépendantes. Nous allons montrer que, partant d’un point x, la chaîne visitera ce point une infinité de fois avec une probabilité qui ne peut être égale qu’à 0 ou 1. On verra ensuite que ces deux types de comportement ne peuvent coexister pour différents points de départ, si l’on impose une propriété d’irréductibilité.
2.1 Récurrence et transience
On reprend, dans le cadre d’une chaîne canonique, les définitions de temps d’entrée, temps de retour successifs, données dans la définition 7. On y ajoute aussi la variable aléatoire NA donnant le nombre de passages de la chaîne dans l’ensemble A, soit
. L’utilisation de l’opérateur de translation θ permet d’obtenir un certain nombre de relations évidentes :
-
![]()
pour
![]()
![]()
; -
sur l’ensemble
![]()
, on a
![]()
; -
dans le cas où A est réduit à un point x ∈ E, on a :
pour
;
, on a
;Un outil essentiel pour la classification des points est fourni par la matrice potentielle.
Définition 8. On appelle matrice potentielle de Q (ou de X) la matrice :
La matrice potentielle peut s’interpréter à l’aide de la chaîne X car :
Donc U(x,y) est le nombre moyen de visites...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 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
Classification des chaînes de Markov
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).
-
...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 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
