# Sur certaines chaînes de Markov non homogènes

J. Larisse, M. P. Schüüzenberger

► To cite this version:

J. Larisse, M. P. Schüüzenberger. Sur certaines chaînes de Markov non homogènes. Annales de l'ISUP, 1964, XIII (1), pp.57-66. hal-04085150

HAL Id: hal-04085150

https://hal.science/hal-04085150

Submitted on 28 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
0

(1)

G₀
Il
qui

ro-
en-
on
par
du
ents
1 0
ite
0.

lian

# SUR CERTAINES CHAINES DE MARKOV NON HOMOGÈNES

par J. LARISSE et M. P. SCHÜTZENBERGER

Soit donnée une chaîne de Markov non-homogène sur un ensemble fini d'états I, c'est-à-dire, soit donnée une représentation $\mu$ d'un monoïde libre F dans le monoïde M des $I \times I$ matrices stochastiques. Pour chaque $f \in F$, le sous-monoïde $\{ \mu f^n : n \in \mathbb{N}_M \}$ de M est une chaîne de Markov finie au sens habituel ; si $\mu f$ appartient au sous-ensemble $M_r$ de M des $I \times I$ matrices stochastiques ayant exactement r racines caractéristiques de module unité, (c'est-à-dire si la chaîne de Markov $\{ \mu f^n : n \in \mathbb{N}_M \}$ a exactement r classes ergodiques), la matrice $\mu f^{r_1} = (\mu f)^{r_1}$ est apériodique et, par conséquent, $\lim_{k \to \infty} \mu f^{kr_1+1}$ existe. C'est une matrice stochastique que l'on désignera par $\bar{\mu}f$ et qui appartient au sous-ensemble $\bar{M}_r \subset M$, des matrices n'ayant que des racines nulles ou de module unité et dont les puisances successives forment un groupe fini.

D'autre part, la donnée de $\mu$ détermine de façon univoque un homomorphisme $\omega$ de F dans le groupe additif des réels tel que pour chaque générateur $x$ de F on ait :

