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   ω = ( ω 1 , ω 2 , … , ω n ) {\displaystyle \ \omega =(\omega _{1},\omega _{2},\dots ,\omega _{n})} de   n {\displaystyle \ n} nombres distincts tirés de   [ [ 1 , n ] ] {\displaystyle \ [\![1,n]\!]}  :

  • de la manière la plus classique, à partir de   ω ,   {\displaystyle \ \omega ,\ } on obtient la permutation   T ω = σ {\displaystyle \ T\omega =\sigma } définie par   σ ( i ) = ω i ,   {\displaystyle \ \sigma (i)=\omega _{i},\ }   1 ≤ i ≤ n {\displaystyle \ 1\leq i\leq n}  ;
Exemple :

Si   ω = ( 2 , 8 , 10 , 6 , 1 , 3 , 12 , 5 , 4 , 9 , 7 , 15 , 11 , 14 , 13 ) ,   {\displaystyle \ \omega {=}(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13),\ } alors

σ ( 1 ) = 2 σ ( 2 ) = 8 σ ( 3 ) = 10 σ ( 4 ) = 6 … = … {\displaystyle {\begin{aligned}\sigma (1)&=2\\\sigma (2)&=8\\\sigma (3)&=10\\\sigma (4)&=6\\\dots &=\dots \end{aligned}}}
  • d'une manière plus liée à la structure des cycles, à partir de   ω ,   {\displaystyle \ \omega ,\ } on obtient la permutation   R ω = τ {\displaystyle \ R\omega =\tau } définie par   τ ( 1 ) = ω 1 ,   {\displaystyle \ \tau (1)=\omega _{1},\ }   τ 2 ( 1 ) = ω 2 ,   {\displaystyle \ \tau ^{2}(1)=\omega _{2},\ } … ,   τ k ( 1 ) = ω k ,   {\displaystyle \ \tau ^{k}(1)=\omega _{k},\ } tant que   k {\displaystyle \ k} est plus petit que la longueur   ℓ 1 {\displaystyle \ \ell _{1}} du cycle de   τ {\displaystyle \ \tau } contenant 1 (   ℓ 1 {\displaystyle \ \ell _{1}} est la taille de l'orbite de 1) : la position de 1 dans la suite   ω {\displaystyle \ \omega } signale d'ailleurs la longueur de ce cycle :   ω ℓ 1 = 1.   {\displaystyle \ \omega _{\ell _{1}}=1.\ } Comment interpréter alors   ω ℓ 1 + 1 {\displaystyle \ \omega _{\ell _{1}+1}}  ? Foata propose d'utiliser la suite restante   ω ′ = ( ω ℓ 1 + 1 , ω ℓ 1 + 2 , … , ω n ) ,   {\displaystyle \ \omega ^{\prime }=(\omega _{\ell _{1}+1},\omega _{\ell _{1}+2},\dots ,\omega _{n}),\ } si elle n'est pas vide, pour encoder les images du plus petit élément   m 2 {\displaystyle \ m_{2}} de cette suite
