---
tags: OPERA, joffrey.chambon
title: RO stochastique Cours 2
---

# Chaîne de Markov
Système observé à des instants discrets
$t = k\tau$, le système est dans un état
chaîne -> liste des états observés
chaîne de Markov -> mécanisme de "transition" -> matrice M

$p_{ij}$ = proba, si le sys est dans l'état i à $t = k\tau$, que le syst passe dans l'état j à $t=(k+1)\tau$

**Régime transitoire** : on s'intéresse aux premiers instants

à $t=k\tau$ -> $\prod _{k} =$ $\begin{bmatrix}\prod _{k}^A & ... & \prod _{k}^E\end{bmatrix}$

$\prod_k^A$ = proba syst état A à $t=k\tau$

à t = 0, état connu on connaît M, on peut calculer $\prod_k$ $\forall k$

$\prod_k = (\prod_{k-1}) * M, k=1, \prod_k= (\prod_0)*M^k$

## Régime permanent
Condition : $\lim_{k \to +\infty} \prod_k$

Si cette limite existe, et si elle est indépendante de l'état initial, la chaine de Markov est **ergodique**

Pour la matrice d'exemple : 5 états intiaux probables

* Animal en A :
* $\prod_0 = \begin{bmatrix}1 & 0 & 0 & 0& 0\end{bmatrix}$
* $\prod_1 = \begin{bmatrix}0.2 & 0.5 & ...\end{bmatrix}$
* Animal en B :
* $\prod_0 = \begin{bmatrix}0 & 1 & 0 & 0& 0\end{bmatrix}$
* $\prod_1 = \begin{bmatrix}0 & 1 & 0 & 0& 0\end{bmatrix}$
* $\prod_{+\infty} = \begin{bmatrix}0 & 1 & 0 & 0& 0\end{bmatrix}$
...
* Animal en E :
* $\prod_0 = \begin{bmatrix}0 & 0 & 0 & 0& 1\end{bmatrix}$
* ne converge pas vers la limite de B, donc non ergodique

## Conditions suffisantes d'ergodicité
3 conditions :
* Le graphe est fini
* Le graphe est fortement connexe
* Le graphe contient au moins une boucle

:::warning
Le graphe peut être ergodique sans vérifier ces conditions puisqu'elles ne sont pas nécéssaires
:::

Graphe de transition :
* sommets -> états
* arcs -> transition i($k\tau$)->j($(k+1)\tau$)
* valuation -> $p_{ij}$

Ici, les 3 conditions suffisantes d'ergodicité ne sont pas vérifiéés, la condition 2 n'est pas vérifiée, donc on ne peut pas conclure
Ici, on a conclu en examinant le cas particulier de la $2^{ème}$ colonne

## Application plus simple
* 3 compartiments : C,D,E


$M = \begin{bmatrix}0.3 & 0.4 & 0.3\\ 0.3 & 0.7 & - \\ 0.4 & - & 0.6\end{bmatrix}$
avec CDE pour lignes et colonnes

Les 3 conditions suffisantes sont vérifiées donc $\prod_{\infty}$ existe

### Calcul du vecteur $\prod_{\infty}$ lorsque la chaîne de Markov est ergodique
$\prod_{k} = (\prod_{k+1}) * M$

$\prod_{\infty} = \prod_{\infty} * M$
$\sum_i \prod_{\infty}^i = 1$

sachant que :
* $\prod_{\infty}^C = c$
* $\prod_{\infty}^D = d$
* $\prod_{\infty}^E = e$

$\prod_{\infty} = \begin{bmatrix}\prod_{\infty}^C & \prod_{\infty}^D & \prod_{\infty}^E\end{bmatrix} = \begin{bmatrix}\prod_{\infty}^C & \prod_{\infty}^D & \prod_{\infty}^E\end{bmatrix} * \begin{bmatrix}0.3 & 0.4 & 0.3\\ 0.3 & 0.7 & - \\ 0.4 & - & 0.6\end{bmatrix}$

on a donc un système :
$c = 0.3*c + 0.3*d + 0.4*e$
$d = 0.4*c + 0.7*d$
$e = 0.3*c + 0.6*e$

$\prod_{\infty} = \begin{bmatrix}c & d & e\end{bmatrix} = \begin{bmatrix}12/37 & 16/37 & 9/37\end{bmatrix}$

### Interprétation

#### Interprétation ponctuelle
Si on observe le système à n'importe quel moment au sein du régime permanent :
* la proba d'observer l'animal en C est de 12/37 et ceci quel que soit l'instant d'observation

On peut parler de "disparition du hasard" ou **stabilisation macroscopique**

Régime transitoire -> **agitation microscopique**, ssi la chaîne de Markov est ergodique il y a une **stabilisation macroscopique** avec le régime permanent

