Discussion :

[fred1599]

Ah, je comprend plus rien

T'aurais pas plutôt un algo sous la main?

Tu n'aurais pas un énoncé d'exercice?

Parce-que là on a vraiment du mal à te suivre...

[melwin]

Pour l'algorithme c'est justement mon problème, j'ai du mal à partir d'un énoncé à faire une analyse.

Pour l'énoncé d'exercice, l'exemple donné avant correspond bien:

C'est le calcul de la distribution stationnaire d'une chaîne de Markov (probabilité vers laquelle converge la suite de variables aléatoire définissant la chaîne).

Sur un thermomètre, les températures peuvent monter, rester stable ou descendre.
- Le premier relevé est stable.
- si le relevé n est stable, le relevé n+1 restera stable avec la probabilité p, baissera ou montera avec la probabilité q.
- si le relevé n monte , le relevé n+1 montera avec la probabilité p, baissera ou sera stable avec la probabilité q.
- si le relevé n baisse, le relevé n+1 baissera avec la probabilité p, montera ou sera stable avec la probabilité q.

Donc c'est une chaîne de Markov : c'est l'évolution au cours du temps d'une Variable X qui peut prendre un nombre fini d'états X = x1, X = x2, ... X = xn et qui passe de l'état xi à l'instant t à l'état xj à l'instant suivant t+1 avec une probabilité pij. Donc la chaîne de Markov est définie par l'espace d'états
S = {x1, x2,...,xn}
et par la matrice de transition (passage)

Code :

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

1
2
3
4
5
 
                              | P11, P12, ..., P1n |
P = pij 1<i<n, 1<j<n = | P21, P22 , ..., P2n |
                              | ...                      |
                               |Pn1, ...          , Pnn|

C'est pour cela que c'est pas facile a expliquer, je suis pas à l'aise en développement et je ne suis pas non plus expert en probabilité et processus stochastique.

Pour le programme on définit des valeurs pour les probabilité qui seront dans la matrice.

[fred1599]

Le seul truc où je buggais en maths c'était les probas, d'ailleurs pour moi c'est pas des maths

Voilà les questions qui permettront d'avancer.

1) Comment tu connais les probabilités p ou q?
2) Tu as 3 états donc une simple liste comme [stable, stable, monte, stable, descend, ...] suffirait non comme résultat?
3) Comment tu calcules la valeur (n+1) si tu connais (n), concrètement?

Ce lien peut aider ?

[melwin]

Donc je me trouve entre les deux, j'ai du mal à en tirer un algorithme et en même temps à écrire le programme correspondant.

Cela serait du genre:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
main
matrice = [[0.3,0.35,0.35][0.3, 0.35, 0.3][0.3,0.3,0.35]] # détermination des probabilité dans la matrice
tableau = ['baisse', 'stable', 'monte'] # détermination des états
Changemnt ('stable' , 100)   # on définit l'état de départ et le nombre par défaut de passage
 
def probChange   # là je suis un peu perdu pour savoir comment procéder
frequence[etat] # on définit la fréquence des états
...
frequence [etat] +=1/nbre de passage    # on calcule la fréquence relative
 
def transition
liste[]
for valeur in valeurEtat (etat): # suivant l'état on récupère
    liste.append [ etat, valeur ] # les valeurs de la matrice
 
var1 = random()
var2= 0.0
for index in range(len(liste)):
    if var2+liste[2]>var1: # si var1 est dans [0 , 0.3)
        return liste[1]        # on passe à l'état baisse
    elif var2 += liste[4]>var1: # si var1 est dans [0.3 , 0.65)
        return liste[3]         # on passe à l'état stable
    else                               # sinon var1 est dans [0.65 , 1)
        return liste[5]           # on passe à l'état monte

[fred1599]

je comprend de nouveau plus rien

Si tu ne réponds pas à mes questions ça va être dur...

Comment concrètement tu passes d'un état à un autre?

Tu as ta matrice de probabilité

Comment dans ton tableau il peut passer de l'état baisse à stable? (formule simple en fonction de n et n+1?)

Ce lien peut aider ?

Ton code ne m'aide pas, parce-que

1) Il est pas indenté, donc illisible
2) valeurEtat, je ne sais pas d'où il vient et ce qu'il contient (même si on devine)

[melwin]

Le seul truc où je buggais en maths c'était les probas, d'ailleurs pour moi c'est pas des maths

Voilà les questions qui permettront d'avancer.