m 2 = min { ω k   | ℓ 1 + 1 ≤ k ≤ n } , {\displaystyle m_{2}=\min\{\omega _{k}\ |\ell _{1}+1\leq k\leq n\},}
en posant   τ ( m 2 ) = ω ℓ 1 + 1 ,   {\displaystyle \ \tau (m_{2})=\omega _{\ell _{1}+1},\ }   τ 2 ( m 2 ) = ω ℓ 1 + 2 ,   … ,   τ k ( m 2 ) = ω ℓ 1 + k ,   {\displaystyle \ \tau ^{2}(m_{2})=\omega _{\ell _{1}+2},\ \dots ,\ \tau ^{k}(m_{2})=\omega _{\ell _{1}+k},\ } là encore, tant que   k {\displaystyle \ k} est plus petit que la longueur   ℓ 2 {\displaystyle \ \ell _{2}} du cycle de   τ {\displaystyle \ \tau } contenant   m 2 {\displaystyle \ m_{2}}  : la position de   m 2 {\displaystyle \ m_{2}} dans la suite   ω {\displaystyle \ \omega } signale d'ailleurs la longueur de ce cycle :   ω ℓ 1 + ℓ 2 = m 2 .   {\displaystyle \ \omega _{\ell _{1}+\ell _{2}}=m_{2}.\ } On itère alors le procédé avec la suite   ω ′ ′ = ( ω ℓ 1 + ℓ 2 + 1 , ω ℓ 1 + ℓ 2 + 2 , … , ω n ) ,   {\displaystyle \ \omega ^{\prime \prime }=(\omega _{\ell _{1}+\ell _{2}+1},\omega _{\ell _{1}+\ell _{2}+2},\dots ,\omega _{n}),\ } tant qu'elle n'est pas vide, pour encoder les images du plus petit élément de cette suite
m 3 = min { ω k   | ℓ 1 + ℓ 2 + 1 ≤ k ≤ n } . {\displaystyle m_{3}=\min\{\omega _{k}\ |\ell _{1}+\ell _{2}+1\leq k\leq n\}.}
Le nombre d'itérations de ce procédé est le nombre de cycles de la décomposition de   τ {\displaystyle \ \tau } en cycles disjoints.

Cette seconde correspondance entre suites sans répétitions et permutations est précisément la correspondance fondamentale de Foata.

Exemple :
  • Toujours avec     ω = ( 2 , 8 , 10 , 6 , 1 , 3 , 12 , 5 , 4 , 9 , 7 , 15 , 11 , 14 , 13 ) ,   {\displaystyle \ \ \omega {=}(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13),\ } on a
m 1 = 1 ,   ℓ 1 = 5 ,   τ ( 1 ) = 2 ,   τ ( 2 ) = 8 ,   τ ( 8 ) = 10 ,   τ ( 10 ) = 6 ,   τ ( 6 ) = 1 , m 2 = 3 ,   ℓ 2 = 1 ,   τ ( 3 ) = 3 , m 3 = 4 ,   ℓ 3 = 3 ,   τ ( 4 ) = 12 ,   τ ( 12 ) = 5 ,   τ ( 5 ) = 4 , m 4 = 7 ,   ℓ 4 = 2 ,   τ ( 7 ) = 9 ,   τ ( 9 ) = 7 , m 5 = 11 ,   ℓ 5 = 2 ,   τ ( 11 ) = 15 ,   τ ( 15 ) = 11 , m 6 = 13 ,   ℓ 6 = 2 ,   τ ( 13 ) = 14 ,   τ ( 14 ) = 13. {\displaystyle {\begin{aligned}m_{1}&=1,\ \ell _{1}=5,\ \tau (1)=2,\ \tau (2)=8,\ \tau (8)=10,\ \tau (10)=6,\ \tau (6)=1,\\m_{2}&=3,\ \ell _{2}=1,\ \tau (3)=3,\\m_{3}&=4,\ \ell _{3}=3,\ \tau (4)=12,\ \tau (12)=5,\ \tau (5)=4,\\m_{4}&=7,\ \ell _{4}=2,\ \tau (7)=9,\ \tau (9)=7,\\m_{5}&=11,\ \ell _{5}=2,\ \tau (11)=15,\ \tau (15)=11,\\m_{6}&=13,\ \ell _{6}=2,\ \tau (13)=14,\ \tau (14)=13.\end{aligned}}}
Ainsi la correspondance fondamentale de Foata associe à   ω {\displaystyle \ \omega } la permutation   τ {\displaystyle \ \tau } dont la décomposition en cycles disjoints est :
τ = ( 2 , 8 , 10 , 6 , 1 )   ( 3 )   ( 12 , 5 , 4 )   ( 9 , 7 )   ( 15 , 11 )   ( 14 , 13 )   =   R ( ω ) . {\displaystyle \tau =(2,8,10,6,1)\ (3)\ (12,5,4)\ (9,7)\ (15,11)\ (14,13)\ =\ R(\omega ).}
Par ailleurs l'écriture traditionnelle de   τ {\displaystyle \ \tau } est :
T − 1 ∘ R ( ω ) = ( 2 , 8 , 3 , 12 , 4 , 1 , 9 , 10 , 7 , 6 , 15 , 5 , 14 , 13 , 11 ) . {\displaystyle T^{-1}\circ R(\omega )=(2,8,3,12,4,1,9,10,7,6,15,5,14,13,11).}
  • D'un autre côté, la décomposition en cycles disjoints de   σ {\displaystyle \ \sigma } est :
