---
tags: Maths, TC, Siarry
---

# Recherche Operationnelle Stochastique

Rappels / Probabilités
Chaîne de Markov
Processus de Markov
Processus de Naissance et de Mort

## Rappels de probabilités (p111)

### Exercice 1

:::success
Une main au bridge : 13 carte tirées d'un jeu de 52 cartes
:::

:::spoiler 1. Probabilité d'avoir dans la main exactement k as ?
$$q_k = \frac{\binom{k}{4}*\binom{13-k}{48}}{\binom{13}{52}}$$
:::

:::spoiler 2. Probabilité d'avoir au moins 1 as ?
$$p = 1 - q_0$$
:::

:::spoiler 3. Probabilité d'avoir une main rouge (13 cartes rouges) ?
$$p = \frac{\binom{13}{26}}{\binom{13}{52}}$$
:::

### Exercice 2

:::success
Un lot contient 12 pièces
- 4 pièces defectueuses
- 8 pièces bonnes

On tire 3 pièces, l'une après l'autre, sens remise après tirage.
:::

1) Probabilité d'avoir aucune pièce défectueuse

:::spoiler Méthode 1 : On tire les 3 pièces d'un coup
\
Nombre de manière de tirer 3 pièces bonnes : $\binom{8}{3}$
$$\frac{{\binom{8}{3}}}{{\binom{12}{3}}} = 0,255$$
:::

:::spoiler Méthode 2 : On tire les pièces l'une après l'autre
\
1er tirage : 4 défect - 8 bonnes -> $\frac{8}{12}$
2e tirage : 4 défects - 7 bonnes -> $\frac{7}{11}$
3e tirage : 4 défects - 6 bonnes -> $\frac{6}{10}$
$$\frac{8}{12} * \frac{7}{11} * \frac{6}{10}$$
:::

### Exercice 3 (Loi binomiale)

:::success
75% des fibres sont courtes.
25% des fibres sont longues.
On tire au hasard 3 fibres.
:::

:::spoiler Probabilité de tirer deux fibres longues et une fibre courte ?
*Tirage d'une fibre*

Proba (1L) = 0,25 = p
Proba (1C) = 0,75 = q

*Tirage de trois fibres*

Loi binomiale = loi de Bernouilli

$3 * p * p * q$

Proba(LLC) = p * p * q
Proba(LCL) = p * q * p
Proba(CLL) = q * p * p

Somme = 3 * p * p * q

Evenement de probabilité p = Pile
Evenement contraire de propabilité q = face

Proba (m fois PILE, (n - m) fois FACE) = $\binom{m}{n} * p^m * q^{n-m}$
:::

### Exercice 4 (Probas conditionnelles, théorème de BAYES)

:::success
Il y a 2 urnes :
- Urne 1 : 4 boules blanches
- Urne 2 : 3 boules blanches et 1 boules noires

Un individu choisi une urne et tire deux boules sucessivement dans cette même urne.
:::

1. Sachant qu'il remet la boule après le premier tirage

:::spoiler a) La probabilité de tirer deux boules blanches
\
Lorsqu'on est dans U1 : $p1(2bb) = 1$
Lorsqu'on est dans U2 : $p2(2bb) = {(\frac{3}{4})}^2$
$$ p(2bb) = \frac{1}{2} * p1(2bb) + \frac{1}{2} * p2(2bb) $$
$$ p(2bb) = \frac{1}{2} * 1 + \frac{1}{2} * {(\frac{3}{4})}^2 $$
$$ p(2bb) = \frac{25}{32} $$

:::

:::spoiler b) Sachant que la première boule était blanche, quelle est la probabilité que la deuxième boule soit blanche ?
\
$$ p = \frac{4}{7} * 1 + \frac{3}{7} * \frac{3}{4}$$
$$ p = \frac{25}{28} $$
:::

\
2. Même question pour un tirage sans remise

