Theory and Applications of Categories, Vol. 22, No. 7, 2009, pp. 199–221.

LOIS DISTRIBUTIVES. APPLICATIONS AUX AUTOMATES STOCHASTIQUES

Dedicated to Albert Burroni on the occasion of the conference organised in Paris VII in 2002 in honour of his retirement.

ELISABETH BURRONI

Résumé. Deterministic automata are algebras of the monad T_{M} associated to a free monoid M. To extend to nondeterministic and stochastic automata such a monadic formalism, it is suitable to resort to a notion richer than the one of monad, but equally basic : the notion of distributive law between two monads. The notion of algebra on a monad is then generalized by the one of algebra for a distributive law. The nondeterministic and stochastic automata are precisely algebras for distributive laws whose first monad is T_{M}. If the nondeterministic case involves a distributive law between T_{M} and the well-known power set monad, the stochastic case involves a distributive law between T_{M} (where, here, M is a measurable monoid) and the probability monad. This allows presentation of the stochastic automata as algebras for this distributive law. This paper taking place at the confluence of the category, automata and probability theories, we have, for the convenience of the reader not aware of each area, made useful reviews about these subjects (in several appendices : A, B, C). We also recall in appendix D the detailed construction of the probability monad ; and, in appendix E, we construct precisely the distributive law which links it to the monad T_{M}.

1. Automates déterministes

Soit M = (M, e, m) un monoïde (e est l’unité de M et m, sa loi, sera notée multiplicativement : (a, b) ↦ ab, pour tout (a, b) ∈ M × M). On lui associe une monade T_{M} = (T_{M} , η, μ) sur la catégorie Ens des ensembles, définie de la manière suivante : l’endofoncteur T_{M} : Ens ⟶ Ens associe, à tout ensemble X, l’ensemble M × X et, à toute application f : X ⟶ Y, l’application M × f : M × X ⟶ M × Y : (a, x) ↦ (a, f(x)) ; de plus, pour tout ensemble X, ηX : X ⟶ M × X et μX : M × M × X ⟶ M × X sont les applications respectivement définies par ηX(x) = (e, x) et μX(a, b, x) = (ab, x) (voir A.4, où, plus généralement, on associe une monade à tout monoïde d’une catégorie monoïdale).

Une T_{M} -algèbre est un couple (X, θ), où X est un ensemble et θ : M × X ⟶ X une application vérifiant les axiomes (A_{1}) et (A_{2}) des algèbres (voir A.3), i.e. vérifiant, pour

Received by the editors 2008-11-27 and, in revised form, 2009-04-27. Transmitted by RJ Wood. Published on 2009-05-19. 2000 Mathematics Subject Classification: 18-02, 18C15, 18C20, 60G05, 60G07. Key words and phrases: category, monad, distributive law, probability. stochastic automata. \begin{matrix}c \\ ◯ \end{matrix} Elisabeth Burroni, 2009. Permission to copy for private use granted.

tout a, b ∈ M et tout x ∈ X,

θ(e, x) = x et θ(ab, x) = θ(a, θ(b, x))

Une T_{M} -algèbre s’appelle plus couramment un M-ensemble, mais, pour des raisons d’homogénéité de terminologie avec la suite, nous lui donnerons également le nom de M-auto-mate déterministe (de loi de transition θ). En se reportant à B.1, on constate trivialement le fait suivant :

1.1. Proposition. Dans le cas où M = Σ^{∗} (c’est-à-dire, le cas où M est le monoïde libre engendré par un ensemble fini Σ), une T_{M} -algèbre est la donnée d’un automate déterministe sur l’alphabet Σ.

Pour décrire, en restant dans un cadre “monadique”, les automates non déterministes et stochastiques, on a besoin d’une notion plus riche que celle de monade, celle de “loi distributive” entre deux monades (voir A.5).

2. Algèbres sur une loi distributive

Les automates non déterministes et stochastiques seront présentés plus loin comme deux cas particuliers d’une notion d’algèbre sur une loi distributive. Pour une introduction aux lois distributives, voir A.5 ; dans cette section nous introduisons ce nouveau type d’algèbre. Les données dans cette section sont les suivantes : T = (T, η, μ) et T′ = (T′, η′, μ′) sont deux monades sur une même catégorie C, et τ : T/T′ une loi distributive de T sur T′, i.e. c’est la donnée d’un triplet τ = (τ, T, T′), où τ : T T′ ⟶ T′T est une transformation naturelle rendant commutatifs les diagrammes (B_{i}) rappelés dans A.5. Tous les résultats donnés ci-dessous ont été démontrés dans [Bu’ 74].

2.1. On appelle τ-algèbre (appelée D-algèbre dans [Bu’ 74]), la donnée d’un couple (X, θ), où X est un objet de C et θ : T X ⟶ T′X un morphisme de C rendant commutatifs les diagrammes suivants dans C :

\xymatrix{(A′_{1}) & T X \ar[rr]^{θ} &  & T′X \\  &  & X \ar[ul]^{ηX} \ar[ur]_{η′X}}

\xymatrix{(A′_{2}) & T T X \ar[r]^{T θ} \ar[dr]_{μX} & T T′X \ar[r]^{τX} & T′T X \ar[r]^{T′θ} & T′T′X \ar[dl]^{μ′X} \\  &  & T X \ar[r]_{θ} & T′X}

On retrouve les T -algèbres, comme cas particulier des τ-algèbres, en prenant T′ = id_{C}, η′ = μ′ = id_{T′} et τ = id_{T}.

LOIS DISTRIBUTIVES. APPLICATIONS AUX AUTOMATES STOCHASTIQUES 201

2.2. La donnée d’une τ-algèbre sur X est équivalente à la donnée d’une T -algèbre sur T′X qui est τ-compatible avec la T′-algèbre libre μ′X (voir A.6). Plus précisément, si (X, θ) est une τ-algèbre, (T′X, μ′X ∘T′θ∘τX) est une T -algèbre qui est τ-compatible avec (T′X, μ′X) ; et inversement, si (T′X, θ) est une T -algèbre τ-compatible avec (T′X, μ′X), alors (X, θ ∘ T η′X) est une τ-algèbre.

2.3. La donnée de la loi distributive τ : T/T′ équivaut à la donnée d’un prolongement de la monade T sur C en une monade T̃ = (T̃, η̃, μ̃) sur la catégorie de Kleisli Kl(T′) (voir A.7), ce qui signifie que les diagrammes suivants commutent si, pour le second, on remplace le couple (⇓, ⇑) par chacun des couples (η, η̃) et (μ, μ̃) (où F_{T′} est défini dans A.7) :

\xymatrix{Kl(T′) \ar[r]^{T̃} & Kl(T′) & Kl(T′) \ar[r]_{⇑} \ar[r] & Kl(T′) \\ C \ar[u]^{F_{T′}} \ar[r]_{T} & C \ar[u]_{F_{T′}} & C \ar[r]_{⇓} \ar[r] \ar[u]^{F_{T′}} & C \ar[u]_{F_{T′}}}

Pour dire cela brièvement, ces diagrammes signifient que, moyennant l’identification de la catégorie C à son image F_{T′}(C) dans Kl(T′) (voir A.7), la restriction de la monade T̃ à C est la monade T. De plus, pour tout morphisme de Kleisli u : X −−→ Y (se reporter à A.7 pour cette notation), T̃u est le morphisme composé τY ∘ T u : T X −−→ T Y.

\xymatrix{ & T′Y &  & T T′Y \ar[r]^{τY} & T′T Y \\ X \ar[ur]^{u} \ar@{-->}[r]_{u} & Y & T X \ar[ur]^{T u} \ar[urr]^{T̃u} \ar@{-->}[rr]_{T̃u} &  & T Y}

2.4. Si θ : T X ⟶ T′X est un morphisme de C, alors (X, θ) est une τ-algèbre dans C ssi c’est une T̃-algèbre dans Kl(T′) ; en effet, remarquant que θ est en fait un morphisme de Kleisli T X −−→ X, ça n’est qu’une question de traduction dans Kl(T′) des axiomes (A′_{i}) de τ-algèbres donnés dans 2.1 : θ ∘ ηX = η′X et θ ∘ μX = μ′X ∘ T′θ ∘ τX ∘ T θ s’écrivent (voir A.7) θ ∘ ηX = \overline{id}_{X} et θ ∘ μX = μ′X ∘ T′θ ∘ T̃θ = θ ¯∘ T̃θ, ou encore, moyennant le fait que la monade T est la restriction de la monade T̃ à C, elle-même considérée comme une sous-catégorie de Kl(T′), θ ¯∘ η̃X = \overline{id}_{X} et θ ¯∘ μ̃X = θ ¯∘ T̃θ, qui ne sont autres que les axiomes (A_{i}) de T̃-algèbres rappelés dans A.3.

2.5. Ceci nous conduit à définir la catégorie Alg(τ) des τ-algèbres comme étant égale à la catégorie Alg(T̃) des T̃-algèbres ; ses objets sont donc les τ-algèbres et ses morphismes les u : (X, θ) −−→ (X′, θ′), i.e. les u : X −−→ X′ vérifiant u ¯∘ θ = θ′ ¯∘ T̃u (ce qui s’écrit T′f ∘ θ = θ′ ∘ T f dans le cas particulier où f : X ⟶ X′ est un morphisme de C).

On a un foncteur F : Alg(T) ⟶ Alg(τ), défini par F (X, θ) = (X, η′X ∘ θ) et F (f) = η′X′ ∘ f (où f : (X, θ) ⟶ (X′, θ′)) qui permet d’identifier Alg(T) à une sous-catégorie de Alg(τ) ; il admet un adjoint à droite U : Alg(τ) ⟶ Alg(T), défini par U(X, θ) = (T′X, μ′X ∘ T′θ ∘ τX) (voir 2.2) et U(u) = μ′X′ ∘ T′u (où u : (X, θ) −−→ (X′, θ′)). Ce couple d’adjoints (F, U) (c’est en fait un relèvement du couple d’adjoints (F_{T′}, U_{T′}) qui induit la monade T′ sur C (voir A.7)) induit lui-même la monade T̃′ sur Alg(T), de sorte que l’on a un foncteur de comparaison plein et fidèle Alg(τ) ⟶^{ϕ_{τ}} Alg(T̃′), défini par ϕ_{τ}(X, θ) = ((T′X, μ′X ∘ T′θ ∘ τX), μ′X) (voir 2.2 et A.6) et ϕ_{τ}(u) = μ′X′ ∘ T′u (où u est comme ci-dessus), qui vérifie les relations ϕ_{τ} ∘ F = F T̃′ et U T̃′ ∘ ϕ_{τ} = U ; ainsi la catégorie Alg(τ) est équivalente à la sous-catégorie pleine ϕ_{τ}(Alg(τ)) de Alg(T̃′) ≃ Alg(T̂) dont les objets sont les ((T′X, θ), μ′X) (voir 2.2 et A.6). Ce foncteur est un relèvement du foncteur de comparaison Kl(T′) ⟶^{ϕ} Alg(T′) rappelé dans A.7.

