Une introduction à la coalescence stochastique additive

Grégory Miermont

1 Introduction

Le but de cet exposé est de donner les idées et les méthodes de base intervenant dans la théorie des processus de coalescence additive. On considère un système constitué d’objets ayant chacun une masse déterminée, dont la somme est finie. Ces objets sont susceptibles de fusionner les uns avec les autres pour former de plus grands objets dont la masse égale la somme des masses de leurs constituants, ce à des temps aléatoires dépendant de leurs masses. Le processus qui donne à chaque temps t ≥ 0 la suite des masses des objets du système à cet instant est appelé un processus de coalescence. La formation de gouttes d’eau dans les nuages, ou encore de galaxies par fusion de “proto-galaxies” plus petites, sont deux exemples naturels de systèmes faisant intervenir de tels processus. Il est à noter que les processus que nous étudierons ignorent délibérément la configuration spatiale des objets, et ne s’intéressent qu’à l’évolution de leurs masses.

Nous nous intéresserons ici plus spécifiquement à la coalescence additive, pour laquelle deux objets de masses respectives m_{i} et m_{j} fusionnent à une “fréquence” m_{i} + m_{j} pour donner un objet unique de masse m_{i} + m_{j}, de telle sorte que le processus obtenu est markovien. Il existe d’autres modèles intéressants de coalescence aléatoire, comme la coalescence multiplicative où la fréquence de coalescence vaut m_{i}m_{j} au lieu de m_{i} + m_{j}, et on peut imaginer des coalescences à fréquence κ(m_{i}, m_{j}) où κ est un noyau positif symétrique.

Dans un premier temps nous introduirons le modèle de base de la coalescence stochastique additive, qui fait intervenir un nombre fini d’objets, puis nous évoquerons rapidement le modèle faisant intervenir un nombre infini de masses. Ensuite, nous introduirons deux façons de coder ces processus, l’une à l’aide d’arbres aléatoires (birthday trees) et l’autre utilisant des processus à accroissements échangeables. Ces deux codages nous permettront alors par des passages à la limite adaptés de construire les processus de coalescence éternels, c’est-à-dire pour lesquels le paramètre temporel décrit ℝ tout entier, et qui sont issus de “micro-objets” de masses infinitésimales.

2 Le modèle de base

Nous construisons ici un processus répondant de façon rigoureuse à la description que nous avons donnée dans l’introduction. Mais tout d’abord, nous faisons quelques rappels fondamentaux sur les variables exponentielles et les processus de Markov.

2.1 Variables exponentielles, processus de Markov

Rappelons qu’une variable exponentielle de paramètre θ > 0 est une variable aléatoire e sur un espace probabilisé (Ω, A, P), dont la densité est donnée par

P [e ∈ dx] = θe^{−θx}1_{x≥0}dx.

En particulier sa moyenne est 1/θ. La propriété essentielle caractérisant les variables exponentielles est leur “non-vieillissement”:

P [e > t + s|e > t] = P [e > s].

Si par exemple, e désigne le temps de vie d’un appareil, alors l’appareil considéré est sans rodage ni usure : sachant au temps t que l’appareil fonctionne toujours, son temps restant de fonctionnement est à son tour exponentiel de même paramètre. On a aussi les propriétés suivantes : si e_{1}, …, e_{k} sont des variables exponentielles indépendantes de paramètres respectifs θ_{1}, …, θ_{k} , alors min(e_{1}, …, e_{k}) est exponentielle de paramètre ∑_{i=1}^{k} θ_{i}. Si e est une variable exponentielle de paramètre θ alors ke est une variable exponentielle de paramètre θ/k. Par ailleurs, on a que

P [min(e_{1}, …, e_{k}) = e_{i}] = \frac{θ_{i}}{∑_{j=1}^{k} θ_{j}}

Un processus de Markov est un processus aléatoire pour lequel, à chaque instant t, la loi de l’évolution du processus après cet instant ne dépend que de l’état à l’instant t et non des états précédents. Nous nous en tiendrons à cette description intuitive dans cet exposé. Tout processus de Markov (X_{t})_{t≥0} (“homogène”) sur un espace E est décrit par son noyau de transition

P_{t}(x, dy) = P [X_{t} ∈ dy|X_{0} = x] {(not.) \atop =} P_{x}[X_{t} ∈ dy].

Un processus est dit de saut pur s’il est continu à droite et admet des limites à gauche en tout point (càdlàg), constant par morceaux. On peut montrer (essentiellement par la propriété de non-vieillissement des lois exponentielles) qu’un processus de Markov càdlàg de saut pur dans un espace d’états fini ou dénombrable E peut se décrire essentiellement comme ceci :

“Il existe une matrice de transition (p(i, j))_{i,j∈E} (c’est-à-dire que p(i, j) ≥ 0 ∀i, j ∈ E et ∑_{j∈E} p(i, j) = 1 ∀i ∈ E) et une fonction positive (a_{i})_{i∈E} telles que si le système est à l’état i à l’instant t ≥ 0, alors après un temps exponentiel de paramètre a_{i}, il saute à l’état j avec probabilité p(i, j).”

Si l’un des a_{i} est nul, l’état i est dit absorbant.

2.2 Modèle avec un nombre fini de fragments

On considère n objets, n ≥ 2, de masses m_{1}, m_{2}, …, m_{n} classées par ordre décroissant. On suppose pour faciliter les notations que la somme des masses est 1.

