Comprendre les Chaines de Markov

Bonjour,


Alors en fait je cherche un coup de mains sur les chaine de markov. Je n'ai pas besoin d'y implémenter, juste d'y comprendre(assez pour pouvoir en faire un usage "boite noire", répondre a des question de vocabulaire et retrouver la méthode de calcul des probabilité "de base") dans le cadre d'un DS (modélisation des réseau, 3A ingé info)

Depuis quelques jours, je lis des cours et des tutos sur le sujet, et je suis bloqué au stade "doudou le hamster", juste avant le début des équations. J'arrive a représenter le système décris, a le paramétrer(quoique), puis faire une matrice de transition. Ensuite c'est Beyrouth, touts les cours part dans un sens différent et a priori aléatoire, je ne suis plus...

http://fr.wikipedia.org/wiki/Cha%C3%...dou_le_hamster
[...]De manière générale, pour n minutes[...], aprés je décroche, avant pec, sauf que je vois pas comment sans ordi si c'est l'etat 240 qui est demandé

Je me suis dit que c'etais une histoire de base en math, mais je me suis retapé l'essentiel des matrice et des proba, rien ne me semble incompréhensible/illogique. Je suis capable de comprendre toute les opérations de base, et je suis toujours bloqué au moment ou, sans la moindre explication, commence les équation.

Sur des dizaine de cours,on commence par les définition(mathématique avec parfois une phrase) D'un type plus ou moins exotique de chaine (déjà j'ai isolé les markoviennes, sans mémoire, et les ergodique/reguliére, sans état absorbant) puis un exemple, le schéma, la matrice (avec les proba d'etat, T ou P), et on commence a bidouiller des matrice et déployer des équation sans indiquer pourquoi et comment, et surtout dans quel but.

Je cherche donc quelqu'un qui pourrais me transmettre une certaine compréhension de cet outil, ou a défaut une méthode rigoureuse/procédurale a appliquer en fonction de .... quequechose d'a priori recherché... Un article de vulgarisation... Un cours clair ou sous un jour inabituel...


Merci d'avance,
Denderk

Ps: C'est des math pur, mais je suis informaticien alors je pense avoir plus de chance d'en comprendre un qu'un matheux, d'ou devoppez/algo :)

Citation:

---

Je cherche donc quelqu'un qui pourrais me transmettre une certaine compréhension de cet outil, ou a défaut une méthode rigoureuse/procédurale a appliquer en fonction de .... quequechose d'a priori recherché... Un article de vulgarisation... Un cours clair ou sous un jour inabituel...

---

Ca va être difficile de faire une vulgarisation plus simple à comprendre que "doudou le hamster" :P

A priori, tu as compris le plus complique : c'est un processus aléatoire sans mémoire avec un nombre fini d'états.

Merci de ta réponse, j'ai sorti cet exemple parce que je le comprend jusque un certain point :aie:

Dans mon cours d'origine, on distingue au moins trois processus sources, markoviens, poissoniens et chaotiques, mais ca me semble être le niveau au dessus, puisque le poissonien il est a mémoire et l'autre il est ... :koi:

Ma principale question en fait c'est, une fois une graph/matrice en place
-> Que puis-je en tirer d'utile/pertinent/instructif (infos/valeurs)? (en français, pas en math)
-> Comment (en math ou en algo) obtenir ces différentes valeurs?

Citation:

---

Envoyé par Denderk

Ma principale question en fait c'est, une fois une graph/matrice en place
-> Que puis-je en tirer d'utile/pertinent/instructif (infos/valeurs)? (en français, pas en math)
-> Comment (en math ou en algo) obtenir ces différentes valeurs?

---

Et bien... heu... ca sert a modéliser un processus stochastique (=aléatoire). A partir de cette modélisation, on peut étudier le comportement du processus : prédiction des états futurs, vraisemblance d'une observation, ...

Tes questions ont l'air d'être d'ordre général, donc il faut peut-être que tu cherches un ouvrage de vulgarisation sur l'analyse stochastique en général. Les chaines de Markov ne sont qu'un modèle particulier parmi d'autres.

Les informations les plus facilement disponibles sont : le "temps" moyen dans un état : « Doudou passe 88,4 % de son temps à dormir ! » et la probabilité étant un état initial donné de se retrouver dans un état après tant de temps.

Je pense que l'exemple suivant est à ta portée et montre comment il est facile d'obtenir cette seconde information.