3. Automates non déterministes

3.1. Introduction. Les automates non déterministes constituent une première variante du cas déterministe. Soit Σ un ensemble fini ; dans un automate non déterministe sur l’alphabet Σ, l’action d’un mot sur un état a pour résultat, non pas un nouvel état (comme dans le cas déterministe), mais un ensemble d’états “possibles” (voir B.2) ; la loi de transition de cet automate est donc une application de la forme Σ^{∗} × X ⟶ PX, où PX est l’ensemble des parties de X. Précisément, on peut redéfinir les automates non déterministes sur un alphabet Σ comme les algèbres d’une loi distributive entre la monade associée au monoïde Σ^{∗} et la “monade des parties”. Nous généralisons en prenant un monoïde M quelconque au lieu de Σ^{∗} (voir [Bu’ 74]), et nous appellerons M-automate non déterministe, une τ-algèbre, où τ : T_{M} /T_{P} est la loi distributive que nous allons maintenant définir.

3.2. Précisément, considérons, comme dans le paragraphe 1, la monade T_{M} sur Ens associée à un monoïde M = (M, e, m) donné ; considérons aussi la monade des parties T_{P} = (P, η′, μ′) sur Ens, où l’endofoncteur P : Ens ⟶ Ens associe à tout ensemble X l’ensemble PX de ses parties, et à toute application f : X ⟶ Y l’application PX ⟶ PY qui, à toute partie A de X, associe son image f(A) dans Y ; de plus, η′X : X ⟶ PX et μ′X : PPX ⟶ PX sont respectivement les applications singleton et réunion. On montre facilement que l’application τX : M × PX ⟶ P(M × X), définie, pour tout (a, A) ∈ M × PX, par τX(a, A) = {a} × A, est la transformation naturelle d’une loi distributive τ : T_{M} /T_{P}. Une τ-algèbre est donc ici la donnée d’un ensemble X muni d’une application θ : M × X ⟶ PX vérifiant les axiomes (A′_{i}) ci-dessus, i.e. tels que, pour tout a, b ∈ M et tout x ∈ X, on ait :

θ(e, x) = {x} et θ(ab, x) = ∪_{y∈θ(b,x)}θ(a, y)

Se reportant à B.2, on obtient la proposition suivante :

3.3. Proposition. Dans le cas où M = Σ^{∗} (et où Σ est un ensemble fini), une τ-algèbre est la donnée d’un automate non déterministe sur l’alphabet Σ.

3.4. La donnée d’un automate non déterministe, i.e. d’une τ-algèbre M × X ⟶^{θ} PX

est équivalente (voir 2.2 ci-dessus) à la donnée d’une T_{M} -algèbre M × PX \underrightarrow{θ̃} PX qui est τ-compatible avec la multiplication μ′X, i.e. telle que, pour tout a ∈ M, l’opérateur θ̃(a, −) : PX ⟶ PX vérifie, pour tout 𝔄 ∈ PPX, θ̃(a, ∪_{A∈𝔄} A) = ∪_{A∈𝔄} θ̃(a, A). Plus précisément, la T_{M} -algèbre θ̃associée à la τ-algèbre θ est définie par θ̃(a, A) = ⋃_{x∈A} θ(a, x) (ainsi l’automate non déterministe sur les états se transforme en un automate déterministe sur les parties d’états, avec une condition de commutation aux réunions).

3.5. La catégorie de Kleisli de la monade T_{P} des parties est (plus précisément : est équivalente à) la catégorie Rel des relations entre ensembles ; en effet, un morphisme u : X −−→ Y dans cette catégorie de Kleisli (voir la convention sur la notation des morphismes de Kleisli et leur composition dans A.7), i.e. une application u : X ⟶ PY dans Ens équivaut à la donnée de la relation R_{u} ⊂ X × Y définie par (x, y) ∈ R_{u} ssi y ∈ u(x) ; on dira donc que u : X −−→ Y est une relation. Si maintenant v : Y −−→ Z est une autre relation, alors, d’après A.7, (v ¯∘ u)(x) = (μ′Z ∘ Pv ∘ u)(x) = ⋃_{y∈u(x)} v(y) ; par suite (x, z) ∈ R_{v¯∘u} ssi il existe y ∈ Y vérifiant (x, y) ∈ R_{u} et (y, z) ∈ R_{v}; on obtient donc la proposition suivante :

3.6. Proposition. La composition ¯∘ dans la catégorie de Kleisli Rel est la composition habituelle des relations.

D’après 2.3, on a un prolongement T̃_{M} : Rel ⟶ Rel qui, à toute relation u : X −−→ Y, associe la relation T̃_{M} u = τY ∘ (M × u) : M × X −−→ M × Y : (a, x) ↦ {a} × u(x). En particulier, pour θ : M ×X −−→ X, la relation T̃_{M} θ = τX∘(M ×θ) : M ×M ×X −−→ M ×X est définie par (T̃_{M} θ)(a, b, x) = {a} × θ(b, x).

De plus, se référant à 2.4, une τ-algèbre θ : M × X ⟶ PX dans Ens est aussi une T̃_{M} -algèbre θ : M × X −−→ X dans Rel.

4. Automates stochastiques

4.1. Introduction. Soit Σ un ensemble fini ; un automate stochastique sur l’alphabet Σ, lorsqu’il lit un mot, donne une probabilité sur les états (voir C.6) ; sa loi de transition (appelée probabilité de transition) est donc une application de la forme Σ^{∗} × X ⟶ ℙX, où ℙX est l’ensemble des probabilités sur X (on doit donc supposer que X est un espace mesurable). On obtient alors les automates stochastiques sur un alphabet Σ comme les algèbres d’une loi distributive entre la monade associée au monoïde Σ^{∗} et la “monade des probabilités”, ces monades étant définies, non pas sur Ens, mais sur la catégorie des espaces mesurables (Σ^{∗} étant muni de sa tribu discrète). Nous généralisons donc en prenant un monoïde M quelconque (mais mesurable : voir 4.2 ci-dessous) au lieu de Σ^{∗}.

4.2. Considérons la catégorie Mes des applications mesurables entre espaces mesurables. C’est une catégorie monoïdale (voir A.1) d’unité 1 et de loi monoïdale le produit d’espaces mesurables. Dans cette catégorie monoïdale, fixons un monoïde M = (M, e, m)

(nous dirons que c’est un monoïde mesurable : M est un espace mesurable, son unité et sa multiplication sont des applications mesurables ; voir A.2) et considérons la monade T_{M} = (T_{M} , η, μ) qui lui est associée sur Mes (voir A.4 ; cette monade est similaire à celle que nous avions définie sur Ens dans le paragraphe 1, sauf qu’ici, les applications ηX et μX sont mesurables pour tout espace mesurable X).

4.3. Décrivons la monade des probabilités T_{ℙ} = (ℙ, η′′, μ′′) sur Mes (voir [Tull 71], [Giry 81], et l’appendice D où nous donnons une preuve détaillée du fait que c’est une monade).

Son endofoncteur ℙ : Mes ⟶ Mes associe à tout espace mesurable X l’ensemble ℙX des probabilités sur X, que l’on munit de la plus petite tribu rendant mesurables les évaluations e_{A} : ℙX ⟶ [0, 1] : p ↦ p(A), lorsque A parcourt la tribu donnée sur X ([0, 1] étant muni de sa tribu borélienne). De plus, si f : X ⟶ Y est une application mesurable, ℙf : ℙX ⟶ ℙY est l’application définie, pour tout p ∈ ℙX, par ℙf(p) = f_{∗}(p), la p-loi de f sur Y (voir C.2).

L’unité et la multiplication de cette monade sont définies comme suit :

– η′′X : X ⟶ ℙX est l’application qui associe la probabililité de Dirac δ_{x} à l’élément x ∈ X;

– μ′′X : ℙ ℙX ⟶ ℙX est l’application qui, à toute probabilité p̂ sur ℙX, associe la probabilité μ′′X(p̂) sur X ainsi définie : pour toute partie mesurable A de X, (μ′′X(p̂))(A) = ∫_{ℙX} e_{A}dp̂ = ∫_{ℙX} e_{A}(p)p̂(dp) = ∫_{ℙX} p(A)p̂(dp) (c’est donc la p̂-moyenne des p(A) lorsque p parcourt ℙX; voir C.2 pour la notation des intégrales).

Bien entendu, les applications ℙf = f_{∗}, η′′X et μ′′X sont mesurables (car leurs composés avec chaque évaluation e_{A} sont mesurables… voir C.1 et l’appendice D).

4.4. On définit une loi distributive τ : T_{M} /T_{ℙ} de la manière suivante : pour tout espace mesurable X, l’application τX : M ×ℙX ⟶ ℙ(M ×X) est définie, pour tout (a, p) ∈ M × ℙX, par τX(a, p) = δ_{a} ⊗p (produit des probabilités δ_{a} et p) ; on vérifie (voir l’appendice E pour une preuve détaillée) que c’est une application mesurable pour tout espace mesurable X et que cela définit une transformation naturelle τ : T_{M} ℙ ⟶ ℙT_{M} qui vérifie les axiomes (B_{i}) des lois distributives (voir A.5). On obtient ainsi une loi distributive τ : T_{M} /T_{ℙ}.

4.5. Proposition. Soit τ : T_{M} /T_{ℙ} la loi distributive décrite dans 4.4 ci-dessus. Une τ-algèbre est la donnée d’un M-automate stochastique, i.e. (voir C.6), c’est la donnée d’un espace mesurable X et d’une application mesurable θ : M × X ⟶ ℙX tels que, pour tout a, b ∈ M, tout x ∈ X et toute partie mesurable A de X, on ait :

θ(e, x) = δ_{x} et (θ(ab, x))(A) =^{⋆} ∫_{X}(θ(a, y))(A)(θ(b, x))(dy)

Dans le cas où M = Σ^{∗} (et où Σ est un ensemble fini), une τ-algèbre est la donnée d’un automate stochastique sur l’alphabet Σ.

