Grandes permutations aléatoires

Piste noire Le 24 décembre 2019  - Ecrit par  Pierre Tarrago Voir les commentaires

Les permutations permettent de décrire les différentes manières d’ordonner des objets. Quand le nombre d’objets est très grand et quand on choisit de les ordonner de manière aléatoire, des phénomènes apparaissent de manière visuelle. Cet article introduit le lecteur à ces phénomènes autour de deux exemples.

Bienvenue au Louxor !

Afin de faciliter la compréhension des concepts de cet article, nous considérerons dans la suite une histoire de spectateurs se rendant à une séance de cinéma. Supposons qu’il y ait $n$ personnes devant le cinéma, où $n$ est un entier plus grand que $1$. Afin de distinguer un spectateur d’un autre, il faut habituellement les nommer : au lieu de donner un prénom à chacun, ce qui deviendrait compliqué si $n$ devenait très grand, nous numérotons juste ces $n$ spectateurs de $1$ à $n$ suivant leur ordre d’arrivée au cinéma. Les spectateurs ayant acheté leur ticket à l’avance, ils ont également un numéro qui correspond au numéro d’achat de leur ticket : par exemple, le premier arrivé avait acheté le numéro $46$, puis le deuxième arrivé le numéro $23$, et ainsi de suite. Un aspect fondamental de ce processus est que chaque spectateur a un numéro de ticket différent de celui des autres spectateurs et, pour simplifier, nous dirons que tous les tickets ont été vendus (les numéros de tickets vont donc également de $1$ à $n$). À la fin de l’attribution des tickets, il en résulte une correspondance entre les nombres de $1$ à $n$ qui désignent le numéro de ticket des spectateurs et les nombres, également de $1$ à $n$, qui désignent leur ordre d’arrivée : cette correspondance est précisément ce qu’on appelle une permutation, que nous noterons généralement $\sigma$ dans la suite. En résumé et de manière plus abstraite, une permutation $\sigma$ de $n$ objets est l’attribution d’une étiquette $\sigma(i)$ comprise entre $1$ et $n$ à chaque nombre $i$, de manière à ce que chaque étiquette soit utilisée exactement une fois. La taille d’une permutation se définit alors comme le nombre d’objets permutés, c’est-à-dire $n$ dans cet encadré. À titre d’exemple, on peut considérer un petit cinéma où seulement cinq spectateurs arrivent : le premier dans la file a le ticket numéro $4$, le deuxième a le numéro $3$, le troisième le numéro $5$, le quatrième le numéro $1$ et enfin le cinquième le numéro $2$. En mathématiques, nous notons simplement
\[\sigma(1)=4, \sigma(2)=3,\sigma(3)=5,\sigma(4)=1, \sigma(5)=2.\]
La figure 1 ci-dessous décrit cette permutation de manière schématique en mettant une flèche allant d’un nombre à son étiquette.

Figure 1 : Exemple de permutation à cinq éléments.

Cet article va donner un aperçu du monde des permutations aléatoires et des phénomènes qui se produisent quand le nombre d’objets permutés est très grand.

Permutations aléatoires

On peut se demander combien il existe de permutations de $n$ objets ; autrement dit, si on appelle $S_{n}$ l’ensemble des permutations de $n$ objets, la question est de calculer le cardinal de $S_{n}$. La réponse peut être obtenue comme suit : pour définir une permutation, nous disposons de $n$ choix possibles pour l’étiquette $1$, puis seulement $n-1$ choix pour l’étiquette $2$ (puisqu’un nombre a déjà été utilisé pour l’étiquette $1$), etc., jusqu’à n’avoir plus que deux choix pour l’étiquette $n-1$ et un seul choix pour l’étiquette $n$. Le cardinal de $S_{n}$ est donc $n\times (n-1)\times ...\times 2\times 1$. Pour gagner de la place, nous appelons cette dernière quantité $n!$ («  factorielle $n$ »).
\[\text{Card}(S_{n})=n\times (n-1)\times ...\times 2\times 1=n!.\]
Il faut savoir que $n!$ est rapidement extrêmement grand. Ainsi, on a $4!=24$ mais déjà $60!$ est à peu près égal à $8\times 10^{80}$, soit le nombre approximatif d’atomes dans l’univers connu (voir [Wikipedia]). Cela pose un problème spécifique dans cet article, puisque le but est d’explorer des phénomènes particuliers qui apparaissent quand on considère de grandes permutations. Sachant qu’il faut considérer des permutations de taille 500 ou 1000 pour faire apparaître des comportements asymptotiques, il est exclu de les lister toutes. Un moyen de contourner ce problème est de considérer des permutations aléatoires, en espérant que cela dégage le comportement typique d’une permutation.

