Discussion :

[melwin]

Bonjour,

Je suis un débutant en programmation et en reprise d'étude. J'ai beaucoup de mal à analyser et à convertir en algorithme.
Donc j'aurais besoin d'aide dans un premier temps pour m'orienter et ensuite éventuellement corriger ou améliorer le programme.
Ensuite, si quelqu'un connait une méthode pour apprendre justement à analyser ce que l'on souhaite programmer.

Je dois élaborer un petit programme en python qui simule une chaîne de Markov.
Le système est composé de 3 états. Il y a des probabilités identique de transitions entre chaque états.
Il y a aussi des probabilités de rester sur le même état.

Pour les variables:
- matrice: matrice 3*3 décrivant les probabilités de transition.
- tableau: distribution initiale, état de départ.
- Nombre : le nombre de pas à effectuer
Fonctions:
- Transition (etat,matrice) : prend l'état de la chaîne et retourne un état de la chaîne.
- probChange (matrice, tableau, nombre): calcule les fréquences de passage sur chacun des états pour obtenir les valeurs théoriques de la limite de la chaîne.

[php_faboul]

Bonjour,

Quel est le problème ?

[melwin]

Bonjour,

Quel est le problème ?

j'ai du mal à analyser les différentes fonctionnalités et à les décrire pour commencer.

Voilà comment je vois les choses:

Fonction1: prend en entrée "etat" de la chaine et fonction de la "matrice" retourne un nouvel "etat" de la chaîne.

Fonction2: enregistre le passage sur chaque 'etat' pour calculer les fréquences relatives de passages => passage/nombre

[fred1599]

C'est quoi un état?

Vous auriez pas plutôt un exemple?

[melwin]

Pour prendre un exemple classique, le tirage répété d'un dé (6 faces).

Chaque fois que l'on fait un tirage (transition) il y a une probabilité de retomber sur le même chiffre ou sur un autre chiffre (etat).

Pour info, la chaîne de Markov, c'est la suite des valeurs obtenues pendant les tirages.

Donc dans mon cas, il n'y a que 3 états.

Il me vient un exemple:
Régulièrement on consulte le thermomètre, la température ne change pas, elle monte ou elle descend.

Donc 3 états : monte, descend, change pas.

On se limite à un cas homogène. C'est à dire que la probabilité de se trouver à l'état Xn+1 à la consultation n+1 ne dépend que de l'état Xn à la consultation n mais pas de n. En gros on considère que la température est montée par rapport à la consultation précédente mais pas parce que c'est la 20ème consultations.

[fred1599]

La valeur lors de la consultation est aléatoire alors?

Si oui la température est comprise entre ... et ... ?

Nombre de consultations?

Selon le nombre de consultations, on peut utiliser de simples listes, il y en faut beaucoup pour utiliser numpy

Une fonction simple pour retourner ton état

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
def tester(actuel, suivant):
    if suivant > actuel : etat = "monte"
    elif suivant < actuel : etat = "descend"
    else: etat = "change pas"
    return etat

[ZZelle]

- Transition (etat,matrice) : prend l'état de la chaîne et retourne un état de la chaîne.
- probChange (matrice, tableau, nombre): calcule les fréquences de passage sur chacun des états pour obtenir les valeurs théoriques de la limite de la chaîne.

Que font exactement tes 2 fonctions ?
Transition calcule en partant de la n-ème distribution d'états (Dn, c'est le vecteur de probabilité des états) la suivante Dn+1 basé sur la transition définie dans la matrice de Markov M:
Dn+1 = transition(Dn, M) = Dn * M ?

probChange calcule la n-ème distribution à partir de la distribition initiale ? D'où
Dn = probChange(M, Do, n) ?

Sauf erreur tu auras du mal à calculer les limites de la chaîne avec ces 2 fonctions ... elles te permettront d'avoir un estimé ... il faudrait une fonction qui puisse calculer la limite d'une exponentiation (c'est le bon terme ?) de matrice pour calculer la limite (numpy c'est le faire ?)

