Discussion :

[dividee]

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?

Désolé, mais là je suis un peu perdu. Je ne suis pas un expert en statistiques, j'ai seulement rencontré les chaînes de Markov auparavant. Je ne comprends pas les nuances entre ces différentes notions. Il me semble que la distribution stationnaire correspond aux "fréquences relatives de passage sur chacun des états". "L'état de la chaîne en sortie" je ne vois pas trop ce que c'est; de quelle sortie s'agit-il ?

[melwin]

T'inquiètes pas, pour moi aussi ce n'est pas évident.

On commence avec un état de départ et suivant les probabilités on passe par les différents états. A la nième itération on est sur l'état Xn.

[mont29]

La valeur de l’état Xn étant aléatoire (pondéré par l’état Xn-1), c’est bien ça*?

C’est ce que fait ce code*:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
def markov(mat, init, nbr=0, seed=0):
    """
    Generator yielding elements of Markov suite, given a (square) matrix of
    changes probabilities, and an initial state.
    Note: Here, states are assumed null or positive integers only!
    If nbr is a positive integer, yields only that number of elements, else
    yield infinitely.
    seed is used to initialize the random generator, so that you will always
    get the same suite if you give the same mat, init and seed.
    """
 
    # Initiate random generator.
    import random
    random.seed(seed)
 
    # This function returns the index in the weights table corresponding to
    # the range into which the uniform random value lays.
    # weights is assumed a list of length ordered elements, like that:
    #     [p1, p2, …, pn-1, 1.0]
    def _weighted_random(weights, length):
        val = random.random()
        # Note: this implements a dichotomous search, for fun...
        split = idx = length // 2
        while 1:
            split = max(1, split // 2)
            if val > weights[idx]:
                idx += split
            elif idx and val < weights[idx - 1]:
                idx -= split
            else:
                return idx
 
    # Builds a custom matrix, more suited than the raw one for our algo.
    # Also checks the given one is square!
    n = len(mat)
    _mat = [[0.0] * n for i in range(n)]
    for i, line in enumerate(mat):
        if len(line) != n:
            raise ValueError("Invalid probability matrix (line {}) is not "
                             "same length as matrix’s high ({})!"
                             "".format(i, n))
        tot = sum(line)
        sum_prob = 0.0
        for j, prob in enumerate(line):
            sum_prob += prob
            _mat[i][j] = sum_prob / tot
 
    # Now, _mat is in form [[0.2, 0.7, 1.0],
    #                       [0.4, 0.7, 1.0],
    #                       [0.3, 0.5, 1.0]]
 
    # Start yielding elements!
    # XXX States (elements) are assumed null or positive integers only, else
    # we would need a mapping to convert from their real value to/from numeric
    # indices...
    nbr_done = 0.0
    el = init
    yield el  # Generate also the init element!
    while nbr_done < nbr:
        # Get a new random element, weighted by the current one's
        # probabilities...
        el = _weighted_random(_mat[el], n)
        yield el
        nbr_done += 1
 
 
# Test code!
import time
 
mat = [[0.2, 0.4, 0.4],
       [0.5, 0.2, 0.3],
       [0.3, 0.3, 0.4]]
 
init_el = 0  # First state.
print(list(markov(mat, init_el, nbr=10, seed=time.time())))
 
init_el = 1  # Second state.
print(list(markov(mat, init_el, nbr=10, seed=time.time())))
 
init_el = 2  # Third state.
print(list(markov(mat, init_el, nbr=10, seed=time.time())))

[ZZelle]

Normalement il ne devrait pas y avoir besoin de générer des nombres aléatoires ... juste des multiplications de vecteur / matrices

en supposant que l'éat a 0, 1,2 soit à gauche, milieu, droite dans la matrice
markov(mat, 0, nbr) = [1, 0, 0 ] * M^nbr
markov(mat, 1, nbr) = [0, 1 ,0 ] * M^nbr
markov(mat, 2, nbr) = [0, 0 ,2 ] * M^nbr

[mont29]

Je ne vois pas comment se passer de nombres aléatoires*??? La multiplication matricielle permet simplement d’avoir la proportion “à l’infini” de chacun des états, pour un état de départ donné. Mais les états eux-même, ou plutôt leurs transitions, restent purement aléatoires, même si leurs probabilités varient…

Ou alors, j’ai manqué quelque chose*!

[melwin]

Je ne vois pas comment se passer de nombres aléatoires*??? La multiplication matricielle permet simplement d’avoir la proportion “à l’infini” de chacun des états, pour un état de départ donné. Mais les états eux-même, ou plutôt leurs transitions, restent purement aléatoires, même si leurs probabilités varient…

Ou alors, j’ai manqué quelque chose*!

Effectivement la multiplication matricielle donnera les probabilités empiriques de la distribution, les limites à l'infini.

Mais à chaque pas, le système se retrouve dans un des états.
Ce qui donne une suite d'états, la chaîne de Markov.

Si on fait plusieurs tests, on ne va pas avoir la même série puisque c'est lié à des probabilités. Mais il faut bien à chaque instant déterminer l'état, d'où le tirage aléatoire.

[dividee]

D'accord, c'est ce que j'appelais "procéder par simulation" dans mes posts précédent. Pour générer une chaîne de Markov, le code de mont29 convient parfaitement.