$\omega x$ = la borne inférieure des entrées positives de $\mu x$ si celles-ci ne sont pas toutes égales à un et $\omega x = 0$ dans le cas contraire (c'est-à-dire si $\mu x$ est un élément du sous-monoïde P de M constitué par les matrices représentant des applications de I dans lui-même).

Pour simplifier, on fera l'hypothèse qu'il existe une valeur positive $\bar{\omega}$ tel que $\omega x > \bar{\omega}$ ou $= 0$ pour tout générateur $x$ et on po-
sera $F_z = \{ f \in F : \omega f > z \}$ pour chaque valeur réelle $z$ (ce qui entraîne donc $\mu f \in P$ pour tout $f \in F \setminus F_o$). Avec ces notations, il résulte d'un théorème récent de J. Wolfowitz [1] (1) que si $\mu f \in M_1$ pour tout $f \in F_o$ on a : $(W_1)$. $0 = \lim_{z \to \infty} \max \{ \| \mu f_1 f_2 - \bar{\mu} f_2 \| : f_1 \in F ; f_2 \in F_z \}$, où la norme $\| \cdot \|$ d'une $I \times I$ matrice quelconque $m$ est $\max_{i \in I} \sum_{j \in I} |m_{i, j}|$.

On se propose ici de vérifier en application de ce théorème que s'il existe un entier $r$ tel que $\mu f \in M_r$ pour tout $f \in F_o$, on peut trouver une application $\pi$ de $F$ dans un sous-ensemble fini de $M$ telle que l'on ait :

$$ (W_r) : 0 = \lim_{z \to \infty} \max \{ \| \mu f_1 f_2 f_3 - \bar{\mu} f_1 \cdot \pi f_2 - \bar{\mu} f_3 \| : f_2 \in F ; f_1, f_3 \in F_z \} . $$

Si toutes les matrices $\mu f$ ($f \in F_o$) satisfont la condition plus forte d'appartenir à $M_r$ et d'avoir r racines égales à un, (c'est-à-dire si toutes les chaînes $\{ \mu f^n : n \in \mathbb{N}^\infty \}$ ($f \in F_o$) sont apéridiques), l'introduction de $\pi$ est inutile et l'on peut écrire :

$$ (W_r^*) : 0 = \lim_{z \to \infty} \max \{ \| \mu f_1 f_2 f_3 - \bar{\mu} f_1 \cdot \mu f_3 \| : f_2 \in F ; f_1, f_3 \in F \} . $$

Nous ne sommes pas en mesure d'apprécier ici la signification éventuelle de ces relations dans la théorie générale des "automates probabilistes" de M. Rabin [2].

## Vérification de la propriété

Nous supposons la représentation $\mu$ donnée et telle que $\{ \mu f : f \in F_o \} \subset M_r$. Le *support* (ou *type* [1]) d'une matrice $m \in M$ est l'ensemble $\beta m \in \mathfrak{P} (I \times I)$ des paires $(i, i') \in I \times I$ telles que $0 \neq m_{i, i'}$, le support de la i-ième ligne de $m$ étant désigné par $\beta_i m = \{ i' \in I : (i, i') \in \beta m \}$. Pour $m, m' \in M$, le *produit* $\beta m \cdot \beta m'$ des supports $\beta m$ et $\beta m'$ est, comme d'usage (cf. [3]), l'ensemble des paires $(i, i'') \in I \times I$ telles que $(i, i') \in \beta m$ et $(i', i'') \in \beta m'$ pour au moins un $i' \in I$. Donc,

<footnote>(1) Nous remercions le Professeur Wolfowitz d'avoir bien voulu nous communiquer son travail avant sa publication.</footnote>
$\beta\text{mm}' = \beta \text{m}, \beta\text{m}'$ et on peut considérer $\beta$ comme un homomorphisme du monoïde $\{ \mu f : f \in F \}$ dans le sous-monoïde de $\mathfrak{P}(I \times I)$ constitué par tous les supports $\beta\text{m}$ tels que $\beta_i \text{m} \neq \emptyset$ pour chaque $i \in I$.

Il résulte immédiatement de ceci que pour $m, m' \in M$ et $i, i' \in I$ on a :

si $\beta_i \text{m}$ est un élément minimal de la famille $\{ \beta_j \text{m} : j \in I \}$ ordonnée par inclusion, $\beta_i \text{mm}'$ est un élément minimal de la famille $\{ \beta_j \text{mm}': j \in I \}$ ;

si $\beta_i \text{mm}' \cap \beta_j' \text{mm}' = \emptyset$, alors, d'une part $\beta_i \text{m} \cap \beta_j' \text{m} = \emptyset$, d'autre part $\beta_j \text{m}' \cap \beta_j' \text{m}' = \emptyset$ pour tout $j \in \beta_i \text{m}$ et $j' \in \beta_j' \text{m}$.

Nous dirons que $\beta \text{m}$ est cyclique si $\beta \text{m} = \beta \text{m}^{2+n}$ pour au moins un $n \in \mathbb{N}$ (et par conséquent pour une infinité de $n \in \mathbb{N}$). On sait que quelque soit $m \in M$, $\beta \text{m}^n$ est cyclique pour $n > (\text{Card } I)!$.