[melwin]

Que font exactement tes 2 fonctions ?
Transition calcule en partant de la n-ème distribution d'états (Dn, c'est le vecteur de probabilité des états) la suivante Dn+1 basé sur la transition définie dans la matrice de Markov M:
Dn+1 = transition(Dn, M) = Dn * M ?

probChange calcule la n-ème distribution à partir de la distribition initiale ? D'où
Dn = probChange(M, Do, n) ?

Sauf erreur tu auras du mal à calculer les limites de la chaîne avec ces 2 fonctions ... elles te permettront d'avoir un estimé ... il faudrait une fonction qui puisse calculer la limite d'une exponentiation (c'est le bon terme ?) de matrice pour calculer la limite (numpy c'est le faire ?)

- Transition va effectivement à partir de la n-ième distribution d'états donner la suivante n+1. Alors comme c'est en fonction de pourcentage, il va falloir faire un random entre 0< X< 1 et le comparer aux valeurs de la matrice avec un
if ... <x
faire...
else


ProbChange va incrémenter la valeur du passage sur chaque état. Cette valeur sera divisée par le nombre de passage pour en donner la fréquence.

[ZZelle]

- Transition va effectivement à partir de la n-ième distribution d'états donner la suivante n+1. Alors comme c'est en fonction de pourcentage, il va falloir faire un random entre 0< X< 1 et le comparer aux valeurs de la matrice avec un
if ... <x
faire...
else

Pourquoi tu as besoin de faire un random ? Dn+1 est fonction de Dn (que tu as) et de M (que tu as), non ?

ProbChange va incrémenter la valeur du passage sur chaque état. Cette valeur sera divisée par le nombre de passage pour en donner la fréquence.

Pas compris, ce qu'est la valeur du passage.
Quand tu dis fréquence, tu veux dire probabilité ?

[melwin]

Pourquoi tu as besoin de faire un random ? Dn+1 est fonction de Dn (que tu as) et de M (que tu as), non ?


Pas compris, ce qu'est la valeur du passage.
Quand tu dis fréquence, tu veux dire probabilité ?

En fonction d'un etat tu as les probabilités données par la matrice.
Ensuite c'est aléatoire en fonction de ces probabilités. Je ne comprends pas ton Dn *M. J'ai l'impression que Dn et M c'est la même chose.


Pour la valeur de passage: prenons le nombre de transitions égal à 100. Après les 100 transitions, imaginons qu'il y a eu 60 stable, 10 baisse et 30 monte. Fréquence relative de stable 60/100 = 0.6, fréquence relative de baisse 10/100 = 0.1, fréquence relative de monte 30/100 = 0.3 .Ça donne effectivement des probabilités de se trouver à un des état à l'instant n.

[dividee]

Ensuite c'est aléatoire en fonction de ces probabilités. Je ne comprends pas ton Dn *M. J'ai l'impression que Dn et M c'est la même chose.

Ce n'est pas aléatoire si on travaille sur la distribution de probabilité des états au lieu de travailler sur les états concrets.
Pour illustrer Dn * M = Dn+1:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
                  [0.3, 0.4, 0.3]
[0.1, 0.8, 0.1] * [0.2, 0.6, 0.2] = [0.23, 0.56, 0.21]
                  [0.4, 0.4, 0.2]

Pour la valeur de passage: prenons le nombre de transitions égal à 100. Après les 100 transitions, imaginons qu'il y a eu 60 stable, 10 baisse et 30 monte. Fréquence relative de stable 60/100 = 0.6, fréquence relative de baisse 10/100 = 0.1, fréquence relative de monte 30/100 = 0.3 .Ça donne effectivement des probabilités de se trouver à un des état à l'instant n.

En travaillant comme cela par simulation, cela convergera aussi, mais beaucoup plus lentement...