186
14 Restaurants chinois
où θ 0 est un paramètre fixé qui ne dépend pas de n. Il s’agit bien d’un
noyau de transition car la somme des longueurs des cycles de σ est n. Le
nom de ce processus provient de l’interprétation des cycles de σ n comme
les tables circulaires occupées par les n clients d’un restaurant chinois, ces
restaurants où les gens s’attablent sans se connaître. Au temps initial 1, le
restaurant ne compte qu’une seule table occupée par un seul client numéroté
1. Par récurrence sur n, à l’instant n + 1, et conditionnellement à tout le passé
σ 1 , . . . , σ n , un nouveau client, numéroté n + 1, pénètre dans le restaurant, et
décide soit de rejoindre l’une des tables déjà occupées (cycles de σ n ) avec une
probabilité proportionnelle à la taille de la table (longueur du cycle), à une
place uniformément choisie, soit de s’asseoir à une table vide (créer un nouveau
cycle de longueur 1 contenant n + 1). Cette interprétation gastronomique
suppose que les convives ne changent jamais de table, que les tables peuvent
avoir un nombre arbitrairement grand de convives, et que le restaurant peut
comporter un nombre arbitrairement grand de tables.
1 6 3
2 4
5
σ 6 = (1, 6, 3)(2, 4)(5) =
1 2 3 4 5 6
6 4 1 2 5 3
et π 6 = {{1, 6, 3}, {2, 4}, {5}}
Fig. 14.1. Configuration avec n = 6 clients sur 3 tables dans le restaurant chinois.
Associons à la permutation aléatoire σ n la partition aléatoire π n de
{1, . . . , n} donnée par le support des cycles. Chaque bloc de π n regroupe les
clients d’une table du restaurant. On a π 1 = {1}, et pour tout n 1, π n est à
valeurs dans l’ensemble Π n des partitions de {1, . . . , n}. En général, l’image
d’une chaîne de Markov par une fonction n’est pas une chaîne de Markov
1 .
Cependant, il se trouve ici que (π n ) n1 est une chaîne de Markov inhomogène
sur ∪ n1 Π n , de noyau de transition donné pour tous (π, π
) ∈ Π n × Π n+1 par
1. Un critère dû à Dynkin fournit une condition suffisante sur la fonction.
14 Restaurants chinois
où θ 0 est un paramètre fixé qui ne dépend pas de n. Il s’agit bien d’un
noyau de transition car la somme des longueurs des cycles de σ est n. Le
nom de ce processus provient de l’interprétation des cycles de σ n comme
les tables circulaires occupées par les n clients d’un restaurant chinois, ces
restaurants où les gens s’attablent sans se connaître. Au temps initial 1, le
restaurant ne compte qu’une seule table occupée par un seul client numéroté
1. Par récurrence sur n, à l’instant n + 1, et conditionnellement à tout le passé
σ 1 , . . . , σ n , un nouveau client, numéroté n + 1, pénètre dans le restaurant, et
décide soit de rejoindre l’une des tables déjà occupées (cycles de σ n ) avec une
probabilité proportionnelle à la taille de la table (longueur du cycle), à une
place uniformément choisie, soit de s’asseoir à une table vide (créer un nouveau
cycle de longueur 1 contenant n + 1). Cette interprétation gastronomique
suppose que les convives ne changent jamais de table, que les tables peuvent
avoir un nombre arbitrairement grand de convives, et que le restaurant peut
comporter un nombre arbitrairement grand de tables.
1 6 3
2 4
5
σ 6 = (1, 6, 3)(2, 4)(5) =
1 2 3 4 5 6
6 4 1 2 5 3
et π 6 = {{1, 6, 3}, {2, 4}, {5}}
Fig. 14.1. Configuration avec n = 6 clients sur 3 tables dans le restaurant chinois.
Associons à la permutation aléatoire σ n la partition aléatoire π n de
{1, . . . , n} donnée par le support des cycles. Chaque bloc de π n regroupe les
clients d’une table du restaurant. On a π 1 = {1}, et pour tout n 1, π n est à
valeurs dans l’ensemble Π n des partitions de {1, . . . , n}. En général, l’image
d’une chaîne de Markov par une fonction n’est pas une chaîne de Markov
1 .
Cependant, il se trouve ici que (π n ) n1 est une chaîne de Markov inhomogène
sur ∪ n1 Π n , de noyau de transition donné pour tous (π, π
) ∈ Π n × Π n+1 par
1. Un critère dû à Dynkin fournit une condition suffisante sur la fonction.