Chaines de Markov a etats discrets (Question difficile)

[superchicken]

Bonjour, j'enonce mon probleme:

Soit une chaine de Markov à 3 etats discrets dont on connait tout: matrice de transition et distribution stationnaire.

A la date n, le systeme se trouve dans l'etat i€{1,2,3}.
Quelle est la probabilité qu'a la date n-p le systeme soit dans l'etat j€{1,2,3}?
Quelle est la succession d'etats la plus probable adoptée par le système de la date n-p à la date n ?

Voila, j'ai beau farfouiller dans Google mais je ne trouve rien qui puisse m'aider :mur:

Merci de votre aide :we:

[fahr451]

bonjour

X(n) = M ^p X(n-p)

M est-elle inversible ?

[superchicken]

M est inversible mais son inverse n'est pas stochastique. Le vecteur X(n-p) que l'on obtient n'a plus de signification probabiliste: ses coefs sont de signe differents. Ce n'est donc pas la bonne méthode :(

[fahr451]

puisque

X(n) = M^(p) X(n-p) avec M inversible on a

X(n-p) =¨M^(-p) X(n)
que M^(-1) soit ou non stochastique, avec ou non des coeffs négatifs

[superchicken]

Ce sont les coefs obtenus pour X(n-p) qui sont de signes opposés. Ils n'ont donc aucune signification probabiliste :(

[BQss]

Bonjour, j'enonce mon probleme:

Soit une chaine de Markov à 3 etats discrets dont on connait tout: matrice de transition et distribution stationnaire.

A la date n, le systeme se trouve dans l'etat i€{1,2,3}.
Quelle est la probabilité qu'a la date n-p le systeme soit dans l'etat j€{1,2,3}?
Quelle est la succession d'etats la plus probable adoptée par le système de la date n-p à la date n ?

Voila, j'ai beau farfouiller dans Google mais je ne trouve rien qui puisse m'aider :mur:

Merci de votre aide :we:

Salut,

P(Xn=i)=vP^n(i) avec vP^n la mesure definie par:
vP(j)=somme(v(i)P(i,j)), v la loi initiale de la chaine P(i,j) le noyau.

P(X(n-p)=j)=vP^(n-p)(j)


Pour ta question:

On a P(Xn=i)=vP^(n-p)*P^p(i)=mP^p(i) avec m=vP^(n-p) "la nouvelle loi initiale" et bien entendu; P(Xn=i|X(n-p)=j)=P^p(j,i)

donc on a :
P(X(n-p)=j|Xn=i)=P(X(n-p)=j,Xn=i)/P(Xn=i)
P(X(n-p)=j|Xn=i)=P(Xn=i|X(n-p)=j)P(X(n-p)=j)/P(Xn=i)

comme:
P(Xn=i|X(n-p)=j)=P^p(j,i)

ca donne:
P(X(n-p)=j|Xn=i)=P^p(j,i)*P(X(n-p)=j)/P(Xn=i)
donc finalement
P(X(n-p)=j|Xn=i)=P^p(j,i)*vP^(n-p)(j)/P(Xn=i)


De plus si la distribution est stationnaire, c'est a dire que la loi initiale est invariante vP=v et donc
P(X(n-p)=j|Xn=i)=P^p(j,i)*v(j)/P(Xn=i)
P(X(n-p)=j|Xn=i)=P(Xp=i,X0=j)/P(Xn=i)



PS: pourquoi mettre "tres compliqué" dans l'enoncé, si c'est tres compliqué pour toi il faut que tu revois un peu ton cours car comme tu peux le voir c'est assez basique ...

[superchicken]

Merci BQss pour ta réponse :we:
Là j'ai pas le temps de la voir, mais je l'examinerai plus tard :)

Pour ce qui est de la difficulté de l'exercice, je pense que la deuxieme question est plus délicate, mais peut être ne présente-elle pas grand interet :)

Enfin pour répondre à ta suggestion avisée, je suis seulement en math spé donc je n'ai pas encore de cours de proba à revoir. :triste:

Mille merci, Sir :zen:

[BQss]

Et pour le systeme le plus probable tu prends le max sur j:

etat le plus probable a n-p connaissant n:

c'est a dire que tu n'as que trois valeures a calculer, et tu prends le max.

[BQss]