1) Comment tu connais les probabilités p ou q?
2) Tu as 3 états donc une simple liste comme [stable, stable, monte, stable, descend, ...] suffirait non comme résultat?
3) Comment tu calcules la valeur (n+1) si tu connais (n), concrètement?

Ce lien peut aider ?

T'inquiètes pas, les proba n'ont jamais été mon truc non plus. Mais comme je fais un master II (à distance en plus) je suis obligé de m'en taper.

1) les probabilités p et q on va les choisir. Après on pourra jouer dessus, si on souhaite avoir un graphe bien particulier.

2) oui je pense. Mon niveau en programmation est très limité, je n'ai pas encore complétement intégré cette logique et je ne connais pas toutes les possibilités du langage.

3) La valeur n+1 ne dépend que de l'état n. En fonction de cet état tu as les probabilités de passer à l'état n+1.

[melwin]

je comprend de nouveau plus rien

Si tu ne réponds pas à mes questions ça va être dur...

Comment concrètement tu passes d'un état à un autre?

Tu as ta matrice de probabilité

Comment dans ton tableau il peut passer de l'état baisse à stable? (formule simple en fonction de n et n+1?)

Ce lien peut aider ?

Ton code ne m'aide pas, parce-que

1) Il est pas indenté, donc illisible
2) valeurEtat, je ne sais pas d'où il vient et ce qu'il contient (même si on devine)

On est en décalage, le temps que je réponde ...

je vais étudier le lien

Il faut lire la matrice comme ça: On fixe que la première ligne va correspondre à baisse, la seconde stable et la troisième à monte.
Quand on regarde la première ligne on peut dire que quand on est à l'état baisse on a :
x% que cela continue de baisser(première valeur)
y% que cela devienne stable (seconde valeur)
z% que cela monte (troisième valeur)

Si par exemple ça monte, le coup d'après on lira la 3ème ligne qui correspond à l'état monte, la première valeur correspond toujours à % baisse, seconde % stable et troisième % continue de monter.


1) il n'est pas identé car je me casse les dents...

2) Là c'est dur pour moi. Donc on passe à l'instant t à l'état n. On récupère les probabilités de changement pour l'état n+1 et à quel état cela correspond.

[fred1599]

x% que cela continue de baisser(première valeur)
y% que cela devienne stable (seconde valeur)
z% que cela monte (troisième valeur)

Oui mais ça par calcul tu ne peux pas le faire, ou je me trompe...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
from random import choice
 
valeurEtat = ["stable", "monte", "descend"]
 
liste = [choice(valeurEtat) for i in xrange(20)]
 
# ['monte', 'monte', 'monte', 'descend', 'descend', 'stable', 'stable', 'descend', 'descend', 'descend', 'stable', 'monte', 'stable', 'stable', 'monte', 'descend', 'monte', 'stable', 'descend', 'descend']
 
f_monte = liste.count('monte')/float(len(liste))
print f_monte # 0.45
 
# etc...

Tout simplement non?

[melwin]

Oui mais ça par calcul tu ne peux pas le faire, ou je me trompe...

C'est pour cela que on doit faire un random et le comparer au pourcentage.

[fred1599]

C'est pour cela que on doit faire un random et le comparer au pourcentage.

Donc... tu as ce qu'il faut, ou tu as encore des questions?

Tu as regardé le lien?

[melwin]

Je suis en train d'étudier le lien.

Il y a encore une partie un peu floue pour moi.
La partie incrémente le nombre de passage à l'état monte par exemple et le calcul de la fréquence relative de cet état.

[fred1599]

Le calcul de la fréquence je l'ai montré dans mon précédent code

Code :

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

f_monte = liste.count('monte')/float(len(liste))

le nombre d'états

Code :

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

n_etats = liste.count('monte') # compte le nombre de 'monte'

[mont29]

J’espère que je ne vais pas encore embrouiller c’t’histoire…

Voilà l’algo schématisé, tel que j’ai compris les choses*:

données en entrée
* Une matrice de probabilité de changements d’états, de taille n×n, n étant le nombre d’états possibles.
* Un état de départ, appelons-le e(0)

processus itératif

Posons que la ligne de la matrice correspondant au nième état e(n) est [p1, p2, …, pm], p1 étant la probabilité de passer à la valeur d’état 1, p2, celle de passer à la valeur d’état 2, etc.
e(n+1) = (p1% de chances d’être l’état 1, p2% de chances d’être l’état 2, … pm% de chances d’être l’état m)