Merci de vos réponses.

pseudocode> Je vais essayer d'élargir ma recherche vers "L'analyse stochastique" donc. Mais bon je croyais justement que "chaine de markov" c'etais déjà très vague...

prgasp77> Je n'ai pas tout compris cet exemple, comme le précédent (les formules kinder surprise, je vois même pas d'ou il les sort O_o) la partie "français" oui. En fait, il me manque juste un document méthodologique! si si si alors cas 1(en francais), faire ca(en math). si si si cas 2, faire ca ....

Où en es-tu de ton apprentissage mathématique ? Maitrises-tu les bases de l'algèbre linéaire ? Si non, je te conseille de trouver un peu de doc à ce sujet ; si oui :

P est la matrice de transition. x est le vecteur état de doudou : chacun des x_i (comprendre la i-ème composante du vecteur) est la probabilité pour que doudou soit dans le i-ème état. Ainsi, [1 0 0] est le vecteur état disant : il est certain que là, doudou dorme (je reprends la même numérotation des états que sur la page wikipédia, dans l'ordre : copeaux, mangeoire, roue) ; [0 0,5 0,5] est le vecteur état disant, soit doudou mange, soit doudou cours (avec la même probabilité).

Maintenant, on attend une minute. Afin de connaître le vecteur état une fois la minute passée, on va appliquer (comprendre multiplier) notre vecteur par la matrice P.
Ainsi, le vecteur x' d'état après une minute est le produit du vecteur x et de P : x' = xP. En reprenant les valeurs de l'exemple de doudou,
http://upload.wikimedia.org/math/b/1...bb18bf1a58.png
Il y a 90% de chance que doudou dorme, 5% qu'il mange et 5% qu'il court !


On va maintenant attendre une minute de plus. On applique la même formule :
x" = x'P
Or, x' = xP
Donc, x" = (xP)P = xP².
On peut interpréter les résultats de la même manière.

Jusque là c'est clair ?

J'ai fait de l'algèbre linéaire mais j'en suis a mon quatrième rattrapage et ca c'est vraiment de la folie.

Je sais qu'on peut utiliser les matrices pour stoker des informations vectorielles ou des équation et qu'il y a des propriétés avec des matrices particulières et des calculs de solutions. Je suis capable d'appliquer une méthode sans fourberie(sans transformation d'expressions littérale) si on me dit les données d'entrée, de sortie et les tests/calculs détaillés a mener.

Jusque là c'est clair, je comprend.

Dans ce cas, tu comprendras la phrase extraite de la page que tu as donnée :

Citation:

---

La théorie montre qu'au bout d'un certain temps, la loi de probabilité est indépendante de la loi initiale.

---

Ainsi, si la suite vectoriellehttps://chart.googleapis.com/chart?c...20\mathbb%20N} admet une limite, elle ne dépend que de P et est déterminée par l'équation https://chart.googleapis.com/chart?c...=\,{\vec%20q}P.

Une simple résolution de système d'équation − qu'est celui formé par l'égalité précédente et celle tirée du fait que la somme des composantes de q est 1 − permet de déterminer analytiquement q. Et que représente q ?

Ca veux dire qu'au fil des multiplication par la matrice, la "loi initiale"(le vecteur état a t=0) a une influence de plus en plus négligeable, et donc le vecteur "etat" au temps 1,2,3... devient la "loi de probabilité" au temps infini.

Je ne vois pas clairement la différence(mathématique) entre les loi, les applications, les fonctions et les processus...

La suite vectorielle, j'en comprend que l'aspect "liste"/"tableau exel..."

Le dernier truc que je comprend c'est http://upload.wikimedia.org/math/6/d...b38be7ba70.png

Sois "recherche du vecteur etat pour t=beaucoup".

Ensuite pour sortir qP=q, il manque forcément un truc. je vois pas le lien entre la limite ci dessus et cette équation.

Je ne sais pas résoudre un système d'équation, mais je sais que c'est possible. Par contre quel systéme? Ca je comprend pas: "− qu'est celui formé par l'égalité précédente et celle tirée du fait que la somme des composantes de q est 1 −" 8O et pareil en math quant je vois apparaitre la matrice diagonale.

q dois étre la loi de probabilité.

Citation:

---

Envoyé par Denderk