Il est clair que la propriété pour une matrice $m \in M$ d'avoir ou non r racines de modules unité, ainsi que la valeur de ces racines dépend exclusivement de son support $\beta \text{m}$. De la même façon si $m \in M_r$, et si $\bar{m} = \lim_{k \to \infty} m^{k r^k + 1}$, le support $\beta \bar{m}$ ne dépend que du support $\beta \text{m}$. Plus précisément, $\mu f \in M_r$ si la chaîne de Markov $\{ \mu f^n : n \in \mathbb{N} \}$ a exactement r classes ergodiques auxquelles on réservera la notation $I_1^*(f)$, $I_2^*(f)$, ..., $I_r^*(f)$ en posant $I^*(f) = \bigcup \{ I_j^*(f) : j \in [1,r] \}$. On sait que si $\mu f \in M_r$, la restriction à $I_j^*(f) \times I$ du support de $\mu f$ est contenue dans un "rectangle" $I_j^*(f) \times I_j^*(f)$ (Cf. [3]) et qu'elle est égale à ce rectangle si $\beta \mu f$ est cyclique. De même la restriction à $I \times I^*(f)$ du support de $\mu f$ est contenue dans $\beta \bar{\mu} f$ et $\beta \bar{\mu} f$ est égale à la restriction à $I \times I^*(f)$ du support de $\mu f$ quand $\beta \mu f$ est cyclique.

Ces notions étant rappelées, définissons $\mathbb{R}$ comme la fermeture convexe du sous-ensemble $P_r \subset \mathbb{P}$ des matrices représentant une application $I \to I$ telle que l'image $I_p$ de $I$ ait au plus r éléments. A chaque $f \in F$ nous associons $\chi_f \in [0,1]$, $\mu_R f \in \mathbb{R}$ et $\mu_R^* f \in M$ par les relations suivantes :
$\mu f = (1 - \chi f) \cdot \mu_R f + \chi f \cdot \mu_R^2 f;$

$\chi f = \text{Min} \{ \chi \in [0,1] : \mu f = (1 - \chi) \cdot m + \chi \cdot m' ; m \in \mathbb{R}, m' \in \mathbb{M} \}$

Enfin, nous désignons par $F_+$ l'ensemble des $f \in F$ tel qu'il existe au moins un $g \in F_0$ de support cyclique et une paire $f', f'' \in F$ satisfaisant $\beta \mu f = \beta \mu f' \text{gf''}$.

**REMARQUE 1.** Pour chaque $f \in F_+$ on a $\chi f < 1$ et $\beta \mu_R f \subset \beta \mu f$.

**Vérification.** Il est clair que $PP_r P \subset P_r$ et que le support de tout $m \in M$ est une union de supports d'applications $p' \in P$. Il en résulte immédiatement que $\chi f' \le \chi f$. $\chi f'$ pour tout $f$, $f' \in F$.

Considérons $g \in F_0$ de support cyclique. Si $I' \subset I$ a un et un seul élément en commun avec chacune des classes ergodiques $I_j^*(g)$, le fait que pour chaque $i \in I$ la ligne $\beta_i \mu g$ contienne au moins un $I_i(g)$ montre qu'il existe au moins un $p \in P_r$ tel que $I' = Ip$ et $\beta p \subset \beta \mu f$. Donc $\chi g < 1$ et par conséquent $\chi f' \text{gf''} < 1$ pour tout $f'$, $f'' \in F$. Comme la propriété $\chi m < 1$ ne dépend en fait que de $\beta m$, l'inégalité $\chi f < 1$ pour $f \in F_+$ est établie.

Soit maintenant $\beta p \subset \beta \mu f$ où $p \in P_r$ et $f \in F$. Si $I' = Ip$, l'union des supports des colonnes de $\mu f$ d'indice $i \in I'$ est égale à $I$, et il en est de même pour toute matrice de la forme $\mu f' f$. Prenant $f' = f$ tel que $\beta \mu f' f$ soit cyclique, on en conclut que $I'$ doit avoir un (et un seul) élément en commun avec chacune des classes ergodiques $I_j^*(f)$ et qu'en particulier $I' \in I^*(f)$. Comme $\beta p \subset \beta \mu f$ et comme la restriction de $\beta \mu f$ à $I \times I^*(f)$ est contenue dans $\beta \mu f$, la remarque est entièrement vérifiée.