Preuve. Il s’agit donc de comparer les axiomes (A′_{i}) de τ-algèbre (voir 2.1) avec les axiomes ci-dessus. L’axiome (A′_{1}) donne immédiatement θ(e, x) = δ_{x} pour tout x ∈ X. Pour l’axiome (A′_{2}), soit a, b ∈ M, x ∈ X et A une partie mesurable de X; on obtient alors d’une part ((θ ∘ μX)(a, b, x))(A) = (θ(ab, x))(A) et, d’autre part ((μ′′X ∘ ℙθ ∘ τX ∘ (M × θ))(a, b, x))(A) = (μ′′X(θ_{∗}(δ_{a} ⊗ θ(b, x))))(A) = ∫_{ℙX} e_{A}d(θ_{∗}(δ_{a} ⊗ θ(b, x))) = ∫∫_{M×X} e_{A} ∘ θd(δ_{a} ⊗ θ(b, x)) = ∫∫_{M×X}(θ(c, y))(A)(δ_{a} ⊗ θ(b, x))(dcdy) = ∫_{X}(θ(a, y))(A)(θ(b, x))(dy). D’où l’égalité =^{⋆} cherchée.

4.6. La donnée d’une τ-algèbre M × X ⟶^{θ} ℙX est équivalente (d’après 2.2 ci-dessus)

à la donnée d’une T_{M} -algèbre M × ℙX \underrightarrow{θ̃} ℙX, τ-compatible avec la multiplication μ′′X (ainsi l’espace des probabilités d’un automate stochastique est un automate déterministe τ-compatible avec la multiplication de la monade T_{ℙ} des probabilités), i.e. telle que, pour tout a ∈ M et tout p̂ ∈ ℙ ℙX, on ait l’égalité : θ̃(a, μ′′X(p̂)) = μ′′X(θ̃_{∗}(δ_{a} ⊗ p̂)). Plus précisément, la T_{M} -algèbre θ̃ associée à la τ-algèbre θ est définie par (θ̃(a, p))(A) = (μ′′X(θ_{∗}(δ_{a} ⊗ p)))(A) = ∫_{ℙX} e_{A}d(θ_{∗}(δ_{a} ⊗ p)) = ∫∫_{M×X} e_{A} ∘ θd(δ_{a} ⊗ p) = ∫∫_{M×X}(θ(b, x))(A)(δ_{a} ⊗ p)(dbdx) = ∫_{X} θ(a, x)(A)p(dx) pour toute partie mesurable A de X.

4.7. La catégorie de Kleisli de la monade T_{ℙ} des probabilités est la catégorie, notée Stoch, dont les objets sont les espaces mesurables et les morphismes les probabilités de transition, puisqu’un morphisme de Kleisli u : X −−→ Y est une application mesurable u : X ⟶ ℙY (voir A.7 et C.4). De plus, si u : X −−→ Y et v : Y −−→ Z sont deux probabilités de transition, leur composé v ¯∘ u dans la catégorie de Kleisli Stoch est ainsi défini (voir A.7) : si x ∈ X et si p̂ est la probabilité image v_{∗}(u(x)) sur ℙZ (c’est donc un élément de ℙ ℙZ), alors (v ¯∘ u)(x) = μ′′Z(p̂) est la probabilité sur Z qui, à toute partie mesurable C de Z, associe le réel (μ′′Z(p̂))(C) = ∫_{ℙZ} e_{C}dp̂ = ∫_{Y} e_{C} ∘ vd(u(x)) = ∫_{Y} e_{C}(v(y))(u(x))(dy) = ∫_{Y} (v(y))(C)(u(x))(dy). On a donc obtenu l’égalité :

((v ¯∘ u)(x))(C) = ∫_{Y} (v(y))(C)(u(x))(dy)

pour tout x de X et toute partie mesurable C de Z; d’où la proposition suivante :

4.8. Proposition. [Giry 81] La composition ¯∘ dans la catégorie de Kleisli Stoch est exactement la composition habituelle des probabilités de transition rappelée dans C.4 : v ¯∘ u = vu.

D’après 2.3 ci-dessus, on a un prolongement T̃_{M} : Stoch ⟶ Stoch qui, à toute probabilité de transition u : X −−→ Y associe la probabilité de transition T̃_{M} u = τY ∘ (M × u) : M × X −−→ M × Y : (a, x) ↦ δ_{a} ⊗ u(x). En particulier, pour θ : M × X −−→ X, la probabilité de transition T̃_{M} θ = τX ∘ (M × θ) : M × M × X −−→ M × X est définie par (T̃_{M} θ)(a, b, x) = δ_{a} ⊗ θ(b, x).

De plus, se référant à 2.4, une τ-algèbre θ : M × X ⟶ ℙX dans Mes est aussi une T̃_{M} -algèbre θ : M × X −−→ X dans Stoch.

5. Processus et chaînes de Markov homogènes

On conserve ici la loi distributive τ : T_{M} /T_{ℙ} du paragraphe 4.

5.1. Se référant à C.8 et C.9, on obtient les corollaires suivants de la proposition 4.5 :

5.2. Corollaire. Dans le cas où le monoïde M est R_{+} (avec l’addition usuelle), que l’on munit de la tribu borélienne, une τ-algèbre étant un R_{+}-automate stochastique, c’est donc un processus Markovien homogène.

5.3. Corollaire. Dans le cas où le monoïde M est N (toujours pour l’addition usuelle), muni de la tribu discrète, une τ-algèbre étant un N-automate stochastique (le monoïde N est librement engendré par Σ = 1), c’est donc une chaine de Markov homogène.

5.4. Dans la catégorie de Kleisli Stoch, on a un objet des entiers naturels (i.e. un NNO… voir A.8) : c’est simplement l’ensemble N des entiers naturels muni de sa tribu discrète et des deux applications z : 1 ⟶ N : 0 ↦ 0 et s : N ⟶ N : n ↦ n + 1 (c’est un NNO dans Ens, donc dans Mes (car N est discret), et donc aussi dans Stoch, puisque le foncteur F_{T_{ℙ}} : Mes ⟶ Stoch possède un adjoint à droite U_{T_{ℙ}} (voir A.7, A.8 et [Bu 86])). Plus concrètement, si 1 −−→^{ν} X et X −−→^{π} X sont deux probabilités de transition, il existe une unique probabilité de transition φ : N −−→ X définie par la récurrence φ(0) = ν et φ(n + 1) = (π ¯∘ φ)(n), i.e. rendant les diagrammes ci-dessous commutatifs dans la catégorie Stoch :

\xymatrix{1 \ar[r]^{z} \ar@{-->}[dr]_{ν} & N \ar[r]^{s} \ar@{-->}[d]_{φ} & N \ar@{-->}[d]^{φ} \\  & X \ar@{-->}[r]_{π} & X}

Ceci traduit de manière catégorique le fait, rappelé dans C.8, que la donnée d’une probabilité ν sur X et d’une probabilité de transition π : X −−→ X détermine entièrement les lois d’une chaîne de Markov homogène (elles s’écrivent, rappelons-le, π_{n} ¯∘ ν = π_{n}ν,

où π_{n} = \overbrace{π ¯∘ … ¯∘ π}^{n fois} = \overbrace{π … π}^{n fois}). En effet, par définition de φ, ces lois s’écrivent ici π_{0} ¯∘ ν = ν = φ(0) et, pour tout n ∈ N^{∗}, π_{n} ¯∘ ν = π_{n} ¯∘ φ(0) = π_{n−1} ¯∘ (π ¯∘ φ(0)) = π_{n−1} ¯∘ φ(1) = ⋯ = π ¯∘ φ(n − 1) = φ(n).

APPENDICES

A. Rappels en théorie des catégories

A.1. Une catégorie monoïdale est définie par un 6-uplet (V, ⊗, I, α, λ, ρ), où V est une catégorie, I un objet de V, ⊗ : V × V ⟶ V un foncteur (appelés, respectivement, unité et loi monoïdale de V) et α, λ et ρ sont des isomorphismes naturels de la forme (où X, Y, Z sont des objets de V) :

α_{X,Y,Z} : X ⊗ (Y ⊗ Z) ≃ (X ⊗ Y) ⊗ Z, λ_{X} : I ⊗ X ≃ X ρ_{X} : X ⊗ I ≃ X,

vérifiant les axiomes suivants :

\xymatrix{X ⊗ (I ⊗ Y) \ar[rr]^{α} \ar[dr]_{X⊗λ} &  & (X ⊗ I) ⊗ Y \ar[dl]^{ρ⊗Y} \\  & X ⊗ Y}

\xymatrix{X ⊗ (Y ⊗ (Z ⊗ T)) \ar[r]^{α} \ar[d]_{X⊗α} & (X ⊗ Y) ⊗ (Z ⊗ T) \ar[r]^{α} & ((X ⊗ Y) ⊗ Z) ⊗ T \\ X ⊗ ((Y ⊗ Z) ⊗ T) \ar[rr]_{α} &  & (X ⊗ (Y ⊗ Z)) ⊗ T \ar[u]_{α⊗T}}

(λ_{I} = ρ_{I} : I ⊗ I ⟶ I est une conséquence). On sait que toute catégorie monoïdale est équivalente à une catégorie monoïdale stricte, i.e. une catégorie monoïdale dans laquelle les isomorphismes α, λ et ρ sont des identités (la loi monoïdale est associative et l’unité est neutre), voir [McL 72]. Cela permet de supposer que la catégorie monoïdale dans laquelle on travaille est stricte et donc qu’on peut la noter par un triplet (V, ⊗, I).

Exemples. La catégorie des ensembles, munie des produits cartésiens et de l’ensemble 1, est une catégorie monoïdale (Ens, ×, 1).

Pour toute catégorie C, on a une catégorie monoïdale (C^{C}, , id_{C}) (notation multiplicative de la loi monoïdale, c’est-à-dire par une absence de symblole !). Les objets de C^{C} sont les endofoncteurs de C et les morphismes, dont la composition est notée par “∘”, sont les transformations naturelles.

A.2. Un monoïde (ou, une monade, au sens premier donné par Benabou [Ben 67]) dans une catégorie monoïdale (V, ⊗, I) est défini par un triplet (M, e, m), où M est un objet de V, e : I ⟶ M et m : M ⊗ M ⟶ M (resp. unité et multiplication du monoïde) sont des morphismes de V vérifiant m∘(e⊗M) = M = m∘(M ⊗e) et m∘(m⊗M) = m∘(M ⊗m).

\xymatrix{I \ar[r]^{e} & M \ar[r]^{e⊗M} \ar[r]_{M⊗e} & M ⊗ M \ar[l]_{m} & M ⊗ M ⊗ M \ar[l]^{M⊗m} \ar[l]_{m⊗M}}

A.3. Une monade sur une catégorie C est un monoïde dans la catégorie monoïdale C^{C} mentionnée plus haut ; c’est donc la donnée d’un triplet T = (T, η, μ), où T : C ⟶ C est un foncteur, η : id_{C} ⟶ T et μ : T T ⟶ T (l’unité et la multiplication de la monade) des transformations naturelles vérifiant μ ∘ ηT = T = μ ∘ T η et μ ∘ μT = μ ∘ T μ.

\xymatrix{id_{C} \ar[r]^{η} & T \ar[r]^{ηT} \ar[r]_{T η} & T T \ar[l]_{μ} & T T T \ar[l]^{T μ} \ar[l]_{μT}}

Etant donné une monade T = (T, η, μ) sur une catégorie C, une T -algèbre est la donnée d’un couple (X, θ), où X est un objet de C et θ : T X ⟶ X un morphisme de C rendant commutatifs les diagrammes suivants dans C :

(A_{1}) \xymatrix{T X \ar[rr]^{θ} &  & X \\  & X \ar[ul]^{ηX} \ar[ur]_{id_{X}}}  (A_{2})  \xymatrix{T T X \ar[r]^{T θ} \ar[d]_{μX} & T X \ar[d]^{θ} \\ T X \ar[r]_{θ} & X}

Toutes les structures libres définissent des monades : par exemple, la monade “monoïdes libres”, la monade “groupes abéliens libres”, etc. ont pour algèbres respectives les monoïdes, les groupes abéliens, etc.

On définit la catégorie Alg(T) des T -algèbres comme étant la catégorie dont les objets sont les T -algèbres et les morphismes les f : (X, θ) ⟶ (X′, θ′), où f : X ⟶ X′ est un morphisme de C vérifiant f ∘ θ = θ′ ∘ T f. On a un foncteur d’oubli U^{T} : Alg(T) ⟶ C défini par U^{T} (X, θ) = X et U^{T} (f) = f : X ⟶ X′ si f : (X, θ) ⟶ (X′, θ′) ; ce foncteur admet un adjoint F^{T} : C ⟶ Alg(T) qui, à tout objet X de C, associe la T -algèbre libre (T X, μX) associée a X (ou engendrée par X) et, à tout morphisme f : X ⟶ Y de C, le morphisme T f : (T X, μX) ⟶ (T X′, μX′) de Alg(T).

Le couple d’adjoints (F^{T} , U^{T}), décrit ci-dessus, induit la monade T sur C.

A.4. Fixons-nous un monoïde (M, e, m) dans une catégorie monoïdale (V, ⊗, I) ; on lui associe naturellement une monade T_{M} = (T_{M} , η, μ) sur V, où l’endofoncteur T_{M} associe l’objet M ⊗ X (resp. le morphisme M ⊗ f : M ⊗ X ⟶ M ⊗ Y) à tout objet X (resp. à tout morphisme f : X ⟶ Y) de V ; de plus, pour tout objet X de V, les morphismes ηX : X ⟶ M ⊗ X et μX : M ⊗ M ⊗ X ⟶ M ⊗ X sont respectivement égaux à e ⊗ X et m ⊗ X.

A.5. Soit T = (T, η, μ) et T′ = (T′, η′, μ′) deux monades sur une même catégorie C. Une loi distributive τ de T sur T′ (ce que l’on notera τ : T/T′ (voir [Beck 69]) est la donnée d’un triplet τ = (τ, T, T′), où τ : T T′ ⟶ T′T est une transformation naturelle rendant commutatifs les diagrammes suivants dans C^{C} :

(B_{1}) \xymatrix{T T′ \ar[rr]^{τ} &  & T′T \\  & T \ar[ul]^{T η′} \ar[ur]_{η′T}}  (B_{2})  \xymatrix{T T′ \ar[rr]^{τ} &  & T′T \\  & T′ \ar[ul]^{ηT′} \ar[ur]_{T′η}}

(B_{3}) \xymatrix{T T′T′ \ar[rr]^{τT′} \ar[dr]_{T μ′} & & T′T T′ \ar[rr]^{T′τ} & & T′T′T \ar[dl]^{μ′T} \\ & T T′ \ar[rr]_{τ} & & T′T}

(B_{4}) \xymatrix{T T T′ \ar[rr]^{T τ} \ar[dr]_{μT′} & & T T′T \ar[rr]^{τT} & & T′T T \ar[dl]^{T′μ} \\ & T T′ \ar[rr]_{τ} & & T′T}

On démontre qu’une loi distributive est une monade dans la 2-catégorie des monades (c’est une des manifestations du caractère ubiquitaire des monades !)

Exemple originel. La loi distributive “modèle” relie la monade “monoïdes libres” à la monade “groupes abéliens libres”. En effet, le schéma d’origine des lois distributives est donné par la distributivité, dans un anneau, de la multiplication par rapport à l’addition, qui fait passer d’un mot de combinaisons linéaires à une combinaison linéaire de mots ; autrement dit, cette distributivité est décrite par une application de la forme τX : (Z^{(X)})^{∗} ⟶ Z^{(X^{∗})}, soumise à des conditions du type des (B_{i}) ci-dessus (où X^{∗} et Z^{(X)} sont respectivement le monoïde libre et le groupe abélien libre engendrés par l’ensemble X).

A.6. Les équivalences de J.Beck.

a) Le fait que le groupe abélien libre engendré par un monoïde M soit encore un monoïde (qui est l’anneau libre des polynômes sur X quand M = X^{∗}) a conduit J.Beck à établir que la donnée d’une loi distributive τ : T/T′ est équivalente :

– d’une part, à la donnée d’un relèvement de la monade T′ sur C en une monade T̃′ = (T̃′, η̃′, μ̃′) sur la catégorie Alg(T) des T -algèbres, ce qui signifie que les diagrammes suivants commutent si, pour le second, on remplace le couple (⇓, ⇑) par chacun des couples (η′, η̃′) et (μ′, μ̃′) :

\xymatrix{Alg(T) \ar[r]^{T̃′} \ar[d]_{U^{T}} & Alg(T) \ar[d]^{U^{T}} & Alg(T) \ar[r]_{⇑} \ar[r] \ar[d]_{U^{T}} & Alg(T) \ar[d]^{U^{T}} \\ C \ar[r]_{T′} & C & C \ar[r]_{⇓} \ar[r] & C}

En bref, si τ : T/T′ est une loi distributive, le premier diagramme signifie que l’image, par le foncteur T̃′, d’une T -algèbre sur X est une T -algèbre sur T′X (plus précisément, T̃′(X, θ) = (T′X, T′θ ∘ τX)), et le second diagramme que η′ = η et μ′ = μ (plus précisément, η̃′(X, θ) = η′X et μ̃′(X, θ) = μ′X).

– d’autre part, à la donnée d’une monade composée T̂ = (T̂, η̂, μ̂) sur C, où T̂ = T′T

(plus précisémént, η̂ = η′η et μ̂ = (μ′μ) ∘ (T′τT)).

b) S’inspirant du fait que la donnée d’une structure d’anneau est équivalente à la donnée de deux opérations × et + telles que la première soit distributive par rapport à la seconde, J.Beck a aussi prouvé que, s’il existe une loi distributive τ : T/T′, alors la donnée d’une T̂-algèbre (X, θ̂) dans C est équivalente à la donnée d’une T̃′-algèbre ((X, θ), θ′) dans Alg(T) (avec θ̂ = θ′ ∘ T′θ; θ = θ̂∘ η′T X et θ′ = θ̂∘ T′ηX), i.e. à la donnée d’une T -algèbre (X, θ) et d’une T′-algèbre (X, θ′) qui sont τ-compatibles, i.e. telles que le diagramme suivant commute dans C :

\xymatrix{ & T T′X \ar[r]^{τX} \ar[dl]_{T θ′} & T′T X \ar[dr]^{T′θ} \\ T X \ar[dr]_{θ} &  &  & T′X \ar[dl]^{θ′} \\  & X \ar[r]_{id} & X}

Ce que l’on peut exprimer en disant que les catégories d’algèbres Alg(T̂) et Alg(T̃′) sont équivalentes.

A.7. Catégorie de Kleisli d’une monade. Soit T = (T, η, μ) une monade sur une catégorie C. La catégorie de Kleisli de T, notée Kl(T), est la catégorie suivante : ses objets sont les mêmes que ceux de C ; un morphisme, noté u : X −−→ Y, dans Kl(T) est un morphisme de C de la forme u : X ⟶ T Y. Le composé v ¯∘ u : X −−→ Z dans Kl(T), de deux morphismes u : X −−→ Y et v : Y −−→ Z, est défini par v ¯∘ u = μZ ∘ T v ∘ u.

\xymatrix{ &  & T T Z \ar[d]^{μZ} \\  & T Y \ar[ur]^{T v} & T Z \\ X \ar@{-->}[r]_{u} \ar[ur]^{u} & Y \ar@{-->}[r]_{v} \ar[ur]^{v} & Z}

L’identité, dans Kl(T), associée à un objet X, est notée \overline{id}_{X} et est définie par \overline{id}_{X} = ηX : X −−→ X.

Entre les catégories C et Kl(T), on a un foncteur U_{T} : Kl(T) ⟶ C défini, pour tout objet X de Kl(T), par U_{T} (X) = T X et, pour tout u : X −−→ Y, par U_{T} (u) = μY ∘ T u : T X ⟶ T Y. Ce foncteur a un adjoint à gauche F_{T} : C ⟶ Kl(T) défini, pour tout objet X, par F_{T} (X) = X et, pour tout morphisme f : X ⟶ Y de C, par F_{T} (f) = ηY ∘f : X −−→ Y (le foncteur F_{T} permet souvent d’identifier C à la sous-catégorie F_{T} (C) de Kl(T)).

Le couple d’adjoints (F_{T} , U_{T}), décrit ci-dessus, induit la monade T sur C.

On a un foncteur plein et fidèle (dit foncteur de comparaison) Kl(T) ⟶^{ϕ} Alg(T) qui vérifie les relations (voir A.3 ci-dessus pour les foncteurs U^{T} et F^{T}) : ϕ ∘ F_{T} = F^{T} et U^{T} ∘ ϕ = U_{T} (il est défini par ϕ(X) = (T X, μX) et ϕ(u) = μY ∘ T u (où u : X −−→ Y)) ; ainsi, la catégorie Kl(T) est èquivalente à la sous-catégorie pleine ϕ(Kl(T)) de Alg(T) dont les objets sont les T -algèbres libres (T X, μX).

En fait, Alg(T) est une complétion de ϕ(Kl(T)) ≃ Kl(T) par conoyaux ; plus précisément, si (X, θ) est une T -algèbre, le morphisme (T X, μX) ⟶^{θ} (X, θ) est un conoyau dans Alg(T) du couple de morphismes de ϕ(Kl(T)) :

\xymatrix{(T T X, μT X) \ar[r]^{T θ} \ar[r]_{μX} & (T X, μX)}

Autrement dit, la T -algèbre (X, θ) est un quotient de la T -algèbre libre (T X, μX)).

A.8. Un objet des entiers naturels (ou NNO), dans une catégorie C avec objet final 1, est la donnée d’un objet N, muni de deux morphismes 1 ⟶^{z} N ⟶^{s} N assujettis à la propriété universelle suivante : pour tout objet X de C, muni de deux morphismes 1 ⟶^{f} X ⟶^{g} X, il existe un unique morphisme φ : N ⟶ X rendant les diagrammes suivants commutatifs dans C :

\xymatrix{1 \ar[r]^{z} \ar[dr]_{f} & N \ar[r]^{s} \ar[d]_{φ} & N \ar[d]^{φ} \\  & X \ar[r]_{g} & X}

Exemple. L’ensemble N des entiers naturels, muni des deux applications : 1 ⟶^{z} N ⟶^{s} N, définies par z(0) = 0 et, pour tout n ∈ N, par s(n) = n + 1, est évidemment un NNO dans la catégorie Ens.

A.9. Proposition. [A. Burroni [Bu 86]] Tout foncteur admettant un adjoint à droite commute aux NNO (en fait, il commute aux extensions de Kan indexées par des graphes).

B. Rappels en théorie des automates déterministes et non déterministes

On fixe un ensemble fini Σ qu’on appelle alphabet et dont les éléments sont appelés symboles. On note Σ^{∗} le monoïde libre engendré par Σ. Les éléments de Σ^{∗} s’appellent des mots. Un mot a ∈ Σ^{∗} est une suite finie a = α_{1}α_{2} … α_{n} de symboles (α_{1}, α_{2}, …, α_{n} ∈ Σ). L’entier n est la longueur de a. En particulier, pour n = 0, on a le mot vide, qu’on notera e, et qui est l’unité du monoïde Σ^{∗}. Pour les deux définitions qui suivent, voir [Star 72].

B.1. Un automate déterministe sur l’alphabet Σ est la donnée d’un couple (X, δ), où X est un ensemble et δ : Σ × X ⟶ X une application appelée fonction de transition. Elle s’étend (par induction sur la longueur des mots) en une application θ : Σ^{∗} × X ⟶ X (appelée loi de transition de l’automate déterministe) vérifiant, pour tout a, b ∈ Σ^{∗} et tout x ∈ X, les deux axiomes suivants :

θ(e, x) = x et θ(ab, x) = θ(a, θ(b, x))

Les éléments de X sont appelés les états de l’automate. L’égalité θ(a, x) = y s’interprète en disant que, lisant a, l’automate passe de l’état x à l’état y. Les deux axiomes ci-dessus reviennent à dire, d’une part que le mot vide ne fait pas changer d’état l’automate et, d’autre part que les mots agissent séquentiellement (i.e. symbole après symbole) sur les états.

B.2. Un automate non déterministe sur l’alphabet Σ est encore la donnée d’un couple (X, δ), mais où la fonction de transition est cette fois de la forme δ : Σ × X ⟶ PX (où PX est l’ensemble des parties de X). Comme précédemment, l’application δ s’étend par induction en une application θ : Σ^{∗} × X ⟶ PX (encore appelée loi de transition de l’automate non déterministe) vérifiant, pour tout a, b ∈ Σ^{∗} et tout x ∈ X, les deux axiomes suivants :

θ(e, x) = {x} et θ(ab, x) = ⋃_{y∈θ(b,x)} θ(a, y)

Ici encore, les éléments de X sont appelés les états de l’automate. L’égalité θ(a, x) = A s’interprète en disant que A est l’ensemble des états “possibles” dans lesquels l’automate peut se mettre, partant de l’état x, quand il lit a; les deux axiomes ci-dessus traduisent encore le fait que le mot vide n’a aucune action sur l’automate et que les mots agissent séquentiellement.

C. Rappels en théorie des probabilités et en théorie des automates stochastiques

Si X, Y, Z, etc. sont des espaces mesurables, on désignera par X, Y, Z, etc. leurs tribus respectives. On considère l’ensemble R (ainsi que toutes ses parties) muni de la tribu borélienne.

C.1. Une probabilité sur l’espace mesurable X est une mesure positive p vérifiant p(X) = 1. Pour tout espace mesurable X, on désigne par ℙX l’ensemble des probabilités sur X; dans tout cet article, l’ensemble ℙX sera considéré comme un espace mesurable en le munissant de la plus petite tribu rendant mesurables les évaluations e_{A} : ℙX ⟶ [0, 1] : p ↦ p(A), où A parcourt la tribu X sur X. Ce qui équivaut à dire que, pour tout espace mesurable Y, une application u : Y ⟶ ℙX est mesurable ssi tous les composés e_{A} ∘ u sont mesurables, lorsque A parcout la tribu X sur X.

C.2. Soit f : X ⟶ Y une application mesurable (appelée aussi variable aléatoire en théorie des probabilités) et p une probabilité sur X. On définit une probabilité image f_{∗}(p)

sur Y en posant (f_{∗}(p))(B) = p( f^{−1}(B)) pour toute partie mesurable B de Y ; on appelle habituellement p-loi de f cette probabilité image f_{∗}(p), et on note p(f ∈ B) l’expression

p( f^{−1}(B)) interprétée comme étant la probabilité que f soit dans B. Dans le cas où l’on a p(f ∈ B) = 1, on dit que f est p-presque sûrement dans B. Dans le cas où Y = R et où f est mesurable positive, l’intégrale de f par rapport à p a un sens (elle peut être infinie) et se note ∫_{X} fdp = ∫_{X} f(x)p(dx) ; si f est mesurable bornée, elle est p-intégrable (i.e. son intégrale par rapport à p existe et est finie).

C.3. Soit X et Y deux espaces mesurables. On appelle probabilité de transition de X vers Y ([Nev 64]) une application π : X × Y ⟶ [0, 1] telle que, d’une part, pour tout x ∈ X, l’application π(x, −) : Y ⟶ [0, 1] est une probabilité sur Y, et, d’autre part, pour tout B ∈ Y, l’application π(−, B) : X ⟶ [0, 1] est mesurable. Soit donc π une telle probabilité de transition de X vers Y, f : Y ⟶ R une application mesurable (positive ou bornée) et x ∈ X; on note ∫_{Y} f(y)π(x, dy) l’intégrale de f par rapport à la probabilité π(x, −) sur Y.

Si π′ est une autre probabilité de transition de Y vers Z, on définit une nouvelle probabilité de transition de X vers Z, appelée produit (ou composition) des probabilités de transition π et π′, en posant, pour tout x ∈ X et tout C ∈ Z :

(π′π)(x, C) =^{(1)} ∫_{Y} π′(y, C)π(x, dy)

Enfin, les probabilités de transition opèrent sur les probabilités de la manière suivante : si ν est une probabilité sur X, π une probabilité de transition de X vers Y, on définit une probabilité πν sur Y en posant, pour tout B ∈ Y :

(πν)(B) =^{(2)} ∫_{X} π(x, B)ν(dx)

En fait, la formule (2) est un cas particulier de la formule (1) en faisant X = 1 dans (1).

C.4. Considérons maintenant une application mesurable u : X ⟶ ℙY ; une telle donnée équivaut au fait que, pour tout x ∈ X, u(x) est une probabilité sur Y et que, par définition même de la tribu sur ℙY (voir C.1 ci-dessus), pour toute partie mesurable B de Y, l’application e_{B} ∘ u : X ⟶ [0, 1] : x ↦ (u(x))(B) est mesurable ; ainsi, la donnée d’une application mesurable u : X ⟶ ℙY est équivalente à la donnée de la probabilité de transition π de X vers Y définie par π(x, B) = (u(x))(B) pour tout x ∈ X et tout B ∈ Y ([Giry 81]).

C.5. Définition. On appellera dorénavant probabilité de transition une application mesurable de la forme u : X ⟶ ℙY ; en particulier, toute probabilité ν sur X s’identifie (en posant ν(0) = ν) à une probabilité de transition ν : 1 ⟶ ℙX.

Les formules (1) et (2) données dans C.3 ci-dessus se traduisent donc ici par :

((vu)(x))(C) =^{(1′)} ∫_{Y} (v(y))(C)(u(x))(dy) et (uν)(B) =^{(2′)} ∫_{X}(u(x))(B)ν(dx)

pour tout x ∈ X, tout C ∈ Z, toute probabilité ν sur X, et toutes probabilités de transition u : X ⟶ ℙY et v : Y ⟶ ℙZ.

C.6. Soit Σ un ensemble fini. Un automate stochastique sur l’alphabet Σ (voir [Star 72]) est la donnée d’un couple (X, θ), où X est un ensemble et θ : Σ^{∗} × X ⟶ ℙX une application mesurable (Σ^{∗} étant muni de sa tribu discrète) vérifiant les deux axiomes suivants :

θ(e, x) = δ_{x} et θ(ab, x)(A) =^{(1′′)} ∫_{X}(θ(a, y))(A)(θ(b, x))(dy)

(où δ_{x} est la probabilité de Dirac au point x) pour tout a, b ∈ Σ^{∗}, tout x ∈ X et tout A ∈ X. Les éléments de X sont appelés les états de l’automate et θ sa probabilité de transition (ce qui est bien naturel, d’après C.4 ci-dessus). L’égalité θ(a, x) = p s’interprète en disant que, pour toute partie mesurable A de X, p(A) est la probabilité que l’automate, partant de l’état x et lisant a, aille dans A; les deux axiomes ci-dessus signifient, d’une part que, partant d’un état x et lisant le mot vide, l’automate reste presque-sûrement dans toute partie mesurable de X contenant x et, d’autre part que cet automate fonctionne encore de façon séquentielle.

La similitude entre les formules (1′) et (1′′) n’a rien de fortuit : en effet, remarquant que, pour tout a ∈ Σ^{∗}, l’application partielle π_{a} = θ(a, −) est aussi une probabilité de transition X ⟶ ℙX, la formule (1′′) peut encore s’écrire, pour tout a, b ∈ Σ^{∗}, tout x ∈ X et tout A ∈ X :

(π_{ab}(x))(A) = ∫_{X}(π_{a}(y))(A)(π_{b}(x))(dy) = ((π_{a}π_{b})(x))(A)

On obtient ainsi la relation de Chapman-Kolmogoroff (généralisée) des automates stochastiques sur un alphabet Σ (qui est en fait équivalente à la formule (1′′), i.e. au second axiome des automates stochastiques) :

π_{ab} = π_{a}π_{b} pour tout a, b ∈ Σ^{∗}

C.7. Définition. On appelle M-automate stochastique (où M est un monoïde mesurable) la donnée d’un couple (X, θ), où X est un espace mesurable et θ : M × X ⟶ ℙX une probabilité de transition vérifiant les mêmes propriétés formelles que ci-dessus, i.e., avec les notations adoptées précédemment, vérifiant, pour tout a, b ∈ M et tout x ∈ X, les axiomes :

π_{e}(x) = δ_{x} et π_{ab} = π_{a}π_{b}

Utilisant la formule (2′) de C.4, on a une probabilité π_{a}ν sur X pour toute probabilité ν sur X qui est définie par (π_{a}ν)(A) = ∫_{X}(π_{a}(x))(A)ν(dx) pour toute partie mesurable A de X; en particulier π_{a}δ_{x} = π_{a}(x) et (π_{e}ν)(A) = ∫_{X}(π_{e}(x))(A)ν(dx) = ∫_{X} δ_{x}(A)ν(dx) = ∫_{X} 1_{A}(x)ν(dx) = ν(A) ; ainsi π_{e}ν = ν.

C.8. Une chaîne de Markov homogène est un automate stochastique sur l’alphabet Σ = 1 (on identifie donc Σ^{∗} à N, avec son addition usuelle, que l’on munit de sa tribu discrète). Soit θ : N × X ⟶ ℙX une telle chaîne de Markov, et notons encore π_{n}(x) = θ(n, x) pour tout n ∈ N et tout x ∈ X ((π_{n}(x))(A) étant la probabilité de passer de x dans A en n pas). La mesurabilité de θ étant équivalente à celle de tous les π_{n} : X ⟶ ℙX, cette chaîne de Markov est équivalente à la donnée de la suite (π_{n}) de probabilités de transition vérifiant, pour tout n, m ∈ N et tout x ∈ X, les axiomes :

π_{0}(x) = δ_{x} et π_{n+m} = π_{n}π_{m}

On dit que π_{n}(x) = π_{n}δ_{x} est la loi de la chaîne au temps n, lorsqu’elle part de x, et, plus généralement, si ν est une probabilité sur X, que π_{n}ν est la loi de la chaîne au temps n, pour la loi initiale ν.

Grâce à la relation de Chapman-Kolmogoroff π_{n+m} = π_{n}π_{m}, les π_{n} avec n ∈ N^{∗} sont entièrement déterminés par la probabilité de transition π_{1} : X ⟶ ℙX, de sorte que les lois d’une chaîne de Markov homogène sont entièrement déterminées par la donnée d’une probabilité de transition π : X ⟶ ℙX (appelée encore probabilité de transition de

la chaîne de markov ; alors π_{n} = \overbrace{π … π}^{n fois}) et d’une probabilité ν sur X (on obtient donc toutes les lois π_{n}ν de la chaîne, et en particulier sa loi initiale π_{0}ν qui n’est autre que ν, d’après C.6).

Les probabilistes ont coutume d’appeler plutôt chaîne de Markov homogène la donnée d’une suite de variables aléatoires dont les lois (voir C.2 ci-dessus) sont du type des π_{n}ν ci-dessus. Il est bien connu des probabilistes que l’on peut toujours construire, a posteriori, une telle chaîne de Markov homogène dont la probabilité de transition π : X ⟶ ℙX et la loi initiale ν sont données a priori : on considère l’espace X^{N}, muni de la tribu produit ; on peut alors construire une unique probabilité P_{ν} (l’indice ν étant là pour “symboliser” le fait que l’on part avec la loi ν) sur cet espace produit, telle que la suite (q_{n}) des projections canoniques X^{N} ⟶ X réponde à la question. En effet, la tribu produit étant la plus petite tribu rendant mesurables les q_{n}, P_{ν} est entièrement déterminée par les P_{ν}(q_{n} ∈ A) pour tout n ∈ N et toute partie mesurable A de X (i.e. par les P_{ν}-lois des q_{n} pour tout n ∈ N ; voir C.2 ci-dessus) : on pose d’abord P_{ν}(q_{n} ∈ A) = (π_{n}ν)(A) =

∫_{X}(π_{n}(x))(A)ν(dx), où π_{n} = \overbrace{π … π}^{n fois} ; on prolonge ensuite P_{ν} aux pavés mesurables (i.e.

aux intersections finies de q_{n_{i}}^{−1} (A_{i})) en posant P_{ν}(q_{0} ∈ A_{0} et q_{n_{1}} ∈ A_{1} et … q_{n_{k}} ∈ A_{k}) = ∫_{A_{0}} ν(dx_{0}) ∫_{A_{1}} π_{n_{1}}(x_{0}, dx_{1}) ∫_{A_{2}} π_{n_{2}−n_{1}}(x_{1}, dx_{2}) … ∫_{A_{k}} π_{n_{k}−n_{k−1}}(x_{k−1}, dx_{k}) ; un théorème de prolongement nous permet alors de prolonger P_{ν} à tous les mesurables de X^{N}. Cette définition de P_{ν} est ad hoc pour que π_{n}ν soit la P_{ν}-loi de q_{n} pour tout n ∈ N, i.e. la loi de la chaîne (q_{n}) au temps n, pour la loi initiale ν. En particulier, π_{0}ν = ν (voir C.6 ci-dessus) est la loi initiale de la chaîne (q_{n}) ; et, en notant P_{x} la probabilité P_{δ_{x}}, P_{x}(q_{n} ∈ A) = (π_{n}δ_{x})(A) = (π_{n}(x))(A), i.e. π_{n}(x) est la loi de la chaîne (q_{n}) au temps n, quand elle part de x.

C.9. Un Processus de Markov homogène (ou processus Markovien homogène) est un R_{+}-automate stochastique (le monoïde R_{+} n’est ni libre ni finiment engendré ; on le munit de l’addition usuelle et de la tribu borélienne) ; c’est donc la donnée d’un espace mesurable X et d’une probabilité de transition θ : R_{+} × X ⟶ ℙX qui vérifie les axiomes (en notant π_{t}(x) la probabilité θ(t, x) pour tout t ∈ R_{+} et tout x ∈ X) :

π_{0}(x) = δ_{x} et π_{s+t} = π_{s}π_{t}

pour tout s, t ∈ R_{+} et tout x ∈ X (ici, a priori, la mesurabilité de tous les π_{t} : X ⟶ ℙX n’est pas une condition suffisante pour que θ : R_{+} × X ⟶ ℙX soit mesurable ; d’ailleurs, ici, on obtient plutôt les processus Markoviens homogènes mesurables, la mesurabilité de θ étant utile dans certains problèmes spécifiques d’intégration). Ici, (π_{t}(x))(A) est la probabilité d’aller, en un temps t, de x dans A; π_{t}(x) = π_{t}δ_{x} est la loi du processus au temps t quand il part de x; plus généralement, si ν est une probabilité sur X, π_{t}ν est la loi du processus au temps t, pour la loi initiale ν.

Le problème de la construction, a posteriori, d’une famille de variables aléatoires dont les lois sont du type des π_{t}ν ci-dessus, i.e. données, a priori, par une probabilité ν sur X et une famille (π_{t}) de probabilités de transition X ⟶ ℙX, indexée par R_{+}, et vérifiant la relation de Chapman-Kolmogoroff π_{t+s} = π_{t}π_{s} est ici plus délicat. En effet, se référant à C.8 ci-dessus, on considère l’espace produit X^{R_{+}} (muni de sa tribu produit, i.e. de la plus petite tribu rendant mesurables les projections canoniques q_{t} : X^{R_{+}} ⟶ X). Bien que l’on puisse toujours poser P_{ν}(q_{t} ∈ A) = (π_{t}ν)(A) pour tout t ∈ R_{+} et pour toute partie mesurable A de X (et donc définir P_{ν} sur les pavés mesurables de l’espace produit X^{R_{+}}), on ne peut pas toujours prolonger P_{ν} en une probabilité sur tous les mesurables de X^{R_{+}} ; c’est cependant possible avec de bonnes hypothèses sur X (par exemple, si X est un espace de Borel, i.e. isomorphe à un borélien de [0, 1]). Dans ce cas, la famille (q_{t}) forme un processus Markovien homogène dont les P_{ν}-lois sont, par définition de P_{ν}, les π_{t}ν.

D. La monade des probabilités

La monade T_{ℙ} = (ℙ, η′′, μ′′) des probabilités sur la catégorie Mes des applications mesurables entre espaces mesurables a été publiée pour la première fois par M.Giry [Giry 81]^{1} ; elle a donné une preuve complète mais succinte du fait que c’est une monade. Nous en donnons ici une preuve détaillée pour rendre ce travail plus accessible aux catégoriciens et aux probabilistes. Nous l’avons décrite rapidement dans la partie 4.3 de cet article.

On reprend les notations fixées dans l’appendice C.

D.1. Rappelons que, pour définir une tribu sur l’ensemble ℙX des probabilités sur un espace mesurable X donné, nous avons utilisé les évaluations e_{A} : ℙX ⟶ [0, 1] : p ↦ p(A) (où A est un partie mesurable de X (i.e. A ∈ X)) qui sont mesurables par définition même de cette tribu. En fait, pour toute application mesurable bornée f : X ⟶ R, on considère l’évaluation e_{f} : ℙX ⟶ R définie par e_{f}(p) = ∫_{X} fdp. Notons, pour tout espace mesurable X, Mes(X) (resp. Mes_{b}(X)) l’espace vectoriel des applications mesurables (resp. mesurables bornées) de X dans R, où R (tout comme [0, 1] ci-dessus) est muni de sa tribu borélienne.

D.2. Lemme. L’application X ⟶ Mes_{b}(ℙX) : A ⟶ e_{A} se prolonge en une application Eval : Mes_{b}(X) ⟶ Mes(ℙX) : f ⟶ e_{f} qui est linéaire et qui commute aux sup_{n}^{↑} (i.e. aux sup dénombrables et croissants) de Mes_{b}(X).

Preuve. Par définition de l’application e_{f}, on a e_{1_{A}} = e_{A} pour tout A ∈ X. En utilisant la linéarité de l’intégrale et le théorème de convergence monotone, on obtient, selon que f ∈ Mes_{b}(X) s’écrit ∑_{i} α_{i}f_{i} (où les α_{i} sont des réels et les f_{i} des applications mesurables bornées sur X; il s’agit bien sûr de sommes finies ici) ou f = sup_{n}^{↑} f_{n} (où les f_{n} forment une suite croissante d’applications mesurables bornées sur X) :

1. Ollivier de la Tullaye [Tull 71] avait fait cette construction antérieurement dans un manuscrit récemment retrouvé.

– d’une part e_{f}(p) = ∫_{X} ∑_{i} α_{i}f_{i}dp = ∑_{i} α_{i} ∫_{X} f_{i}dp = ∑_{i} α_{i}e_{f_{i}}(p) pour tout p ∈ ℙX, i.e. e_{∑_{i} α_{i}f_{i}} = ∑_{i} α_{i}e_{f_{i}};