A toute suite décroissante (a_{1}, …, a_{k}) de réels strictement positifs on associe (a_{1}, …, a_{k})^{⊕(i,j)} la suite de k − 1 éléments obtenue en additionant les masses a_{i} et a_{j} et en réordonnant les masses obtenues.

A chaque couple de masses (m_{i}, m_{j}), i < j on associe alors une variable exponentielle e_{ij} de paramètre m_{i} + m_{j}, de telle sorte que les variables (e_{ij})_{i<j} sont indépendantes. Au temps e = min_{i<j} e_{ij} le système issu de l’état (m_{1}, …, m_{n}) évolue : il existe presque sûrement un unique couple (i, j), i < j, tel que e = e_{ij}. Le système passe alors de l’état (m_{1}, m_{2}, …, m_{n}) à (m_{1}, …, m_{n})^{⊕(i,j)}. Ensuite, le système continue d’évoluer de la même façon jusqu’à ce qu’un unique objet de masse 1 demeure. On note m = (m_{1}, …, m_{n}), et C^{m}(t) = (C_{1}^{m}(t), …, C_{#(t)}^{m}(t)), où #(t) est le nombre d’objets présents à l’instant t, le processus obtenu à l’instant t en classant par ordre décroissant les masses de objets. Soit ℙ_{m} la loi de ce processus.

Théorème 1. Le processus C^{m} est un processus markovien de saut pur, dont le mécanisme de transition est déterminé ainsi : partant de l’état C^{m}(s) à l’instant s, le processus saute au bout d’un temps exponentiel de paramètre #(s) − 1 à l’état C^{m}(s)^{⊕(i,j)} avec probabilité (C_{i}^{m}(s) + C_{j}^{m}(s))/(#(s) − 1).

Preuve. La propriété de Markov de ce processus découle de la description que nous avons donnée des processus de Markov de saut pur dans un espace fini (ici, l’espace constitué de toutes les combinaisons possibles des masses entre elles). Il reste à vérifier que les paramètres que nous avons donnés sont les bons.

Comme on a, si m_{1}, …, m_{k} ont pour somme 1,

∑_{1≤i<j≤k}(m_{i} + m_{j}) = k − 1,

on obtient bien que le temps e = min_{i<j} e_{ij} de la coalescence suivante partant d’un état à k éléments est exponentiel de paramètre k − 1. Par ailleurs, on a que e = e_{i,j} avec probabilité (m_{i} + m_{j})/(k − 1) d’après les rappels sur les variables exponentielles, ce qui donne immédiatement le résultat. □

On peut ajouter que ce processus est binaire, c’est-à-dire qu’il ne peut y avoir plus de deux objets qui coalescent en même temps. Par ailleurs, il y a un “découplage” entre la suite des états distincts du processus de coalescence, et les temps séparant deux de ces états, à cause du fait que les temps de transition dépendent de l’état du système à un instant t uniquement en fonction de #(t), qui décroît de n à 1 lorsque t augmente.

Corollaire 1. On se donne une chaîne de Markov (C_{k})_{1≤k≤n} issue de l’état C_{1} = (m_{1}, …, m_{n}) de probabilité de transition donnée par

P [C_{k+1} = C_{k}^{⊕(i,j)}|C_{k}] = ((C_{k})_{i} + (C_{k})_{j})/(n − k)

et une suite (T_{1}, T_{2}, …, T_{n−1}) de variables exponentielles indépendantes, et indépendantes de la chaîne de Markov, de paramètres respectifs n − 1, n − 2, …, 1. Alors le processus donné par

C(t) = C_{k} pour t ∈ [ ∑_{1≤r≤k−1} T_{r}, ∑_{1≤r≤k} T_{r}[

et C(T_{1} + … + T_{n−1}) = (1) est le processus de coalescence additive issu de (m_{1}, …, m_{n}).

Remarque. On peut donner une autre construction intéressante du processus de coalescence décrit ici. En effet, si on interprète les variables ci-dessus e_{ij} comme le minimum de deux variables exponentielles e_{ij}^{i} et e_{ij}^{j} indépendantes de paramètres m_{i} et m_{j}, on s’aperçoit que le processus peut se décrire ainsi : On part de l’état (m_{1}, …, m_{n}). Soient e_{1}, …, e_{n} n variables exponentielles standard (i.e. de paramètre 1). Soit

e = min(e_{1}/m_{1}, …, e_{n}/m_{n}) = e_{i^{∗}}

pour un certain i^{∗}. La variable e est alors exponentielle de paramètre 1. Au temps e/n le système bascule à l’état (m_{1}, …, m_{n})^{⊕(i^{∗},j^{∗})} où j^{∗} est choisi au hasard uniformément dans {1, …, n} − {i^{∗}}. Ensuite le système évolue similairement jusqu’à ce qu’un seul élément demeure. Si l’on avait pris des temps de transition égaux à e au lieu de e/n, on aurait obtenu le système de serveurs agrégatifs décrit dans [2], dans lequel des serveurs, une fois qu’ils ont servi leur client, s’agrègent au hasard avec un autre serveur pour l’aider.

2.3 Cas d’un nombre infini de fragments

On aimerait à présent construire une famille de lois (ℙ_{m})_{m∈S^{↓}} sur les trajectoires à valeurs dans S^{↓}, où

S^{↓} = {(m_{1}, m_{2}, …), m_{1} ≥ m_{2} ≥ … ≥ 0, ∑_{i=1}^{∞} m_{i} = 1},

telle que ℙ_{m} soit égale à la loi décrite précédemment pour la restriction de m à son support lorsque ce dernier est fini. De plus, on aimerait que sous cette loi, le processus canonique soit un “bon” processus de Markov (la bonne notion intervenant ici est de dire que le processus est de Hunt, et nous ne donnons pas de détails), vérifiant entre autres la propriété forte de Markov (où on remplace les temps fixes par des temps d’arrêt), et stable par passage à la limite (si une suite de bons processus de Markov de mêmes noyaux de transition converge en loi vers un certain processus, ce dernier est à son tour markovien, de même noyau de transition).

On munit S^{↓} de la distance l_{1} habituelle. Par ailleurs on considère l’espace 𝔻(ℝ_{+}, S^{↓}) des processus càdlàg sur ℝ_{+}, que l’on munit de la topologie de Skorohod. Il est inutile de donner trop de détails techniques dans cet exposé, et on renvoie à Billingsley [3] pour des précisions concernant cette topologie classique en probabilités.

Pour m ∈ S^{↓}, on définit la mesure σ-finie μ(m, dm′) sur S^{↓} qui place sur m^{⊕(i,j)} la masse m_{i} + m_{j} pour tout i ≠ j (cette notation est évidente au vu de ce qui précède).

Théorème 2 (Evans et Pitman [5]). Il existe une unique famille (ℙ_{m})_{m∈S^{↓}} de lois sur 𝔻(ℝ_{+}, S^{↓}) et un noyau de transition (P_{t})_{t≥0} tels que, si (X_{t}^{m})_{t≥0} a pour loi ℙ_{m},

1. Si m est à support fini, le processus X^{m} restreint à son support a la même loi que le processus décrit plus haut, issu de m|_{supp m}.

2. X^{m} a des trajectoires binaires p.s. : pour tout s ≥ 0 on passe de l’état X_{s−}^{m} à l’état X_{s}^{m} en fusionnant au plus deux des masses de X_{s−}^{m} entre elles.

3. (μ(m, dm′))_{m∈S^{↓}} est un noyau de saut pour X^{m}.

4. X^{m} est un processus de Hunt càdlàg et les applications m ↦ P_{t}(m, ·) et m ↦ ℙ_{m} sont continues.

Dans la dernière assertion, le mot “continues” est à interpréter au sens de la topologie faible pour les mesures. La troisième assertion signifie que pour toute fonction f positive borelienne,

ℙ_{m}[ ∑_{0≤s≤t} f(X_{s−}^{m}, X_{s}^{m})1_{X_{s}^{m}≠X_{s−}^{m}}] = ℙ_{m}[ ∫_{0}^{t} ∫ f(X_{s−}^{m}, m′)μ(X_{s−}^{m}, dm′)ds].

C’est la façon rigoureuse de définir la notion “le système passe de l’état m à l’état m^{⊕(i,j)} avec la fréquence m_{i} + m_{j}”.

Nous ne donnons pas de preuve de ce théorème qui requiert des outils longs à élaborer.

3 Deux codages des processus de coalescence

Afin d’étudier finement les processus de coalescence, une méthode est de trouver une représentation du processus issu d’un nombre fini d’objets à l’aide d’outils mathématiques dont la structure est connue, et qui admettent des formes limite lorsque le nombre d’objets tend vers +∞. Nous donnons les deux représentations employées par Aldous, Evans et Pitman d’une part, et Bertoin d’autre part, dans l’ordre “historique”.

3.1 Codage par les “arbres d’anniversaires”

Dans [5] et [1] (voir aussi [4]), on donne un moyen de coder les processus de coalescence à l’aide d’arbres appelés birthday trees. Cette dénomination provient du problème très connu qui suit : si chaque individu d’un groupe est né indépendamment des autres, uniformément l’un des 365 jours de l’année, combien faut-il de personnes au minimum dans le groupe pour que deux personnes aient le même anniversaire avec probabilité supérieure à 1/2 ? La réponse s’obtient par un petit calcul combinatoire, mais le problème est plus difficile si, tout en conservant l’indépendance des jours de naissance, les probabilités diffèrent selon les jours. Les “arbres d’anniversaires” permettent d’étudier des comportements asymptotiques de ce problème.

Il s’agit d’arbres à nœuds dans ℕ = {1, 2, … } (avec la notation anglosaxonne), ou un de ses sous-ensembles, que l’on obtient ainsi : on prend des variables aléatoires i.i.d. W_{0}, W_{1}, W_{2}, … à valeurs dans ℕ, telles que P [W_{i} = j] = m_{j} où m_{j} est la probabilité de naître le jour...j. On place alors un crayon au point W_{0}. Si W_{1} = W_{0} on laisse le crayon en place, sinon on trace une arête orientée de W_{0} à W_{1}. A l’étape k, si W_{k} ∈ {W_{0}, …, W_{k−1}} on déplace le crayon en W_{k} sans tracer d’arête orientée, et sinon on en trace une de W_{k−1} à W_{k}. On appelle T (W) l’arbre obtenu. Il est facile de voir que l’ensemble des nœuds de cet arbre est égal au support de m, p.s. Ces arbres possèdent une racine, qui est le point depuis lequel toutes les arêtes pointent, c’est-à-dire W_{0}. Pour k ≥ 1 on appelle R_{k} l’instant de la k-ième répétition dans la suite (W_{m}). L’outil permettant d’étudier le problème des anniversaires est la proposition suivante :

Proposition 1 (Camarri et Pitman [4]). Soit t un arbre orienté depuis sa racine à sommets dans {1, …, n}. Soit T (W) l’arbre construit comme ci-dessus, avec supp m ⊂ {1, …, n}. Alors

P [T (W) = t] = ∏_{s nœuds de T (W)} m_{s}^{C_{s}t}

où C_{s}t désigne le nombre d’enfants du nœud s dans t.

De plus, la suite (W_{0}, W_{R_{1}−1}, W_{R_{2}−1}, …) est i.i.d. et indépendante de l’arbre T (W).

La preuve repose entièrement sur des calculs combinatoires, mais n’est pas aisée pour autant! Exercice(!)

Nous proposons à présent une construction des processus de coalescence à l’aide de ces arbres. Conditionellement à l’arbre T (W), on associe à chacune de ses arêtes e (pour “edge”) une variable U_{e} uniforme sur [0, 1], de sorte que les variables obtenues sont indépendantes. Pour q ∈ [0, 1], soit F(q) la forêt obtenue en effaçant les arêtes e pour lesquelles U_{e} ≤ q. De la sorte, F(q) est donc la forêt obtenue en effaçant les arêtes de T (W) indépendamment, avec probabilité q. On note ensuite Y (q) la suite décroissante des masses des composantes connexes (des arbres quoi!) de la forêt F(q). Par masse on entend la somme des m_{s} pour tous les sommets s de l’arbre. Ainsi Y (0) = (1), Y (1) = (m_{1}, …, m_{n}). Y est appelé processus de fragmentation.

Proposition 2 (Evans et Pitman [5]). Le processus Y (e^{−t})_{0≤t} a pour loi celle de la coalescence additive issue de m.

Preuve. Nous montrons tout d’abord que la suite des états de ce processus a la même loi dans les deux cas. Pour ce faire nous construisons une suite de forêts de la façon suivante : on part de la forêt triviale (F_{1}^{1}, …, F_{1}^{n}) constituée des singletons {1}, …, {n}. On se donne n variables aléatoires X_{1}, …, X_{n} indépendantes avec P [X_{k} = i] = m_{i}, i ∈ {1, …, n}. A l’étape k, on part d’une forêt F_{k} à n−k +1 arbres, et on relie par une arête orientée le noeud X_{k}, appartenant à l’un des arbres de la forêt, à la racine de l’un des n−k autres arbres, que l’on choisit au hasard uniformément. Pour 1 ≤ k ≤ n on appelle Z(k) la suite décroissante des masses des n − k + 1 composantes de la forêt F_{k}. Alors il est facile de voir, à la lumière de la remarque qui suit le Corollaire 1, que (Z(k))_{1≤k≤n} a la même loi que la chaîne de Markov (C_{k}) du Corollaire 1.

De plus, un raisonnement par récurrence implique que la forêt obtenue cidessus à l’étape n a la loi de l’arbre d’anniversaire associé aux probabilités (m_{1}, …, m_{n}) : soit F_{kn} l’ensemble des forêts à k arbres dont les nœuds appartiennent à {1, …, n}. Alors si f ∈ F_{kn},

P [F_{k} = f] = \frac{1}{C_{n−1}^{k−1}} ∏_{1≤s≤n} m_{s}^{C_{s}f} .

Ceci est vrai à l’étape 1, supposons-le vrai pour k. Soit f′ ∈ F_{k+1n} et f ∈ F_{kn} telle que f′ s’obtient de f en ajoutant une arête entre la feuille s̃ de l’un des arbres de f et une racine d’un des n − k autres arbres (il y a k forêts de ce type, une par arête de f′). Alors on a

P [F_{k+1} = f′|F_{k} = f] = \frac{ms̃}{n − k}

Soit par l’hypothèse de récurrence

P [F_{k+1} = f′, F_{k} = f] = \frac{ms̃}{(n − k)C_{n−1}^{k−1}} ∏_{1≤s≤n} m_{s}^{C_{s}f} = \frac{1}{kC_{n−1}^{k}} ∏_{1≤s≤n} m_{s}^{C_{s}f′}

En sommant sur les f décrites ci-dessus, on a le résultat.

De ce fait, la forêt F_{n} est un arbre de loi celle de T (W). Et la démonstration par récurrence ci-dessus montre également que pour décrire la construction à l’envers, il faut enlever les arêtes uniformément : par la règle de Bayes,

P [F_{k} = f|F_{k+1} = f′] = 1/k

où f est l’une des k forêts obtenues de f′ en enlevant l’une de ses arêtes.

Il reste juste à montrer que les temps de transition sont les bons. Pour ce faire on réordonne les variables (U_{e})_{e∈T (W)} sur [0, 1] sous le nom 0 ≤ U_{1} ≤ U_{2} ≤ … ≤ U_{n−1} ≤ 1, et on remarque que lorsque t augmente, les temps écoulés entre deux transitions pour Y (e^{−t}) sont donnés par les quantités

log(1/U_{n−1}), log(U_{n−1}/U_{n−2}), …, log(U_{2}/U_{1}),

qui sont des variables exponentielles indépendantes de paramètres respectifs n − 1, n − 2, …, 1. Pour le prouver, on peut par exemple utiliser la représentation en loi classique :

(U_{1}, U_{2}, …, U_{n−1}) {Loi \atop =} (\frac{s_{1}}{s_{1} + … + s_{n}} , \frac{s_{1} + s_{2}}{s_{1} + … + s_{n}} , …, \frac{s_{1} + … + s_{n−1}}{s_{1} + … + s_{n}} )

où les s_{i} sont exponentielles standard indépendantes. □

3.2 Un codage par les ponts à accroissements échangeables

Nous allons maintenant nous inspirer essentiellement du travail effectué par Bertoin [2]. Le cadre plus naturel dans lequel nous nous plaçons est celui du système de serveurs agrégatifs décrit plus haut après le Corollaire 1, et qui est égal en loi au processus de coalescence additive à un changement de temps près (on fait dérouler le temps k−1 fois plus vite lorsqu’il y a k objets pour obtenir la coalescence additive).

Plus précisément nous construisons le système de serveurs agrégatifs (R(t))_{t≥0} comme suit. On considère n clients ayant besoin de quantités de services s_{1}, s_{2}, …, s_{n}. Ils sont servis par n serveurs, avec des rapidités de service respectives m_{1} ≥ m_{2} ≥ … ≥ m_{n}, c’est-à-dire qu’une quantité de service a est exécutée en un temps a/m_{i} par le serveur i. On suppose que ∑ m_{i} = 1. Au départ le client i va vers le serveur i, et dès qu’un client a été servi, il s’en va et son serveur choisit de fusionner avec un serveur choisi au hasard parmi les autres pour l’aider en formant un serveur de rapidité de service la somme des rapidités des serveurs initiaux. On note R(t) la suite décroissante des rapidités de service des serveurs présents à l’instant t. On suppose que les services demandés s_{1}, …, s_{n} sont exponentiels standard indépendants.

On nomme A_{1} le temps où un premier client a été servi :

A_{1} = min(s_{1}/m_{1}, s_{2}/m_{2}, …, s_{n}/m_{n}),

et plus généralement A_{k} le premier temps où k clients ont été servis. On observe que A_{n} = s_{1} + … + s_{n} car les serveurs travaillent à tout instant, la somme de leurs rapidités est 1 et le travail total à accomplir est s_{1} +…+s_{n}. De plus A_{1} est exponentielle standard et par récurrence et non-vieillissement de la loi exponentielle, (A_{k+1} − A_{k})_{0≤k≤n−1} sont exponentielles standard indépendantes.

Ce système est très proche de la construction exposée précédemment pour les arbres et comme il a été dit plus haut, il s’agit d’un processus de coalescence “ralenti”. Plus exactement, si

I(t) = \frac{t − A_{k}}{n − k − 1} + ∑_{j=0}^{k−1} \frac{A_{j+1} − A_{j}}{n − j − 1} , t ∈ [A_{k}, A_{k+1}],

et si T = I^{−1}, alors (R(T (t)))_{0≤t≤I(A_{n−1})} est égal en loi au processus de coalescence additif issu de (m_{1}, …, m_{n}). Remarquer qu’on arrête le processus au temps où il ne reste plus qu’un serveur, A_{n−1}, plutôt qu’au temps A_{n} où le dernier client s’en va.

Avant de proposer un codage de ce processus nous donnons quelques bases concernant la notion d’échangeabilité.

Définition 1. Une suite de variables aléatoires (X_{1}, X_{2}, …, X_{n}) est dite échangeable si pour toute permutation σ de {1, …, n}, on a

(X_{1}, …, X_{n}) {Loi \atop =} (X_{σ(1)}, …, X_{σ(n)}).

Un processus à accroissements échangeables sur [0, 1] est un processus stochastique (X_{t})_{0≤t≤1} tel que pour tous intervalles I_{1}, …, I_{n} inclus dans [0, 1] de même longueur et disjoints, la suite de variables (X_{I_{k}})_{1≤k≤n} est échangeable, où on a noté X_{I} = X_{sup I} − X_{inf I} pour I un intervalle de [0, 1].

Exemples. Des variables i.i.d., la suite des tirages de n boules identiques numérotées de 1 à n et placées dans une urne, sont des variables échangeables.

Un théorème de Kallenberg [6] montre que tout processus X à accroissements échangeables sur [0, 1] peut se représenter de la sorte :

X_{t} = αt + σb_{t} + ∑_{i=1}^{∞} β_{i}(1_{t≥U_{i}} − t)

où on s’est donné les trois suites indépendantes de variables aléatoires suivantes

1. α, β_{1}, β_{2}, … sont des variables aléatoires indépendantes telles que p.s., ∑_{i=1}^{∞} β_{i}^{2} < ∞,

2. U_{1}, U_{2}, … est une suite de variables uniformes sur [0, 1] indépendantes,

3. σ ∈ ℝ_{+} et b est un pont brownien standard sur [0, 1].

Un pont brownien standard est un processus stochastique qui peut être décrit comme étant le mouvement brownien issu de 0 et conditionné à y revenir au temps 1. On renvoie à la littérature sur le mouvement brownien (par exemple [8]) pour plus de détails car nous n’utiliserons pas ses propriétés ici. Ici, on parlera de pont plutôt que de processus lorsque le coefficient α est nul.

Nous proposons maintenant le codage suivant. Soit

b_{m}(s) = ∑_{i=1}^{n} m_{i}(1_{s≥U_{i}} − s)

le pont à accroissements échangeables, où les U_{i}, i.i.d. uniformes, sont données par U_{1} uniforme indépendante de (s_{i})_{1≤i≤n} et

U_{i} = U_{1} + \frac{s_{1} + s_{2} + … + s_{i−1}}{s_{1} + s_{2} + … + s_{n}} , 2 ≤ i ≤ n

où la somme est prise modulo 1. D’après la représentation en loi donnée à la fin de la partie précédente, ces variables sont bien uniformes i.i.d., de plus elles sont indépendantes de A_{n} comme le montre un simple calcul.

On note ensuite ε_{m}(s) = b_{m}(s + s_{min}) − inf b_{m} où s_{min} est l’unique réel s tel que b_{m}(s−) = inf b_{m}. L’unicité de ce réel découle d’un théorème général de Knight [7] sur les processus à accroissements échangeables, et il est facile de voir qu’il est égal à l’un des U_{i}, qui sont les temps de saut de b_{m}. On appelle ε_{m} l’excursion de Vervaat associée à b_{m}. Enfin, soit ε_{m}^{(t)}(s) = ts − ε_{m}(s) et

(\overline{ε}_{m}^{(t)}(s))_{0≤s≤1} = ( sup_{0≤s′≤s} ε_{m}^{(t)}(s′))_{0≤s≤1}

son processus du supremum. Les trajectoires de ce processus sont croissantes et définissent donc une mesure de Stieljes d\overline{ε}_{m}^{(t)}(s). On nomme intervalles de constance de \overline{ε}_{m}^{(t)} les composantes connexes du complémentaire du support de cette mesure (intervalles maximaux où \overline{ε}_{m}^{(t)} est constante).

Soit F^{m}(t) la suite décroissante (finie) des longueurs des intervalles de constance de \overline{ε}_{m}^{(t)}. On l’appelle processus de fragmentation associé à b_{m}.

Proposition 3 (Bertoin [2]). Pour t ∈]0, A_{n}[, on a

\frac{A_{n}}{t} F^{m}(\frac{A_{n}}{t} − 1) = R(t).

Preuve. On remarque que la loi du système est la même si au départ on prend une permutation aléatoire uniforme σ sur {1, …, n}, que le i-ième client choisit le σ(i)-ième serveur, et que le serveur qui s’occupe du client i, quand il a terminé son service, fusionne avec le serveur qui sert le client i + 1 (de ce fait on place les serveurs sur ℤ/nℤ). De ce point de vue on peut remarquer que b_{m} atteint son minimum en U_{ℓ+1}−, où ℓ est l’indice du dernier client servi. En effet les clients indicés par ℓ + 1, …, ℓ + i ne sont servis que par des serveurs d’indices ℓ + 1, …, ℓ + i, et ils sont entièrement servis avant le temps A_{n} et donc pour tout 1 ≤ i ≤ n − 1,

(m_{σ(ℓ+1)} + … + m_{σ(ℓ+i)})A_{n} > s_{ℓ+1} + … + s_{ℓ+i}

ce qui implique b_{m}(U_{ℓ+i+1}−) > b_{m}(U_{ℓ+1}−).

Sans perte de généralité, comme le système est invariant par rotation des indices, on peut supposer que le minimum est atteint en U_{1}−. De la sorte,

ε_{m}(s) = ∑_{i=1}^{n} m_{σ(i)}(1_{s≥V_{i}} − s)

où V_{i} = U_{i} − U_{1}. On note 0 = g_{1} < d_{1} < … < g_{k} < d_{k} < 1 les extrémités gauches et droites des k intervalles de constance de \overline{ε}_{m}^{(τ)} où τ = t^{−1}A_{n} − 1. On constate alors aisément (un dessin facilite les choses) que

∑_{i=1}^{n} m_{σ(i)}1_{g_{j}≤U_{i}≤d_{j}} = t^{−1}A_{n}(d_{j} − g_{j})

Ensuite soit K = sup{k : U_{k} ≤ d_{1}}. On remarque que si K ≥ 2 et si 2 ≤ i ≤ K,

\overline{ε}_{m}^{(τ)}(U_{j}−) = t^{−1}A_{n}U_{j} − (m_{σ(1)} + … + m_{σ(j−1)}) < 0

de sorte que

(m_{σ(1)} + … + m_{σ(j−1)})t > s_{1} + … + s_{j−1}

et si K < n, le fait que \overline{ε}_{m}^{(τ)}(U_{K+1}−) > 0 donne que

(m_{σ(1)} + … + m_{σ(K)})t < s_{1} + … + s_{K}.

Autrement dit, au temps t, les K − 1 premiers serveurs (dont les taux sont m_{σ(1)}, …, m_{σ(K−1)}) ont déjà servi leurs clients et ont fusionné mais en revanche (comme le client n n’a pas été servi avant le temps A_{n} comme expliqué plus haut) le client K n’a pu être servi complètement. De ce fait, ∑_{i=1}^{n} m_{σ(i)}1_{g_{j}≤U_{i}≤d_{j}} est bien égal au taux de service du premier serveur à l’instant t. On raisonne de même pour les autres interalles de constance, par récurrence. □

Ainsi, si à l’inverse on part du pont b_{m} construit avec des variables (U_{i}) i.i.d. uniformes, on peut en prenant une variable A indépendante de même loi que A_{n} recontruire un processus ayant même loi que R(t), et donc aussi un autre ayant même loi que C^{m}(t).

4 Les coalescences éternelles

On s’intéresse à présent aux processus de coalescence définis, non plus sur [0, +∞[, mais sur ℝ tout entier, c’est-à-dire (hormis le processus constant (1, 0, …)) partant d’une “poussière” infinitésimale au temps −∞, mais dont le noyau de transition est toujours celui de la coalescence additive décrit dans le Théorème 2. Deux problèmes principaux se posent :

– Savoir construire de tels processus,

– caractériser la frontière d’entrée du processus.

Expliquons ce dernier terme. La loi d’un processus de Markov (X_{t})_{t≥0} est entièrement déterminée par son noyau de transition et par son point de départ X_{0}, qui peut être aléatoire ou non. Mais il suffit de connaître le processus issu d’un point x déterministe quelconque, car alors le processus issu d’une variable aléatoire est obtenu par mélange : si P_{X_{0}} désigne la loi du processus issu de X_{0} de loi μ, alors on a P_{X_{0}} = ∫ μ(dx)P_{x}. De la même façon, la frontière d’entrée de la coalescence éternelle est le plus petit ensemble de lois dont tout processus de coalescence éternel est un mélange. Des théorèmes reposant sur de l’analyse convexe entraînent qu’il s’agit de l’ensemble des lois de probabilités sur les processus càdlàg sur ℝ pour lesquels la tribu au temps −∞ est triviale, c’est-à-dire que sous ces lois, les événements faisant intervenir uniquement le comportement asymptotique du processus en −∞ sont de probabilité 0 ou 1 (en particulier, les comportements asymptotiques en −∞ sont déterministes). On parle de coalescence extrémale.

Nous allons évoquer les méthodes permettant de répondre à ces deux problèmes. Si, “historiquement”, la méthode de codage par les arbres a été la première utilisée, nous allons faire une présentation par les processus à accroissements échangeables car ils demandent moins d’outils.

La partie précédente nous permet de construire, à partir d’un pont à accroissements échangeables et d’une variable aléatoire indépendante, le processus de coalescence issu de l’état (m_{1}, …, m_{n}) à l’instant 0. Nous considérons à présent une suite positive (θ_{i})_{i≥1} de carré sommable, avec ∑_{i=1}^{∞} θ_{i}^{2} = 1 − σ^{2} ≤ 1 vérifiant

∑_{i=1}^{∞} θ_{i} = ∞ ou σ ≠ 0.

On note ensuite

b_{θ}(s) = σb_{s} + ∑_{i=1}^{∞} θ_{i}(1_{s≥U_{i}} − s)

le pont de Kallenberg dont les sauts sont les θ_{i} et de composante gaussienne (pont brownien) σb. La condition ci-dessus sur θ est nécessaire et suffisante pour que ce pont soit à variation infinie sur [0, 1] (ou tout sous-intervalle d’intérieur non vide). A b_{θ} on peut de la même façon que ci-dessus associer un processus F^{θ}(t) en introduisant l’excursion de Vervaat ε_{θ} obtenue de b_{θ} comme ci-dessus, en mettant bout-à-bout les processus post- et pre- minimum. Le théorème de Knight cité plus haut implique que dans notre cas, où b_{θ} est à variation infinie, le minimum est toujours atteint en un unique point (presque-sûrement), mais cette fois ce point est p.s. un point de continuité au lieu d’un saut. On définit similairement à ci-dessus les processus ε_{θ}^{(t)}, \overline{ε}_{θ}^{(t)}. Enfin on note F^{θ}(t) la suite décroissante des longueurs des intervalles de constance de \overline{ε}_{θ}^{(t)}. Le fait que le processus ε_{θ}^{(t)} est à variation infinie entraîne que F^{θ}(t) est dans S^{↓} (c’est-à-dire de somme 1) pour tout t, et il y a d’ailleurs équivalence (voir [2]).

On se donne alors une suite (m^{n})_{n≥1} ∈ (S^{↓})^{ℕ} vérifiant les conditions suivantes : m^{n} est à support fini pour tout n, et

σ_{n} → 0, \frac{m_{i}^{n}}{σ_{n}} → θ_{i}, i ≥ 1

où σ_{n} = (∑_{i=1}^{∞}(m_{i}^{n})^{2})^{1/2}. Il en existe (exercice un peu lourd). Soit également b_{m^{n}} le pont défini comme dans la partie précédente. On définit également ε_{m^{n}} et F^{m^{n}} comme précédemment. Alors

Lemme 1. La suite de processus (σ_{n}^{−1}ε_{m^{n}}) converge au sens de Skorohod vers ε_{θ}.

Ce lemme est une conséquence de [6], qui entraîne la convergence de (σ_{n}^{−1}b_{m^{n}}) vers b_{θ}, et du fait que (sous certaines hypothèses techniques) la transformation qui à un pont associe son excursion de Vervaat est une transformation continue pour la métrique de Skorohod.

Soit alors (A^{(n)}) une suite de variables aléatoires telle que A^{(n)} est distribuée comme la somme de #supp m^{n} variables exponentielles standard indépendantes. On appelle également T^{(n)}(t) le changement de temps adéquat pour passer du système de serveurs agrégatifs déduit de b_{m^{n}} au processus de coalescence associé. Nous avons donc un processus de coalescence

C^{n}(t) = \frac{A^{(n)}}{T^{(n)}(t)}F^{m^{n}}(\frac{A^{(n)}}{T^{(n)}(t)} − 1).

Le théorème suivant, prouvé par Aldous et Pitman à l’aide des arbres et par Bertoin à l’aide des processus à accroissements échangeables, répond à la première interrogation.

Théorème 3 (Aldous-Pitman, Bertoin [1, 2]). Le processus

(C^{n}(− log σ_{n} − log t))_{0<t<1/σ_{n}}

converge au sens des lois de dimension finie vers le processus (F^{θ}(t))_{t≥0}. Le processus (F^{θ}(e^{−t}))_{−∞<t<+∞} est un processus de coalescence éternel.

et à la seconde par le

Théorème 4 (Aldous et Pitman [1]). Tout processus de coalescence éternel extrémal est de la forme (F^{θ}(e^{−(t−t_{0})}))_{−∞<t<+∞} pour un θ répondant aux conditions plus haut et un réel t_{0}.

Nous ne donnons que l’idée de la démonstration du premier théorème, le second utilisant du calcul stochastique élaboré sur les processus de coalescence.

Le résultat est une conséquence logique du lemme précédent. En effet, il est logique (mais un peu technique à montrer) que le processus de fragmentation, au temps t, associé à l’excursion σ_{n}^{−1}ε_{m^{n}} converge vers F^{θ}(t). Par ailleurs, la fragmentation associée au pont σ_{n}^{−1}ε_{m^{n}} est la même que celle associé à ε_{m^{n}}, mais où le temps est multiplié par σ_{n}. Donc (F^{m^{n}}(σ_{n}t)) converge (au moins au sens des distributions de dimension finie) vers F^{θ}(t). Par ailleurs, un calcul donne que cette dernière suite de processus est égale en loi à

\frac{1}{1 + σ_{n}t}C^{n}((T^{(n)})^{−1}(\frac{A^{(n)}}{1 + σ_{n}t})).

Il faut alors contrôler que le changement de temps qui intervient ci-dessus converge vers − log(σ_{n}t), ce qui provient d’une application corsée de la loi des grands nombres, et que les passages à la limite en loi sont valides, ce qui est assez technique.

Enfin, à partir du moment où l’on sait que la suite des processus considérés converge en loi, en utilisant les “bonnes” propriétés des processus de Hunt décrites plus haut, on déduit que le processus limite a le bon noyau de transition et est donc un processus de coalescence additive. Remarque. Comme il a été dit, les processus éternels ont d’abord été décrits par Aldous et Pitman en utilisant des continuum random trees (CRT) inhomogènes, qui sont d’une certaine façon des limites en loi des arbres d’anniversaire ci-dessus, et où, au lieu de couper des arêtes indépendamment, on coupe l’arbre par un processus de Poisson le long de son squelette (un CRT étant un espace métrique muni d’une mesure de longueur σ-finie).

5 Commentaires et questions

La notion d’échangeabilité, qui a été entrevue ici, est très importante dans les études tournant autour de la coalescence : elle a été employée dans les travaux de Kingman sur les partitions aléatoires de ℕ (très liés aux processus de fragmentation), et réapparaît dans les CRT d’Aldous et Pitman ainsi que dans les ponts que nous avons employés.

Par ailleurs, les liens précis existant entre les deux codages présentés ici restent très obscurs.

D’autre part, les résultats que nous avons présentés ici sont de nature purement existentielle pour la plupart, et le problème principal qui se pose ensuite est de donner de bonnes descriptions des lois de ces processus, de leurs comportements asymptotiques etc... De plus tous les problèmes d’existence ne sont pas réglés, en particulier dans le cas non-additif, et dans le cas additif on n’a pas de caractérisation satisfaisante du semigroupe ou du générateur infinitésimal.

Enfin, la représentation par les ponts induit un ordre naturel sur les objets qui coalescent (représentés par les intervalles d’une partition de [0, 1]) dont l’interprétation n’est pas totalement évidente, et qui semble liée fortement au caractère additif des processus que nous avons étudiés.

Références

[1] D.J. Aldous et J. Pitman: Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent: Prob. Theory Relat. Fields 118, 455-482 (2000).

[2] J. Bertoin: Eternal additive coalescents and certain bridges with exchangeable increments. Ann. Probab. (2001) (to appear).

[3] P. Billingsley, Convergence of probability measures. Wiley and Sons, New-York 1979.

[4] M. Camarri et J. Pitman: Limit distributions and random trees derived from the birthday problem with unequal probabilities. Electronic Journal of Probability, Vol. 5, Paper no. 2, 1-18 (2000).

[5] S. N. Evans et J. Pitman: Construction of Markovian coalescents, Ann. Inst. Henri Poincaré 34, 339-383 (1998).

[6] O. Kallenberg: Canonical representations and convergence criteria for processes with interchangeable increments. Z. Wahrscheinlichkeitstheorie verw. Geb. 27, 23–36 (1973).

[7] F. B. Knight: The uniform law for exchangeable and Lévy process bridges. Hommage à P. A. Meyer et J. Neveu. Astérisque 236, 171– 188 (1996).

[8] D. Revuz et M. Yor: Continuous martingales and Brownian motion, 3^{e} édition, Springer, Berlin (1999)