σ = ( 2 , 8 , 5 , 1 )   ( 10 , 9 , 4 , 6 , 3 )   ( 12 , 15 , 13 , 11 , 7 )   ( 14 ) . {\displaystyle \sigma =(2,8,5,1)\ (10,9,4,6,3)\ (12,15,13,11,7)\ (14).}
Ainsi la correspondance fondamentale de Foata associe à   σ {\displaystyle \ \sigma } la suite   ω ~ {\displaystyle \ {\tilde {\omega }}} suivante :
ω ~ = R − 1 ∘ T ( ω ) = ( 2 , 8 , 5 , 1 , 10 , 9 , 4 , 6 , 3 , 12 , 15 , 13 , 11 , 7 , 14 ) . {\displaystyle {\tilde {\omega }}=R^{-1}\circ T(\omega )=(2,8,5,1,10,9,4,6,3,12,15,13,11,7,14).}

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 k {\displaystyle k} donné s'écrit de k {\displaystyle k} manières différentes (123 s'écrit aussi 231 ou 312), et l'unique décomposition en cycles d'une permutation à ℓ {\displaystyle \ell } cycles disjoints, de longueurs respectives ( k j ) 1 ≤ j ≤ ℓ ,   {\displaystyle (k_{j})_{1\leq j\leq \ell },\ } s'écrit donc de

ℓ ! ∏ 1 ≤ j ≤ ℓ k j {\displaystyle \ell !\prod _{1\leq j\leq \ell }k_{j}}

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 m 1 = 1 ,   {\displaystyle m_{1}=1,\ } suivi par le cycle contenant le plus petit élément, m 2 ,   {\displaystyle m_{2},\ } 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 m 2 ,   {\displaystyle m_{2},\ } etc.

Réciproquement, chaque encodage ω {\displaystyle \omega } 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 n {\displaystyle n} nombres tous différents, mais sans marques qui puissent indiquer la fin de chaque cycle), on remarque que si ω {\displaystyle \omega } est associé, via la correspondance fondamentale de Foata, à une permutation τ ,   {\displaystyle \tau ,\ } alors chaque m i {\displaystyle m_{i}} est plus petit que tous les nombres entiers situés après lui dans la suite ω ,   {\displaystyle \omega ,\ } et que cette propriété est caractéristique des m i ,   {\displaystyle m_{i},\ } 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 m i {\displaystyle m_{i}} sont exactement les records vers le bas de la suite renversée ω ~ = ( ω n , ω n − 1 , … , ω 1 ) {\displaystyle {\tilde {\omega }}=(\omega _{n},\omega _{n-1},\dots ,\omega _{1})} . Ainsi

Propriété — Les cycles de la permutation R ω {\displaystyle R\omega } associée à la suite ω {\displaystyle \omega } par la correspondance fondamentale de Foata sont décrits par les fragments de cette suite ω {\displaystyle \omega } qui se terminent par les records vers le bas de la suite renversée ω ~ = ( ω n , ω n − 1 , … , ω 1 ) {\displaystyle {\tilde {\omega }}=(\omega _{n},\omega _{n-1},\dots ,\omega _{1})} . En particulier le nombre de cycles dans la décomposition de la permutation R ω {\displaystyle R\omega } est égal au nombre de records vers le bas de la suite renversée ω ~ = ( ω n , ω n − 1 , … , ω 1 ) {\displaystyle {\tilde {\omega }}=(\omega _{n},\omega _{n-1},\dots ,\omega _{1})} .

