Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Propriété de Markov
Résumé
vignette|Exemple de processus stochastique vérifiant la propriété de Markov: un mouvement Brownien (ici représenté en 3D) d'une particule dont la position à un instant t+1 ne dépend que de la position précédente à l'instant t.
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.
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 :
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 :
Cette forme de la propriété de Markov faible est plus forte que la forme précédente, et entraîne en particulier que
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 inhomogènes à l'optimisation combinatoire, voir l'article Recuit simulé.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (25)
COM-309: Introduction to quantum information processing
Information is processed in physical devices. In the quantum regime the concept of classical bit is replaced by the quantum bit. We introduce quantum principles, and then quantum communications, key d
MGT-484: Applied probability & stochastic processes
This course focuses on dynamic models of random phenomena, and in particular, the most popular classes of such models: Markov chains and Markov decision processes. We will also study applications in q
COM-516: Markov chains and algorithmic applications
The study of random walks finds many applications in computer science and communications. The goal of the course is to get familiar with the theory of random walks, and to get an overview of some appl
Publications associées (221)
Personnes associées (38)
Concepts associés (9)
Champ aléatoire de Markov
Un champ aléatoire de Markov est un ensemble de variables aléatoires vérifiant une propriété de Markov relativement à un graphe non orienté. C'est un modèle graphique. Soit un graphe non orienté et un ensemble de variables aléatoires indexé par les sommets de . On dit que est un champ aléatoire de Markov relativement à si une des trois propriétés suivantes est vérifiée c'est-à-dire que deux variables aléatoires dont les sommets associés ne sont pas voisins dans le graphe sont indépendantes conditionnellement à toutes les autres variables.
Chaîne de Markov
vignette|Exemple élémentaire de chaîne de Markov, à deux états A et E. Les flèches indiquent les probabilités de transition d'un état à un autre. En mathématiques, une chaîne de Markov est un processus de Markov à temps discret, ou à temps continu et à espace d'états discret. Un processus de Markov est un processus stochastique possédant la propriété de Markov : l'information utile pour la prédiction du futur est entièrement contenue dans l'état présent du processus et n'est pas dépendante des états antérieurs (le système n'a pas de « mémoire »).
Couverture de Markov
En apprentissage automatique, la couverture de Markov pour un nœud d'un réseau bayésien est l'ensemble des nœuds composés des parents de , de ses enfants et des parents de ses enfants. Dans un réseau de Markov, la couverture de Markov d'un nœud est l'ensemble de ses nœuds voisins. La couverture de Markov peut également être désignée par . Chaque ensemble de nœuds dans le réseau est conditionnellement indépendant de lorsqu'il est conditionné sur l'ensemble , c'est-à-dire lorsqu'elle est déterminée sur la couverture de Markov du nœud .