– d’autre part e_{f}(p) = ∫_{X} sup_{n}^{↑} f_{n}dp = sup_{n}^{↑} ∫_{X} f_{n}dp = sup_{n}^{↑} e_{f_{n}}(p) pour tout p ∈ ℙX, i.e. e_{sup_{n}^{↑} f_{n}} = sup_{n}^{↑} e_{f_{n}}.

Il en résulte immédiatement que l’application Eval proposée est linéaire et commute aux sup_{n}^{↑}. On en déduit aussi que l’application e_{f} est mesurable lorsque, d’abord f est étagée sur X (en se limitant à des f_{i} de la forme 1_{A_{i}}, on obtient e_{∑_{i} α_{i}1_{A_{i}}} = ∑_{i} α_{i}e_{A_{i}}, de sorte que e_{∑_{i} α_{i}1_{A_{i}}} est mesurable) ; puis lorsque f est une fonction mesurable bornée positive sur X (elle s’écrit alors f = sup_{n}^{↑} f_{n}, où les f_{n} forment une suite croissante d’applications étagées sur X, de sorte que e_{sup_{n}^{↑} f_{n}} = sup_{n}^{↑} e_{f_{n}} est mesurable) ; puis enfin lorsque f est simplement mesurable bornée (on écrit f = f^{+}−f^{−} avec f^{+} et f^{−} mesurables bornées positives, de sorte que e_{f} = e_{f^{+}} − e_{f^{−}} est mesurable).

D.3. L’endofoncteur ℙ : Mes ⟶ Mes est défini ainsi : à tout espace mesurable X, il associe l’ensemble ℙX des probabilités sur X, muni de la plus petite tribu rendant mesurables les évaluations e_{A}, lorsque A parcourt la tribu X sur X; à toute application mesurable f : X ⟶ Y, il associe l’application f_{∗} : ℙX ⟶ ℙY : p ↦ f_{∗}(p), (voir C.2). La fonctorialité de ℙ résulte de l’égalité (g ∘ f)_{∗} = g_{∗} ∘ f_{∗}. Pour vérifier que ℙ est bien un endofoncteur sur Mes, Il faut juste s’assurer que, pour toute application mesurable f, l’application f_{∗} est mesurable, i.e., par définition même de la tribu sur ℙY, que, pour tout B ∈ Y, l’application e_{B} ∘ f_{∗} est mesurable. Mais ceci est immédiat, puisque, pour

toute probabilité p sur X, on a (e_{B} ∘f_{∗})(p) = e_{B}(f_{∗}(p)) = (f_{∗}(p))(B) = p( f^{−1}(B)) = e_{A}(p),

i.e. e_{B} ∘ f_{∗} = e_{A}, où A = f^{−1}(B) ; or e_{A} est mesurable puisque A l’est (car B et f sont supposés mesurables).

Remarquons en passant que, pour tout A ∈ X, on a ℙ1_{A} = (1_{A})_{∗} = e_{A}; en effet, a priori (1_{A})_{∗} : ℙX ⟶ ℙ2 : p ↦ (1_{A})_{∗}(p), mais en identifiant ℙ2 à [0, 1] (toute probabilité p ∈ ℙ2 s’identifiant à sa valeur p({1}) ∈ [0, 1] qui la détermine entièrement), (1_{A})_{∗}(p)

s’identifie à ((1_{A})_{∗}(p))({1}) = p(1_{A}^{−1}({1})) = p(A) = e_{A}(p). On peut alors retrouver que e_{B} ∘ f_{∗} est mesurable en écrivant e_{B} ∘ f_{∗} = (1_{B})_{∗} ∘ f_{∗} = (1_{B} ∘ f)_{∗} = (1_{A})_{∗} = e_{A}, où

A = f^{−1}(B).

D.4. L’unité de la monade des probabilités est η′′X : X ⟶ ℙX : x ↦ δ_{x}; La naturalité

de η′′ résulte du fait que, pour tout x ∈ X et tout B ∈ Y, on a (f_{∗}(δ_{x}))(B) = δ_{x}( f^{−1}(B)) = 1

ou 0 (selon que x ∈ f^{−1}(B) ou non) = 1 ou 0 (selon que f(x) ∈ B ou non) = δ_{f(x)}(B), i.e. f_{∗}(δ_{x}) = δ_{f(x)}.

La mesurabilité de η′′X résulte de celle des e_{A} ∘ η′′X, lorsque A parcourt X. Or, pour tout x ∈ X, (e_{A} ∘ η′′X)(x) = e_{A}(η′′X(x)) = e_{A}(δ_{x}) = δ_{x}(A) = 1_{A}(x), i.e. e_{A} ∘ η′′X = 1_{A} qui est mesurable, puisque A l’est.

\xymatrix{ℙX \ar[r]^{f_{∗}} & ℙY & ℙ ℙX \ar[d]_{μ′′X} \ar[r]^{(f_{∗})_{∗}} & ℙ ℙY \ar[d]^{μ′′Y} \\ X \ar[u]^{η′′X} \ar[r]_{f} & Y \ar[u]_{η′′Y} & ℙX \ar[r]_{f_{∗}} & ℙY}

D.5. La multiplication de la monade des probabilités est ainsi définie : μ′′X : ℙ ℙX ⟶ ℙX est l’application qui, à toute probabilité p̂ sur ℙX, associe la probabilité μ′′X(p̂) sur X qui, à toute partie mesurable A de X, associe (μ′′X(p̂))(A) = ∫_{ℙX} e_{A}dp̂ = ∫_{ℙX} e_{A}(p)p̂(dp) = ∫_{ℙX} p(A)p̂(dp).

Vérifions que, pour tout p̂ ∈ ℙ ℙX, on a bien μ′′X(p̂) ∈ ℙX. Soit donc p̂ une probabilité sur ℙX; d’abord μ′′X(p̂) est positive (car e_{A} l’est) et (μ′′X(p̂))(X) = 1 (car e_{X}(p) = p(X) = 1 pour tout p ∈ ℙX). Soit maintenant (A_{n}) une suite de parties mesurables de X, 2 à 2 disjointes et telles que ⋃ A_{n} soit aussi mesurable ; alors, utilisant le lemme D.2 ci-dessus et le fait que, pour tout n ∈ N, on a 1_{⋃_{k=0}^{n} A_{k}} = ∑_{k=0}^{n} 1_{A_{k}}, on peut écrire e_{⋃ A_{n}} = e_{sup_{n}^{↑} ⋃_{k=0}^{n} A_{k}} = sup_{n}^{↑} e_{⋃_{k=0}^{n} A_{k}} = sup_{n}^{↑} e_{∑_{k=0}^{n} 1_{A_{k}}} = sup_{n}^{↑} ∑_{k=0}^{n} e_{A_{k}}, de sorte que (μ′′X(p̂))(⋃ A_{n}) = ∫_{ℙX} e_{⋃ A_{n}}dp̂ = ∫_{ℙX} sup_{n}^{↑} ∑_{k=0}^{n} e_{A_{k}}dp̂ = sup_{n}^{↑} ∑_{k=0}^{n} ∫_{ℙX} e_{A_{k}}dp̂ = ∑_{k=0}^{∞}(μ′′X(p̂))(A_{k}), ce qui prouve la σ-additivité de μ′′X(p̂).

Pour prouver la naturalité de μ′′, on doit vérifier l’égalité f_{∗} ∘ μ′′X = μ′′Y ∘ (f_{∗})_{∗} pour toute application mesurable f : X ⟶ Y. Soit donc p̂ ∈ ℙ ℙX et B ∈ Y; alors ((f_{∗} ∘

μ′′X)(p̂))(B) = (μ′′X(p̂))( f^{−1}(B)) = ∫_{ℙX} e_{A}dp̂ où A = f^{−1}(B), et ((μ′′Y ∘ (f_{∗})_{∗})(p̂))(B) =

∫_{ℙY} e_{B}d(f_{∗})_{∗}(p̂) = ∫_{ℙX} e_{B} ∘ f_{∗}dp̂; il suffit donc d’utiliser l’égalité e_{B} ∘ f_{∗} = e_{A} établie ci-dessus dans D.3.

Reste donc à prouver la mesurabilité de μ′′X pour tout espace mesurable X; par définition de la tribu sur ℙX, cela revient à la mesurabilité des e_{A} ∘ μ′′X, lorsque A parcourt la tribu X donnée sur X. Or, pour tout p̂ ∈ ℙ ℙX, on a (e_{A} ∘ μ′′X)(p̂) = e_{A}(μ′′X(p̂)) = (μ′′X(p̂))(A) = ∫_{ℙX} e_{A}dp̂ = e_{e_{A}}(p̂) (voir D.1 ci-dessus pour la définition des e_{f}), de sorte que e_{A} ∘ μ′′X = e_{e_{A}}; ceci prouve la mesurabilité de e_{A} ∘ μ′′X, puisque e_{A} est mesurable (par définition de la tribu sur ℙX) et bornée (voir le lemme D.2).

Avant de quitter ce paragraphe, établissons le lemme suivant dont on se servira dans D.7 :

D.6. Lemme. Pour tout f ∈ Mes_{b}(X) et tout p̂ ∈ ℙ ℙX, l’application e_{f} est p̂-intégrable et l’on a l’égalité :

∫_{X} fd(μ′′X(p̂)) =^{∗} ∫_{ℙX} e_{f}dp̂

Preuve. Par le lemme D.2, on sait que l’application e_{f} : ℙX ⟶ R est mesurable. De plus, par définition même de la probabilité μ′′X(p̂), l’égalité =^{∗} est vraie lorsque f = 1_{A}, où A ∈ X (puisque e_{1_{A}} = e_{A}). Il en résulte immédiatement, par linéarité de l’intégrale, que l’égalité =^{∗} est vraie lorsque f est étagée. Elle est donc encore vraie lorsque f est mesurable bornée positive, puisqu’elle s’écrit alors f = sup_{n}^{↑} f_{n}, où les f_{n} sont étagées (on utilise le théorème de convergence monotone). Le passage au cas où f est seulement mesurable bornée n’est qu’une formalité en écrivant f = f^{+} − f^{−} (on a bien sûr exploité les propriétés de l’application Eval du lemme D.2). D’où le résultat.

D.7. Prouvons maintenant que T_{ℙ} = (ℙ, η′′, μ′′) est bien une monade.

– L’égalité μ′′X ∘ η′′ℙX = id_{ℙX} résulte du fait que, pour tout p ∈ ℙX, on a μ′′X(η′′ℙX(p)) = p; en effet, pour tout A ∈ X, on a (μ′′X(η′′ℙX(p)))(A) = (μ′′X(δ_{p}))(A) = ∫_{ℙX} e_{A}dδ_{p} = e_{A}(p) = p(A).