Cela permet de retrouver les fins de cycles de la permutation encodée par la suite ω ,   {\displaystyle \omega ,\ } et de vérifier ainsi que chaque suite possède un antécédent unique dans l'ensemble des permutations.

Exemple :

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 :

  ω ~ = ( 13 _ , 14 , 11 _ , 15 , 7 _ , 9 , 4 _ , 5 , 12 , 3 _ , 1 _ , 6 , 10 , 8 , 2 ) , {\displaystyle \ {\tilde {\omega }}{=}({\underline {\mathbf {13} }},14,{\underline {\mathbf {11} }},15,{\underline {\mathbf {7} }},9,{\underline {\mathbf {4} }},5,12,{\underline {\mathbf {3} }},{\underline {\mathbf {1} }},6,10,8,2),}

ce qui, comparé à la décomposition en cycles disjoints de la permutation   τ   {\displaystyle \ \tau \ }  :

τ = ( 2 , 8 , 10 , 6 , 1 )   ( 3 )   ( 12 , 5 , 4 )   ( 9 , 7 )   ( 15 , 11 )   ( 14 , 13 ) , {\displaystyle \tau {=}(2,8,10,6,1)\ (3)\ (12,5,4)\ (9,7)\ (15,11)\ (14,13),}

indique comment inverser la correspondance fondamentale de Foata.

Applications

On peut considérer le groupe symétrique   S n   {\displaystyle \ {\mathfrak {S}}_{n}\ } 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   ( Y 1 , Y 2 , Y 3 , … )   {\displaystyle \ (Y_{1},Y_{2},Y_{3},\dots )\ } de variables de Poisson indépendantes de paramètres respectifs 1, 1/2, 1/3, etc., 1/n, conditionnées à ce que :

∑ k ≥ 1   k Y k   =   n . {\displaystyle \sum _{k\geq 1}\ k\,Y_{k}\ =\ n.}

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 X = ( X k ) k ≥ 1 {\displaystyle X=(X_{k})_{k\geq 1}} à valeurs dans le simplexe de dimension infinie :

S = { x = ( x k ) k ≥ 1 |   x i ≥ 0 , ∀ i ≥ 1  et  ∑ i ≥ 1 x i = 1 } {\displaystyle S=\left\{x=(x_{k})_{k\geq 1}\,\left|\ x_{i}\geq 0,\forall i\geq 1{\text{ et }}\sum _{i\geq 1}x_{i}=1\right.\right\}} .

La description la plus parlante du processus de Poisson-Dirichlet est donnée par l'« algorithme » suivant, qui produit le processus de Poisson-Dirichlet X = ( X k ) k ≥ 1 {\displaystyle X=(X_{k})_{k\geq 1}}  :

  • casser un bâton de longueur 1, en deux morceaux de tailles aléatoires respectives Y 1 = U 1 {\displaystyle Y_{1}=U_{1}} et R 1 = 1 − Y 1 {\displaystyle R_{1}=1-Y_{1}} , puis casser à nouveau le morceau restant R 1 = 1 − Y 1 {\displaystyle R_{1}=1-Y_{1}} en deux morceaux aléatoires Y 2 = R 1 U 2 {\displaystyle Y_{2}=R_{1}U_{2}} et R 2 = R 1 ( 1 − U 2 ) {\displaystyle R_{2}=R_{1}(1-U_{2})} , puis casser à nouveau le morceau restant R 2 {\displaystyle R_{2}} en deux morceaux aléatoires Y 3 = R 2 U 3 {\displaystyle Y_{3}=R_{2}U_{3}} et R 3 = R 2 ( 1 − U 3 ) {\displaystyle R_{3}=R_{2}(1-U_{3})} , etc. de manière à produire une suite Y = ( Y k ) k ≥ 1 {\displaystyle Y=(Y_{k})_{k\geq 1}} à valeurs dans S {\displaystyle S}  ;
  • ordonner la suite Y = ( Y k ) k ≥ 1 {\displaystyle Y=(Y_{k})_{k\geq 1}} dans l'ordre décroissant pour obtenir une suite décroissante X = ( X k ) k ≥ 1 {\displaystyle X=(X_{k})_{k\geq 1}} à valeurs dans S {\displaystyle S} .

