Markov Chain, calculer les probabilitées de transition

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Spudd
Messages: 1
Enregistré le: 08 Mai 2021, 03:25

Markov Chain, calculer les probabilitées de transition

par Spudd » 08 Mai 2021, 04:11

Bonjour à tous , j'essaye actuellement de résoudre le problème suivant:
Supposons que l'on vous donne une chaîne de Markov en temps discret composée des états 1, 2, 3 et 4 disposés dans une chaîne linéaire. Les probabilités d'être dans l'état 1 sont de 1/10, dans l'état 2 de 4/10 et dans l'état 3 de 2/10. Les transitions autorisées sont de 1 à 2 (et retour), de 2 à 3 et retour et de 3 à 4 et retour.

1 - Représentez graphiquement cette chaîne de Markov en utilisant des flèches pour indiquer les transitions d'état autorisées.
2 - Étiquetez les flèches avec les probabilités de transition qui réalisent les probabilités de l'état stable (steady state probability). Ecrivez les probabilités de transitions sous forme de fractions.
Utilisez la formule de Metropolis pour les calculer. Sous la visualisation du graphique, écrivez explicitement la formule que vous avez utilisée pour calculer la probabilité de transition de l'état 4 à l'état 3.


Afin de trouver la probabilité de transition j'ai appliquer la méthode de mon cours que voici:
Image

Calcul de l'acceptance :
Image

(Je sais que steady state probability représente les probabilités d'un état après un grands nombres d'itérations. Je sais comment le calculer avec l'algorythme Metropolis mais ce n'est pas ce qui est demandé ici.)

1 - Voici mon graph:
Image

J'ai rajouté la steady state probability pour l'état 4 qui est selon moi de 3/10. Est-ce correct ?

2 - J'ai essayer de calculer les probabilitées de transitions entre les états 1 => 2 et 2 => 1 (en suivant la méthode en screenshot):

J'ai calculer les acceptances pour les transitions entre états:
Image

Je ne comprends cependant pas le point numéro 2 de la méthode. Pourriez-vous me l'expliquer ou me mettre sur la voie ?

Merci pour votre aide et bonne journée :)



Vassillia

Re: Markov Chain, calculer les probabilitées de transition

par Vassillia » 09 Mai 2021, 01:12

Bonjour,
Je ne suis pas une experte en chaine de Markov (genre pas du tout) mais j'aime bien alors j'ai essayé l'exercice en faisant quelques recherches.

Avec une matrice de transition irréductible qui vérifie => , c'est à dire tout aller implique un retour, on peut définir une nouvelle matrice de transition qui simule la loi avec
si et sinon
les coefficients diagonaux sont choisis pour que la somme par ligne donne 1
Cette matrice est reversible donc la mesure est stationnaire et c'est gagné pour nous.

Bref, dans ton cas, tu ne connais pas la matrice donc on ne va pas s'embetter, on va en créer une qui fait l'affaire, on peut prendre n'importe laquelle tant qu'elle est correcte.
Pour simplifier et retomber sur ta formule sans avoir à faire attention à qui est le plus grand entre ou je prendrai pour probabilité1/2 partout en rajoutant une boucle sur 1 et sur 4 et cela devrait le faire. J'ai vérifié, la matrice que je calcule par la suite donne bien les probabilités voulues par l'exercice donc je ne me suis pas loupée dans mon raisonnement normalement.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Markov Chain, calculer les probabilitées de transition

par GaBuZoMeu » 09 Mai 2021, 11:37

Bonjour,

Je ne comprends absolument pas ce que Vassilia fait avec sa probabilité 1/2 partout.
Je ne connais pas l'"algorithme de Metropolis", mais son principe semble être d'équilibrer les échanges entre deux états pour garder la stabilité de la configuration. Ça ne marche certainement pas avec des 1/2 partout. Si on a un état 1 avec probabilité 1/10 et un état 2 avec probabilité 4/10, la probabilité de transition de 1 vers 2 doit être 4 fois plus grande que la probabilité de transition de 2 vers 1 pour assurer l'équilibre des échanges.

Après, il faut s'arranger pour que la somme des probabilités de transition sortantes à partir d'un état ne dépasse pas 1, bien sûr. Un moyen simple de faire ça est que la probabilité de transition de l'état A vers l'état B soit égale à la probabilité de B, et la probabilité de B vers A égale à la probabilité de A.
Modifié en dernier par GaBuZoMeu le 09 Mai 2021, 12:05, modifié 1 fois.