Cela pose toutefois plusieurs questions. La première est de savoir ce qu’on entend par permutation aléatoire. Nous ne connaissons rien des permutations pour l’instant, donc le plus sage est de tirer uniformément au hasard une permutation $\sigma$ parmi l’ensemble $S_n$ des permutations de taille $n$. La probabilité de tirer une permutation $\sigma_{0}$ est ainsi
\[\mathbb{P}(\sigma=\sigma_{0})=\frac{1}{\text{Card}(S_{n})}=\frac{1}{n!}.\]
Nous verrons à la fin de cette exposition qu’il existe d’autres manières de prendre une permutation au hasard, avec d’autres résultats intéressants à la clef.

La deuxième question est de savoir comment représenter une telle permutation aléatoire. La manière la plus simple est d’écrire une permutation $\sigma$ de $S_n$ comme une liste des éléments $1,\ldots,n$, telle que $\sigma(i)$ est en position $i$. Par exemple, la permutation $\sigma_{0}$ donnée en figure 1 est écrite $(4,3,5,1,2)$. Cette écriture est simple mais ne permet pas de voir grand-chose. Une deuxième solution est de construire un tableau carré à $n\times n$ cases (aussi appelé « matrice »), et de mettre un $1$ dans chaque case ayant pour colonne $i$ et pour ligne $\sigma(i)$, et des $0$ partout ailleurs. Ainsi la permutation donnée en figure 1 peut être représentée par le tableau en figure 2.

$\begin{pmatrix} 0&0&0&1&0\\ 0&0&0&0&1\\ 0&1&0&0&0\\ 1&0&0&0&0\\ 0&0&1&0&0\\ \end{pmatrix}$
Figure 2 : Représentation matricielle de la permutation définie en figure 1.

Dans la représentation précédente, il y a un seul $1$ dans chaque colonne, donc il y a $n$ cases remplies de $1$ pour $n^2$ cases au total. On peut voir les $1$ comme des particules sur un fond de $0$. Voici en image une permutation de taille $500$ tirée aléatoirement représentée sous forme matricielle (nous avons remplacé les $1$ par des points bleus, et omis les $0$).

Figure 3 : Permutation aléatoire de taille $500$ tirée uniformément, représentée sous forme matricielle.

On remarque que les points bleus sont à peu près uniformément répartis dans le carré. Ce résultat peut se démontrer rigoureusement, mais une manière intuitive de le voir est de réaliser qu’en chaque entier $i$, la permutation n’a aucune raison de prendre une valeur plutôt qu’une autre : il y a donc en chaque colonne $i$ un point dont le numéro de ligne prend n’importe quelle valeur avec même probabilité.

Nous allons voir dans la suite que changer notre manière de représenter une permutation ou de tirer une permutation au hasard fait apparaître de nouveaux phénomènes.

Algorithme de Robinson-Schensted-Knuth