En clair, e(n+1) n’est lié à e(n) que par le tableau de probabilités (la ligne de la matrice) correspondant à la valeur de e(n)

Bon, en écrivant ça, je me rends compte que ce n’est effectivement pas évident à expliquer de manière simple… Par contre, la programmation du truc n’est franchement pas compliquée (j’ai un code dispo, générique (c-à-d fonctionnant avec n’importe quel nombre d’états) dispo (sans numpy), je le mettrai si vous voulez… Mais amha, une fois compris qu’il faut utiliser le module random, le reste vient tout seul.

[melwin]

J’espère que je ne vais pas encore embrouiller c’t’histoire…

Non, non! Merci de ton intervention.

Ton explication est plutôt pas mal je trouve, car effectivement ce n'est pas une simple affaire.

Ensuite pour numpy, je fais le mec qui connais, mais j'ai cherché, fouillé, étudié du code et je ne comprends pas toujours tout pour l'instant. Alors du coup je fais pareil sans être sûr de ce que j'avance. je ne connais donc pas bien le module numpy...

[melwin]

Le calcul de la fréquence je l'ai montré dans mon précédent code

Pour la fréquence, j'étais justement sur la partie construire un histogramme à l'aide d'un dictionnaire, dans le livre pour apprendre à programmer en python

Code :

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

1
2
3
4
 
frequence {}
for n in machinbidule():
    frequence [n]+= 1/nbrpassage

[fred1599]

python c'est bien

Code :

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

1
2
3
4
5
6
7
>>> from collections import Counter
>>> from random import choice
>>> valeurEtat = ["stable", "monte", "descend"]
>>> liste = [choice(valeurEtat) for i in xrange(20)]
>>> freq = Counter(liste)
>>> freq
Counter({'monte': 8, 'descend': 7, 'stable': 5})

[mont29]

Je suis désolé, mais j’ai vraiment l’impression que vous compliquez beaucoup les choses…

Voici comment j’ai procédé pour créer un itérateur yieldant les états d’une suite de Markov, en partant d’un état de départ et d’une matrice de probabilités de transitions*:

* D’abord, créer à partir de la matrice d’entrée une matrice modifiée, plus adaptée à la génération pondérée de valeurs (états) aléatoires, qui contienne pour chaque ligne une liste de n valeurs croissantes, telle que la dernière valle 1.0. Autrement dit, transformer par exemple

Code :

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

1
2
3
[[0.2, 0.5, 0.3],
 [0.3, 0.3, 0.4],
 [0.4, 0.5, 0.1]]

en

Code :

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

1
2
3
[[0.2, 0.7, 1.0],
 [0.3, 0.6, 1.0],
 [0.4, 0.9, 1.0]]

Ensuite, je génère un nombre aléatoire entre 0.0 et 1.0 (random.random()), et avec une fonction de recherche par dichotomie, je retourne l’indice (donc l’état) dont la valeur est la plus proche par le bas. Et voilà, j’ai mon état n+1, et c’est reparti pour un tour…

Ainsi, pour la première ligne (qui correspond à l’état 0), j’ai 20% de chances de rester à l’état zéro (nombre aléatoire entre 0.0 et 0.2), 50% de chances de passer à l’état 1 (nombre aléatoire entre 0.2 et 0.7), et 30% de chances de passer à l’état 2 (nombre aléatoire entre 0.7 et 1.0).

Ce processus est de plus très facilement généralisable à n états quelconques (avec une matrice carrée n×n).

PS: si l’on veut d’autres valeurs d’état que 0, 1, 2, etc., il suffit d’ajouter (et d’utiliser) un mapping valeur_réelle_détat <=> nombre…

[dividee]

Je ne pense pas que c'est un très bon exercice pour apprendre à programmer en Python, étant donné qu'il cumule la difficulté de la programmation et la compréhension mathématique des chaines de Markov.

Si le but est de déterminer la distribution stationnaire de la chaîne de Markov, la simulation (avec random()) est une manière très inefficace de la déterminer; c'est 100000 fois plus rapide de calculer la distribution directement.

Si je reprends la matrice de mont29:

Code :

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

1
2
3
    [[0.2, 0.5, 0.3],
M =  [0.3, 0.3, 0.4],
     [0.4, 0.5, 0.1]]

Supposons que l'état initial est le premier état; cela peut être représenté par la distribution suivante:

Code :

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

D0 = [1.0, 0.0, 0.0]

L'état suivant aura la distribution suivante D1 = D0 * M.
C'est une multiplication matricielle:

Code :

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

1
2
3
                  [0.2, 0.5, 0.3]
[1.0, 0.0, 0.0] * [0.3, 0.3, 0.4] = [0.2, 0.5, 0.3]
                  [0.4, 0.5, 0.1]

Cela indique qu'il y a 20% de chances que ce soit l'état 1, 50% que ce soit l'état 2 et 30% que ce soit l'état 3.
On peut itérer cette opération D2 = D1 * M

Code :

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

1
2
3
                  [0.2, 0.5, 0.3]
[0.2, 0.5, 0.3] * [0.3, 0.3, 0.4] = [0.31, 0.4, 0.29]
                  [0.4, 0.5, 0.1]

Donc D2 = [0.31, 0.4, 0.29]

Avec 10 itérations comme cela, j'obtiens:

Code :

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

D10 = [0.29861096960000016, 0.41666662400000015, 0.2847224064000001]

Ce qui donne une meilleure estimation de la distribution stationnaire que de générer une chaîne de Markov de 1000000 d'états...

Et encore c'est une implémentation naïve, vu que cela revient à calculer
Dn = D0 * M^n où n est le nombre di'térations.

Avec numpy c'est trivial

Code :

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

1
2
3
4
5
6
7
8
9
10
import numpy as np
from numpy.linalg import matrix_power
 
M = np.array([[0.2, 0.5, 0.3],
             [0.3, 0.3, 0.4],
             [0.4, 0.5, 0.1]])
 
D = np.array([1.0, 0.0, 0.0])
 
print "distribution stationnaire =", np.dot(D, matrix_power(M, 100))

Résultat:

Code :

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

distribution stationnaire = [ 0.29861111  0.41666667  0.28472222]

n = 100 est déjà plus que suffisant pour atteindre la limite de précision des floats, mais faire le calcul pour n=1000000000 n'est pas sensiblement plus lent, l'exponentiation de matrices étant une opération rapide.

[edit]: en jetant un coup d'oeil sur wikipédia, je vois qu'il y a une solution analytique (sauf cas "pathologiques"):

Code :

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

1
2
3
4
# à la suite suite du code précédent
from numpy.linalg import pinv
 
print "analytiquement: ", pinv(np.hstack((np.eye(3) - M, np.ones((3,1)))))[-1]

[melwin]

Je ne pense pas que c'est un très bon exercice pour apprendre à programmer en Python, étant donné qu'il cumule la difficulté de la programmation et la compréhension mathématique des chaines de Markov.

Pour commencer, merci de ton intervention.

Je pense aussi que c'est un peu hard pour commencer avec ça. Il faut dire que je n'ai pas trop le choix puisqu'on me le demande pour mon cours de Processus Stochastique et simulation.

Heureusement qu'en parallèle j'avais commencé à me familiariser avec le langage python. Je n'en suis qu'au début, mais là j'ai du coups abordé des notions plus poussées.

Je trouve, pour avoir été rebuté par plusieurs tentatives de me mettre à la programmation (PHP, JAVA), que Python est plutôt pas mal pour commencer.

[melwin]

Supposons que l'état initial est le premier état; cela peut être représenté par la distribution suivante:

Code :

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

D0 = [1.0, 0.0, 0.0]

L'état suivant aura la distribution suivante D1 = D0 * M.
C'est une multiplication matricielle:

Avec 10 itérations comme cela, j'obtiens:

Code :

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

D10 = [0.29861096960000016, 0.41666662400000015, 0.2847224064000001]

Ce qui donne une meilleure estimation de la distribution stationnaire que de générer une chaîne de Markov de 1000000 d'états...

Et encore c'est une implémentation naïve, vu que cela revient à calculer
Dn = D0 * M^n où n est le nombre di'térations.


n = 100 est déjà plus que suffisant pour atteindre la limite de précision des floats, mais faire le calcul pour n=1000000000 n'est pas sensiblement plus lent, l'exponentiation de matrices étant une opération rapide.

Effectivement ça semble plus simple. Pour la trivialité, mes connaissance ne me permettent pas d'en juger.

Alors en procédant de la sorte on obtient les probabilités empiriques de la distribution. Quel est l’état de la chaîne en sortie et les fréquences relative de passage sur chacun des états?