Il résulte de $\beta \mu f \subset \beta \mu f$ que chaque classe $I_j^*(f)$ admet un sous-ensemble minimal $I_j^{*(f)}$ tel que $I^{*(f)} \times I_j^{*(f)}$ contienne la restriction à $I^{*(f)} \times I_j^{*(f)}$ du support de $\mu_R f$. De même, il existe un sous-ensemble maximal $I_j^{**}(f)$ contenant tous les $i \in I$ tels que $\beta_i \mu_R f \subset I_j^{**}(f)$.
RENARQUE 1 bis. Si $f, f' \in F_+$, il correspond à chaque $j \in [1, r]$ un et un seul $j' \in [1, r]$ tel que $I_j^*(f) \subset I_{j'}^*(f')$.

Vérification. Soit pour $m \in M$, $\Delta(m)$ la cardinalité maximale d'un ensemble de lignes de m ayant leurs supports deux à deux disjoints. On vérifie facilement que pour tout $m$, $m' \in M$ on a $\Delta(\text{mm}') \le \Delta(m)$, $\Delta(m')$. Donc, si $f \in F_+$, on a $\Delta(\mu f) \le r$ puisque $\beta\mu f$ admet $\beta\mu g$ comme facteur et $\Delta(\mu f) = r$ puisque $\Delta(\mu f) = r$ pour $n \ge (\text{Card } I)!$.