Nous introduisons maintenant une manière plus originale de représenter une permutation. Cette représentation est obtenue comme résultat d’un algorithme appelé algorithme de Robinson-Schensted-Knuth (du nom des trois inventeurs de l’algorithme), ou plus simplement algorithme RSK. Le but de cet algorithme est d’enregistrer une permutation dans deux tableaux sans perdre d’information sur la permutation. Ce que nous entendons par tableau est un peu différent de l’usuel tableau de données : pour nous, un tableau à $n$ cases n’est pas forcément rectangulaire, mais le nombre de cases par ligne doit être décroissant en partant du haut. On les appelle alors des tableaux de Young, du nom de celui qui les a inventés.

Figure 4 : Deux exemples de tableaux de Young et un contre-exemple.
La salle est ouverte

Une idée de l’algorithme RSK peut être donnée en reprenant l’exemple de notre cinéma, et en considérant maintenant que les spectateurs rentrent dans la salle de projection. Ils remplissent la salle de places assises, et on suppose que l’intérêt des places est décroissant de haut en bas et de gauche à droite (l’écran est en haut à gauche de notre salle de cinéma). Le déroulement du remplissage de la salle est dicté par un principe fondamental : un client, ne voulant pas être moins bien placé qu’une autre personne ayant acheté son ticket plus tard, ne supporte pas d’être assis à droite d’un client au numéro de ticket supérieur. Cela donne le déroulement suivant.

  1. Quand le client $i$ arrive dans la salle avec le numéro de ticket $\sigma(i)$, il s’assoit dans la première rangée, sur le premier siège qui est soit vide soit occupé par un client $j$ au numéro de ticket $\sigma(j)$ supérieur au sien. Si le siège qu’il voulait prendre est occupé par un client précédent, ce dernier est éjecté dudit siège et part s’asseoir dans la rangée inférieure. Si le nouveau client avait le plus grand numéro de toute la rangée, il s’assoit tout au bout en occupant le premier siège vacant.
  2. Quand le client éjecté d’une rangée part s’asseoir dans la rangée directement inférieure, il reproduit exactement le schéma précédent dans la nouvelle rangée, et ainsi de suite.
  3. Une fois que tous les clients successivement éjectés lors de l’arrivée du client $i$ ont trouvé leur place, le client $i+1$ entre dans la salle, et le processus recommence.
  4. Le remplissage de la salle s’arrête quand tous les clients sont entrés dans la salle.

Dans le cas de la permutation en figure 1, nous avons donné en figure 5 ce que donnerait le remplissage de la salle. Notez que nous avons seulement représenté les étiquettes, puisque le numéro d’un client est sous-entendu par son ordre d’arrivée.

Figure 5 : Algorithme de remplissage du tableau $P$ à partir de la permutation $\sigma=(4,3,5,1,2)$ (Algorithme Robinson-Schensted-Knuth).

En réfléchissant à l’algorithme de remplissage, on peut voir que la forme que prend l’ensemble des sièges occupés est justement un tableau de Young. Si $\sigma$ est une permutation de taille $n$, on obtient donc à la fin un tableau $P$ à $n$ cases dont la forme peut être décrite par la longueur de ses rangées successives $(\lambda_{1}\geq \lambda_{2}\geq \ldots\geq\lambda_{r})$ et qui est rempli par les entiers de $1$ à $n$. Avec un peu plus d’effort, on peut montrer que le remplissage est strictement croissant vers la droite le long des lignes et vers le bas le long des colonnes : on dit que le tableau est standard.

Une question naturelle est de savoir si on peut retrouver la permutation $\sigma$ (c’est-à-dire l’ordre d’arrivée des clients) en observant le tableau $P$ : la réponse est non, avant tout parce qu’il y a beaucoup moins de tableaux standards de taille $n$ que de permutations. Une autre explication est qu’en arrivant dans la salle après le remplissage, on ne sait pas dans quel ordre les sièges ont été occupés. On ne voit qu’une salle de cinéma, avec certains sièges occupés par des personnes dont on peut juste vérifier le numéro de ticket. On peut remédier à cela en construisant un autre tableau $Q$, de la même forme que $P$, qui indique en chaque case le moment où elle est occupée pour la première fois par le processus de remplissage. Ce tableau est également standard. Dans notre exemple initial, le couple $(P,Q)$ de tableaux obtenus est le suivant :