Ca veux dire qu'au fil des multiplication par la matrice, la "loi initiale"(le vecteur état a t=0) a une influence de plus en plus négligeable, et donc le vecteur "etat" au temps 1,2,3... devient la "loi de probabilité" au temps infini.

---

Tout à fait.

Citation:

---

Envoyé par Denderk

Je ne vois pas clairement la différence(mathématique) entre les loi, les applications, les fonctions et les processus...

---

Tout ces concepts sont intimement reliés. Par exemple, une loi de probabilité peut être représentée par sa fonction de densité et décrire un processus que l'on met en application à des fins d'exercice ;). Pour plus de détails sur ces notions, je te conseillerais quelques recherches personnelles.

Citation:

---

Envoyé par Denderk

La suite vectorielle, j'en comprend que l'aspect "liste"/"tableau exel..."

---

Ok, pourquoi pas. Si tu comprends bien alors ce que représente une « ligne » de ton tableau excel.

Citation:

---

Envoyé par Denderk

Le dernier truc que je comprend c'est http://upload.wikimedia.org/math/6/d...b38be7ba70.png

Sois "recherche du vecteur etat pour t=beaucoup".

Ensuite pour sortir qP=q, il manque forcément un truc. je vois pas le lien entre la limite ci dessus et cette équation.

---

De l'expression http://upload.wikimedia.org/math/6/d...b38be7ba70.png à l'équation q=qP, il n'y a qu'un pas. [VULGARISATION]De la définition même de limite, on en déduit que si la limite q existe, alors le fait de multiplier q à droite par P est sans effet puisque la différence entre https://chart.googleapis.com/chart?c...{%28\infty%29} et https://chart.googleapis.com/chart?c...1%2B\infty%29} est nécessairement nulle [/VULGARISATION]. On se sert souvent de cette « technique » pour calculer la limite d'une suite naturelle définie récursivement.

Ensuite, le calcul de q est clairement détaillé dans la page Wikipedia. De q=qP on en déduit q(I-P)=0 (tu suis là ?) ; or I-P est connue. Je te renvoie alors à tes cours d'algèbre pour la résolution des équations de la forme AB=0.

Citation:

---

Envoyé par Denderk

Je ne sais pas résoudre un système d'équation, mais je sais que c'est possible. Par contre quel systéme? Ca je comprend pas: "− qu'est celui formé par l'égalité précédente et celle tirée du fait que la somme des composantes de q est 1 −" 8O et pareil en math quant je vois apparaitre la matrice diagonale.

---

Lorsque je parle de système d'équation, je parle de celui qui se cache sous l'équation matricielle q=qP. À cela, il faut ajouter que la somme des composantes de q vaut 1.

Citation:

---

Envoyé par Denderk

q dois étre la loi de probabilité.

---

Non, P est le meilleur candidat pour représenter la loi de probabilité (sans l'être − comme une fonction de densité n'est pas une loi de probabilité). q est plus, s'il existe, une moyenne. En reprennant les données du problème de doudou, http://upload.wikimedia.org/math/2/c...f3ddae71fb.png : n moyenne, le processus stochastique se trouvera 88,4% dans l'état 0, 4,42% dans l'état 1 et 7,18% dans l'état 2.


En espérant avoir aidé, cordialement,

J'ai revu les système, je pense que je saurais résoudre un système de 2 ou 3 équation genre ca: http://fr.wikipedia.org/wiki/Syst%C3...A9mentaires%29

L'usage des termes loi, application & co est spécifique au sein de chaque théorie/branche des math en gros.

Youp, merci, je comprend pourquoi qP=q, c'est bien la "technique" qu'il me manquais!

(Par contre, j'ai du mal a admettre que ca n'implique pas nécessairement q=0(vecteur nul) ou P=1(enfin identité) mais c'est parce que j'arrive pas me mettre en univers {|R;|R;|R} je pense)

Je ne comprend toujours pas les manipulations, mais je comprend qu'il s'agit d'une méthode de résolution de systèmes. On as quatre équation, trois dans la matrice(par la multiplication par (x,y,z)?) et une dans le postulat x+y+z=1.

Je me représente assez mal "intellectuellement" les matrice. Je ne vois pas comment passer du systéme a la matrice et inversement. Je ne comprend pas les propriété qui permette de faire apparaitre I (le les ai lu).

Merci beaucoup de ton aide.

J'ai édité mon message précédent pour y inclure l'explication manquante ... je supprimerai ce message une fois que tu en aura pris connaissance.