# TP 3 : Chaînes de Markov

Matteo STAIANO

## 1 Historique d’une navigation web

#### 1)

$\begin{pmatrix}0.5&0.3&0.2\\0.2&0.8&0\\0.3&0.3&0.4\end{pmatrix}$. La matrice n’est pas strictement positive car nous avons $M_{2,3} = 0$. En mettant la matrice au carré, nous obtenons : $\begin{pmatrix}0.37&0.45&0.18\\0.26&0.7&0.04\\0.33&0.45&0.22\end{pmatrix}$. La matrice de transitions est donc primitive, et par conséquent irréductible.

#### 2)

$M^t = \begin{pmatrix}0.5&0.2&0.3\\0.3&0.8&0.3\\0.2&0&0.4\end{pmatrix}​$. Nous avons :

0. $\begin{pmatrix}0\\1\\0\end{pmatrix}$
2. $M^t . \begin{pmatrix}0\\1\\0\end{pmatrix} = \begin{pmatrix}0.2\\0.8\\0\end{pmatrix}$.
3. $M^t . \begin{pmatrix}0.2\\0.8\\0\end{pmatrix} = \begin{pmatrix}0.26\\0.7\\0.04\end{pmatrix}$.
4. $M^t . \begin{pmatrix}0.26\\0.7\\0.04\end{pmatrix} = \begin{pmatrix}0.282\\0.65\\0.068\end{pmatrix}$.

#### 3)

Par résolution du système suivant :

$\begin{cases}a = 0.5a + 0.2b + 0.2c\\b = 0.3a+0.8b+0.3c\\c=0.2a+0.4c\\1=a+b+c\end{cases}$, nous obtenons $w = \begin{pmatrix}0.3\\0.6\\0.1\end{pmatrix}$.

#### 4)

$M^{10} = \begin{pmatrix}0.300195&0.599414&0.100391\\0.29987&0.600391&0.0997396\\0.300195&0.599414&0.100391\end{pmatrix}\\M^{20}=\begin{pmatrix}0.3&0.599999&0.1\\0.3&0.6&0.0999997\\0.3&0.599999&0.1\end{pmatrix}\\M^{100} = \begin{pmatrix}0.3&0.6&0.1\\0.3&0.6&0.1\\0.3&0.6&0.1\end{pmatrix}$

Il semble possible d’obtenir $w$ de façon approchée en élevant la matrice à une puissance très élevée et en multipliant ensuite celle-ci par un vecteur à 1 dimension, $\begin{pmatrix}1\\0\\0\end{pmatrix}$ par exemple.

## Génération aléatoire de texte

### Apprentissage de la chaîne de Markov

```python
def statistiques(s):
    out = [[0 for i in range(256)] for j in range(256)]
    for i in range(len(s) - 1):
        if ord(s[i]) <= 255 and ord(s[i + 1]) <= 255:
            out[ord(s[i])][ord(s[i + 1])] += 1

    return out


def matriceProbas(mat):
    out = [[0 for i in range(256)] for j in range(256)]
    for i in range(256):
        total = sum(mat[i])
        if total > 0:
            for j in range(256):
                out[i][j] = mat[i][j] / total

    return out
```

La fonction  `statistiques(s)` prend en paramètre la chaîne de caractères du livre et retourne une matrice représentant le nombre de fois qu’un caractère est suivi par un autre en particulier.

La fonction `matriceProbas(mat)` prend en paramètre la matrice générée par `statistiques()` et retourne la probabilité pour chaque caractère d’être suivi par un autre en particulier.

### Génération de texte

```python
def matriceProbasCumulees(mat):
    out = [[0 for i in range(256)] for j in range(256)]
    for i in range(256):
        tmp = 0
        for j in range(256):
            out[i][j] = mat[i][j] + tmp
            tmp = out[i][j]

    return out
```

La fonction `matriceProbasCumulees(mat)` prend la matrice de la fonction `matriceProbas(mat)` en paramètre et retourne la matrice des probabilités cumulées correspondant à notre texte.

Nous pouvons en profiter pour vérifier que les matrices générées sont bien stochastiques : la somme des probabilités sur chaque ligne de la matrice de probabilités est égale à 1 (ou 0 pour les caractères jamais présents dans le texte). De même, le dernier élément de chaque ligne de la matrice des probabilités cumulées est égal à 1 ou 0 (à une précision relative liée à l’arrondi automatique effectué par l’ordinateur, de l’ordre de $10^{-16}$).

```python
def successeur(mat, a):
    r = uniform(0, 1)
    for i in range(256):
        if r > P[ord(a)][i]:
            continue
        return chr(i)
```

La fonction `successeur(mat, a)` prend la matrice des probabilités cumulées et un état (une lettre) pour générer un successeur.

```python
def generationAleatoire(mat, init, n):
    out = ""
    tmp = init
    for i in range(n - 1):
        tmp = successeur(mat, tmp)
        out += tmp
    return out
```

La fonction `generationAleatoire(mat, init, n)` génère une chaîne de caractères de n caractères en générant à chaque fois le successeur de l’état actuel avec la fonction `successeur()`.

Nous observons que malgré l’improbabilité de générer des phrases compréhensibles, on reconnaît souvent la consonance de certaines langues.

`germinal.txt`

**maloiraint sanemeuse  e chenet lais
derchantoyait etoulluagene come l a hu isachoidesune blemen pe**

`lotr.txt`

**y    l. theal  l-
t d s  pane  gho he hix!  there as, 'rksoncefrnd  us Evindowed  A biefid withtod**

`goethe.txt`

**n Welsohtell din  scheichte omaunen vimm on l ellltsicheice PHIhen Amend)
 ierangsttegsaun dindich **

`quijote.txt`

**(smíalllalanide lguriónas cheso ntronco qulorice e po o,  de sotó con pujo (s a, las seizante**

### Extensions

Si on prend en compte les deux derniers caractères, il s’agit toujours d’une chaîne de Markov, cachée. En effet, l’état courant ne dépend que de l’état précédent, agrégation de deux caractères. Les états sont donc toutes les combinaisons de deux caractères.

```python
def statistiques(s):
    out = [[[0 for i in range(256)] for j in range(256)] for k in range(256)]
    for i in range(len(s) - 1):
        if ord(s[i]) <= 255 and ord(s[i + 1]) <= 255:
            out[ord(s[i])][ord(s[i + 1])][ord(s[i + 2])] += 1

    return out
```

La complexité augmente d’un degré en raison du rajout d’une 3e dimension au tableau. Nous passons donc de $o(n^2)$ à $o(n^3)$.