Cours 7 : Chaînes de Markov

Chaînes de Markov :

  • Modèle simple
  • On remarque qu’à chaque sommet, somme des probas de quitter ce sommet = 1 (proba conditionnelle).

Prérequis sur les matrices positives

Déf :

Soit $X∈ℝ^n$.

$X$ est positif :

ssi toutes ses coordonnées sont positives.

On note $X≥0$.

De même, on considérera, dans ce cours, que :

une matrice $M$ est positive (noté $M≥0$).

ssi tous ses coefficients le sont.

NB :

  1. Sur $ℝ^n$, on peut définir une relation
\[X≥Y ⟺ X-Y≥0\]

C’est une relation d’ordre partiel (total si $n=1$).

  1. On note $X>0$.

Si toutes les composantes de $X$ sont $>0$.

(de même pour une matice).

Attention :

\[X≥0 ∧ X≠0 \not⟹ X>0\]

  1. Si $M≥0$ et si $X≥0$, $MX≥0$

    et donc si $M_1$ et $M_2$ sont deux matrices positives,

    \[M_1 M_2 ≥ 0\]

Ex :

Soit $G = (⟦1, n⟧, E)$ un graphe orienté, $M$ sa matice d’incidence.

Si $M^k = (m_{i, j}^{(k)})$,

$m_{i, j}^{(k)}$ est le nombre de chemins de $i$ à $j$ de longueur $k$.

Une matrice $M=(m_{i, j})$ est dite stochastique si

  • $M≥0$
  • $∀i∈⟦1, n⟧, \sum_{j=1}^n m_{i, j} = 1$

Notations :

On pose ${\bf 1}≝ (1, ⋯, 1)$

(on confond $ℝ^n$ et $𝕸_{n,1}(ℝ)$, on tranchera selon le contexte)

Soit $M∈𝕸_n(ℝ)$.

Prop : $M$ est stochastique ssi :

  • $M≥0$
  • $M{\bf 1} = {\bf 1}$

Corollaire :

  1. L’ensemble des matrices stochastiques est stable par produit et exponentiation (puissances).

  2. L’ensemble des matrices stochastiques est convexe.

Prop : Le rayon spectral $𝜌(M)$ d’une matice stochastique $M$ vaut 1.

Th :

\[𝜌(M)<1 ⟺ \lim\limits_{n⟶+∞} M^n = 0\]

NB : La norme d’opérateur sur $𝕸_n(ℝ)$ associée à la norme sup sur $ℝ^n$ est :

\[∀M=(m_{i,j}), \vert \vert M \vert \vert_1 = \sup_i (\sum_j \vert m_{i,j}\vert)\]

Dém :

$M=(m_{i,j}), X = (x_i)$

\[MX = (\sum m_{i,j} x_j)\] \[∀i, \vert \sum_j m_{i,j} x_j \vert ≤ \sum_j \vert m_{i,j} x_j \vert ≤ \vert\vert x\vert \vert_∞ \sum_j \vert m_{i,j}\vert\]

Donc

\[\sup_i \vert \sum_j m_{i,j} x_j \vert ≤ \vert\vert x\vert \vert_∞ \sup_i \sum_j \vert m_{i,j}\vert\]

et

\[\sup_{\vert\vert x\vert \vert_∞≤1} \vert\vert Mx\vert \vert_∞ ≤ \sup_i \sum_j \vert m_{i,j}\vert\]

Réciproquement :

Si $\sup_i \sum_j \vert m_{i,j}\vert$ est atteint pour la ligne $i_0$ :

Avec $X≝ (sign(m_{i_0, j}))_j$

Alors $\vert\vert X\vert \vert_∞ = 1$ et

\[\vert\vert MX\vert \vert_∞ = \sum_j \vert m_{i_0, j}\vert = \sup_i \sum_j \vert m_{i,j}\vert\]

Proposition : Soit $M=(m_{i,j})$ :

\[𝜌(M)≤ \vert\vert M\vert \vert_1\]

Dém :

Soit $𝛼∈ℂ$ une vp de $M$ et $X∈ℂ^n$ non nul tq

\[MX = 𝛼X\]

alors :

\[∀i, \sum_j m_{i,j} x_j = 𝛼x_i\]

Si $\vert\vert X\vert\vert_∞$ est atteint en la coordonnée $i_0$, i.e :

\[0 ≠ \vert x_{i_0}\vert = \sup_j \vert x_j \vert\]

Alors pour $i=i_0$ :

\[\vert 𝛼 \vert ≤ \sum_j \vert m_{i_0,j}\vert \frac{x_j}{x_{i_0}}\vert ≤ \sum_j \vert m_{i_0,j}\vert ≤ \vert\vert M\vert \vert_1\]

Chaînes de Markov : définition

Chaîne de Markov :

Une chaîne de Markov (cdM) est la donnée d’un triplet $(G, 𝜆_0, ℙ)$, où :

  • $G = (S,E)$ est un graphe orienté fini.

  • $𝜆_0$ est une loi de proba sur $S$ : $(𝜆_0(s))_{s}$ avec :

    • $∀s, 𝜆_0(s)∈[0,1]$
    • $\sum_s 𝜆_0(s) = 1$

    $𝜆_0$ est appelée loi initiale

  • $ℙ = (P_{i,j})_{(i,j)∈S^2}$ une matrice stochastique

Le plus souvent :

  • $S = ⟦1,n⟧$ :

    • alors $𝜆_0$ est vu comme un vecteur dans $ℝ^n$ et $ℙ∈𝕸_n(ℝ)$.

Une telle donnée définit un processus stochastique : $\lbrace X_n \rbrace_{n∈ℕ}$ où chaque $X_n$ est une v.a à valeurs dans $S$ de la façon suivante :

  • $X_0$ est de loi $𝜆_0$ : $X_0$ représente la position de départ dans $G$
  • $X_n$ est de loi $𝜆_n$ déf par réc :
    • \[∀t∈S, 𝜆_n(t) = P(X_n = t) = \sum_{s∈S} P_{s,t} P(X_{n-1} = s) = \sum_{s} P(X_n = t \vert X_{n-1} = s) P(X_{n-1} = s)\] 
digraph {
        1 -> 2[label="1/3"];
        1 -> 3[label="1/3"];
        1 -> 1[label="1/3"];
        2 -> 2[label="1/2"];
        2 -> 3[label="1/4"];
        2 -> 1[label="1/4"];
        3 -> 2[label="2/3"];
        3 -> 4[label="1/3"];
        4 -> 4[label="1"];        
	}
\[S= \lbrace 1, 2, 3, 4 \rbrace\] \[ℙ = \begin{pmatrix} 1/3 & 1/3 & 1/3 & 0 \\ 1/4 & 1/2 & 1/4 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}\]

$∀s, t$ :

NB :

  1. $P(X_n = t \vert X_{n-1}=s)$ est donnée par le coefficient $P_{s,t}$ de la matrice $ℙ$. C’est indépendant de $n$.

  2. $∀s_0, ⋯, s_{n-1}, t$ :

    \[P(X_n = t \vert X_{n-1}=s_{n-1}, ⋯, X_0 = s_0) = \frac{P(X_n = t, X_{n-1}=s, ⋯, X_0=s_0)}{P(X_{n-1}=s, ⋯, X_0=s_0)} \\ = P(X_n=t \vert X_{n-1} = s_{n-1})\]

    (prop. de Markov)

  3. \[(𝜆_n(t))_{t∈S} = (ℙ(X_n = t))_{t∈S} \\ = (ℙ(X_{n-1} = s))_{s∈S} ℙ \\ = (𝜆_{n-1}(s))_{s∈S} ℙ\]

    Multiplication à droite :

    \[P(X_n = t) = \sum_{s,t} P_{s,t} P(X_{n-1} = s)\]

On en déduit :

\[∀n , (𝜆_n(t))_{t∈S} = (ℙ(X_n = t))_{t∈S} \\ = (ℙ(X_{0} = s))_{s∈S} ℙ^n = (𝜆_{0}(s))_{s∈S} ℙ^n\]

NB : ce qu’on appelle chaîne de Markov, c’est le processus stochastique $(X_n)_n$

3. Chaînes de Markov absorbantes

On ne fixe pas la longueur des chemins au départ, car on veut se promener dans le graphe.

Les chemins infinis (qui ne bouclent pas sur un même sommet avec une proba 1) sont de proba 0.

NB (bonus) :

⟶ On va avoir besoin de la tribu engendrée par les cylindres/cônes ! (théroèmes de prolongement, etc … ⟶ espace de proba non trivial)

Chaîne de Markov $((S,E), ℙ, 𝜆_0)$ absorbante :

ssi il existe un état $f∈S$ tq :

  • $P_{f,f}= 1$ (donc $∀s≠f, P_{f,s} = 0$)
  • $∀s∈S$, il existe un chemin dans le graphe de $s$ vers $f$

NB : S’il existe, un tel état est unique.

Dans une chaîne de Markov, un état $s$ tq $p_{s,s}=1$ est dit absorbant.

Ex :

le dernier graphe donné en exemple précédemment est absorbant.

Th :

Soit $𝒞$ une chaîne de Markov absorbante, dont $f$ est l’unique état absorbant, $(X_n)_n$ le processus stochastique défini par $𝒞$.

Alors :

\[\lim_{n→+∞} P(X_n = f) = 1\]

NB (bonus) :

Les $X_n$ tendent en loi vers le Dirac en $f$.

Dém :

Soit $s∈S$.

Soit $s⟶ s_1 ⟶ ⋯ ⟶ s_n = f$ un chemin de longueur $n$ de $s$ vers $f$.

Soit $p$ sa proba.

Alors trivialement : pour tout $N≥n$, il existe un chemin de longueur $N$ allant de $s$ vers $f$ (il suffit de boucler sur $f$).

On en déduit que :

  • on peut trouver un même entier $m$ tq $∀s∈S$, il existe un chemin de longueur $m$ de $s$ vers $f$ (1)

  • $∀s∈S$, la suite $(P(X_n=f \vert X_0 = s))_{n∈ℕ}$ est croissante :

    \[P(X_{n+1}=f \vert X_0 = s) = \sum\limits_{\text{ chemin de long. } n+1 :\, \, \, s_0 ⟶ ⋯ ⟶ s_{n+1}=f} P(s_0 ⟶ ⋯ ⟶ s_{n+1}) \\ = \underbrace{\sum\limits_{\text{ chemin de long. } n : s_0 ⟶ ⋯ ⟶ s_n = f ⟶ s_{n+1}=f} P(s_0 ⟶ ⋯ ⟶ s_{n+1})}_{= P(X_n=f \vert X_0 = s)} + \underbrace{\sum\limits_{\text{ chemin de long. } n : s_0 ⟶ ⋯ ⟶ s_n ≠ f ⟶ s_{n+1}=f} P(s_0 ⟶ ⋯ ⟶ s_{n+1})}_{≥0}\]

On a :

\[ℙ^m = \begin{pmatrix} & & & \ast \\ & Q & & \vdots \\ & & & \ast \\ 0 & ⋯ & 0 & 1 \\ \end{pmatrix}\]

(si $f$ est le dernier sommet)

où les $\ast$ sont strictement positifs.

La matrice $Q = (q_{s,t})_{s,t∈S\backslash \lbrace f \rbrace}$ est une matrice à coeff. positifs tq :

\[∀s, \sum_t q_{s,t} < 1\]

donc

\[\vert \vert Q \vert \vert_1 < 1\]

et donc la suite $Q^k$ tend vers $0$.

\[∀s, t ∈ S\backslash \lbrace f \rbrace, \lim_{k⟶+∞} P(X_{km}=t \vert X_0 =s) = 0\]

donc

\[\lim_{k⟶+∞} P(X_{km}=f \vert X_0 =s) = 1\]

La suite $(P(X_{n}=f \vert X_0 =s))_n$ est croissante et admet une sous-suite qui converge vers 1, donc elle converge vers 1.

On conclut en remarquant que :

\[P(X_n=f) =\sum_{s∈S} P(X_n = f \vert X_0 = s)P(X_0 = s)\]

et

\[\sum_s P(X_0 = s) =1\]

4. Classification des états. Convergence asymptotique.

NB : Dans un graphe orienté, la relation

$i≃j$ ssi il existe un chemin de $i$ vers $j$ et un chemin de $j$ vers $i$ OU $i=j$

est une relation d’éq. dont les classes d’éq sont appelées composantes fortement connexes du graphe (cfc).

Si $𝒞_1, 𝒞_2$ deux cfc :

si $∃i_1 ∈𝒞_1, i_2∈𝒞_2$ tq on a un chemin de $i_1$ vers $i_2$

alors $∀i_1∈𝒞_1, i_2∈𝒞_2$, il n’existe pas de chemin de $i_2$ vers $i_1$

On peut déf des arêtes sur l’ensemble des cfc :

$𝒞_1 ⟶ 𝒞_2$ ssi $𝒞_1 ≠ 𝒞_2$ et $∃i_1 ∈𝒞_1, i_2∈𝒞_2$ tq il existe un chemin de $i_1$ vers $i_2$.

Le graphe orienté ainsi obtenu est appelé graphe réduit.

Il est acyclique.

Soit $𝒞 = (S, ℙ, 𝜆_0)$ une cdM.

Un état dans $S$ est dit récurrent s’il est dans une cfc finale (une dont on ne sort pas).

Sinon, l’état est dit transient.

NB :

  • il existe forcément une cfc finale car tous les chemins dans le graphe réduit sont de longueur finie (il est acyclique)
  • Une cdM absorbante a un unique état récurrent qui est son état absorbant.
  • Un état absorbant est récurrent

Th : Soit $𝒞$ une cdM, $R⊆S$ , $R$ l’ensemble des états récurrents de $𝒞$.

Alors \(\lim_{n⟶+∞} P(X_n ∈R)=1\)

Dém :

On considère la cdM $𝒞’ ≝ (S\backslash R \sqcup \lbrace F \rbrace, Q, 𝜇_0)$.

\[∀s, t ∈ S\backslash R, q_{s,t} = P_{s,t}\] \[s∈S\backslash R, q_{s,F} = \sum_{t∈R} P_{s,t}\]

Cette chaîne $𝒞’$ est absorbante d’état absorbant $F$.

  • $(X_n)$ processus de $𝒞$
  • $(Y_n)$ processus de $𝒞’$
\[P(X_n∈R) = \sum_s P(X_n ∈R \vert X_0 =s) P(X_0 =s)\\ = \underbrace{\sum_{s∈R } P(X_0 =s)}_{P(Y_0=F) = P(X_0 ∈R)} + \sum_{s\not∈R } \underbrace{P(X_n ∈R \vert X_0 =s)}_{\text{ proba de l'ens. des chem. partant de $s$ et qui finissent dans $R$}} P(X_0 =s)\]

$s⟶ ⋯ ⟶ s_n$ est un tel chemin.

Soit $i$ le min des indices tq $s_i∈R$.

Alors

\[s⟶ ⋯ ⟶ s_{i-1} ⟶ \underbrace{s_{i} ⟶ ⋯ ⟶ s_n}_{∈R}\]

en regroupant les chemins qui correspondent à une même valeur de $i$ et $s_{i-1}$, on a les chemins tq

$Y_0=s, ⋯, Y_{i-1}=s_{i-1}$ et $Y_i = ⋯ = Y_n = F$

On obtient ainsi $P(Y_n=F \vert Y_0 =s)$

\[P(Y_n = F \vert Y_0 = s) = \sum_{i<n, s_0 ⟶ ⋯ ⟶ s_{i-1}∉F⟶s_i∈F} P(s_0 ⟶ ⋯ ⟶ s_{i-1}⟶s_i∈F)\]

$𝒞’$ étant absorbante, on applique le théorème précédent.

5. Comportement asymptotique des chaînes de Markov irréductibles et apériodiques

Chaîne de Markov irréductible :

ssi son graphe est fortement connexe.

NB : En particulier, elle n’a pas d’état transient.

Chaîne de Markov apériodique :

On dit qu’elle est apériodique si le pgcd des longueurs des cycles vaut 1.

C’est le cas si la matrice $ℙ$ est $>0$.

Thm : Soit $𝒞 = (S, ℙ, 𝜆_0)$ une chaîne irréductible et apériodique. Alors :

Il existe un unique vecteur de proba $𝜇=(𝜇(s))_{s∈S}$ ($∀s∈S, 𝜇(s)≥0$ et $\sum_s 𝜇(s) = 1$) tel que :

\[𝜇ℙ = 𝜇\]

ce vecteur est appelé loi stationnaire.

  • De plus, la suite $ℙ^k$ converge vers la matrice de rang 1 $L$ dont toutes les lignes valent $𝜇$

ce qui équivaut à :

\[∀s∈S, \lim_n P(X_n = s) = 𝜇(s)\]

Hypothèse :

$ℙ= (p_{i,j}), ∀i, j, p_{i,j}>0$

Comme $ℙ$ est une matrice stochastique $M$,

\[\vert \vert ℙ \vert \vert_1 = 1 = 𝜌(ℙ)\]

Lemme : Sous ces hypothèses, 1 est l’unique vp de module 1, et le sep associé est la droite engendrée par 1.

Dém :

Soit $𝛼∈ℂ$ une vp de module 1, $x = (x_i)∈ℂ^n$ un vec.p associé.

\[ℙx = 𝛼x ⟺ ∀i, 𝛼x_i = \sum_j p_{i, j} x_j\]

Soit $i_0$ tq

\[\vert x_{i_0} \vert = \max_i \vert x_i \vert\] \[𝛼 = \sum_j p_{i_0,j} \frac{x_j}{x_{i_0}}\]

Donc $𝛼$ est une combinaison barycentrique de nombres complexes $\frac{x_j}{x_{i_0}}$ de module inférieur à 1, donc comme $\vert 𝛼 \vert=1$, tous ces complexes sont égaux à $𝛼$.

En effet :

\[\vert 𝛼 \vert ≤ \sum_j p_{i_0,j} \vert \frac{x_j}{x_{i_0}} \vert\]

Donc si $∃j; \vert x_j \vert< \vert x_{i_0} \vert$, alors

\[\vert 𝛼 \vert < \sum_j p_{i_0, j}=1\]

: absurde.

donc $∀j, \vert x_j \vert = \vert x_{i_0} \vert$

donc

\[\frac{x_j}{x_{i_0}}= \exp(i𝜃_j)\]

avec

  • $\exp(i𝜃_{i_0})=1$
  • $𝛼=\exp(i𝛽)$
\[𝛼= \sum_j p_{i_0, j} \exp(i𝜃_j) ⟺ 1 = \sum_j p_{i_0, j} \exp(i(𝜃_j-𝛽)) \\ ⟺ \begin{cases} 1 = \sum_j p_{i_0, j} \cos((𝜃_j-𝛽)) \\ 0 = \sum_j p_{i_0, j} \sin((𝜃_j-𝛽)) \end{cases}\]

Si $a, b∈[-1, 1], t∈]0,1[$ :

\[1 = ta + (1-t)b \\ 0 = t\underbrace{(1-a)}_{≥0} + (1-t)\underbrace{(1-b)}_{≥0}\]

donc $a=1, b=1$.

Par récurrence, on montre que tous les cos sont égaux à 1, et donc $x_j=x_{i_0}𝛼$, donc (pour $j=i_0$) $𝛼=1$.

On note $𝛼_j$ (resp. $m_j$) les vp de $ℙ$ (resp. leurs multiplicité).

Alors par le lemme de décomposition des noyaux :

\[ℂ^n = \bigoplus_j Ker(ℙ-𝛼_j Id)^{m_j} \\ = Ker(ℙ-𝛼_1 Id)^{m_1} \oplus F\]

$F$ est un sev stable par $ℙ$ et sur lequel l’endo induit par $ℙ$ est rayon spectral $<1$.

Lemme 2 : \(Ker(ℙ-Id)^{m_1} = Ker(ℙ-Id)\)

Dém :

\[∀x, \vert \vert x \vert \vert ≤ 1\]

si $ℙ$ est stochastique,

\[\vert \vert ℙx \vert \vert ≤ \vert \vert \vert ℙ \vert \vert \cdot \vert \vert \vert x \vert \vert = \vert \vert x \vert \vert\]

Supposons qu’il existe un vecteur $x$ de norme inférieure à 1 tel que :

  • $x∉Ker(ℙ-Id)$
  • $x∈Ker(ℙ-Id)^2$

Soit $y≝ (ℙ-Id)(x)$ : alors

  • $ℙx = x+y$
  • $ℙy = y$

On en déduit par récurrence :

\[ℙ^k(x) = x + ky\]

Comme $y≠0$,

\[\lim_{k⟶∞} \vert \vert x + ky \vert \vert = +∞\]

Or : $∀k, ℙ^k$ est stochastique, donc

\[\vert \vert ℙ^k \vert \vert ≤ 1\]

Contradiction.

De plus :

\[0⊆Ker(ℙ-Id) ⊆ ⋯ ⊆ Ker(ℙ-Id)^r ⊆ Ker(ℙ-Id)^{r+1}\]

La suite est évidemment croissante, et elle stationne (facile à montrer).

Donc

\[Ker(ℙ-I)^n = Ker(ℙ-I)^2 = Ker(ℙ-I)\]

$∃U$ matrice de changement de base,

$∃M$ matrice telle que $𝜌(M)<1$;

\[ℙ = U \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & M & \\ 0 & & & \\ \end{pmatrix}U^{-1}\]

($ℂ^n = ker(ℙ-I) \oplus F$)

\[ℙ^k = U \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & M^k & \\ 0 & & & \\ \end{pmatrix}U^{-1}\]

Comme $𝜌(M)<1$,

\[\lim_{k⟶∞} M^k = 0\]

On en déduit que la suite $(ℙ^k)$ est convergente de limite

\[L ≝ U \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & 0 & \\ 0 & & & \\ \end{pmatrix}U^{-1}\]

On obtient que $L$ est une matrice de rang 1.

Comme $(ℙ^k)$ est une suite de matrices stochastiques, $L$ l’est aussi (leur ensemble est fermé).

En particulier :

\[L \textbf{1} = \textbf{1}\]

Comme $rg(L)=1$,

  • $\Im(L) = ⟨ \textbf{1}⟩$
  • $L = \textbf{1} (u_1 ⋯ u_s)$

Pour un vecteur ligne $(u_1 ⋯ u_s)$.

et comme $L$ est stochastique :

\[\sum_i u_i = 1\]

Donc

\[(u_1 ⋯ u_s) L = (u_1 ⋯ u_s) \textbf{1} (u_1 ⋯ u_s) \\ = (\sum_i u_i)(u_1 ⋯ u_s) = (u_1 ⋯ u_s)\]

Donc $(u_1 ⋯ u_s)$ est vp de $L$ (à gauche) relativement à 1.

Comme $ℙ$ et $^tℙ$ ont le même polynôme caractéristique, on sait que 1 est valeur propre de multiplicité 1 à gauche dans $ℙ$, et qu’il existe une unique droite propre relativement à 1 à gauche pour $ℙ$.

$\lbrace w \mid w ℙ = w \rbrace$ est une droite.

Soit $w_0$ non nul dans cette droite.

\[w_0 = w_0 ℙ ⟹ ∀k≠0, w_0 = w_0 ℙ^k\]

et donc par passage à la limite,

\[w_0 = w_0 L\]

donc $w_0$ est colinéaire à $(u_1 ⋯ u_s)$.

On en déduit que $(u_1 ⋯ u_s)$ est l’unique vecteur de probabilité dans la droite $\lbrace w \mid w ℙ = w \rbrace$.

C’est l’unique solution du système linéaire

\[\begin{cases} ∀j, \sum_i p_{i,j} u_i = u_j \\ \sum_i u_i = 1 \end{cases}\]

NB :

  • Le comportement asymptotique de la chaîne ne dépend pas de la solution initiale. Il dépend uniquement de la matrice $ℙ$.

  • Dans le cas particulier où la distribution initiale est la distribution $(u_1 ⋯ u_s)$, on a :

    \[(P(X_n = i))_i = (P(X_0 = i))ℙ^n\]

    Donc $(P(X_n = i))_i = (u_1 ⋯ u_s)$

    Toutes les v.a $X_n$ ont la même loi, c’est pourquoi on l’appelle la loi stationnaire.

Cas général : $𝒞$ est apériodique et irréductible.

Si $i∈S$, $d_i$ le pgcd des longueurs des chemins fermés passant par $i$.

(ces longueurs forment un monoïde)

Lemme : Si $𝒞$ est irréductible,

\[∀i, j ∈S, d_i = d_j\]

Dém :

\[i ⟶^{\ast l} j ⟶^{\ast p} ⟶^{\ast m} i\]

Un chemin fermé de longueur $p$ passant par $j$ permet de construire un chemin fermé de long. $l+p+m$ passant par $i$.

donc

\[d_i \mid l+p+m\]

pour $p=0$ :

\[d_i \mid l+m\]

donc

\[d_i \mid p\]

et enfin

\[d_i \mid d_j\]

Par symétrie : $d_i = d_j$.

Prop : $d$ est le pgcd des long. des chemins fermés ne passant pas 2 fois par le même état.

Dém :

Soit $e$ ce pgcd : $d \mid e$.

Soit $p$ la longueur d’un chemin fermé.

On montre que $e \mid p$ par réc sur $p$.

  • Soit le chem. considéré de passe pas deux fois par le même sommet et $e \mid p$ par déf.

  • Soit il passe deux fois par le même sommet.

    On peut alors le décomposer en la concaténation d’un chem. fermé de longueur $<p$, et un chemin fermé ne passant pas 2 fois par le même sommet : le résultat est acquis par hypothèse de réc.

Prop : Si $d=1$, il existe $N>0$ tq $∀i,j, ∀n≥N$, il existe un chem. de long. $n$ de $i$ vers $j$.

(ou : $∀n≥N, ℙ^n >0$)

$∀i, ∃N_i; ∀n ≥N_i$, il existe un chem. fermé de long. $n$ passant par $i$. (cf le TD 10)

$∀i, j$, il existe un chemin : $i⟶^{\ast l_{i, j}}j$

Prenons

\[N ≝ \max(l_{i,j}) + \max(N_i)\]

$∀n≥N$ : on peut compléter tout chem. allant de $i$ à $j$ en $l_{i,j}$ étapes en un chemin allant de $j$ à $j$ en $n-l_{i,j}$ étapes, car

\[n-l_{i,j}≥N_j\]

Temps d’absorption

Problème : Étant donnée une chaîne de Markov absorbante, d’état absorbant $f$, pour un état $i$ de la chaîne, on note $T_i$ la variable aléatoire à valeurs dans $ℕ∪\lbrace ±∞\rbrace$ qui est la longueur d’un chemin de source $i$ et de dernier état $f$.

\[(T_i = n) = \lbrace i ⟶ i_1 ⟶ ⋯ ⟶ i_n = f \text{ et } ∀j<n, i_j ≠ f\rbrace\]

NB : ne dépend que de $X_0, ⋯, X_n$ : temps d’arrêt

\[(T_i = +∞) = \lbrace i ⟶ i_1 ⟶ ⋯ ⟶ i_j ⟶ i_{j+1} ⟶ ⋯ \text{ chemin infini et } ∀j, i_j ≠ f\rbrace\]

On peut déifinir $T_f$, mais :

\[T_f = 0\]

Ex :

  digraph {
    rankdir=LR;
    1 -> 1[label="p"];
    1 -> f[label="1-p"];
    f -> f[label="1"];
  }
\[P(T_1 = 0) = 0\] \[P(T_1 = n) = p^{n-1} (1-p)\] \[E(T_1) = \sum\limits_{ n≥1 } n p^{n-1}(1-p) \\ = (1-p) \frac{1}{(1-p)^2} \\ = \frac{1}{1-p}\]

Th : Soit $𝒞$ une cdM absorbante. $𝒞$ est définie par $(S, 𝜆_0, ℙ)$ d’état absorbant $f$.

Soit $Q$ la matrice extraite de $ℙ$ de la façon suivante :

\[ℙ = \begin{pmatrix} && & * \\ &Q& & \vdots \\ && & * \\ 0 &⋯& 0 & \underbrace{1}_{\text{colonne de} f} \\ \end{pmatrix}\]

Alors

\[𝜌(Q)< 1\]

et $(E(T_i))_{i≠f}$ est l’unique solution du système linéaire

\[X = \mathbf{1} + QX\]

En particulier,

\[∀i≠f, E(T_i) < +∞\]

NB :

\[𝜌(Q)<1 ⟺ I-Q \text{ inversible }\]

donc $X = \mathbf{1} + QX$ a une unique solution : $(I-Q)^{-1} \mathbf{1}$

De plus,

\[𝜌(Q)<1 ⟹ \sum\limits_{ j∈ℕ } Q^j\]

est convergente.

Dém :

1) $𝜌(Q)<1$

\[ℙ = \begin{pmatrix} && & * \\ &Q& & \vdots \\ && & * \\ 0 &⋯& 0 & \underbrace{1}_{\text{colonne de} f} \\ \end{pmatrix}\]

donc $∃N$ tq :

\[ℙ^N = \begin{pmatrix} && & *>0 \\ &Q^N& & \vdots \\ && & *>0 \\ 0 &⋯& 0 & 1 \\ \end{pmatrix}\]

car $∃N$ tq $∀i≠f, i⟶ ⋯ ⟶f$ de longueur $N$.

En prenant la norme $\vert \vert \vert M \vert \vert \vert = \sup_{\vert \vert X \vert \vert = 1} \vert \vert MX \vert \vert_1 = \sup_i \sum_j \vert m_{i,j} \vert$, on a

$\vert \vert \vert P^N \vert \vert \vert = 1$ et $\vert \vert \vert Q^N \vert \vert \vert < 1$, donc

\[𝜌(Q^N) ≤ \vert \vert \vert Q^N \vert \vert \vert < 1\]

Comme $Sp(Q^N) = \lbrace 𝛼^N, 𝛼∈Sp(Q) \rbrace$ (trigonalisation de $Q$), on en déduit que

\[𝜌(Q)<1\]

2)

\[\begin{align*} nP(T_i = n) & = n \sum_{\substack{i⟶ i_1 ⟶ ⋯ ⟶ i_{n-1} ⟶ f \\ i_j ≠ f}} p_{i, i_1} ⋯ p_{i_{n-1}, f} \\ & = n \left(\sum_{i⟶ i_1} p_{i, i_1≠f} \sum_{\substack{i_1 ⟶ ⋯ ⟶ i_{n-1} ⟶ f \\ i_j ≠ f}} p_{i_1, i_2} ⋯ p_{i_{n-1}, f} \right) \\ & = n \left(\sum_{i⟶ i_1≠f} p_{i, i_1} P(T_{i_1}= n-1) \right) \\ ⟹ \sum_n nP(T_i = n) & = p_{i,f} + \sum_{\substack{n ≥2 \\ i⟶ i_1≠f}} p_{i, i_1} (n P(T_{i_1}= n-1)) \\ & = \underbrace{p_{i,f} + \sum_{\substack{n \\ i⟶ i_1≠f}} p_{i, i_1} P(T_{i_1}= n-1)}_{ = P(\lbrace i⟶ ⋯ ⟶ i_n = f, n∈ℕ \rbrace) = 1 \text{ (chaîne absorbante)}} + \sum_{\substack{n ≥2 \\ i⟶ i_1≠f}} p_{i, i_1} ((n-1) P(T_{i_1}= n-1)) \\ \end{align*}\]

donc

\[\left(\sum_n n P(T_i = n)\right)_{i≠f} = \mathbf{1} + Q\left(\left(\sum_n n P(T_i = n)\right)_{i≠f}\right)\]

Leave a comment