Considérons maintenant le cas particulier de l'énoncé où $\beta\mu f$ et $\beta\mu f'$ sont cycliques. La relation $\Delta(\mu f') = r$ montre que pour chaque $i \in I_j^*(f)$, le support $\beta_i\mu f'$ doit avoir une intersection non vide avec une seule classe $I_{j'}^*(f)$. Le cas général s'en déduit immédiatement: en effet, $I_j^*(f) \subset I_{j'}^*(f)$ et les seuls $i \in I$ tels que $\beta_i\mu f'$ n' intersecte qu'une seule classe $I_{j'}^*(f')$, appartiennent à l'union $I_j^{**}(f')$ des ensembles disjoints $I_{j'}^{**}(f')$.

Nous écrivons désormais pour abréger $\lim_{z \to \infty} \max$ et nous désignons par $f_z$ et $f'_z$ des variables liées par la condition $f_z, f'_z \in F_z$.

RENARQUE 2. $\lim_{z \to \infty} \| \mu f_z - \mu_R f_z \| = 0$.

Vérification. Soit $B = \{ \beta \mu f : f \in F_o \}$. Si un élément $b \in B$ appartient à une $\mathcal{A}$-classe régulière ([4]), il existe un élément $b' \in B$ tel que $b^{12} = b'$ et $b'b = b$. Donc si $B_+$ est l'idéal de B engendré par les $\mathcal{A}$-classes régulières, l'image inverse de B par $\beta^{-1}$ appartient à $F_+$.

Soit $h$ le nombre des $\mathcal{A}$-classes de $B$. Nous montrons d'abord que tout produit $b_1b_2...b_h$ de $\bar{h} = 2^{h-1}$ éléments de $B$ a au moins un facteur droit non vide $b_{k_0}...b_{k_{l_1}}...b_h$ appartenant à une $\mathcal{A}$-classe régulière de $B$. Ceci est trivial pour $h = 1$ puisque dans ce cas $B$ a une seule $\mathcal{A}$-classe qui est nécessairement régulière. On peut donc supposer le résultat vérifié quand $B$ a moins de $h > 1$ $\mathcal{A}$-classes et, naturellement, on peut aussi supposer qu'aucun des $b_{k_i}$ ($k' = 1, 2, ..., \bar{h} = 2^{h-1}$)
n'appartient lui-même à une $\mathcal{A}$-classe régulière. Comme toutes les $\mathcal{A}$-classes considérées sont finies, ceci entraîne ([5]) que pour chaque $k' < \bar{h}$ les trois éléments $b_{k'}$, $b_{k'+1}$ et $b_k, b_{k'+i}$ n'appartiennent pas à la même $\mathcal{A}$-classe. Donc le sous-monoïde engendré par les $2^{h-2}$ produits $b_1b_2, b_3b_4, \dots, b_{h-1}b_h$ a au plus h-1 $\mathcal{A}$-classes et le résultat découle de l'hypothèse d'induction.

Soit maintenant $F'_+ = F_+ \setminus (F_+)^2$. Le résultat qui vient d'être vérifié montre que tout $f \in (F_0)^{n\bar{h}}$ a au moins n facteurs dans $F'_+$. En outre, faisant intervenir l'hypothèse selon laquelle $\omega x = 0$ ou $\omega x > \bar{\omega} > 0$ pour tout $x \in X$, on voit que $\omega f > 1 - \bar{\omega}^{\bar{h}}$ pour tout $f \in F'_+$. Donc $\chi f < (1 - \bar{\omega})^n$ pour chaque $f \in (F_0)^{n\bar{h}}$ ce qui entraîne $\text{Lim } \chi f_z = 0$ et achève la vérification de la remarque 2.

Soit V l'ensemble des I-vecteurs v à coordonnées non négatives tels que $\sum_{i \in I} v_i = 1$. Pour $(v, v') \in V \times V$ et $m \in M$ nous posons : $\delta_{v,v'}m = 1 - \sum_{i \in I} \text{Min} \{ (vm)_i, (v'm)_i \}$. D'après Hajnal ([6]), pour tout $m' \in M$ on a : $0 \le \delta_{v,v'}mm' \le \delta_{v,v'}m \le 1$ avec $\delta_{v,v'}m = 0$ (resp. = 1) si et seulement si $vm = v'm$ (resp. $\beta vm \cap \beta v'm = \emptyset$). Quand $\mu$ et $\mu'$ sont deux applications de F dans M telles que : $\text{Lim } \| \mu f_z - \mu' f_z \| = 0$ on a évidemment $\text{Lim } | \delta_{v,v'}\mu f_z - \delta_{v,v'}\mu' f_z | = 0$.

Nous considérons maintenant un sous-ensemble fixe K de I ayant r éléments et nous définissons la $I \times I$ matrice $e_k$ par $(e_k)_{i,i'} = 1$ si $i = i'$ $\in K$ ; $= 0$, autrement. Pour abréger, nous écrivons $m' \in M'$ (resp. $m'' \in M''$) si $m' = m \cdot e_k$ (resp. $m'' = e_k \cdot m$ pour au moins un $m \in M$) et si $m'$ contient r lignes ayant des supports disjoints telles que toute autre ligne soit une combinaison linéaire à coefficients non négatifs de ces dernières (resp. et si $m''$ a r lignes ayant des supports disjoints non vides.).

**REMARQUE 3.** Il existe deux applications $\mu' : F \to M'$ et $\mu'' : F \to M''$ telles que $\text{Lim } \| \mu f_z - \mu' f_z \| = 0$.
**Vérification** : Nous utilisons les notations de la Remarque 1 bis. Le support de la restriction de $\mu_R f_z$ à $I^{\#}(f_z) \times I$ est une union de r rectangles dis joints $I_j^{\#}(f_z) \times I_j$, $(f_z)$. Comme $\mu_R f_z$ appartient à la ferme- ture convexe $\overline{R}$ de $\overline{P}$, ceci entraîne que deux lignes quelconques de cette matrice soient égales quand l'intersection de leurs supports n'est pas vide. Il existe donc une matrice $\mu''f_z \in \overline{M}''$ dont les lignes non nulles sont égales aux r lignes distinctes de la restriction de $\mu_R f_z$ à $I^{\#}(f_z) \times I$.

Soit $f'_z$ un autre élément de $\overline{F}_z$. D'après la Remarque 1 bis, chacun des ensembles $I_j^{\#}(f')$ est contenu dans un et un seul ensembles $I_j^{\#}(f_z)$ et $\mu_R f'_z$ est identique à la somme de ses restrictions à $I \times I_j^{\#}(f_z)$ ($j \in [1, r]$). Donc deux lignes quelconques non nulles de la restric- tion à $I \times I_j^{\#}(f_z)$ de $\mu_R f'_z$. $\mu_R f_z$ sont proportionnelles et l'on peut trouver une application $\upsilon' : \overline{F} \times \overline{F} \to \overline{M}'$ telle que l'on ait $\mu_R f'_z$. $\mu_R f_z = \upsilon'(f'_z, f_z)$. $\mu'_f_z$ identiquement. D'après la Remarque 2, $\lim_{\|\mu'_f_z f'_z - \mu_R f'_z\| = 0} \lim_{\|\mu f'_z f_z - \upsilon'(f'_z, f_z) \mu'_f_z\| = 0}$ ce qui entraîne la validité de la Remarque 3.

**REMARQUE 3 bis.** Si les applications $\mu' : \overline{F} \to \overline{M}'$ ; $\upsilon : \overline{F} \times \overline{F} \times \overline{F} \to \overline{M}$ et $\mu''$: $\overline{F} \to \overline{M}''$ satisfont la relation $\lim_{\|\mu f_z f'_z - \mu'_f_z \upsilon(f_z, f, f'_z)\| = 0}$, il existe trois applications $\bar{\mu}' : \overline{F} \to \overline{M}'$ ; $\rho : \overline{F} \times \overline{F} \times \overline{F} \to \overline{M}''$ et $\bar{\mu}''$: $\overline{F} \to \overline{M}''$ telles que :

$$ \lim_{\|\mu'_f_z - \bar{\mu}' f_z f'_z\|} = \lim_{\|\upsilon(f_z, f, f'_z) - \rho(f_z, f, f'_z)\|} = $$

$$ \lim_{\|e_K \circ \upsilon(f_z, f, f'_z) \cdot \mu'' f_z - \bar{\mu}'' f_z f'_z\|} = 0, \text{ et qu'en outre, d'une part la restriction de } \rho(f, f, f') \text{ à } K \times I \text{ représente une permutation de } K, \text{ d'autre part, pour tout } f' \in F_o, \bar{\mu}' f' = \bar{\mu}' f' \cdot \bar{\mu}'' f' \text{.} $$

**Vérification.** L'existence d'applications $\bar{\mu}' : \overline{F} \to \overline{M}'$ et $\bar{\mu}'' : \overline{F} \to \overline{M}''$ satis faisant l'identité $\bar{\mu}' f' = \bar{\mu}' f' \cdot \bar{\mu}'' f'$ est triviale et il est clair que toutes les paires d'applications satisfaisant ces conditions sont équivalentes sur $F_o$ à une permutation de $K$ près.
Désignons maintenant par $\lambda^i m$ la plus grande entrée de la i-ème colonne de m. Il est bien connu que $\lambda^i m^m < \lambda^i m$ identiquement. Donc pour tout $i \in I$ et $(f_z, f, f'_z) \in F \times F \times F$ on a $\lambda^i \bar{\mu} f_z f'_z = \lambda^i \bar{\mu}'' f_z f'_z \le \lambda^i \mu f_z f'_z$ et
$$ \lambda^i (\mu' f_z, \cup(f_z, f, f'_z), \mu'' f'_z) \le \lambda^i (\cup(f_z, f, f'_z), \mu'' f'_z) \le \lambda^i \mu'' f'_z. $$
Les hypothèses impliquent

$$ \mathrm{Lim} \ || \lambda^i (\mu' f_z, \cup(f_z, f, f'_z), \mu'' f'_z) - \lambda^i \mu f_z f'_z || = 0 $$

et, comme $\bar{\mu} f_z f'_z$ et $\mu'' f'_z$ appartiennent à $M''$, on a $\sum_{i \in I} \lambda^i \bar{\mu}'' f_z f'_z = \sum_{i \in I} \lambda^i \mu'' f'_z = r$. Donc, pour chaque $i \in I$, $\mathrm{Lim} |\lambda^i \bar{\mu}'' f_z f'_z| - \lambda^i (\cup(f_z, f, f'_z), \mu'' f'_z)| = \mathrm{Lim} |\lambda^i (\cup(f_z, f, f'_z), \mu'' f'_z)| - \lambda^i \mu'' f'_z| = 0$ et $\mathrm{Lim} \sum_{i \in I} \lambda^i (\cup(f_z^*, f, f'_z), \mu'' f'_z) = r$ ce qui montre l'existence de $\rho: F \times F \times F \to M$, identique à $\cup$ sur $(\Gamma K) \times I$, se réduisant à une permutation de K sur $K \times I$ et satisfaisant $\mathrm{Lim} || \cup(f_z, f, f'_z) - \rho(f_z, f, f'_z) || = 0$. D'après la première de ces relations on peut choisir $\bar{\mu}'': F \to M''$ telle que $\mathrm{Lim} || e_K \cdot \rho(f_z, f, f'_z), \mu'' f'_z - \bar{\mu}'' f_z f'_z || = 0$. Ceci établit la partie de la remarque concernant les applications $\bar{\mu}''$ et $\rho$.

De façon analogue, pour tout $(v, v') \in V \times V$ on a :

$$ \delta_{v,v'}, \bar{\mu}' f_z f'_z = \delta_{v,v'}, \bar{\mu} f_z f'_z \le \delta_{v,v'}, \mu f_z f'_z \text{ et } \mathrm{Lim} \delta_{v,v'}, \mu f f' < \mathrm{Lim} \delta_{v,v'}, \mu f_z. $$

Comme l'ensemble des $(v, v') \in V \times V$ telles que $\delta_{v,v'}, \bar{\mu}' f_z f'_z$ (resp. $\delta_{v,v'}, \mu' f_z$) est 0 ou 1 détermine $\bar{\mu}'$ (resp. $\mu'$) à une permutation près de K et comme le support de la restriction de $\mu f_z f'_z$ à $I \times I^*(f_z, f'_z)$ est contenu dans $\beta \bar{\mu} f_z f'_z$, la vérification est achevée.

**PROPRIETE 1** : Si $\mu: F \to M$ est telle que pour chaque $f \in F_o$ la chaîne de Markov $\{ \mu^\alpha : n \in \mathbb{N} \}$ a exactement r classes ergodiques, il existe une application $\pi$ de F dans un sous ensemble fini de M telle que :

$$ (W_r) \cdot \mathrm{Lim} \ || \mu f_z f'_z - \bar{\mu} f_z \cdot \pi f \cdot \bar{\mu} f'_z || = 0. $$

Si en outre toutes les chaînes $\{ \mu^\alpha : n \in \mathbb{N} \}$ ($f \in F_o$) sont apériodiques, on peut écrire :

$$ (W_r^*) \cdot \mathrm{Lim} \ || \mu f_z f'_z - \bar{\mu} f_z \cdot \mu f'_z || = 0. $$
Vérification. D'après la Remarque 3, il existe deux applications $\mu' : F \to M'$ et $\mu'' : F \to M''$ telles que $\lim_{\|\mu\|} \|\mu'_{F_z} - \mu''_{F_z}\| = 0$.

Prenant une application $\nu$ de $F \times F \times F$ sur la matrice unité $e_I$ et employant la Remarque 3 bis, ceci montre que $\lim_{\|\bar{\mu}f_z - \mu f_z\|} = 0$ et qu'il n'y a aucune diminution de généralité à supposer désormais que $\mu' = \bar{\mu}'$ et $\mu'' = \bar{\mu}''$, c'est-à-dire que $\mu'f$. $\mu''f = \bar{\mu}f$ pour tout $f \in F_o$. Le premier de ces résultats donne

$$ \lim_{\| \mu f_z f'_z - \bar{\mu} f_z \|} \| \mu f_z f'_z \| = \lim_{\| \bar{\mu} f_z f'_z - \mu f_z \|} \| \bar{\mu} f_z f'_z \| = 0. $$

Comme $\bar{\mu}f_z$. $\mu f$. $\bar{\mu}f'_z = \mu'f_z$. $\nu(f_z, f, f'_z)$. $\mu''f'_z$ où maintenant $\nu$ est une application quelconque de $F \times F \times F$ dans $M$ telle que $e_K \cdot \nu(f_z, f, f') = \mu''f$. $\mu f$. $\mu'f'$, on peut appliquer de nouveau la Remarque 3 bis qui montre cette fois l'existence d'une application $\rho$ de $F \times F \times F$ dans $M$ telle que $e_K \cdot \rho$ soit une permutation de $K$ et que $\lim_{\| \mu''f_z - e_K \cdot \rho(f_z, f, f'_z) \|} = 0$. D'après l'hypothèse faite plus haut, $\mu'f_z$. $\mu''f'_z = \bar{\mu}f_z$ et $\mu'f'_z$. $\mu''f'_z = \bar{\mu}f'_z$. On en conclut que $\mu''f_z$. $\mu f$. $\mu'f'_z$ est elle-même, pour tout $(f_z, f, f'_z) \in F \times F \times F_o$, une matrice ayant son support contenu dans $K \times K$ et représentant une permutation de cet ensemble.

Puisque les matrices $\mu'f_z$, $\mu f$ et $\mu'f'_z$ ont des entrées non néga-tives, ceci entraîne $\mu''f_z$. $\mu f$. $\mu'f'_z = \mu'f_z$. $\pi f$. $\mu'f'_z$ quelque soit l'appli-cation $\pi : F \to M$ telle que $\beta\mu f = \beta\pi f$. Par conséquent, sous cette hypothèse $\bar{\mu}f_z$. $\mu f$. $\bar{\mu}f'_z = \bar{\mu}f_z$. $\pi f$. $\bar{\mu}f'_z$ ce qui achève la vérification de $(W_r)$ puisque le monoïde $\{ \beta\mu f : f \in F \}$ est fini.

Supposons maintenant que toutes les chaînes $\{ \mu f^n : n \in \mathbb{N} \}$ soient apériodiques, c'est-à-dire que $\bar{\mu}f = \bar{\mu}f^2$ pour tout $f \in F_o$, c'est-à-dire encore, (dans les notations de la Remarque 2 bis) que $I_j^{*(f)} \subset I_j^{**}(f)$ pour tout $j \in [1, r]$. La Remarque 2 bis montre que l'on peut choisir l'indexage des classes ergodiques des différentes chaînes $\{ \mu f^n : n \in \mathbb{N} \}$ ($f \in F_o$) de telle sorte que $I_j^{*(f)} \subset I_j^{*(f')}$ pour tout $f, f' \in F_x$ et $j \in [1, r]$. Ceci entraîne que $\mu''f_z$. $\mu'f'_z = e_K$ identiquement quand $f_z, f'_z \in F_+$. La propriété est entièrement vérifiée.

<figure><img src="image_2.png" /></figure>
REFERENCES

[1]. J. WOLFOWITZ : Products of indecomposable, aperiodic stochastic matrices, Proc. Amer. Math. Soc. 14, (1963) : 733-737.

[2]. M.O. RABIN : Probabilistic Automata, Information and Control 6, (1963) : 230-245.

[3]. J. RIGUET : Relations binaires, fermetures, correspondances de Galois, Bull. Soc. Math. France, 76, (1948) : 114-155.

[4]. D.D. MILLER and A.H. CLIFFORD : Regular $\omega$-classes in semi-groups, Trans. Amer. Math. Soc., 82, (1956) : 270-280.

[5]. J.A. GREEN : On the structure of semi-groups, Ann. of Math. 54, (1951) : 163-172.

[6]. J. HAJNAL : Weak ergodicity in non-homogeneous Markov chains, Proc. Cambridge Philos. Soc., 54, (1958) : 233-246.

Cetis Euratom (Ispra)

et Faculté des Sciences (Poitiers)

Reçu le 22 décembre 1963

<figure><img src="image_3.png" /></figure>