À la conquête du nord-est

La plus longue sous-suite croissante d’une permutation aléatoire

Piste bleue 28 juillet 2014  - Ecrit par  Xavier Caruso Voir les commentaires (2)

Un samedi après-midi par mois environ (hors vacances scolaires), le séminaire Mathematic Park se réunit à l’IHP et propose, à un public d’étudiants, de professeurs et de passionnés de mathématiques, un exposé d’une heure et demie sur des thèmes variés. C’est ainsi que le 9 novembre 2013, Valentin Feray est venu nous parler de la longueur de la plus longue sous-suite d’une permutation aléatoire. Quelques explications ci-dessous.

Sur le carré dessiné ci-dessous, nous avons placé au hasard 50 points — qui peuvent par exemple représenter des villes sur une carte — et relié certains d’entre eux (marqués en rouge) de façon à ce que le chemin obtenu se dirige toujours vers le nord-est.

PNG

Le chemin que nous avons tracé relie 9 villes. Aurait-on pu trouver un autre chemin qui en relie davantage ? Il se trouve que non, comme on peut s’en convaincre après une longue recherche exhaustive (qu’il est préférable de confier à un ordinateur) [1].

Bien sûr, si les points avaient été disposés de manière différente, il aurait été possible de trouver un chemin passant par plus de villes : voyez, par exemple, le carré représenté ci-dessous où on a pu exhiber un parcours en reliant 14 !

PNG

Quelques statistiques

Nous pouvons maintenant tenter et retenter l’expérience un grand nombre de fois et faire des statistiques. Voici un diagramme en bâtons qui indique combien de fois chaque « nombre maximal de villes visitées par un chemin nord-est » a été obtenu pour un total de 1000 expériences.

PNG

Nous constatons que ce nombre reste concentré autour de sa valeur moyenne qui est entre 11 et 12. Ce diagramme nous apprend encore plus précisément qu’il serait très étonnant d’obtenir, de façon aléatoire, une configuration pour laquelle le plus long chemin nord-est passe par un nombre de villes qui n’est pas compris entre 9 et 14. Notez bien cependant que cela n’est pas impossible : il se peut même, à vrai dire, qu’il existe un chemin nord-est passant par toutes les villes dans le cas où celles-ci seraient alignées sur la diagonale sud-ouest / nord-est du carré. De même, il ne pourrait exister aucun chemin nord-est reliant deux villes si toutes les villes étaient alignés sur l’autre diagonale. De telles configurations sont toutefois extrêmement peu probables.

Sur la dépendance par rapport au nombre de villes

Que se passe-t-il à présent si nous ne partons pas de 50 villes, mais de 100 ou encore davantage ? Bien entendu, il sera alors logiquement possible de trouver un chemin « nord-est » passant par plus de villes. Mais dans quelles proportions cette augmentation aura-t-elle lieu ? Voici un tableau qui fait apparaître la moyenne de nombre maximal de villes visitées par un chemin nord-est en fonction du nombre de villes total.

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Nombre de villes} & 100 & 200 & 300 & 400 & 500 & 600 & 700 & 800 & 900 \\ \hline \begin{array}{c}\text{Nombre maximal de villes} \\ \text{visitées par un chemin nord-est}\end{array} & 16,\!7 & 24,\!5 & 30,\!6 & 35,\!7 & 40,\!3 & 44,\!2 & 48,\!2 & 51,\!8 & 55,\!0 \\ \hline \end{array}\]

Nous remarquons que, certes, la deuxième ligne croît en même temps que la première mais elle le fait à une allure moindre. Lorsque l’on passe par exemple de 200 à 800 villes, le nombre de villes est multiplié par 4 alors que le nombre correspondant sur la seconde ligne du tableau est seulement multiplié par 2 environ. De même, lorsque l’on passe de 100 à 900 villes, le nombre de villes est multiplé par 9 et celui de la seconde ligne par 3 environ.

En fait, il se trouve qu’en moyenne, le nombre maximal de villes visitées par un chemin nord-est varie proportionnellement non pas au nombre de villes mais à sa racine carrée ! Ceci est cohérent avec les observations qui ont été faites : en effet, la racine carrée de 4 (qui est le facteur multiplicatif lorsqu’on passe de 200 à 800 villes) est 2 (qui est le facteur multiplicatif correspondant sur la seconde ligne du tableau) et, de même, celle de 9 est 3. Par ailleurs, remarquons que ce comportement n’est en réalité pas surprenant car, comme on le voit sur la vignette de cet article, lorsque le nombre de villes est grand, un chemin nord-est optimal aura tendance à suivre la diagonale autour de laquelle se trouve un nombre de villes proportionnel à la racine carrée du nombre total de villes (la diagonale est de dimension 1, alors que le carré lui-même est de dimension 2).

L’exposé de Valentin Feray

Dans son exposé au séminaire Mathematic Park, Valentin Feray aborde ces questions et donne plusieurs éléments qui mettent en avant la dépendance en la racine carrée que nous venons d’évoquer. Attention, dans son exposé, Valentin adopte une présentation différente du problème (tri d’un jeu de cartes) et n’explique le rapport avec « le plus long chemin nord-est » qu’après une heure d’exposé environ. Mais, ne vous inquiétez pas, il traite bien, dès le début, la même question.

Visionnez-le ci-dessous. Attention, certains passages de cet exposé sont classés hors-piste.

Post-scriptum :

Je remercie Valentin Feray, d’une part, pour son exposé et, d’autre part, pour avoir relu et corrigé une version préliminaire de cet article.

Je remercie également vivement, pour leur relecture rapide et efficace, antoine.levitt, juju17 et fpiou.

Article édité par Xavier Caruso

Notes

[1En réalité, on peut être plus malin en parcourant les villes de bas en haut et en construisant de proche en proche des chemins nord-est « maximaux » reliant le coin sud-ouest à chacune des villes. Cette méthode permet de trouver le chemin optimal en effectuant environ $50 \times 50 = 2500$ « calculs » élémentaires alors qu’une recherche exhaustive vraiment naïve demande de tester, au bas mot, plusieurs millards de possibilités.

Partager cet article

Pour citer cet article :

Xavier Caruso — «À la conquête du nord-est» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

  • À la conquête du nord-est

    le 29 juillet 2014 à 13:55, par ThePolyscope

    Merci pour cet article illustré très intéressant.

    Pour poursuivre l’analogie géométrique et aller plus loin que la dépendance à la racine carré, si l’on considère que les N villes approximent la surface S du carré (de diagonale sqrt(2*S)), et qu’un chemin « nord-est optimal aura tendance à suivre la diagonale », est-il juste de dire pour un grand nombre de tirages à N fixé que la limite de cette moyenne vaut sqrt(2*N) ?

    Votre tableau surestime systématiquement cette relation, ce qui laisse à penser qu’elle est fausse. Qu’es ce qui met en défaut cette analogie géométrique ?

    Merci !

    Répondre à ce message
    • À la conquête du nord-est

      le 31 juillet 2014 à 13:02, par Xavier Caruso

      Non, l’équivalent exact est $2 \sqrt N$ et non pas $\sqrt{2N}$. Trouver la bonne constante devant $\sqrt N$ revient en gros à estimer la déviation à la diagonale du « chemin optimal » ; c’est un problème nettement plus difficile.

      Répondre à ce message

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é ?

Suivre IDM