Chaîne de Markov

Un problème, une question, un nouveau théorème ?

Modérateurs : JeanN, Michel Quercia

Répondre
Poppim
Messages : 29
Enregistré le : jeu. juin 11, 2015 8:13 am
Classe : MP 5/2

Chaîne de Markov

Message par Poppim » mer. juin 13, 2018 8:53 am

Bonjour, une chaîne de Markov dans laquelle les probabilités de passage d'un état à un autre sont changés à chaque étape est-elle encore une "chaîne de Markov" ?

Est-ce que ça s'apparente plus à une chaîne de Markov cachée, ou est-ce que je dois préférer parler d'automate ?

Merci

Tsukhie
Messages : 147
Enregistré le : sam. juin 15, 2013 10:09 pm

Re: Chaîne de Markov

Message par Tsukhie » mer. juin 13, 2018 9:40 am

Les chaînes de Markov (en général) sont caractérisées par le fait que la loi de \( X_{n+1} \) sachant \( (X_0, X-1, ..., X_n) \) est la même que la loi \( X_{n+1} \) sachant \( (X_n) \).

Ce qu'on étudie la plupart du temps (pour des questions de simplicité, de propriétés qu'on peut obtenir, etc), ce sont les chaînes de Markov homogènes: c'est à dire que la loi de \( X_{n+1} \) sachant \( (X_n) \) ne dépend pas de \( n \).

Le souci, c'est que parler de chaînes de Markov non homogènes peut être assez compliqué en général.

(Peut-être que ton problème peut aussi s'évoquer en terme d'automate, je ne sais pas du tout).

BobbyJoe
Messages : 95
Enregistré le : lun. oct. 16, 2017 10:49 pm

Re: Chaîne de Markov

Message par BobbyJoe » mer. juin 13, 2018 9:40 am

C'est encore une chaîne de Markov (s'il y "absence de mémoire" ou plus formellement que le processus vérifie la propriété de Markov (faible ou forte)) mais dans ce cas, elle est dite inhomogène...

Poppim
Messages : 29
Enregistré le : jeu. juin 11, 2015 8:13 am
Classe : MP 5/2

Re: Chaîne de Markov

Message par Poppim » mer. juin 13, 2018 9:50 am

Tsukhie a écrit :
mer. juin 13, 2018 9:40 am
Ce qu'on étudie la plupart du temps (pour des questions de simplicité, de propriétés qu'on peut obtenir, etc), ce sont les chaînes de Markov homogènes: c'est à dire que la loi de \( X_{n+1} \) sachant \( (X_n) \) ne dépend pas de \( n \).

Le souci, c'est que parler de chaînes de Markov non homogènes peut être assez compliqué en général.
Merci pour ta réponse. Dans mon problème, la loi change mais ne dépend pas de \( n \). Ca dépend d'observations extérieures.


Vu sur Wikipedia : "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 »)."

En fait je crois que mon problème se ramène à un modèle de Markov caché, mais ça me semble un peu compliqué et théorique pour pas grand chose... Je des informations qui me permettent de dire qu'à l'étape \( k \), je suis sur tel état avec une certaine probabilité, et j'ai aussi une matrice de passage qui me donne les probabilités de passer d'un état à un autre. Mon but est de donner la probabilité qu'on soit sur tel état à une certaine étape. J'ai donc deux sources d'informations : une matrice de passage qui est constante au cours du temps, et les observations que je fais qui changent à chaque étape mais qui ne me donnent pas une information sûre.

Avatar du membre
siro
Messages : 2828
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: Chaîne de Markov

Message par siro » mer. juin 13, 2018 10:23 am

Pour calculer la proba d'être dans l'état I, prendre la somme de (proba d'arriver à l'état I en passant par le chemin C) sommé sur les chemins C ?

Si tu as une mémoire des n derniers états tu peux toujours te ramener au cas sans mémoire en augmentant la quantité d'informations codée dans l'état courant. (Par exemple si tu as la mémoire des deux derniers états et n états possibles, tu es conjugué à 2n états et pas de mémoire.)
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Poppim
Messages : 29
Enregistré le : jeu. juin 11, 2015 8:13 am
Classe : MP 5/2

Re: Chaîne de Markov

Message par Poppim » mer. juin 13, 2018 10:47 am

C'est pas tout à fait ce que je recherche. Tout ce que je veux, c'est connaître l'état du système (la probabilité d'être sur tel ou tel état) à l'étape \( k+1 \), connaissant l'état du système à l'état \( k \), la matrice de passage d'un état à un autre, et le vecteur d'observation qui me donne une probabilité d'être sur tel ou tel état à l'étape \( k+1 \).

Avatar du membre
bullquies
Messages : 6343
Enregistré le : mar. avr. 17, 2012 9:19 pm
Classe : Thé à la

Re: Chaîne de Markov

Message par bullquies » mer. juin 13, 2018 11:07 am

Si j'ai bien compris ce que tu dis, tu cherches à faire une bayesian inference, c'est-à-dire que tu as une distribution a priori, une observation, et tu veux calculer une distribution a posteriori

https://en.wikipedia.org/wiki/Bayesian_inference

Poppim
Messages : 29
Enregistré le : jeu. juin 11, 2015 8:13 am
Classe : MP 5/2

Re: Chaîne de Markov

Message par Poppim » mer. juin 13, 2018 11:41 am

Ca à l'air d'être ça, je vais regarder. Merci

Avatar du membre
Der RHDJ
Messages : 1757
Enregistré le : sam. avr. 12, 2014 11:26 pm
Classe : Jône
Localisation : Boue

Re: Chaîne de Markov

Message par Der RHDJ » mer. juin 13, 2018 11:47 am

EDIT : je n'avais pas vu que tu connaissais l'état à l'étape n. Bon du coup ma solution n'est pas adaptée, mille excuses.

Tu as effectivement un modèle de markov caché, je ne pense pas qu'il y ait de formalisme plus approprié ici. Ça se résout très bien algorithmiquement avec l'algorithme de Viterbi que tu dois pouvoir trouver sans trop de souci dans des bibliothèques R ou Python.

L'avantage c'est que comme tu connais déjà ta matrice de passage, tu as un gros gain de complexité (c'est en O(nombre d'observations * [nombre d'états]²). Tu peux même utiliser du lazy Viterbi qui est réputé bien fonctionner.
2012-2013 : 1/2 insouciante
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités