3.1. Chaine de Markov en temps long

Soit \((X_n)_{n \ge 0}\) une chaîne de Markov (CM) sur \(E\) dénombrable de matrice de transition \(P\). Dans la suite, \(\mu\) désigne un mesure positive sur \(E\), non nulle et telle que \(\mu(x) < +\infty\) pour tout \(x \in E\).

Definition 3.1

Une mesure positive \(\mu\) sur \(E\) est invariante pour \(P\) si elle vérifie

(3.1)\[ \mu = \mu P \quad \text{i.e.} \quad \forall x \in E, \quad \mu(x) = \sum_{y \in E} \mu(y) P(y, x).\]

Ce système d’équations linéaires est appelé équations de bilan global. Une probabilité invariante pour \(P\) (ou stationnaire) est une mesure invariante de masse 1.

Si \(X_0\) suit la loi \(\pi\) invariante pour \(P\) alors \(X_n \sim \pi\) pour tout \(n \ge 0\), d’où le nom de probabilité stationnaire: la loi marginale \(X_n\) sera la loi \(\pi\), la même pour tout indice \(n \ge 0\).

Soit \(\pi\) une probabilité invariante pour \(P\) sur \(E\) vérifiant \(\pi(x) > 0\) pour tout \(x \in E\). On introduit la matrice \(Q\) par

\[\begin{equation*} \forall x, y \in E, \quad Q(x, y) = \frac{\pi(y)}{\pi(x)} P(y, x). \end{equation*}\]

Alors \(Q\) est une matrice stochastique car pour tout \(x\in E\), \(\sum_{y \in E} Q(x, y) = 1\). De plus, si \(X_0 \sim \pi\) on a (formule de Bayes)

\[\begin{equation*} \begin{split} \forall n \ge 0, \quad \mathbf{P} \big(X_n = y| X_{n+1} = x\big) &= \frac{\mathbf{P} \big(X_n = y, X_{n+1} = x)}{\mathbf{P}\big(X_{n+1} = x\big)} \\ & = \frac{\mathbf{P}\big(X_{n+1} = x| X_n = y \big) \mathbf{P}\big(X_n = y\big)}{\mathbf{P}\big(X_{n+1} = y\big)} \\ & = \frac{\pi(y)}{\pi(x)} P(y, x) = Q(x, y). \end{split} \end{equation*}\]

Ainsi on peut interpréter \(Q\) comme la matrice de transition de la chaîne de Markov après retournement du temps. Cela introduit la notion de réversibilité.

Definition 3.2

La CM de transition \(P\) est réversible par rapport à la mesure positive \(\mu\) si

(3.2)\[ \forall x, y \in E, \quad \mu(x) P(x, y) = \mu(y) P(y, x)\]

Ce système d’équations linéaires est appelé équations de bilan détaillé.

Par abus, on dit que \(\mu\) est une mesure réversible. Il est important de noter que si \(P\) est réversible par rapport à \(\mu\) alors \(\mu\) est invariante pour \(P\). En effet si \(P\) est réversible par rapport à \(\mu\)

\[\begin{equation*} \forall x \in E, \quad \sum_{y \in E} \mu(y) P(y, x) = \sum_{y \in E} \mu(x) P(x, y) = \mu(x). \end{equation*}\]

La notion de mesure réversible est plus forte que celle de mesure invariante: une mesure peut être invariante sans être réversible.

Si \(P\) est réversible par rapport à une probabilité \(\pi\) et \(X_0 \sim \pi\) alors pour tout \(n \ge 0\), le vecteur \((X_0,\dots, X_n)\) a même loi que le vecteur (retourné en temps) \((X_n, \dots, X_0)\).

Ces systèmes d’équations linéaires (3.1) ou (3.2) permettent de trouver algébriquement une expression explicite de \(\mu\), mais lorsque \(\operatorname{card}(E)\) est grand ces systèmes sont complexes à résoudre. Ensuite il faut normaliser la mesure \(\mu\) et donc calculer la constante de normalisation \(\sum_x \mu(x)\) ce qui est aussi coûteux. Une alternative est d’utiliser la convergence de la CM vers sa probabilité stationnaire. Pour cela il est utile de rappeller de deux notions importantes: l’irréductibilité et l’apériodicité de la CM.

Definition 3.3

Une CM est irréductible si la probabilité d’atteindre un point \(y \in E\) partant d’un point \(x \in E\) en un nombre fini d’étapes est strictement positive i.e.

\[\begin{equation*} \forall x, y \in E, \quad \exists n= n_{x, y} \ge 1, \quad P^{n}(x, y) > 0. \end{equation*}\]

Dans toute la suite on considère des chaines de Markov irréductible sur \(E\). On admet le résultat suivant.

Theorem 3.1

Une CM irréductible possède au plus une probabilité invariante \(\pi\) et \(\pi(x) > 0\) pour tout \(x \in E\). Si \(E\) est fini alors une CM irréductible possède une unique probabilité invariante.

Definition 3.4

Un état \(x \in E\) est dit apériodique si \(\exists N_x \ge 1\), \(\forall n \ge N_x\), \(P^n(x, x) > 0\). Une chaine de Markov dont tous les états sont apériodiques est dite apériodique.

Une chaine de Markov irréductible qui possède 1 état apériodique est apériodique.

Definition 3.5

Une chaine de Markov \((X_n)_{n \ge 0}\) vérifie la condition de Doeblin s’il existe \(\ell \ge 1\), \(\alpha > 0\) et \(c\) une probabilité sur \(E\) tels que

\[\begin{equation*} \forall x, y \in E, \quad P^\ell(x, y) \ge \alpha c(y). \end{equation*}\]

Il est important de remarquer qu’une chainte de Markov irréductible qui vérifie la condition de Doeblin est apériodique. Si \(E\) est fini, la proposition suivante donne la réciproque.

Proposition 3.1

Si \(E\) est fini, une CM irréductible vérifie la condition de Doeblin si et seulement si elle est apériodique.

La condition de Doeblin permet d’obtenir la convergence de \((X_n)_{n \ge 0}\) vers sa probabilité invariante et une vitesse de convergence géométrique qui dépend de \(\alpha\) et de \(\ell \ge 1\). La vitesse est d’autant plus rapide que \(\ell\) est petit et \(\alpha\) proche de 1.

Dans la suite on note \(\|\cdot\|\) la norme en variation d’une mesure (signée) \(\mu\) sur \(E\) définie comme \(1/2\) de la norme \(l^1\) d’un vecteur de \(\mathbf{R}^E\) i.e.

(3.3)\[\begin{equation} \| \mu \| = \frac{1}{2} \sum_{x \in E} |\mu(x)|. \end{equation}\]

Proposition 3.2

Si \((X_n)_{n \ge 0}\) est une CM de matrice de transition \(P\) irréductible vérifiant la condition de Doeblin, alors pour toute loi initiale \(\nu\) de \(X_0\), la loi de \(X_n\) converge en variation vers une probabilité \(\pi\), plus précisément

\[\begin{equation*} \| \nu P^n - \pi \| \le (1 - \alpha)^{\lfloor n / l \rfloor}. \end{equation*}\]

De plus \(\pi\) est l’unique probabilité invariante de \((X_n)_{n \ge 0}\).

Proof. On suppose d’abord le cas \(\ell = 1\). Soit \(\mu\) et \(\mu'\) deux probabilités quelconques sur \(E\), alors

\[\begin{align*} \| \mu P - \mu'P \| & = \frac{1}{2} \sum_{y \in E} |\mu P(y) - \mu' P(y)|, \\ & = \frac{1}{2} \sum_{y \in E} \big| \sum_{x \in E} (\mu(x) - \mu'(x)) P(x, y) \big|, \end{align*}\]

Or \(\sum_{x \in E} (\mu(x) - \mu'(x)) c(y) = 0\) pour tout \(y \in E\) donc

\[\begin{equation*} \| \mu P - \mu' P \| = \frac{1}{2} \sum_{y \in E} \big| \sum_{x \in E} (\mu(x) - \mu'(x)) (P(x, y) - \alpha c(y)) \big|. \end{equation*}\]

Par inégalité triangulaire et comme \(P(x, y) - \alpha c(y) \ge 0\) et \(\sum_{y \in E} (P(x, y) - \alpha c(y)) = 1-\alpha\), on obtient par Fubini

\[\begin{align*} \| \mu P - \mu' P \| & \le \frac{1}{2} \sum_{x \in E} |\mu(x) - \mu'(x)| (1 - \alpha), \\ & = (1 - \alpha) \| \mu - \mu' \|. \end{align*}\]

L’application \(\big( \mu \mapsto \mu P \big)\) est contractante de rapport \((1-\alpha)\) pour la norme en variation. Elle admet donc un unique point fixe qu’on note \(\pi\), probabilité sur \(E\) vérifiant \(\pi = \pi P\). Si \(X_0\) est de loi \(\nu\) alors \(X_n\) est de loi \(\nu P^n\) et

(3.4)\[\begin{equation} \| \nu P^n - \pi \| = \| \nu P^n - \pi P^n \| \le (1 - \alpha)^n \|\nu - \pi\|, \end{equation}\]

en itérant. On conclut en remarquant que \(\|\nu - \pi\| \le \|\nu\| + \|\pi\| = 1\).

Pour le cas général \(\ell > 1\), on considère la chaine de Markov \((X_{k \ell})_{k \ge 0}\) qui est de transition \(P^\ell\) et qui vérifie Doeblin avec \(\ell' = 1\), le même \(\alpha > 0\) et la même probabilité \(c\) que \((X_n)_{n \ge 0}\). D’après ce qui précède, si \(X_0 \sim \nu\) alors

(3.5)\[\begin{equation} \| \nu P^{k \ell} - \pi \| \le (1 - \alpha)^k, \end{equation}\]

où \(\pi\) est l’unique probabilité vérifiant \(\pi = \pi P^\ell\) i.e. \(\pi\) est invariante pour \(P^\ell\). Mais on a

\[\begin{equation*} \pi P = \pi P^\ell P = (\pi P) P^\ell, \end{equation*}\]

donc \(\pi P\) est invariante pour \(P^\ell\) et par unicité \(\pi = \pi P\) donc \(\pi\) est invariante pour \(P\). Soit \(n \ge 1\) une itération que l’on écrit sous la forme \(n = k \ell + p\) avec \(0 \le p < \ell\), alors

\[\begin{equation*} \| \nu P^n - \pi \| = \| \nu P^{k\ell+p} - \pi P^\ell \| \le (1-\alpha)^k \| \nu P^\ell - \pi \|. \end{equation*}\]

d’où le résultat énoncé avec \(k = \lfloor n / \ell \rfloor\).