On a donc transformé une permutation $\sigma$ en un couple de tableaux standards à $n$ cases de même forme $(P(\sigma),Q(\sigma))$. Le bon point est qu’on peut maintenant retrouver $\sigma$ à partir de $(P(\sigma),Q(\sigma))$ ! Il suffit de rembobiner l’algorithme sur le tableau $P$, puisqu’on sait quelle place est occupée à chaque moment grâce au tableau $Q$. Par exemple, dans l’exemple de la figure 5, on sait que le dernier siège à être occupé est celui qui contient le $5$, car c’est la case numérotée $5$ sur le tableau $Q$. On enlève donc le $5$ de sa case dans le tableau $P$ et on le met dans la rangée supérieure, à la place du plus grand numéro plus petit que lui (le $2$ dans notre cas). Puis on éjecte le $2$ : comme il était sur la première rangée, il sort du tableau et cela veut dire que le dernier élément de la permutation $\sigma$ était $2$ (ce qui est bien le cas). Puis on recommence avec la case du tableau $P$ qui est numérotée $4$ dans le tableau $Q$, etc.

Il y a en fait une correspondance exacte entre l’ensemble des permutations de taille $n$ et l’ensemble des couples de tableaux standards de taille $n$ de même forme (la forme des deux tableaux variant suivant la permutation). L’avantage est que sous cette nouvelle représentation, une permutation aléatoire de grande taille adopte une forme typique, comme on le voit en figure 6 où nous avons uniquement représenté le tableau $P$, le tableau $Q$ adoptant exactement la même forme.

Figure 6 : Tableau standard $P$ (retourné de 180°) associé à une permutation aléatoire de taille $10000$. Chaque pixel coloré correspond à une case du tableau, et la couleur du pixel indique la valeur de l’entier remplissant la case correspondante.

Le tableau $P$ qui apparait en figure 6 ne dépend presque plus de la permutation quand $n$ est grand, et sa forme limite a une expression que l’on sait écrire explicitement à l’aide des fonctions usuelles (racine carrée, ...). Nous voyons de plus que les courbes de niveaux qui représentent le remplissage du tableau sont des versions réduites de la courbe extérieure. Cette forme asymptotique traduit des comportements typiques de permutations de grande taille.
Par exemple, on peut montrer que la longueur de la première rangée $\lambda_{1}$ de $P(\sigma)$ est égale à la plus longue sous-suite croissante de la permutation $\sigma$ : c’est-à-dire le plus grand $k>0$ tel qu’il existe une suite $1\leq i_{1} < i_{2}< \ldots < i_{k}\leq n$ avec $\sigma(i_{1})<\sigma(i_{2})<\ldots<\sigma(i_{k})$ (voir le bloc déroulant ci-dessous pour une introduction plus détaillée). Dans l’exemple de la figure 6, on voit qu’après renormalisation par $\sqrt{n}=100$, la longueur de la première ligne est approximativement $2$. Ce phénomène est vrai en général et a été prouvé indépendamment par Vershik et Kerov [VK] et par Logan et Shepp [LS].

Sous-suites croissantes de permutation et tableaux de Young

Rappelons qu’une suite $u=(u_{k})_{1\leq k\leq n}$ (parfois $n$ est infini !) est une séquence ordonnée de nombres. On dit que la suite $u$ est croissante si pour tout $k$ entre $1$ et $n-1$, $u_{k}$ est plus grand que $u_{k-1}$. Par exemple, la suite $(2,5,13,24)$ est croissante alors que la suite $(3,5,16,5,2,17)$ ne l’est pas.