Si les variables aléatoires réelles ( U k ) k ≥ 1 {\displaystyle (U_{k})_{k\geq 1}} sont indépendantes et suivent toutes la loi bêta de paramètre (1, θ), alors X = ( X k ) k ≥ 1 {\displaystyle X=(X_{k})_{k\geq 1}} suit la loi de Poisson-Dirichlet de paramètre (0, θ).

Nota. Y ( ω ) {\displaystyle Y(\omega )} appartient à S {\displaystyle S} si et seulement si

∑ i ≥ 1 U i ( ω ) = + ∞ {\displaystyle \sum _{i\geq 1}U_{i}(\omega )=+\infty } ,

ce qui se produit avec probabilité 1 dans le cas du processus de Poisson-Dirichlet. Les Y i ( ω ) {\displaystyle Y_{i}(\omega )} sont donnés par la formule explicite

Y i ( ω ) = U i ( ω ) ∏ 1 ≤ k ≤ i − 1 ( 1 − U k ( ω ) ) {\displaystyle Y_{i}(\omega )=U_{i}(\omega )\prod _{1\leq k\leq i-1}(1-U_{k}(\omega ))} ,

et les restes R i ( ω ) {\displaystyle R_{i}(\omega )} sont donnés par

R i ( ω ) = ∏ 1 ≤ k ≤ i ( 1 − U k ( ω ) ) {\displaystyle R_{i}(\omega )=\prod _{1\leq k\leq i}(1-U_{k}(\omega ))} .

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   X ( n ) ( ω ) = ( X k ( n ) ( ω ) ) k ≥ 1   {\displaystyle \ X^{(n)}(\omega )=\left(X_{k}^{(n)}(\omega )\right)_{k\geq 1}\ } 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     ω = ( 2 , 8 , 10 , 6 , 1 , 3 , 12 , 5 , 4 , 9 , 7 , 15 , 11 , 14 , 13 )   {\displaystyle \ \ \omega =(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13)\ } et   τ = ( 2 , 8 , 10 , 6 , 1 )   ( 3 )   ( 12 , 5 , 4 )   ( 9 , 7 )   ( 15 , 11 )   ( 14 , 13 ) , {\displaystyle \ \tau =(2,8,10,6,1)\ (3)\ (12,5,4)\ (9,7)\ (15,11)\ (14,13),} on a

X ( 15 ) ( ω ) = ( 1 3 ,   1 5 ,   2 15 ,   2 15 ,   2 15 ,   1 15 ,   0 ,   0 ,   0 ,   0 ,   … ) . {\displaystyle X^{(15)}(\omega )=\left({\frac {1}{3}},\ {\frac {1}{5}},\ {\frac {2}{15}},\ {\frac {2}{15}},\ {\frac {2}{15}},\ {\frac {1}{15}},\ 0,\ 0,\ 0,\ 0,\ \dots \right).}

Alors [2],[3]