#### Interpétation statistique
On observe l'animal toutes les secondes pendant 1 heure, on a donc 3600 "photos", on peut alors trier les photos :
* photos de type C
* photos de type D
* photos de type E

On devrait alors avoir la réparition suivante :
* 12/37
* 16/37
* 9/37

Si on réitère l'expérience, on devrait obtenir à peu près les mêmes proportions

## 2ème Application (p114)
Un garagiste parisien, dispose de 4 véhicules loués à la journées.
Chaque véhicule loué peut tomber en panne avec une proba $p$ et une proba de non-panne $p=q-1$
Le garagiste peut faire 1 seule réparation par journée
$\tau$ = 1 journée

Demande supérieure à l'offre

Le garagiste ne loue des véhicules que si il y a au moins 2 véhicules en état de marche au début de la journée.

### Q1 : Modéliser le fonctionnement à l'aide d'une chaîne de Markov

Besoin de modifier le problème réel pour l'adapter en chaîne de markov : système considéré, $\tau$, états possibles à $t=k\tau$, matrice de transition M, graphe de transition

* états : nb de véhicule qui marchent en début de journée
* 4 états : A(1), B(2), C(3), D(4) -> impossible d'avoir 4 véhicules en panne
* Matrice :
* 1ère ligne de M : hypothèse à $t=k\tau$, système dans l'état A, pas de location , le vendeur répare 1 véhicule durant la journée, 1 possiblité
* 2ème ligne de M : hypothèse à $t=k\tau$, système dans l'état B. 3 possiblité :
* 0 panne : $q²$
* 1 panne : $2pq$, facteur 2 : nombre de manière pour que le véhicule tombe en panne
* 2 pannes : $p²$
* 3ème ligne de M : état C -> 3 véhicules marchent et ils sont loués. 4 possibilités :
* 0 panne : $q^3$ (D)
* 1 pannes : $C_3^1 pq² = 3pq²$ ( C )
* 2 pannes : $C_3^2 p²q = 3p²q$ (B)
* 3 pannes : $p^3$ (A)
* 4ème ligne de M : état D -> 4 véhicules marchent et ils sont loués. 5 possibilités :
* 0 panne : $q^4$ (D)
* 1 panne : $4pq^3$ (D)
* 2 pannes : $6p²q²$ ( C )
* 3 pannes : $4p^3q$ (B)
* 4 pannes : $p^4$ (A)

* $M = \begin{bmatrix}0 & 1 & 0 & 0\\ p² & 2pq & q² & 0\\ p^3 & 3p²q & 3pq² & q^3 \\ p^4 & 4p^3q & 6p^2q^2 & 4pq^3 + q^4\end{bmatrix}$

On pose : $p = \frac{1}{2} = q$
Donc, on a :

$M = \begin{bmatrix}0 & 1 & 0 & 0\\ 1/4 & 2/4 & 1/4 & 0\\ 1/8 & 3/8 & 3/8 & 1/8 \\1/16 & 4/16 & 6/16 & 5/16\end{bmatrix}$

### Q2 : Régime transitoire
Initialement, les 4 véhicules sont en état de marche
Quelles sont les probabilités des 4 états possibles au bout d'1 journée et de 2 journées ?

à $t = 0$, $\prod_0 = \begin{bmatrix}0 & 0 & 0 & 1\end{bmatrix}$
à $t = \tau$, $\prod_1 = \prod_0 * M = \begin{bmatrix}1/16 & 4/16 & 6/16 & 5/16\end{bmatrix}$
à $t = 2\tau$, $\prod_2 = \prod_1 * M = \begin{bmatrix}33/256 & 104/256 & 82/256 & 37/256\end{bmatrix}$

### Q3 : Régime permanent
Au bout d'un grand nombre de jour de location, existe-t-il une limite aux probabilités des états du parc de véhicules ? (limite indépendante de l'état inital)

$\prod_0 = \begin{bmatrix}0 & 0 & 0 & 1\end{bmatrix}, \to_{k\to +\infty} \prod_{\infty}$ ?
$\prod_0 = \begin{bmatrix}0 & 0 & 1 & 0\end{bmatrix}, \to_{k\to +\infty} \prod_{\infty}$ ?
...

Ici, les 3 conditions suffisantes d'ergodicité sont vérifiées :
* graphe fini
* fortement connexe
* au moins 1 boucle

$\prod_{\infty}$ existe et est indépendant de $\prod_0$

#### Calcul de $\prod_{\infty}$
$\prod_{\infty} = \begin{bmatrix}\prod_{\infty}^A & \prod_{\infty}^B & \prod_{\infty}^C & \prod_{\infty}^D\end{bmatrix} = \begin{bmatrix}a & b & c & d\end{bmatrix}$

On a un système :
$a = 1/4*b + 1/8*c + 1/16*d$
$b = a + 2/4*b + 3/8*c + 4/16*d$
$c = 1/4*b + 3/8*c + 6/16*d$
$d = 1/8*c + 5/16*d$
:::info
Pour vérifier qu'il n'y a pas d'erreur :
$a+b+c+d = 1$
:::