Une sous-suite d’une suite $u$ désigne n’importe quelle suite que l’on peut obtenir à partir de $u$ en supprimant certains nombres, tout en gardant le même ordre. Ainsi, $(2,13,24)$ est une sous-suite de $(2,5,13,24)$. Dans le paragraphe ci-dessus, nous nous intéressons à la plus longue sous-suite croissante d’une permutation. Cela veut dire qu’on considère une permutation $\sigma$ de taille $n$ comme une suite en l’écrivant $\left(\sigma(1),\ldots,\sigma(n)\right)$. Ainsi, la permutation $(4,3,5,1,2)$ donnée en exemple en figure 1 a comme sous-suites croissantes (en oubliant celles triviales de longueur $1$)
\[(4,5), (3,5), (1,2).\]
La longueur de sa plus longue sous-suite croissante est donc $2$, et il y a en fait trois « plus longues sous-suites croissantes différentes » de cette longueur. On vérifie bien que c’est exactement la longueur de la première ligne du tableau $P(\sigma)$ obtenu en figure 5.

Ce phénomène est vrai en général. On peut esquisser une preuve de ce phénomène, qui est due à Schensted : il faut remarquer que si on fixe une case $r$ de la première ligne du tableau $P(\sigma)$ et on regarde la suite $(v^r_{1},v_{2}^r,\ldots)$ des entiers insérés dans cette case lors de l’insertion RSK, on obtient une sous-suite $v^r$ de $\sigma$ qui est décroissante. Si $l$ est la longueur de la première ligne de $P(\sigma)$, on a donc $l$ sous-suites décroissantes $v^1,\ldots,v^l$ de $\sigma$ qui sont disjointes (ce qui veut dire qu’aucun des entiers qui apparaissent dans une sous-suite ne peut apparaître dans une autre). De plus, chaque entier compris entre $1$ et $n$ appartient à une de ces sous-suites, puisqu’il est inséré dans le tableau à une certaine case de la première ligne. Considérons maintenant une sous-suite $u=(\sigma(i_1),\ldots,\sigma(i_{l+1})$ de $\sigma$ de longueur $l+1$ : par le principe des tiroirs, il existe donc deux éléments $\sigma(i_j)$ et $\sigma(i_j')$ de la sous-suite, avec $ j < j ' $, qui appartiennent à une même sous-suite décroissante parmi les sous-suites $v^1,\ldots,v^l$. On a donc $\sigma(i_j)>\sigma(i_{j'})$, et $u$ n’est pas croissante. On en déduit que toute sous-suite décroissante a une longueur au plus $l$.

Il suffit donc de trouver une sous-suite de longueur exactement $l$ pour prouver le résultat. Pour cela, il faut prendre la sous-suite des entiers qui occupent pour la première fois chaque case de la première ligne. Cette sous-suite est croissante par définition de l’algorithme, et est de taille exactement $l$. Dans l’exemple en figure 1, cette suite est $(4,5)$.

Tableaux standards en escalier et permutations aléatoires

Nous avons vu dans la section précédente que passer d’une visualisation matricielle à une visualisation sous forme de tableaux faisait apparaître des phénomènes intéressants dans le cas d’une permutation tirée uniformément au hasard. Inversement, nous allons voir maintenant que changer la manière de choisir une permutation aléatoire produit des comportements intéressants sous visualisation matricielle.

De manière étonnante, la nouvelle manière de tirer une permutation aléatoire fait encore appel à un tableau standard. Nous allons considérer des tableaux standards en escalier : la première rangée a $n-1$ cases, la suivante $n-2$ et ainsi de suite. On peut montrer qu’un tel tableau a $m=\frac{n(n-1)}{2}$ cases : en effet, si on juxtapose un tel diagramme avec un autre tourné de 180 degrés (voir la figure 7), on obtient un diagramme rectangulaire de $n\times (n-1)$ cases.

Parmi ces cases, il y en a de particulières qui sont les « marches » de l’escalier. Numérotons-les de $1$ à $n-1$ de bas en haut. Pour $n=4$, nous obtenons par exemple le tableau standard en escalier suivant (mais il y a autant de possibilités que de tableaux standards de la même forme).

Figure 7 : Exemple de tableau standard en escalier pour $n=4$ et figure de la preuve de l’identité $m=n(n-1)/2$.

Nous allons construire un mot de taille $m$ à partir d’un tableau standard $T$ en escalier de taille $m$ en retirant les entiers un à un en suivant la règle dite d’évacuation, qui est décrite dans l’encadré suivant.

Un jeu de chaises musicales

Reprenons encore une fois notre salle de cinéma, en supposant que maintenant le film est terminé et l’évacuation de la salle va avoir lieu. La sortie est en bas à droite et, cette fois, la règle d’évacuation est que la personne ayant le numéro le plus élevé part en premier. De plus, à chaque fois qu’un spectateur part, un mouvement de foule rapide se produit : les spectateurs étant toujours pressés, ils cherchent à occuper une chaise adjacente dès qu’elle se libère, afin de se rapprocher de la sortie. Mais encore une fois la même règle précédente s’applique : seul celui des voisins qui a le numéro le plus élevé à le droit d’occuper la chaise qui vient d’être vacante. Ainsi dans l’exemple de la figure 7, le numéro $6$ part, puis immédiatement le $3$ prend sa place et le $1$ prend la place du $3$. Puis le numéro $5$ part, et immédiatement le $2$ prend sa place (le $1$ n’est plus adjacent au $2$ car il a prit la place du $3$ à l’étape précédente). Une fois ce mouvement terminé, celui qui a le plus grand numéro part et ainsi de suite. L’évacuation du tableau de la figure 7 est donnée en figure 8.

Dans le cas de nos tableaux en escalier, il est important d’enregistrer la position de chaque entier au moment où il est évacué. Cela donne l’algorithme d’évacuation suivant :

  1. On regarde la case qui contient la plus grande étiquette (qui doit être $m=n(n-1)/2$). Comme le tableau est standard, cette étiquette doit être sur un bord du tableau (une marche de l’escalier). On repère le numéro de la marche, que l’on nomme $i_{1}$, puis on efface l’étiquette, en opérant ensuite le jeu de chaises musicales décrit dans l’encadré précédent.
  2. On regarde la case qui contient la plus grande étiquette après l’évacuation de $m$, on repère le numéro de la marche que l’on nomme $i_{2}$, puis on efface l’étiquette. On applique le jeu de chaises musicales puis on recommence pour obtenir les symboles $i_{3},\ldots, i_{m}$.

A la fin, nous avons obtenu un mot $w(T)=i_{1}\ldots i_{m}$ en les entiers $1$ à $n-1$. Un exemple du processus d’évacuation pour le tableau standard en escalier donné en figure 7 est donné en figure 8.

Figure 8 : Tableau standard en escalier pour $n=4$ et processus d’évacuation donnant le mot $231231$

Grâce à ce mot, nous allons créer une suite de $m$ permutations $(\sigma_{0},\ldots, \sigma_{m})$ qui commence en l’identité $\sigma_{0}=(1,2,\ldots,(n-1),n)$ et qui termine en la permutation $\sigma_{m}=(n,n-1,\ldots,2,1)$. On lit le mot $w(T)$ de gauche à droite, et à chaque lettre $i_{t}$ on crée une nouvelle permutation $\sigma_{t}$ à partir de $\sigma_{t-1}$ en échangeant les étiquettes $\sigma_{t-1}(i_{t})$ et $\sigma_{t-1}(i_{t}+1)$. Dans l’exemple de la figure 8 qui donne le mot $w(T)=231231$, cela donne la suite de permutations
\[(1234)\xrightarrow[2]{}(1324)\xrightarrow[3]{}(1342)\xrightarrow[1]{}(3142)\xrightarrow[2]{}(3412)\xrightarrow[3]{}(3421)\xrightarrow[1]{}(4321).\]

Si $T$ a été tiré uniformément parmi les tableaux en escalier standards de taille $m$, la suite que l’on obtient avec notre algorithme est également aléatoire. De manière surprenante, quand on représente la suite de permutations sous leur forme matricielle et quand $n$ est grand, on obtient une évolution quasiment déterministe de la suite d’images en fonction de $t$. De plus, même sous forme de mot d’intéressants phénomènes apparaissent : si on fixe un entier $i$, la suite $(\sigma_{t}(i))_{1\leq t\leq m}$ suit une évolution sinusoïdale de période $\pi/(2m)$.

Figure 9 : Évolution de la permutation $\sigma_{t}$ pour $t=0,m/4,m/2,3m/4,m$ pour $n=500$ et évolution de la suite $(\sigma_{t}(i))_{1\leq t\leq m}$ pour $i=\lfloor \frac{k\cdot n}{16}\rfloor$, $k=1,\ldots, 15$.

Ces phénomènes mystérieux ont été découverts en 2006 par Angel, Holroyd, Romik et Virag [AHRV] et n’ont été rigoureusement prouvés que très récemment par Dauvergne et Virag [Dau, DV]. Ces deux derniers auteurs ont expliqué l’évolution sinusoïdale de chaque suite $(\sigma_{t}(i))_{1\leq t\leq m}$ et ils ont montré que sous représentation matricielle, $\sigma_{t}$ s’inscrit dans une ellipse dont le rapport entre le petit axe et le grand axe est $\sqrt{\frac{1-\cos(t\pi/m)}{1+\cos(t\pi/m)}}$. Leur résultat est en fait plus précis, puisqu’ils ont montré que la distribution des points bleus dans la figure 9 (pour $t=m/2$ par exemple) est approximativement la même que celle d’un nuage de $n$ points tirés uniformément sur une sphère, puis projetés sur le plan horizontal à l’équateur (voir la figure 10). Il est à noter que la répartition des points semble beaucoup plus uniforme dans le cas de la permutation $\sigma_{m/2}$ que dans le cas de la projection des points tirés au hasard sur la sphère. Ce phénomène de répulsion, assez courant dans l’étude de grands objets aléatoires issus de structures algébriques, n’est pas encore élucidé dans ce cas précis.

Figure 10 : Ensemble de $n$ points tirés aléatoirement uniformément sur la sphère de rayon 1, puis projetés sur le plan équateur horizontal. Permutation $\sigma_{t}$ pour $t=m/2$ (dans les deux cas, $n=500$).

Bibliographie

[AHRV] Angel, O., Holroyd, A. E., Romik, D. and Virág, B. (2007). Random sorting networks, Advances in Mathematics, 215(2), 839-868.

[Dau] Dauvergne, D. (2018). The Archimedean limit of random sorting networks. arXiv preprint arXiv:1802.08934.

[DV] Dauvergne, D. and Virág, B. (2018). Circular support in random sorting networks. arXiv preprint arXiv:1802.08933.

[VK] Vershik, A. M. and Kerov, S. V. E. (1977). Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux, Doklady Akademii Nauk, Vol. 233, No. 6, pp. 1024-1027.

[LS] Logan, B. F. and Shepp, L. A. (1982). A variational problem for random Young tableaux, Young Tableaux in Combinatorics, Invariant Theory, and Algebra, pp. 63-79.

[Wikipedia] Wikipedia

Post-scriptum :

Je remercie Mathilde Herblot, P.Levallois et Michele Triestino pour leur lecture d’une version préliminaire de cet article et pour leurs commentaires utiles. Je remercie également l’équipe d’Image des Maths pour le suivi de la rédaction (Clément Caubel, Pierre-Antoine Guihéneuf et Maï Sauvageot).

Article édité par Pierre-Antoine Guihéneuf

Partager cet article

Pour citer cet article :

Pierre Tarrago — «Grandes permutations aléatoires» — Images des Mathématiques, CNRS, 2019

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?