Chaîne de Markov
Chaîne de Markov
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
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
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).
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
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
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.Tsukhie a écrit : ↑13 juin 2018 09:40Ce 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.
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
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.)
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.
Re: Chaîne de Markov
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
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
https://en.wikipedia.org/wiki/Bayesian_inference
The Axiom of Choice is obviously true, the Well-Ordering Principle is obviously false, and nobody knows about Zorn's Lemma. - Jerry Bona
Re: Chaîne de Markov
Ca à l'air d'être ça, je vais regarder. Merci
Re: Chaîne de Markov
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.
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
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