Chaîne de Markov

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

Messages : 0

Inscription : 11 juin 2015 08:13

Profil de l'utilisateur : Élève de lycée

Chaîne de Markov

Message par Poppim » 13 juin 2018 08:53

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

Messages : 0

Inscription : 15 juin 2013 22:09

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par Tsukhie » 13 juin 2018 09:40

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).

Messages : 0

Inscription : 16 oct. 2017 22:49

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par BobbyJoe » 13 juin 2018 09:40

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...

Messages : 0

Inscription : 11 juin 2015 08:13

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par Poppim » 13 juin 2018 09:50

Tsukhie a écrit :
13 juin 2018 09:40
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.

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par siro » 13 juin 2018 10:23

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.

Messages : 0

Inscription : 11 juin 2015 08:13

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par Poppim » 13 juin 2018 10:47

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 $.

Messages : 3823

Inscription : 17 avr. 2012 21:19

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par bullquies » 13 juin 2018 11:07

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
The Axiom of Choice is obviously true, the Well-Ordering Principle is obviously false, and nobody knows about Zorn's Lemma. - Jerry Bona

Messages : 0

Inscription : 11 juin 2015 08:13

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par Poppim » 13 juin 2018 11:41

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

Messages : 2

Inscription : 12 avr. 2014 23:26

Profil de l'utilisateur : Élève de lycée

Re: Chaîne de Markov

Message par Der RHDJ » 13 juin 2018 11:47

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