Pas de probleme, dommage qu'il y est pas de probas en spe, ce serait une bonne nouvelle.

PS:
"Quelle est la probabilité qu'a la date n-p le systeme soit dans l'etat j€{1,2,3}" je ne sais pas si c'est ton enoncée mais on dit plutot
"Quelle est la probabilité qu'a la date n-p le systeme ait été dans l'etat j€{1,2,3} sachant qu'il était dans l'etat i à la date n" car il y a une chronologie et de plus on suppose l'etat n connu.

[BQss]

puisque

X(n) = M^(p) X(n-p) avec M inversible on a

X(n-p) =¨M^(-p) X(n)
que M^(-1) soit ou non stochastique, avec ou non des coeffs négatifs

Salut fahr quelle est cette methode. Ici M^p est une matrice contenant des probabilité d'obtenir X(p)=j sachant que X(0)=i. Et X(n) est une valeure, on ne peut relier une valeure d'un coté a un produit d'une valeure(deterministe donc) par une "probabilité" de l'autre et par consequent inverser apres( avec des p(Xn) peut-etre peut on faire quelquechose par contre). Veux tu dire que la loi de X(n-p) "=" la loi de X(n) "a un facteur M^p" pres? Que veux tu dire exactement?

Merci.

[superchicken]

réponse a BQss(21h29)
J'ai du mal m'exprimer sur la question 2:
Il s'agit en fait de trouver quelle est la succession d'etats la plus probable de la date n-p à la date n.

exemple:
à la date n, le systeme est en 1.
il est le plus probable que le systeme ait ete en l'etat 3 à la date n-p (d'apres le résultat de la question 1).
exemple de réponse: il est le plus probable que le systeme ait emprunté le chemin suivant:
3,2,1,1,3,...,2,1,2,3,1

Existe-t-il un algorithme quelconque pour trouver le chemin le plus probable sans avoir à calculer toutes les possibilités (qui à partir d'un certain p deviennent plutot nombreuses)?

[BQss]

réponse a BQss(21h29)
J'ai du mal m'exprimer sur la question 2:
Il s'agit en fait de trouver quelle est la succession d'etats la plus probable de la date n-p à la date n.

exemple:
à la date n, le systeme est en 1.
il est le plus probable que le systeme ait ete en l'etat 3 à la date n-p (d'apres le résultat de la question 1).
exemple de réponse: il est le plus probable que le systeme ait emprunté le chemin suivant:
3,2,1,1,3,...,2,1,2,3,1

Existe-t-il un algorithme quelconque pour trouver le chemin le plus probable sans avoir à calculer toutes les possibilités (qui à partir d'un certain p deviennent plutot nombreuses)?

Oui il y a une methode, la methode du plus court chemin(politique de bellman:"toute politique optimale est formé de politique residuelle optimale"), et l'algorythme est un algorythme retrograde de cette forme:


Ici c'est beaucoup plus simple on ne devrait pas avoir besoin de l'esperance ni du parametre W qui est un parametre general issue de la chaine. Il suffit de chercher le produit maximum car ici:
P(Xn+1=x(n+1),...,Xn+p=x(n+p)|Xn=xn)=
P(xn,x(n+1))P(x(n+1),x(n+2))...P(x(n+p-1),x(n+p))
avec P la matrice de transition(le noyau).
Il faut chercher le max de pour un x(n+p) fixé. C'est a dire tout simplement chercher ce qui maximise le produit:



mais si tu es en spe tu devrais attendre un peu pour faire ca, il faut des bonnes bases en proba quand meme, c'est du niveau master de maths appliqué et ca prendrait du temps a t'expliquer. Donne moi ton mail en pv je t'enverrai tout les cours necessaire, mais je doute que tu es le temps de les lire avec la spe.




Si non j'ai trouvé un cours qui devrait aller la dessus:
http://www.bretagne.ens-cachan.fr/DIT/People/Claude.Jard/Cours7_algo.pdf

C'est de la programmation dynamique, j'ai pas trop le temps de t'expliquer mais c'est pas super dur. Les algos y sont assez simples.

Sinon tape dans google:
programmation dynamique... Je t'enverrai par mail si tu veux plus mais j'ai pas plus de temps j'ai justement des partiels de proba a taffer.

a+ .