Proba:Chaînes de Markov

De Ensiwiki
Aller à : navigation, rechercher


Wikicours.png Chaînes de Markov
Matière Proba 2
Chapitre 10
Promo 1A
Date 2007
Professeur O. François
Auteur L. Petit
PDF Le Post'IT

Propriétés - Théorème

C'est un processus itératif (X_n)_{n\geq 1} à valeurs dans un ensemble fini E.

P(X_n = j | X_{n-1}=i, X_{n-2}=i_{n-2},..., X_0=i_0) = p_{ij}
Chaine Markov.png
Graphe de transitions i \to j si et seulement p_{ij} >0 matrice de transition.
P = \begin{pmatrix} p_{11} & \cdots & p_{1m} \\ \vdots & \ddots & \vdots \\ p_{m1} & \cdots & p_{mm}\end{pmatrix} \begin{array}{l} \sum_j p_{ij} = 1 \\ 0 \leq p_{ij} \leq 1 \end{array}
DéfinitionProposition

\forall i,j \in E, n,k \geq 0 :

P(X_{n+k} = j | X_n = i) = p_{ij}^{(k)} = (P^k)_{ij}
DéfinitionProposition


\textrm{Soit\,} \Pi_0 = P(X_0 = \bullet) \textrm{\,(loi\,de\,} X_0 \textrm{)}
= (\Pi_1^0 , ... , \Pi_m^0)
= (P(X_0 = 1), ... , P(X_0 = m))
\textrm{Soit\,} \Pi_n = P(X_n = \bullet)
= \Pi_0 P^n = \Pi_{n-1} P
DéfinitionDéfinition

On dit que la loi \Pi est invariante :

\Pi = \Pi P
DéfinitionThéorème

On suppose que P est irréductible et apériodique. Alors :

  1. \exists une unique loi invariante \Pi
  2. \forall i \in E, P(X_n = j | X_0 = i) \to \Pi(j)
  3. \left|P(X_n = j | X_0 = i) - \Pi(j)\right| \leq c \rho^n

    \rho = \max \{ \left|\lambda\right|, \, \lambda \textrm{\,valeur\,propre\,de\,} P \neq 1 \}

Exemples

Exemple : Une petite grenouille saute de nénuphar en nénuphar dans une mare. Questions typiques

  1. Au temps n = 0, la grenouille est sur le nénuphar 1. Quelle est la probabilité de la voir sur le nénuphar 3 après 5 sauts ?
    P(X_5 = 3 | X_0 = 1) = ? = \it (P^5)_{13}
  2. Après un nombre arbitraire de sauts ? (état équilibre) \it \Pi(3)

Exemple : Lors d'un cours dans l'amphi E le chiffon disparaît sous le tableau avec la probabilité p. Un prof qui ne trouve pas le chiffon parvient à le récupérer avec la probabilité q.

Question Probabilité de voir un prof repêcher le chiffon avec succès dans l'amphi E.

E = \{0,1\}, \begin{array}{ll} 0 = \textrm{\,pas\,chiffon} \\ 1 = \textrm{\,chiffon} \end{array}

Exemple Markov.png

Solution Markov X_n = état après n cours.

(\Pi_0, \Pi_1) \begin{pmatrix} 1-q & q \\ p & 1-p \end{pmatrix} = (\Pi_0, \Pi_1)

Ce qui nous donne :

\left\{\begin{array}{rll} \Pi_0 - \Pi_0 q + \Pi p & =  & \Pi_0 \\ q\Pi_0 + \Pi_1 - \Pi p & = & \Pi_1 \\
\Pi_0 + \Pi_1 & = & 1\end{array}\right.

On obtient donc : \Pi_0 - \Pi_0 q + (1-\Pi_0) p = \Pi_0 \Rightarrow \Pi_0 = \frac{p}{p+q}

D'où :

\Rightarrow P(\textrm{Succes\,peche}) \approx q \frac{p}{p+q}
= \underbrace{P(\textrm{Succes\,peche\,|\,Pas\,chiffon})}_{q} \underbrace{P(\textrm{Pas\,chiffon})}_{\frac{p}{p+q}}

Solution directe

P(X_n = 0) = P(X_n = 0 | X_{n-1} = 0) P(X_{n-1} = 0) + P(X_n = 0 | X_{n-1} = 1) P(X_{n-1}=1)
\Pi_0(n) = (1-p)\Pi_0(n-1) + p(1-\Pi_0 (n-1))

Une solution particulière est constante : \Pi_0 = (1-q) \Pi_0+p(1-\Pi_0) \Rightarrow \Pi_0 = \frac{p}{p+q}

\Pi_n(0) = (1-(p+q))\Pi_{n-1}(0) + p

\Pi_n(0) = K (\underbrace{1-(p+q)}_{\in [-1,1]})^n + \frac{p}{p+q} \to \frac{p}{p+q}

Remarque : La vitesse de convergence est dictée par la seconde valeur propre de :

P = \begin{pmatrix} 1-q & q \\ p & 1-p \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}

Donc 1 est valeur propre de P.

2 - (p+q) - 1 = 1 - (p+q), valeur propre : \left|\lambda\right| < 1.

Exemple Markov Periodique.png


DéfinitionDéfinition

P irréductible si \exists k tel que p_{ij}^k > 0, \forall i,j

Chaine Markov Irreductible.png

P réductible Le morceau entouré est réductible

Chaine Markov Reductible.png