:::spoiler a)
\
Lorsqu'on est dans U1 : $p1(2bb) = 1$
Lorsqu'on est dans U2 : $p2(2bb) = \frac{3}{4} * \frac{2}{3}$
$$ p(2bb) = \frac{1}{2} * p1(2bb) + \frac{1}{2} * p2(2bb) $$
$$ p(2bb) = \frac{3}{4} $$
:::

:::spoiler b)
\
$$ p = \frac{4}{7} * 1 + \frac{3}{7} * \frac{2}{7}$$
$$ p = \frac{6}{7} $$
:::

### Exercice 5 (de BAYES)

:::success
Dans une usine de boulons, on a 3 urnes :
* La machine A produit 25% des boulons, dont 5% défectueux
* B -> 35%, 4% défectueux
* C -> 40%, 2% défectueux
On tire un boulon au hasard et il est défectueux.
:::

:::spoiler Quelle est la probabilité qu'il vienne de A ?
$P(A) = 0,25$ ; $P(B) = 0,35$ ; $P(C) = 0,40$
$P(d/A) = 0,05$ ; $P(d/B) = 0,04$ ; $P(d/C) = 0,02$

Théorème de BAYES:
$P(A/d) = \frac{P(d/A)*P(A)}{P(d)}$
Théorème des probabilités totales:
$P(d) = P(A)*P(d/A) + P(B)*P(d/B) + P(C)*P(d/C)$
:::

## Chaînes de Markov

C'est un modèle pour un processus :
* aléatoire
* discret
* sans mémoire
:::info Déf
* On a un "système observé" à des instants discrets.


* à un instant d'observation donné $t = k*\tau$ le système est nécessairement dans un **ETAT** et un seul, parmi une liste d'états possibles connue à l'avance.
:::

#### Exemples

Ici, le système est un animal enfermé dans une cage


ici $\tau$ = 1 seconde

Il y a cinqs états possibles
"L'animal est dans le comportement C" <=> "Le système est dans l'état C"
_Remarque_: Pas d'état transitoire

* On s'intéresse à la chaîne formée par les états successifs observés à $t = 0$, $t = \tau$, $t = 2\tau$, etc
Ex:
A A A B B ...
A C C C D ...

