Page 1 sur 1

Chaîne de Markov

Posté : mer. juin 13, 2018 8:53 am
par Poppim
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

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 9:40 am
par Tsukhie
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).

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 9:40 am
par BobbyJoe
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...

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 9:50 am
par Poppim
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.

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 10:23 am
par siro
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.)

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 10:47 am
par Poppim
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 \).

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 11:07 am
par bullquies
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

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 11:41 am
par Poppim
Ca à l'air d'être ça, je vais regarder. Merci

Re: Chaîne de Markov

Posté : mer. juin 13, 2018 11:47 am
par Der RHDJ
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.