Correspondance fondamentale de Foata
En mathématiques, et plus précisément en combinatoire, la correspondance fondamentale de Foata est une correspondance entre suites sans répétitions et permutations, différente de la correspondance classique où la suite sans répétitions est la suite des images, par la permutation, des éléments 1, 2, 3, etc. dans cet ordre. Cette correspondance facilite, par exemple, l'analyse combinatoire du nombre de cycles et de la taille des cycles d'une permutation.
Description
Il y a plusieurs manières d'encoder une permutation à l'aide d'une suite de nombres distincts tirés de :
- de la manière la plus classique, à partir de on obtient la permutation définie par ;
Si alors
- d'une manière plus liée à la structure des cycles, à partir de on obtient la permutation définie par … , tant que est plus petit que la longueur du cycle de contenant 1 ( est la taille de l'orbite de 1) : la position de 1 dans la suite signale d'ailleurs la longueur de ce cycle : Comment interpréter alors ? Foata propose d'utiliser la suite restante si elle n'est pas vide, pour encoder les images du plus petit élément de cette suite
- en posant là encore, tant que est plus petit que la longueur du cycle de contenant : la position de dans la suite signale d'ailleurs la longueur de ce cycle : On itère alors le procédé avec la suite tant qu'elle n'est pas vide, pour encoder les images du plus petit élément de cette suite
- Le nombre d'itérations de ce procédé est le nombre de cycles de la décomposition de en cycles disjoints.
Cette seconde correspondance entre suites sans répétitions et permutations est précisément la correspondance fondamentale de Foata.
- Toujours avec on a
- Ainsi la correspondance fondamentale de Foata associe à la permutation dont la décomposition en cycles disjoints est :
- Par ailleurs l'écriture traditionnelle de est :
- D'un autre côté, la décomposition en cycles disjoints de est :
- Ainsi la correspondance fondamentale de Foata associe à la suite suivante :
Bijectivité
Cet encodage d'une permutation par une suite, attribué à Foata, est-il bijectif, c.-à-d. atteint-on toutes les permutations ? N'atteint-on pas plusieurs fois la même permutation ? En effet, un cycle de longueur donné s'écrit de manières différentes (123 s'écrit aussi 231 ou 312), et l'unique décomposition en cycles d'une permutation à cycles disjoints, de longueurs respectives s'écrit donc de
manières différentes, puisque des cycles disjoints commutent. De plus la séquence obtenue en juxtaposant les écritures des différents cycles est ambiguë, car on y perd la trace des séparations entre les cycles.
Cependant, on notera que la séquence obtenue à l'aide de la correspondance de Foata évite tous ces écueils. En effet on n'écrit pas chaque cycle n'importe comment, mais en terminant par son plus petit élément, ce qui fixe une manière unique d'écrire chaque cycle. Par ailleurs, on n'écrit pas les cycles dans n'importe quel ordre, mais rangés par ordre croissant du plus petit élément de chaque cycle. Il est ainsi clair que chaque permutation possède un seul encodage, bien défini, donné par le cycle contenant 1, écrit de sorte à se terminer par suivi par le cycle contenant le plus petit élément, n'appartenant pas au cycle de 1, s'il existe des éléments n'appartenant pas au cycle contenant 1, ce deuxième cycle écrit de sorte à se terminer par etc.
Réciproquement, chaque encodage ne peut être associé qu'à une seule permutation : en effet, bien que la fin de chaque cycle ne soit pas indiquée par l'encodage (qui est une suite de nombres tous différents, mais sans marques qui puissent indiquer la fin de chaque cycle), on remarque que si est associé, via la correspondance fondamentale de Foata, à une permutation alors chaque est plus petit que tous les nombres entiers situés après lui dans la suite et que cette propriété est caractéristique des puisque le plus petit élément du cycle apparaissant en dernier dans le cycle, les autres nombres du cycle sont suivis, un peu plus loin, par un nombre qui est strictement plus petit. En d'autres termes, les sont exactement les records vers le bas de la suite renversée . Ainsi
Propriété — Les cycles de la permutation associée à la suite par la correspondance fondamentale de Foata sont décrits par les fragments de cette suite qui se terminent par les records vers le bas de la suite renversée . En particulier le nombre de cycles dans la décomposition de la permutation est égal au nombre de records vers le bas de la suite renversée .
Cela permet de retrouver les fins de cycles de la permutation encodée par la suite et de vérifier ainsi que chaque suite possède un antécédent unique dans l'ensemble des permutations.
Dans l'exemple de la section précédente, les records vers le bas de la suite renversée apparaissent ci-dessous en gras et soulignés :
ce qui, comparé à la décomposition en cycles disjoints de la permutation :
indique comment inverser la correspondance fondamentale de Foata.
Applications
On peut considérer le groupe symétrique des permutations de n symboles comme un univers probabiliste, chaque permutation étant équiprobable. Alors la longueur des cycles, le nombre de cycles de la décomposition d'une permutation en cycles disjoints, le nombre de montées, le nombre d'inversions, etc. sont des variables aléatoires, dont la loi est intéressante. Par exemple, une formule due à Cauchy indique que la loi jointe du nombre de cycles de longueur respectivement 1,2,3, etc. est la loi d'une suite de variables de Poisson indépendantes de paramètres respectifs 1, 1/2, 1/3, etc., 1/n, conditionnées à ce que :
Cela entraîne (mais pas immédiatement) que la loi jointe du nombre de cycles de longueur respectivement 1, 2, etc. converge vers une suite de variables de Poisson indépendantes de paramètres respectifs 1, 1/2, 1/3, etc., non conditionnées, mais cela ne permet pas de dire grand chose sur la loi limite des longueurs des plus grands cycles d'une permutation tirée au hasard. C'est là, entre autres, que la correspondance de Foata montre son utilité.
Stick-breaking process, processus de Poisson-Dirichlet et longueurs des cycles
Stick-breaking process et processus de Poisson-Dirichlet
Le processus de Poisson-Dirichlet (en)[1] de paramètre (0, θ) est une variable aléatoire à valeurs dans le simplexe de dimension infinie :
La description la plus parlante du processus de Poisson-Dirichlet est donnée par l'« algorithme » suivant, qui produit le processus de Poisson-Dirichlet :
- casser un bâton de longueur 1, en deux morceaux de tailles aléatoires respectives et , puis casser à nouveau le morceau restant en deux morceaux aléatoires et , puis casser à nouveau le morceau restant en deux morceaux aléatoires et , etc. de manière à produire une suite à valeurs dans ;
- ordonner la suite dans l'ordre décroissant pour obtenir une suite décroissante à valeurs dans .
Si les variables aléatoires réelles sont indépendantes et suivent toutes la loi bêta de paramètre (1, θ), alors suit la loi de Poisson-Dirichlet de paramètre (0, θ).
Nota. appartient à si et seulement si
ce qui se produit avec probabilité 1 dans le cas du processus de Poisson-Dirichlet. Les sont donnés par la formule explicite
et les restes sont donnés par
Lien avec les longueurs des cycles
Considérons une permutation au hasard sur n symboles, τ, ou encore la suite ω de n nombres tous différents qui lui est associée par la correspondance de Foata. Notons la suite finie des longueurs des cycles de la décomposition de τ, rangées par ordre décroissant, longueurs toutes divisées par n, et suite finie complétée par une suite infinie de zéros.
Par exemple, pour et on a
Alors [2],[3]
Théorème — est une suite de variables aléatoires à valeurs dans le simplexe , suite qui converge faiblement vers une distribution de Poisson-Dirichlet de paramètre (0,1) (i.e. les variables aléatoires réelles intervenant dans la définition du processus de Poisson-Dirichlet suivent toutes la loi Bêta de paramètre (1,1), qui n'est autre que la loi uniforme sur l'intervalle [0,1]).
Grâce à la correspondance de Foata, on voit que les longueurs des cycles sont dictées par les positions des nombres (les records successifs) lesquelles positions sont uniformément distribuées sur la place laissée par les cycles précédents, ce qui fait apparaître naturellement une version discrète du stick-breaking process. On peut alors sans peine formaliser une démonstration rigoureuse du résultat de convergence en loi ci-dessus.
Il est facile de voir que le nombre de suites ω de n nombres différents pris dans et vérifiant est (n-1)!. Donc la longueur, que nous noterons du cycle contenant 1 dans la décomposition en cycles disjoints de vérifie
Or, si on pose
on constate que et ont la même loi. Par ailleurs
Comme la suite converge presque sûrement vers on en déduit que la suite converge en loi vers
Examinons maintenant la longueur, que nous noterons du cycle contenant dans la décomposition en cycles disjoints de On voit facilement que la loi conditionnelle de sachant que est la loi uniforme sur en effet, sachant que la suite ω commence par une suite de k-1 nombres bien précis, suivis du nombre 1, les n-k! manières de terminer la suite ω sont équiprobables, et la position du plus petit nombre restant, est donc uniformément répartie sur les n-k positions de cette suite, pour la même raison que précédemment : ainsi la loi conditionnelle de sachant tout sur les k premiers termes de la suite, est la loi uniforme sur et ne dépend donc pas vraiment des k-1 premiers termes de cette suite, mais uniquement du fait que le nombre 1 apparaît à la k-ème position. La loi uniforme sur est donc aussi la loi conditionnelle de sachant que
Posons
Alors les couples et ont même loi, mais le second couple converge presque sûrement vers En effet :
Donc le couple converge en loi vers De manière un peu fastidieuse, mais sans grande difficulté, on obtiendra ainsi, pour tout k, la convergence en loi de vers ; une méthode plus élégante, consistant à étudier la convergence des restes, est esquissée plus bas. Cela entraîne la convergence en loi de la suite vers la suite Sur le simplexe, l'opération consistant à ordonner une suite de manière décroissante est une opération continue pour la topologie de la convergence terme à terme (qui est métrisable). Ainsi les suites obtenues en réordonnant de manière décroissante les suites à savoir les suites convergent en loi également, vers la réordonnée décroissante de la suite Y, qui, par définition, est un processus de Poisson-Dirichlet de paramètre (0,1).
Nota : une suite ne peut pas toujours être réordonnée de manière décroissante (par exemple l'énumération de tous les rationnels ne peut pas être réordonnée ainsi), mais une suite appartenant au simplexe peut toujours être réordonnée de manière décroissante, car l'ensemble des termes de cette suite supérieurs à ε>0 est un ensemble fini, donc bien ordonné.
Etude des restes. Etant donné un début de suite quelconque de longueur n-k, la fin de la suite, de longueur k, est uniformément distribuée parmi les k! fins de suites possibles. Il est alors commode d'étudier les restes successifs :
L'uniformité des suites résiduelles, remarquée un peu plus haut, entraîne que la loi conditionnelle de sachant que est la loi uniforme sur (la position du minimum de la suite résiduelle, de longueur k, étant uniformément distribuée sur il suit que le nombre de termes de la suite apparaissant après le minimum est uniformément distribué sur Cela fait de la suite une chaîne de Markov, partant de n, de noyau de transition très simple
Or on peut engendrer une telle chaîne de Markov à l'aide d'une suite de variables aléatoires indépendantes uniformes sur [0,1], via la relation de récurrence
Posons
On montre facilement que
donc la suite converge presque sûrement, terme à terme, vers la suite Par conséquent, la suite converge en loi vers la suite r. La suite des longueurs des cycles, tels qu'ils apparaissent dans la correspondance de Foata, est déduite de la suite des restes à l'aide de la relation
Ainsi la suite converge en loi vers la suite et par ailleurs
Notons que la loi de (premier terme de la suite X) est appelée distribution de Dickman et est omniprésente dans l'analyse probabiliste d'objets algébriques (taille du plus grand facteur premier d'un nombre entier tiré au hasard, degré du facteur premier de plus haut degré d'un polynôme tiré au hasard, taille du plus long cycle d'une permutation tirée au hasard, etc.).
Interprétations du nombre de Stirling
Les nombres de Stirling de première espèce comptent le nombre de permutations de n objets ayant exactement k cycles, mais aussi le nombre de permutations de n objets ayant exactement k records. À l'aide du code de Lehmer d'une permutation, le nombre de records, et donc le nombre de cycles également, peuvent être vus comme des sommes de variables de Bernoulli indépendantes, ce qui explique la forme multiplicative de la série génératrice des nombres de Stirling, et ouvre la voie à des estimées précises sur la concentration de la loi du nombre de cycles (estimations via l'inégalité de Hoeffding, ou bien à l'aide du théorème central limite).
Voir aussi
Notes
- ↑ (en) J. F. C. Kingman, « Random Discrete Distributions », Journal of the Royal Statistical Society, Series B (Methodological), vol. 37, no 1, , p. 1-22 (JSTOR 2984986).
- ↑ (en) A. M. Vershik et A. A. Shmidt, « Limit measures arising in the theory of groups I. », Theor. Probab. Appl., vol. 22, , p. 79-85.
- ↑ (en) J. F. Kingman, « The population structure associated with the Ewens sampling formula », Theor Popul Biol., vol. 11, no 2, , p. 274-283
Bibliographie
- (en) M. Lothaire, Combinatorics on Words, Addison–Wesley, coll. « Encyclopedia of Mathematics and its Applications », (réimpr. 1997), 260 p., Section 10.2.
- (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, (ISBN 0-521-89806-4, lire en ligne), Section II.6.3.
- (en) Jean Bertoin, Random Fragmentation and Coagulation Processes, Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics », , 1re éd., 288 p. (ISBN 0521867282), Section 2.2.4.
- (en) Jim Pitman, Combinatorial Stochastic Processes: Ecole d'Eté de Probabilités de Saint-Flour XXXII - 2002, Springer, coll. « Lecture Notes in Mathematics », , 1re éd., 256 p. (ISBN 354030990X)
Article connexe
Portail des mathématiques