Vassillia

Re: Markov Chain, calculer les probabilitées de transition

par Vassillia » 09 Mai 2021, 12:03

Mais, mais... c'est normal que la matrice Q ne soit pas la bonne puisqu'il faut la transformer en la matrice P avec la formule de Metropolis.

La matrice Q c'est ce dont il a besoin à l'étape 2, il multiplie chaque coefficient par la probabilité de l'acceptation de l'étape 1. On peut sûrement faire autrement mais j'ai essayé le plus possible de me rapprocher de son cours.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Markov Chain, calculer les probabilitées de transition

par GaBuZoMeu » 09 Mai 2021, 12:15

Vassilia, où vois-tu une matrice Q et une matrice P dans l'énoncé ?

Ce que je comprends de l'énoncé, qui ne me paraît pas très clair (est-ce vraiment l'énoncé original ???) :

On a le graphe qui indique les possibilités de transition entre états. Ça, OK. On indique pour chaque état des probabilités, et on veut trouver une matrice de transition telle que cette configuration donnée soit une configuration stable pour la chaîne de Markov.

Vassillia

Re: Markov Chain, calculer les probabilitées de transition

par Vassillia » 09 Mai 2021, 12:33

D'accord, je ne vois pas de matrice P et Q dans l'énoncé, tu as raison. Par contre, je vois que d'après son cours, il veut multiplier une probabilité d'acceptation (en version simplifiée) avec un coefficient dans le point 2. Je dis juste que ce coefficient peut être systématiquement 1/2 et il me semble que cela répond à sa question. Sinon, je comprends exactement l'énoncé comme toi et sauf erreur de ma part, c'est ce que donne la méthode.

Vassillia

Re: Markov Chain, calculer les probabilitées de transition

par Vassillia » 09 Mai 2021, 13:56

J'essaye d'expliquer autrement, je reconnais volontiers que je ne suis pas claire vu que je suis en mode découverte et que je suis repartie d'une formule théorique pour essayer de comprendre ce qu'est la formule de Metropolis.

La probabilité d'acceptation telle que définie dans l'exercice, c'est l'inverse du rapport dont parle GaBuZoMeu et je suis bien d'accord qu'il faut l'obtenir.
Mais on peut s'arranger autrement pour que la somme des probabilités sortantes soient inférieure ou égale à 1.
Il suffit de multiplier toutes les probabilités d'acceptation par un coefficient qui va bien. Ce coefficient peut par exemple être choisi pour rendre "réglementaire" la chaine de markov en le mettant partout.

Pourquoi ?
Et bien parcequ'ensuite on multiplie ce coefficient par la probabilité d'acceptation ce qui le laisse tel quel dans un sens et le fait diminuer dans l'autre sens de sorte à obtenir le rapport désiré. Quand la somme des probabilités sortantes ne vaudra plus 1, il suffira de boucler sur l'état et de rajouter ce qui nous manque.

C'est mieux ?

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

Re: Markov Chain, calculer les probabilitées de transition

par beagle » 15 Mai 2021, 16:27

Puisque tu cherches en foutant le bordel à faire fermer les fils de discussions,
on pourrait peut-être essayer dans tes fils de discussions à toi
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

Re: Markov Chain, calculer les probabilitées de transition

par beagle » 15 Mai 2021, 16:28

"Il suffit de multiplier toutes les probabilités d'acceptation par un coefficient qui va bien"

je ne comprends pas pourquoi il faut multiplier,
dans les chaines de Markov c'est pas plus simple d'additionner?
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

Re: Markov Chain, calculer les probabilitées de transition

par beagle » 15 Mai 2021, 16:29

Vassilia, où vois-tu une matrice Q et une matrice P dans l'énoncé ?

Ce n'est pas l'inverse une matrice PQ pour torcher l'exo?
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

Re: Markov Chain, calculer les probabilitées de transition

par beagle » 15 Mai 2021, 16:29

"Avec une matrice de transition irréductible "

pourquoi est-elle irréductible, on ne comprend pas bien
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

Re: Markov Chain, calculer les probabilitées de transition

par beagle » 15 Mai 2021, 16:31