Théorème —    ( X ( n ) ) n ≥ 1   {\displaystyle \ \left(X^{(n)}\right)_{n\geq 1}\ } est une suite de variables aléatoires à valeurs dans le simplexe   S   {\displaystyle \ S\ } , suite qui converge faiblement vers une distribution de Poisson-Dirichlet de paramètre (0,1) (i.e. les variables aléatoires réelles   ( U k ) k ≥ 1   {\displaystyle \ (U_{k})_{k\geq 1}\ } 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   m i   {\displaystyle \ m_{i}\ } (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.

Démonstration

Il est facile de voir que le nombre de suites ω de n nombres différents pris dans   [ [ 1 , n ] ]   {\displaystyle \ [\![1,n]\!]\ } et vérifiant   ω k = 1   {\displaystyle \ \omega _{k}=1\ } est (n-1)!. Donc la longueur, que nous noterons   n Y 1 ( n ) ( ω ) ,   {\displaystyle \ nY_{1}^{(n)}(\omega ),\ } du cycle contenant 1 dans la décomposition en cycles disjoints de   τ = R ( ω ) ,   {\displaystyle \ \tau =R(\omega ),\ } vérifie

∀ k ∈ [ [ 1 , n ] ] , P ( n Y 1 ( n ) = k ) = 1 n . {\displaystyle \forall k\in [\![1,n]\!],\qquad \mathbb {P} \left(nY_{1}^{(n)}=k\right)={\frac {1}{n}}.}

Or, si on pose

Y ^ 1 ( n )   =   ⌈ n U 1 ⌉ n , {\displaystyle {\widehat {Y}}_{1}^{(n)}\ =\ {\frac {\lceil nU_{1}\rceil }{n}},}

on constate que   Y 1 ( n )   {\displaystyle \ Y_{1}^{(n)}\ } et   Y ^ 1 ( n )   {\displaystyle \ {\widehat {Y}}_{1}^{(n)}\ } ont la même loi. Par ailleurs

U 1   ≤   Y ^ 1 ( n )   <   U 1   +   1 n . {\displaystyle U_{1}\ \leq \ {\widehat {Y}}_{1}^{(n)}\ <\ U_{1}\ +\ {\frac {1}{n}}.}

Comme la suite   ( Y ^ 1 ( n ) ) n ≥ 1   {\displaystyle \ \left({\widehat {Y}}_{1}^{(n)}\right)_{n\geq 1}\ } converge presque sûrement vers   U 1 ,   {\displaystyle \ U_{1},\ } on en déduit que la suite   ( Y 1 ( n ) ) n ≥ 1   {\displaystyle \ \left({Y}_{1}^{(n)}\right)_{n\geq 1}\ } converge en loi vers   U 1 .   {\displaystyle \ U_{1}.\ }

Examinons maintenant la longueur, que nous noterons   n Y 2 ( n ) ( ω ) ,   {\displaystyle \ nY_{2}^{(n)}(\omega ),\ } du cycle contenant   m 2   {\displaystyle \ m_{2}\ } dans la décomposition en cycles disjoints de   τ = R ( ω ) .   {\displaystyle \ \tau =R(\omega ).\ } On voit facilement que la loi conditionnelle de   n Y 2 ( n ) ,   {\displaystyle \ nY_{2}^{(n)},\ } sachant que   n Y 1 ( n ) = k ,   {\displaystyle \ nY_{1}^{(n)}=k,\ } est la loi uniforme sur   [ [ 1 , n − k ] ] :   {\displaystyle \ [\![1,n-k]\!]:\ } 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,   m 2 ,   {\displaystyle \ m_{2},\ } 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   n Y 2 ( n ) ,   {\displaystyle \ nY_{2}^{(n)},\ } sachant tout sur les k premiers termes de la suite, est la loi uniforme sur   [ [ 1 , n − k ] ] ,   {\displaystyle \ [\![1,n-k]\!],\ } 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   [ [ 1 , n − k ] ]   {\displaystyle \ [\![1,n-k]\!]\ } est donc aussi la loi conditionnelle de   n Y 2 ( n ) ,   {\displaystyle \ nY_{2}^{(n)},\ } sachant que   n Y 1 ( n ) = k .   {\displaystyle \ nY_{1}^{(n)}=k.\ }

Posons

Y ^ 2 ( n )   =   ⌈ n ( 1 − Y ^ 1 ( n ) ) U 2 ⌉ n . {\displaystyle {\widehat {Y}}_{2}^{(n)}\ =\ {\frac {\left\lceil n(1-{\widehat {Y}}_{1}^{(n)})U_{2}\right\rceil }{n}}.}

Alors les couples   ( Y 1 ( n ) , Y 2 ( n ) )   {\displaystyle \ (Y_{1}^{(n)},Y_{2}^{(n)})\ } et   ( Y ^ 1 ( n ) , Y ^ 2 ( n ) )   {\displaystyle \ ({\widehat {Y}}_{1}^{(n)},{\widehat {Y}}_{2}^{(n)})\ } ont même loi, mais le second couple converge presque sûrement vers   ( U 1 , ( 1 − U 1 ) U 2 ) = ( Y 1 , Y 2 ) .   {\displaystyle \ \left(U_{1},(1-U_{1})U_{2}\right)=(Y_{1},Y_{2}).\ } En effet :

( 1 − U 1 ) U 2   − U 2 n   ≤ Y ^ 2 ( n )   =   ⌈ ⌊ n ( 1 − U 1 ) ⌋ U 2 ⌉ n   ≤   ( 1 − U 1 ) U 2   + 1 n . {\displaystyle (1-U_{1})U_{2}\ -{\frac {U_{2}}{n}}\ \leq {\widehat {Y}}_{2}^{(n)}\ =\ {\frac {\left\lceil \lfloor n(1-U_{1})\rfloor U_{2}\right\rceil }{n}}\ \leq \ (1-U_{1})U_{2}\ +{\frac {1}{n}}.}

Donc le couple   ( Y 1 ( n ) , Y 2 ( n ) )   {\displaystyle \ (Y_{1}^{(n)},Y_{2}^{(n)})\ } converge en loi vers   ( Y 1 , Y 2 ) .   {\displaystyle \ (Y_{1},Y_{2}).\ } De manière un peu fastidieuse, mais sans grande difficulté, on obtiendra ainsi, pour tout k, la convergence en loi de   ( Y i ( n ) ) 1 ≤ i ≤ k   {\displaystyle \ (Y_{i}^{(n)})_{1\leq i\leq k}\ } vers   ( Y i ) 1 ≤ i ≤ k   {\displaystyle \ (Y_{i})_{1\leq i\leq k}\ } ; 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   Y ( n )   {\displaystyle \ Y^{(n)}\ } vers la suite   Y .   {\displaystyle \ Y.\ } 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   Y ( n ) ,   {\displaystyle \ Y^{(n)},\ } à savoir les suites   X ( n ) ,   {\displaystyle \ X^{(n)},\ } 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 :

R 0 ( n ) = n ,   R 1 ( n )   =   n − n Y 1 ( n ) ,   R 2 ( n )   =   n − n Y 1 ( n ) − n Y 2 ( n ) ,   R 3 ( n )   =   n − n Y 1 ( n ) − n Y 2 ( n ) − n Y 3 ( n ) ,   … {\displaystyle R_{0}^{(n)}=n,\ R_{1}^{(n)}\ =\ n-nY_{1}^{(n)},\ R_{2}^{(n)}\ =\ n-nY_{1}^{(n)}-nY_{2}^{(n)},\ R_{3}^{(n)}\ =\ n-nY_{1}^{(n)}-nY_{2}^{(n)}-nY_{3}^{(n)},\ \dots }


L'uniformité des suites résiduelles, remarquée un peu plus haut, entraîne que la loi conditionnelle de   R ℓ + 1 ( n ) {\displaystyle \ R_{\ell +1}^{(n)}} sachant que   ( R j ( n ) ) 1 ≤ j ≤ ℓ = ( r 1 , r 2 , … , r ℓ − 1 , k ) ,   {\displaystyle \ \left(R_{j}^{(n)}\right)_{1\leq j\leq \ell }=(r_{1},r_{2},\dots ,r_{\ell -1},k),\ } est la loi uniforme sur   [ [ 0 , k − 1 ] ]   {\displaystyle \ [\![0,k-1]\!]\ } (la position du minimum de la suite résiduelle, de longueur k, étant uniformément distribuée sur   [ [ 1 , k ] ] ,   {\displaystyle \ [\![1,k]\!],\ } il suit que le nombre de termes de la suite apparaissant après le minimum est uniformément distribué sur   [ [ 0 , k − 1 ] ] ) . {\displaystyle \ [\![0,k-1]\!]).} Cela fait de la suite   ( R j ( n ) ) j ≥ 0   {\displaystyle \ \left(R_{j}^{(n)}\right)_{j\geq 0}\ } une chaîne de Markov, partant de n, de noyau de transition très simple

p k , j   =   1 k   1   I 0 ≤ j < k , k , j ∈ N . {\displaystyle p_{k,j}\ =\ {\frac {1}{k}}\ 1\!\!\!\ {\text{I}}_{0\leq j<k},\qquad k,j\in \mathbb {N} .}

Or on peut engendrer une telle chaîne de Markov à l'aide d'une suite   ( U j ) j ≥ 1   {\displaystyle \ \left(U_{j}\right)_{j\geq 1}\ } de variables aléatoires indépendantes uniformes sur [0,1], via la relation de récurrence

R ^ j ( n )   =   ⌊ R ^ j − 1 ( n ) ( 1 − U j ) ⌋ , j ≥ 1 ,  et  R ^ 0 ( n )   =   n . {\displaystyle {\widehat {R}}_{j}^{(n)}\ =\ \left\lfloor {\widehat {R}}_{j-1}^{(n)}(1-U_{j})\right\rfloor ,\qquad j\geq 1,\qquad {\text{ et }}{\widehat {R}}_{0}^{(n)}\ =\ n.}

Posons

r j   =   ∏ k = 1 j ( 1 − U k ) , j ≥ 1 ,  et  r 0   =   1. {\displaystyle r_{j}\ =\ \prod _{k=1}^{j}(1-U_{k}),\qquad j\geq 1,\qquad {\text{ et }}r_{0}\ =\ 1.}

On montre facilement que

0   ≤   n r j − R ^ j ( n )   ≤   j , j ≥ 0 , {\displaystyle 0\ \leq \ nr_{j}-{\widehat {R}}_{j}^{(n)}\ \leq \ j,\qquad j\geq 0,}

donc la suite   ( R ^ j ( n ) / n ) j ≥ 1   {\displaystyle \ \left({\widehat {R}}_{j}^{(n)}/n\right)_{j\geq 1}\ } converge presque sûrement, terme à terme, vers la suite   r = ( r j ) j ≥ 1 .   {\displaystyle \ r=\left(r_{j}\right)_{j\geq 1}.\ } Par conséquent, la suite   ( R j ( n ) / n ) j ≥ 0   {\displaystyle \ \left(R_{j}^{(n)}/n\right)_{j\geq 0}\ } converge en loi vers la suite r. La suite des longueurs des cycles, tels qu'ils apparaissent dans la correspondance de Foata,   ( n Y j ( n ) ) j ≥ 1 ,   {\displaystyle \ \left(nY_{j}^{(n)}\right)_{j\geq 1},\ } est déduite de la suite des restes à l'aide de la relation

n Y j ( n )   =   R j − 1 ( n )   −   R j ( n ) , j ≥ 1. {\displaystyle nY_{j}^{(n)}\ =\ R_{j-1}^{(n)}\ -\ R_{j}^{(n)},\qquad j\geq 1.}

Ainsi la suite   ( Y j ( n ) ) j ≥ 1 ,   {\displaystyle \ \left(Y_{j}^{(n)}\right)_{j\geq 1},\ } converge en loi vers la suite   ( r j − 1 − r j ) j ≥ 1 ,   {\displaystyle \ \left(r_{j-1}-r_{j}\right)_{j\geq 1},\ } et par ailleurs

r j − 1 − r j   =   Y j , j ≥ 1. {\displaystyle r_{j-1}-r_{j}\ =\ Y_{j},\qquad j\geq 1.}

Notons que la loi de   X 1   {\displaystyle \ X_{1}\ } (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

  1. ↑ (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).
  2. ↑ (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.
  3. ↑ (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

Bijection de Joyal

  • icône décorative Portail des mathématiques