* Mécanisme de transition (ou changement d'état) fixé entre 2 instants d'observation successifs $k\tau$ et $(k+1)\tau$ (k quelconque)
On suppose connue la probabilité $p_{ij}$
$p_{ij} =$ Proba, si le système est dans l'état $i$ à $t = k\tau$, que le système se retrouve dans l'état $j$ à $t = (k+1)\tau$

Tous les $p_{ij}$, $\forall(i, j)$, sont regroupées dans la matrice M, dite **matrice de transition**
$$M: n*m$$
$n$ = nb total d'états possibles

ex: n = 5

| $i$\\$j$ | A | B | C | D | E |
|:---:|:---:|:---:|:---:|:---:|:---:|
| A | 0,2 | 0,5 | 0,3 | 0 | 0 |
| B | - | 1 | - | - | - |
| C | - | - | 0,3 | 0,3 | 0,4 |
| D | - | - | 0,3 | 0,7 | - |
| E | - | - | 0,4 | - | 0,6 |

_Rem:_ la sommme des termes d'une même ligne = 1
_Rem:_ $\tau$ assez petit pour que, entre 2 instatns d'obs successifs, l'anmial est resté dans le compartiment, ou bien il s'est retrouvé dans le compartiment voisin

- Avec ce mécanisme de transition, la chaîne des états observés s'appelle une **chaîne Markov**.

Schéma de ses grands morts (passé, présent, futur)
La connaissance de l'état présent est suffisante pour calucler les états futurs, $\forall$ les états passés.

_Rem_: tous les porcessus aléatoires ne sont pas markoviens

### Régime transitoire d'une chaîne de Markov
- On suppose connus :
* l'état à $t = 0$
* la matrice M
Ex:
| à $t = 0$, animal en A ;
| M -> connue
- Peut-on calculer dans quel état sera le système à $t = 32\tau$ ?
On peut calculer la probabilité de chaqun des 5 états = $t = 32\tau$.
Ces 5 probas sont regroupées dans un vecteur-ligne:
$$\pi_{32} = (\pi_{32}^{A}, \pi_{32}^{B} ... \pi_{32}^{E})$$

A chaque instant k$\tau$ on peut calculer 5 probabilités regroupés dans le vecteur $\pi_k$.

Le vecteur $\pi_k$ s'obtient par la formule :
$$ \pi_k = (\pi_{k-1}) * M $$
avec $k = 1, 2, ...$

#### Exemple
$k=1$
$\pi_1 = \pi_0 * M$
$\pi_0 =$ (1 0 0 0 0) si animal en A au départ

$$ \pi_k = \pi_0 * M^{32} $$
$$ \pi_k = \pi_n * M^{k-n} $$

- _Régime permanent_: peut exister ou ne pas exister -> **ERGODICITE** de la ch. de M.
- Le ch. de M. est **ergodique** s'il existe un limite au vecteur $\pi_{k}$ lorsque $k \to +\infty$, et si cette limite est indépendante de l'état initial.
$$\pi_\infty = (\pi_\infty^A \quad \pi_\infty^B \quad \dots \quad \pi_\infty^E)$$

Ici, la ch. de M. n'est pas endique car la 2e colonne converge cers le vecteur (0 1 0 0 0) et par exemple la colonne 5 ne peut pas converger vers le ecteur (0 1 0 0 0 ) car l'animal n'ira jamais en B.

02.03.20

### Conditions suffisantes d'ergodicité

La chaîne de Markov est ergodique si le **graphe de transition** est : (condition suffisante)
1. Fini
2. Fortement connexe
3. Avec au moins 1 boucle

#### Graphe de transition
- sommets = états
- arcs = transition(i,j) depuis $t=k\tau$ vers $t=(k+1)\tau$
- valuations = $p_{i,j}$

(Si la moindre critique sur ce schéma, s'adresser à Louis Marsais)

Les conditions (1) et (3) sont vérifiées
La condition (2) n'est pas vérifiée
=> ergodicité ? => on sait déjà que la ch. de M. ne l'est pas à cause de la colonne B

### Comment calcule-t-on le vecteur $\pi_{\infty}$

$$ \pi_k = (\pi_{k-1} * M) $$

### Interpréter le vecteur $\pi_{\infty}$

$$ \pi_{\infty} = \pi_{\infty} * M $$
$$ \sum_{i} \pi_{\infty}^i = 1 $$

$$ \pi_{\infty} = \pi_{\infty} * M \\
\pi_{\infty} = ( \pi_{\infty}^C \pi_{\infty}^D \pi_{\infty}^E) \\
\pi_{\infty} = (c, d, e) \\
(c, d, e) = (c, d, e) * MATRICE \\
c = 0,3c + 0,3d + 0,4e \\
d = 0,4c + 0,7d \\
e = 0,3c + 0,06e \\
\pi_{\infty} = (c\ d\ e) = (12/37, 16/37, 9/37) $$

Matrice =
| 0,3 | 0,4 | 0,3 |
| -------- | -------- | -------- |
| 0,3 | 0,7 | - |
| 0,4 | - | 0,6 |

### Interprétation de l'ergodicité

#### Interprétation ponctuelle

Régime transitoire: premiers instants
Régime permanent (n'apparaît que si ergodicité): à partir d'un certain temps

Si on fait une interprétation ponctuelle d'un instant quelconque dans le régime permanent, les probabilités des états sont données par $\pi_\infty$. Ces probabilités ne varient plus d'un instant à l'autre.
=> Stabilisation macroscopique ("disparition du hasard")
se superpose à l'agitation microscopique -> ce qu'on observe au début

*Rq:*
* L'agitation microscopique est toujours présente.
* La stabilisation macroscopique n'a lieu que si la ch. de M. est ergodique.

#### Interprétation statistique

On observe un animal pendant une heure, avec une photo par secondes (donc 3600 photos).
On reparti ensuite les photos dans un camembert.

Catégorie C : 12/37
Catégorie D : 16/37
Catégorie E : 9/37

Si on refait la même expérience une heure plus tard, on aura toujours la même proportion de photo dans les catégories.

#### 2e application

Problème du garagiste (p114)

Cas réel = calcul de la recette annuelle du garagiste
- Un garagiste dispose d'un parc de 4 véhicules loués à la journée.
- Chaque véhicule loué peut tomber en panne avec une proba $p$ ($q = 1 - p$).
- Le garagiste effectue les réparations en soirée. Il ne peut en faire qu'une par soir.
- On considère l'état du système au début de chaque journée. $\rightarrow \tau= 1$ jour.
- Le garagiste ne loue ses véhicules que s'il y a au moins 2 véhicules en état de marche au début de la journée.
- On suppose que la demande de location est supérieure à l'offre = tous les véhicules disponible à la location sont systématiquement loués.

:::spoiler 1. Modéliser le fonctionnement de ce garage à l'aide d'une chaîne de Markov

*Modélisation d'un pb réel sous forme de Ch de M:*
Questions qu'il faut se poser :
- Etats possible à $t=k\tau$ ?
- Valeurs de $\tau$ ?
- matrice M ?
- graphe de transition ?

**Modélisation**

- $\tau$ = 1 journée
- Etats possibles ? -> nb de véhicules en état de marche
- A : 1
- B : 2
- C : 3
- D : 4
- L'état avec 0 véhicule qui marche n'est pas possible

**Matrice de transition**

$$
\begin{array}{c|cccc}
{} & {A} & {B} & {C} & {D} \\
\hline
{A} & {0} & {1} & {0} & {0} \\
{B} & {p^2} & {2pq} & {q^2} & {0} \\
{C} & {p^3} & {3p^2q} & {3pq^2} & {q^3} \\
{D} & {p^4} & {4p^3q} & {6p^2q^2} & {4pq^3 + q^4} \\
\end{array}
$$

**1ere ligne**

à $t=k\tau$, le système est dans l'état A
Quelles sont les états possibles à $t=(k+1)\tau$ ?

1 véhicule en panne -> Non loué
1 réparation le soir
Le lendemain 1 véhicule qui marche
=> état B
On écris 0, 1, 0, 0 dans la première ligne de la matrice

**2eme ligne**

Etat B = 2 véhicules qui marchent
2 véhicules loués

- si 2 véhicule en panne = $p^2$ => Etat A
- si 1 véhicule en panne = $2pq$ => Etat B
- si 0 véhicule en panne = $q^2$ => Etat C
=> somme égale à 1 (on a envisagé tous les cas possibles)

**3eme ligne**

Etat C = 3 véhicules qui marchent
3 véhicules loués

- 3 pannes = $p^3$ = Etat A
- 2 pannes = $\binom{2}{3}p^2q=3p^2q$ = Etat B
- 1 panne = $\binom{1}{3}pq^2=3pq^2$ = Etat C
- 0 panne = $q^3$ = Etat D

**4eme ligne**

Etat D = 4 véhicules qui marchent
4 véhcules loués

- 4 pannes = $p^4$ = Etat A
- 3 pannes = $\binom{3}{4}p^3q = 4p^3q$ = Etat B
- 2 pannes = $\binom{2}{4}p^2q^2 = 6p^2q^2$ = Etat C
- 1 pannes = $\binom{1}{4}pq^3 = 4pq^3$ = Etat D
- 0 pannes = $q^4$ = Etat D
Etat D = P(1 panne) + P(0 panne)

**Graphe de transition**


:::

:::spoiler 2. Application et étude de la limite pour p=q=1/2 et à t=0 tout marche

$\pi_0 = (0\ 0\ 0\ 1)$
$\pi_1 = \pi_0 * M = (1/16,\ 4/16,\ 6/16,\ 5/16)$ (Somme = 1)
$\pi_2 = \pi_1 * M = (33/256,\ 104/256,\ 82/256,\ 27/256)$

Au bout d'un grand nombre de jours de location, existe-t-il une limite aux probas des différents états du parc de véhicules ? (ceci indépendamment de l'état initial)
=> Lié à l'ergodicité de la chaîne de Markov

Ici, les trois conditions suffisantes d'ergodicité sont vérifiées. => La ch. de M. est ergotique.

**Calcul de $\pi_{\infty}$**

$$ \pi_{\infty} = (a\ b\ c\ d)*M $$
$$
\pi_{\infty} =
\begin{pmatrix}
{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{pmatrix}
$$
$$
\left\{
\begin{array}{ll}
a = 1/4b + 1/8c + 1/16c \\
b = a + 2/4b + 3/8c + 4/16d \\
c = 1/4b + 3/8c + 6/16d \\
d = 1/8c + 5/16d
\end{array}
\right.
$$
$$ \pi_\infty = (61/361,\ 196/361,\ 88/361,\ 16/361) $$

**Interprétation statistique**

On laisse le garage fonctionner pendant 1 an, et on arrive en régime permanent.

On trouve
- Etat A = 61/361 (envrion 2 mois = pas d'argent)
- Etat B = 196/361 (environ 6,5 mois)
- Etat C = 88 / 361 (environ 3 mois)
- Etat D = 16 / 361 (environ 0,5 mois = beaucoup d'argent)

On peut ainsi calculer la recette annuelle (quelle que soit l'année considérée) => Stabilisation macroscopique

**Reprendre la modélisation si p=0**

Système déterministe

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

Au bout de maximum 3 jours le système arrive dans l'état D et y reste indéfiniment.

:::

### Processus de Markov : Généralisation dans le cas continu

Un système est observé $\forall t$ (temps continu).
On aura un certain nombre d'états à un instant t.
Comment s'intéresser à des transitions ?
On s'intéresse aux transitions entre deux instants voisins : $t$ et $t + dt$

++Hypothèse++ : on suppose que les changements d'état du système sont dus à des phénomènes aléatoires régis par des lois de Poisson

:::warning

**Rappel concernant la loi de Poisson** :fish:

On a un bureau de poste avec deux guichets : G1 et G2.
Les arrivées suivent une loi de Poisson de taux $\lambda$
Les sorties de G1 suivent une loi de Poisson de taux $\mu_1$
Les sorties de G2 suivent une loi de Poisson de taux $\mu_2$

La probabilité d'observer $n$ arrivées pendant la durée d'observation $t$ est de
$$ P_n(t)=\frac{(\lambda t)^n}{n!}.e^{-\lambda t} $$

**Propriété particulière de la loi de Poisson**
Entre deux instants voisins $t$ et $(t+dt)$, la probabilité d'occurence d'un évènement vaut $\lambda . dt$

**Conséquence**
Entre deux instants voisins $t$ et $t+dt$, un seul évènement a pu se produire (++Règle d'or++)

**Probabilité**
La probabilité de deux arrivées pendant le même $dt$ : $(\lambda dt)^2 < \lambda dt$ => impossible

3 lois de Poisson
1 seul évènement peut se produire
- 1 arrivée -> Proba $\lambda dt$
- 1 sortie venant de G1 -> Proba $\mu_1dt$
- 1 sortie venant de G2 -> Proba $\mu_2dt$

*Rq*: Il est impossible d'observer pendant le temps $dt$ la sortie par le guichet G1 et l'entrée d'un usager.
:::