– L’égalité μ′′X ∘ ℙη′′X = id_{ℙX} résulte du fait que, pour tout p ∈ ℙX, on a μ′′X((η′′X)_{∗}(p)) = p; en effet, pour tout A ∈ X, on a (μ′′X((η′′X)_{∗}(p)))(A) = ∫_{ℙX} e_{A}d(η′′X)_{∗}(p) = ∫_{X} e_{A} ∘ η′′Xdp = p(A), puisque e_{A} ∘ η′′X = 1_{A} (voir D.4 cidessus).

– L’égalité μ′′X ∘ μ′′ℙX = μ′′X ∘ ℙμ′′X résulte du fait que, pour tout ˆ p̂ ∈ ℙ ℙ ℙX, on a μ′′X(μ′′ℙX(ˆp̂)) = μ′′X((μ′′X)_{∗}(ˆp̂)) ; en effet, pour tout A ∈ X, on a :

– d’une part (μ′′X(μ′′ℙX(ˆp̂)))(A) = ∫_{ℙX} e_{A}d(μ′′ℙX(ˆp̂)) =^{∗} ∫_{ℙ ℙX} e_{e_{A}}dˆp̂ =

∫_{ℙ ℙX} e_{e_{A}}(p̂)ˆp̂(dp̂) = ∫_{ℙ ℙX}(∫_{ℙX} e_{A}dp̂)ˆp̂(dp̂) (la dernière égalité résultant de la définition des e_{f}, et l’égalité =^{∗} du lemme D.6 ci-dessus) ;

– d’autre part (μ′′X((μ′′X)_{∗}(ˆp̂)))(A) = ∫_{ℙX} e_{A}d(μ′′X)_{∗}(ˆp̂) = ∫_{ℙ ℙX} e_{A} ∘ μ′′Xdˆp̂ = ∫_{ℙ ℙX} e_{A}(μ′′X(p̂))ˆp̂(dp̂) = ∫_{ℙ ℙX}(μ′′X(p̂))(A)ˆp̂(dp̂) = ∫_{ℙ ℙX}(∫_{ℙX} e_{A}dp̂)ˆp̂(dp̂).

E. La loi distributive τ : T_{M}/T_{ℙ}

Elle est définie par les τX : M ×ℙX ⟶ ℙ(M ×X) : (a, p) ↦ δ_{a} ⊗p, pour tout espace mesurable X (M étant bien sûr un monoïde mesurable).

E.1. Pour la naturalité de τ, on vérifie la commutativité du diagramme suivant pour toute application mesurable f : X ⟶ Y :

\xymatrix{M × ℙY \ar[r]^{τY} & ℙ(M × Y) \\ M × ℙX \ar[u]^{M×f_{∗}} \ar[r]_{τX} & ℙ(M × X) \ar[u]_{(M×f)_{∗}}}

On doit donc vérifier que, pour tout (a, p) ∈ M × ℙX, on a δ_{a} ⊗ f_{∗}(p) = (M × f)_{∗}(δ_{a} ⊗ p). Or, pour tout pavé mesurable A × B de M × Y, on a, d’une part (δ_{a} ⊗ f_{∗}(p))(A × B) =

δ_{a}(A)(f_{∗}(p))(B) = δ_{a}(A)p( f^{−1}(B)), et, d’autre part ((M × f)_{∗}(δ_{a} ⊗ p))(A × B) = (δ_{a} ⊗

p)((M × f^{−1})(A × B)) = (δ_{a} ⊗ p)(A × f^{−1}(B)) = δ_{a}(A)p( f^{−1}(B)).

La mesurabilité de τX résulte de celle des e_{A×B} ∘τX, pour tout pavé mesurable A×B de M × X. Or, pour tout (a, p) ∈ M × ℙX, on a (e_{A×B} ∘ τX)(a, p) = e_{A×B}(δ_{a} ⊗ p) = (δ_{a} ⊗ p)(A × B) = δ_{a}(A)p(B) = 1_{A}(a)e_{B}(p) ; la mesurabilité de e_{A×B} ∘ τX résulte donc directement de celle de A et de B.

E.2. Reste à vérifier les axiomes (B_{i}) (voir A.5).

(B_{1}) : L’égalité τX ∘ (M × η′′X) = η′′(M × X) résulte du fait que, pour tout (a, x) ∈

M × X, on a δ_{a} ⊗ δ_{x} = δ_{(a,x)}. (B_{2}) : L’égalité τX ∘ ηℙX = ℙηX résulte du fait que, pour toute probabilité p sur X et

tout pavé mesurable A × B de M × X, on a ((ηX)_{∗}(p))(A × B) = p(ηX^{−1}(A × B)) = 1_{A}(e)p(B) = δ_{e}(A)p(B) = (δ_{e} ⊗ p)(A × B), la seconde égalité résultant du fait que

(ηX^{−1})(A × B) = {x ∈ X | (e, x) ∈ A × B} = B ou ∅, selon que e ∈ A ou non.

(B_{3}) : L’égalité τX ∘ (M × μ′′X) = μ′′(M × X) ∘ ℙτX ∘ τℙX résulte du fait que, pour tout (a, p̂) ∈ M × ℙ ℙX et tout pavé mesurable A × B de M × X, on a, en posant p = μ′′X(p̂) :

– d’une part (τX((M × μ′′X)(a, p̂)))(A × B) = (δ_{a} ⊗ p)(A × B) = δ_{a}(A)p(B) ;

– d’autre part (μ′′(M ×X)((τX)_{∗}(τ(ℙX)(a, p̂))))(A×B) = (μ′′(M ×X)((τX)_{∗}(δ_{a}⊗ p̂)))(A × B) = ∫_{ℙ(M×X)} e_{A×B}d(τX)_{∗}(δ_{a} ⊗ p̂) = ∫∫_{M×ℙX} e_{A×B} ∘ τX d(δ_{a} ⊗ p̂) = ∫∫_{M×ℙX}(e_{A×B}(δ_{b} ⊗ q))(δ_{a} ⊗ p̂)(dbdq) = ∫∫_{M×ℙX}((δ_{b} ⊗ q)(A × B))(δ_{a} ⊗ p̂)(dbdq) = ∫∫_{M×ℙX} δ_{b}(A)q(B)(δ_{a} ⊗ p̂)(dbdq) = ∫_{ℙX} δ_{a}(A)q(B)p̂(dq) = δ_{a}(A) ∫_{ℙX} q(B)p̂(dq) = δ_{a}(A) ∫_{ℙX} e_{B}(q)p̂(dq) = δ_{a}(A)p(B).

(B_{4}) : L’égalité τX ∘ μℙX = ℙμX ∘ τ(M × X) ∘ (M × τX) résulte du fait que, pour tout (a, b, p) ∈ M × M × ℙX et tout pavé mesurable A × B de M × X, on a ((μX)_{∗}(τ(M ×X)((M ×τX)(a, b, p))))(A×B) = ((μX)_{∗}(τ(M ×X)(a, δ_{b} ⊗p)))(A×

B) = ((μX)_{∗}(δ_{a} ⊗ (δ_{b} ⊗ p)))(A × B) = (δ_{(a,b)} ⊗ p)(μX^{−1}(A × B)) =^{∗∗} δ_{ab}(A)p(B) =

(δ_{ab} ⊗ p)(A × B) = (τX(μℙX(a, b, p)))(A × B), l’égalité =^{∗∗} résultant du fait que

μX^{−1}(A × B) = {(c, d, x) ∈ M × M × X | cd ∈ A et x ∈ B} = {(c, d) ∈ M × M | cd ∈

A} × B.

Remerciements. Je tiens à remercier Jacques Penon pour les nombreuses discussions stimulantes que j’ai eues avec lui au cours de la rédaction de ce texte, ainsi que Philippe Bougerol pour m’avoir accordé du temps en répondant avec précision à toutes mes questions sur des points délicats de la théorie des probabilités.

Bibliographie

[Beck 69] J. Beck : Distributive laws, in Seminar on triples and categorical homology theory.119–140. LNM 80. Springer. 1969.

[Ben 67] J. Benabou : Introduction to bicategories, in Report of the Midwest category seminar. 1–77. LNM 47, Springer 1967.

[Bu 86] A. Burroni : Récursivité graphique (1ère partie) : catégorie des fonctions récursives formelles. Cahiers de topologie et géométrie différentielle. 49–79. Vol XXVII-1, [Bu’ 74] E. Burroni : Algèbres non déterministes et D-catégories. Cahiers de topologie et géométrie différentielle. 417–475. Vol XIV-4, 1973.

[Giry 81] M. Giry : A categorical approach to probability theory, in Categorical aspects of topology and analysis. 68–85, LNM 915. 1981.

[McL 72] S. Mac Lane : Categories for the working mathematician. GMT 5, Springer. 1972.

[Nev 64] J. Neveu : Calcul des probabilités. Masson. 1964.

[Star 72] P.H. Starke : Abstract automata. North-Holland. 1972.

[Tull 71] O. de la Tullaye : L’intégration considérée comme l’algèbre d’un triple. Rapport de Stage de D.E.A. Manuscrit. 1971.

Université Paris Diderot-Paris 7 UFR de Mathématiques, Case 7012 Bâtiment Chevaleret 75205 Paris cedex 13. France.

Email: eburroni@math.jussieu.fr

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/22/7/22-07.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University : rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University : barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, McGill University : gavin seal@fastmail.fm

Transmitting editors.

Richard Blute, Université d’ Ottawa : rblute@uottawa.ca Lawrence Breen, Université de Paris 13 : breen@math.univ-paris13.fr Ronald Brown, University of North Wales : ronnie.profbrown (at) btinternet.com Aurelio Carboni, Università dell Insubria : aurelio.carboni@uninsubria.it Valeria de Paiva, Cuill Inc. : valeria@cuill.com Ezra Getzler, Northwestern University : getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge : M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge : ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus : kock@imf.au.dk Stephen Lack, University of Western Sydney : s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo : wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg : loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht : moerdijk@math.uu.nl Susan Niefield, Union College : niefiels@union.edu Robert Paré, Dalhousie University : pare@mathstat.dal.ca Jiri Rosicky, Masaryk University : rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago : bshipley@math.uic.edu James Stasheff, University of North Carolina : jds@math.unc.edu Ross Street, Macquarie University : street@math.mq.edu.au Walter Tholen, York University : tholen@mathstat.yorku.ca Myles Tierney, Rutgers University : tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria : robert.walters@uninsubria.it R. J. Wood, Dalhousie University : rjwood@mathstat.dal.ca