$\prod_{\infty} = \begin{bmatrix}a & b & c & d\end{bmatrix} = \begin{bmatrix}61/361 & 136/361 & 88/361 & 16/361\end{bmatrix}$

#### Interprétation statistique de l'ergodicité
Pendant 1 an on prend une "photo" chaque jour, si on tri ces "photos", on aura la réparition décrite dans la matrice $\prod_{\infty}$.
Et si on répète l'expérience, on aura à peu près les mêmes proportions

Le garagiste peut calculer à l'avance sa recette annuelle et cette recette sera la même chaque année.

On remarque que le dénominateur $361 \approx 365$, on a donc :
* 2 mois dans l'état A (1 véhicule marche), pas de recette
* 6.5 mois dans l'état B (2 véhicules loués), recette
* 3 mois dans l'état C (3 véhicules loués), recette
* 0.5 mois dans l'état D (4 véhicules loués), recette

On est très peu dans l'état D car on a pris une proba de panne élevée.
**Avantage de l'ergodicité : on a un calcul déterministe malgré l'agitation microscopique**

### Q4 : Reprendre la modélisation dans les cas limites (p = 0 et p = 1)

#### p = 0
Le véhicule ne tombe jamais en panne
Comportement déterministe, q=1
$M = \begin{bmatrix}0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \\0 & 0 & 0 & 1\end{bmatrix}$

état D -> état permanent absorbant.
Au bout de 3 jours , le système sera dans l'état D indéfiniment

#### p = 1
Le véhicule tombe toujours en panne
On a donc, q = 0

$M = \begin{bmatrix}0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 \\1 & 0 & 0 & 0\end{bmatrix}$

Cycle permanent absorbant A-B-A-B-etc
Au bout d'une journée au plus, le système est piégé dans le cycle ABAB...
Donc, processus déterministe

# Processus de Markov
Généralisation de la chaîne de Markov dans le cas du temps continu. Plus de notion de chaîne.

Problème : **comment introduire la notion de transition alors que le temps n'est plus discrétisé ?**

On va introduire la notion d'instant voisin (le voisin est infiniment proche de t)

## Loi de Poisson
Utilisée pour décrire des phénomnènes aléatoires, ex : arrivées ou sorties d'usagers dans un bureau de poste.

:::info
Du Poisson partout !
:::

La probabilité d'observer n arrivée pendant le temps $t$ sera donnée par
:::success
$P_n(t) = \frac{(\lambda t)^n}{n!} * e^{-\lambda t}$, loi poisson de taux $\lambda$
:::

### Propriété fondamentale
La proba d'une arrivée pendant $dt$ (infiniment petit) vaut $\lambda dt$

Conséquence : pendant le temps $dt$, il n'y a que 2 possibilités :
* 1 arrivée se produit : $\lambda dt$
* aucune arrivée : $1 - \lambda dt$ -> proba la plus grande

:::info
Il est considéré comme impossible d'avoir 2 arrivée observées entre $t$ et $t + dt$ -> la proba que cela arrive est de $(\lambda dt) * (\lambda dt) = \lambda²(dt)²$, donc négligeable
:::

:::info
S'il y a plusieurs sources d'aléas (G1, G2, ...), on obsevera entre $t$ et $t + dt$ au plus 1 seul évènement (de l'une ou l'autre des différentes sources d'aléas). Il est donc exclu d'avoir pendant le même $dt$ d'avoir 1 arrivée et 1 sortie venant de G1
:::

## Application
* On a un magasin de stockage de composants électroniques avec 3 parties : L1, L2, L3
* On a 2 robots qui se déplacent pour prélever des composants
* Chaque robots fait un prélèvement en L1 selon une loi de Poisson de taux $\mu_1$, la proba d'un prélèvement entre $t$ et $t + dt$ est de $\mu_1dt$
* Une fois le prélèvement en L1 fait, le robot se déplace instantanément vers L2 avec la proba $p$ ou L3 avec la proba $q = 1-p$
* Arrivé en L2, le robot stationne jusqu'à ce qu'il effectue un prélèvement, selon une loi de Poisson de taux $\mu_2$
* Arrivé en L3, le robot stationne jusqu'à ce qu'il effectue un prélèvement, selon une loi de Poisson de taux $\mu_3$
* Une fois le prélèvement effecuté en L2 ou L3, le robot retourne instantanément en L1
* Si les 2 robots sont présents dans le même lieu à un instant donné, seul le premier arrivé peut effecuter un prélèvement

On peut décrire le fonctionnement du système qui est formé avec les 3 lieux et les 2 robots à l'aide d'un processus de Markov, car les sources d'aléas sont TOUTES régies par des lois de Poisson.