Vassillia tu te souviens du chantage si on ne retire pas les propos de beagle je me casse du site maths forum,
ce qui a bien sur fait fermer mon fil de discussion par sa majesté et tu as atteint ton but.
Mais c'est pas honnète cette attitude,
tu es allée à confesse depuis?
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

Re: Markov Chain, calculer les probabilitées de transition

par beagle » 15 Mai 2021, 16:32

Ils sont où les VAM , chombier et lycéen,
faut pas hésiter à poser des questions
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Vassillia

Re: Markov Chain, calculer les probabilitées de transition

par Vassillia » 15 Mai 2021, 21:01

Je savais que je pouvais compter sur toi pour continuer à m'amuser ! Tu es la valeur sure du forum de ce point de vue :hehe:
D'une part, ce n'est pas mon fil, j'ai répondu à une question d'étudiant pour rendre service et car l'exercice m'intéressait, tu peux le faire fermer en trollant, cela ne me dérange pas.
D'autre part, tes questions sur le fond ne me gênent pas, j'y répondrai surement si j'avais le moindre espoir que tu y comprennes quelque chose mais ce n'est pas le cas. Note que j'ai répondu aux remarques précédentes qui étaient constructives et pertinentes même si à première vue nous n'étions pas d'accord.
Et enfin j'assume tout à fait mon attitude envers toi, je te donne un scoop, cela ne va pas s'arranger, bien au contraire, ma bienveillance a des limites, tu les as largement dépassé. Je n'hésiterai pas à me moquer de toi ouvertement chaque fois que tu diras n'importe quoi.
A la prochaine.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Markov Chain, calculer les probabilitées de transition

par lyceen95 » 16 Mai 2021, 00:02

Les probabilités 1/10, 4/10, 2/10 et 3/10 représentent quoi ?

Une position de 'stabilité' ? Sur 10 étapes, il y en aurait en moyenne 3 pendant lesquelles le 'jeton' serait à l'emplacement 4 ?
Sauf que c'est impossible.
A chaque fois que le jeton est à l'emplacement 4, juste avant et juste après, il est à l'emplacement 3. Il est donc plus souvent à l'emplacement 3 qu'à l'emplacement 4.
Incompatible avec les probas 2/10 pour l'emplacement 3 et 3/10 pour l'emplacement 4.

Mystère.

Même avec les probabilités 1/10, 4/10, 3/10 et 2/10, le problème n'a pas de solution.

Vassillia

Re: Markov Chain, calculer les probabilitées de transition

par Vassillia » 16 Mai 2021, 00:59

Les probabilités dont tu parles représentent les probabilités d'être dans chaque état et on veut que ces probabilités soient stables. Le jeton est nul part en fait, il est potentiellement dans chaque état avec la probabilité donnée et on regarde comment vont évoluer ces probabilités.

On a probablement perdu définitivement le demandeur donc je me permets de mettre la solution, voici la chaine que l'on trouve par la formule de Metropolis imposée par son cours
Image
C'est valable :
Etat 1 :
Etat 2 :
Etat 3 :
Etat 4 :

Mais je mets quand même celle que l'on trouve avec la version de GaBuZoMeu, ce qu'il propose est nettement plus pratique et intuitif
Image
C'est évidemment valable aussi :
Etat 1 :
Etat 2 :
Etat 3 :
Etat 4 :

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Markov Chain, calculer les probabilitées de transition

par lyceen95 » 16 Mai 2021, 01:49

Je pensais qu'on n'avait que les 6 flèches du premier schéma.. et ça ne collait pas.
Si on a en plus des flèches d'un point vers lui même, ça roule.

Et si on a trouvé ces 2 solutions, il me semble que toute combinaison linéaire de ces 2 solutions sera aussi une solution ?

Vassillia

Re: Markov Chain, calculer les probabilitées de transition

par Vassillia » 17 Mai 2021, 00:24

Oui, pour moi, tant que la somme de tes constantes vaut 1, il ne devrait pas y avoir de problème mais on peut donner directement la forme générale

Si on considère la distribution de probabilité à obtenir, on peut prendre n'importe quelle matrice de transition qui vérifie avec la somme des probas sortantes qui vaut 1 c'est à dire
Pourquoi ?
Pour tout état avec une probabilité
A l'étape suivante, on aura la probabilité

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 14 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite