Category: Geekery

Un petit article pour réagir à l’actualité très récente de ces derniers jours, c’est à dire la mort de Johnny Hallyday ; si vous n’êtes pas au courant, c’est que vous vivez dans une grotte (voir ici par exemple). Cet immense chanteur a fait une très grande carrière et fait partie du patrimoine musical français. Depuis son décès, les radios et les chaînes de télévision diffusent plus ou moins en boucle ses titres, en hommage. C’est d’ailleurs ce qui nous amène à la question du jour : combien de temps cela prendrait à diffuser la totalité de l’oeuvre de Johnny à la radio ?

Pour répondre à cette question, nous allons utiliser l’article Wikipedia sur sa discographie, très bien fourni. Il faut évidemment se limiter à un certain nombre d’albums : on va choisir les albums studios, en excluant ceux faits exclusivement pour l’étranger, qui ne seraient pas diffusés sur une radio française. Le jeu de données est disponible ici, si vous souhaitez l’utiliser.

Le résultat, sans plus attendre, est que la cinquantaine d’albums studio de Johnny demanderait 36 heures, 2 minutes et 22 secondes à être diffusée ! Soit, en sachant que sa mort a eu lieu aux environs de 2h du matin le mercredi 6 décembre 2017, cela veut dire que si une radio l’avait appris directement, elle aurait pu diffuser en boucle sans jamais se répéter des titres du chanteur jusqu’à jeudi 7 à 14h. Et encore, on ne compte pas les albums live !

On peut également utiliser ce jeu de données pour regarder la durée moyenne des chansons. Plusieurs études ont montré que la longueur des chansons a évolué dans les dernières décennies, avec un minimum dans les années 60 et un maximum dans les années 90. Un graphe animé est disponible ici :

On peut faire le même graphe pour les chansons de notre idole des jeunes, et on se rend compte que l’on retrouve quasiment la même courbe ! Il était donc bien un reflet de son époque.

Et enfin, est-ce que vous saviez que Johnny et Pasteur étaient morts dans la même ville ? Peut-être une idée pour un prochain article, d’ailleurs…

En France, la tradition veut que l’on décore les parcs, rond-points et les rues des villes et des villages avec des fleurs. Une autre tradition très française est le concours et la notation, et ce domaine n’y a pas échappé. En effet, le Conseil national des Villes et Villages Fleuris décerne régulièrement des “fleurs” aux différentes communes françaises, suivant la qualité de leurs décorations et de leurs jardins. Ce site donne la liste des villes récompensées. Or, ici, nous aimons beaucoup les données relatives aux villes de France : voir par exemple ici ou ici. Quels sont les déterminants d’une “fleur” ? Comment faire pour en obtenir plus ? Essayons de voir ce que la statistique peut nous apprendre sur le sujet.

Premiers résultats

Nous allons mobiliser d’autres informations sur les communes :

• Le nombre d’habitants
• Le nombre d’hôtels présents sur la commune (disponible ici)
• Le nombre de lits présents dans la commune (disponible au même endroit que précédemment)
• Le vote politique au second tour de la présidentielle 2012 (disponible ici sur data.gouv)

On récupère donc les informations présentes sur le site des Villes et Villages Fleuris pour connaître le nombre de fleurs associé à chaque ville. C’est 0 pour les villes qui ne sont pas dans la liste du site, et de 1 à 4 pour les autres. Nous allons ensuite réaliser une régression linéaire sur cette variable à partir des autres informations. Le choix de la régression linéaire a été fait car le caractère ordonné, c’est à dire que 2 fleurs soient supérieures à une seule, est important dans ce contexte. Les résultats obtenus sont les suivants :

On voit ainsi que la population, le nombre d’hôtels et le pourcentage de personnes qui ont voté pour Nicolas Sarkozy, le candidat de la droite à l’élection présidentielle en 2012, impliquent un nombre plus important de “fleurs” sur le classement de l’association. On peut en déduire que les villages qui ont tendance à accueillir des touristes décorent plus leurs jardins. Plus marginalement, les villes plus peuplées ou plus conservatrices obtiennent plus de fleurs. Ce résultat nous rappelle les résultats liés aux noms des rues, par exemple la Rue des Fleurs qui est plus marquée à droite.

Répartition géographique

Une autre question qu’on peut se poser est celle de la répartition géographique de ces communes. On peut s’intéresser à leur répartition par département ou par région, mais nous allons plutôt nous intéresser à une autre question, celle de l’autocorrélation spatiale. L’idée est d’étudier l’influence du voisinage entre deux communes : vont-elles avoir le même score en termes de “fleurs” ? Ou est-ce que ces communes sont réparties un peu aléatoirement sur le territoire ? (voir par exemple ici, pour plus d’informations).

Regardons par exemple la carte de Provence-Alpes-Côte d’Azur :

Sur cette carte, les villes et les villages sont en vert lorsqu’ils ont été récompensés, avec une teinte de plus en plus marquée lorsqu’ils ont plusieurs “fleurs”. On remarque que des groupes de communes, par exemple autour de Marseille ou d’Antibes, ont toutes eu des fleurs. Cela pourrait être un effet d’entraînement, par exemple des maires voisins connaissent mieux ce système lorsque leur voisin y a participé.

Avancé – Cette hypothèse peut se vérifier mathématiquement : on peut calculer des indicateurs de “corrélation spatiale”, et donc de regroupements de valeurs similaires, comme par exemple l’Indice de Moran. On trouve un résultat strictement positif, ce qui s’interprète bien de cette façon là.

En France comme dans la plupart des pays du monde, nous avons suivi avec attention l’élection du 45ème président des États-Unis, Donald Trump (si vous n’étiez pas au courant, il est temps de sortir de votre grotte !). Cela a été l’occasion de mieux connaître le système électoral américain, et de réviser sa géographie des états américains : quels états sont démocrates ? Où se situe vraiment le Wisconsin ? Comment fonctionne le système de grands électeurs ?

Il faut dire que pour nous, français, le système est très éloigné de notre élection présidentielle. Certes, les primaires des différents partis sont un phénomène qui tend à se développer en France, mais nous restons attachés à l’élection directe du président, marqueur politique important de la Ve République. Cependant, cela n’empêche pas de réfléchir à d’autres systèmes de vote (l’article wikipedia est d’excellente qualité, et je ne développerai pas le sujet ici, mais peut-être dans un prochain article !). Par exemple, serait-il possible de transposer le système américain des grands électeurs par état à la France ?

Un bref rappel du système américain

Si vous êtes experts en politique américaine, ou si avez suivi le Monde ces derniers mois, vous pouvez sauter cette partie ! Sinon, profitons en pour faire un bref rappel de ce qu’il faut savoir sur le système politique américain pour l’adapter à la France. Les États-Unis, comme leur nom l’indique, sont découpés en 50 états qui ont chacun un gouvernement, des lois et des réglementations propres. Un système politique et administratif fédéral complète ce dispositif, pour les sujets tels que les relations internationales sur lesquels le pays ne doit porter qu’une seule voie. Le président des États-Unis, actuellement Barack Obama, dispose du pouvoir exécutif au niveau fédéral. Il existe de nombreux contre-pouvoirs au POTUS, principalement au niveau des chambres de représentants, bien plus qu’en France.

Le président est élu au suffrage universel indirect. Chaque état vote pour élire ses représentant au collège des grands électeurs, qui votent ensuite pour élire le président. Les règles d’élection des grands électeurs au sein de chaque état peuvent varier, mais globalement, elles respectent la règle dite du “winner takes all” : le parti ou les candidats qui ont la majorité des votes de l’état remportent la totalité des sièges mis en jeu. Ce système est à l’opposé des systèmes dits proportionnels. En France, les législatives reprennent un peu ce système, sauf qu’un seul siège est mis en jeu dans chaque circonscription ; les débats autour de l’introduction d’une “dose de proportionnelle” sont fréquents à ce sujet.

Le nombre de sièges attribué à chaque état correspond globalement à sa population, hormis que les états les moins peuplés sont favorisés par rapport aux grands états. Par exemple, la Californie a 55 grands électeurs pour 38,8 millions d’habitants, tandis que le Wyoming en a 3 pour 500 000 habitants, soit cinq à six fois plus de sièges par habitant. Nous discutions déjà de ce point dans l’article précédent (en). Il y a en tout 538 grands électeurs à pourvoir ; les projections les plus fiables en donnent 306 à Donald Trump pour l’élection de 2016.

Adaptation au système français

Nous allons essayer d’adapter le système de collège électoral de grands électeurs à la France. Pour cela, nous allons nous intéresser aux seconds tours des élections présidentielles (pour coller au plus près du système bi-partisan des États-Unis), en excluant ceux atypiques (1969 et 2002), en se limitant à la France métropolitaine (dans une optique de simplification, les modalités de vote dans les DOM et pour les français à l’étranger évoluant beaucoup). Les données sont disponibles sur data.gouv pour la période 1965 – 2002.

On va réaliser le découpage au niveau départemental de la France, en considérant qu’un département correspond à un état américain (hormis pour la Corse, qu’on regroupe en un seul département pour des questions de comparabilité). Nous avons donc 95 “états” français, et chacun d’entre eux doit se voir attribuer un nombre de sièges dans notre collège de grands électeurs fictif. Pour cela, nous allons répliquer la méthodologie américaine, et répartir 538 sièges en favorisant les départements les moins peuplés. Nous obtenons alors 3 grands électeurs dans la Creuse et la Lozère, et jusqu’à 13 grands électeurs dans le Nord.

On calcule ensuite pour chaque élection quel parti sort vainqueur du vote au niveau de chacun des départements ; les grands électeurs associés lui sont alors attribués. Une fois ce processus effectué pour tous les départements, nous avons une idée de la composition du collège électoral, et ainsi du nom du président qui aurait été élu via ce dispositif. Voici les résultats obtenus :

On remarque que ce système fictif conduit tout de même à l’élection du même président pour les sept échéances électorales considérées que ce qui s’est réellement passé. Les écarts de composition du collège électoral sont plus intéressants : le plus grand est en 1988, avec 425 des 638 grands électeurs acquis à la gauche (et François Mitterrand avait largement gagné, avec 54,02 % des voix), et le plus faible est en 1974 (et effectivement l’écart était très faible). Le système semble donc fiable.

Les “swing” départements

Aux États-Unis, l’élection se joue souvent sur un petit nombre d’états, appelés swing states ou états pivots. En effet, une grande partie des états sont acquis dès le début par un parti, qui y réalise d’excellents scores, et il n’y a donc pas d’intérêt stratégique pour le candidat du parti adversaire à faire campagne là-bas (par exemple, la Californie est démocrate). Ce sont les états fortement en bleu ou en rouge dans le modèle de prédiction de FiveThirtyEight (en) (on ne reviendra pas sur le candidat qui avait le plus de chances de l’emporter, surtout que leur modèle de prédiction était largement meilleur que celui des autres médias américains).

On peut se poser la même question en France : si l’on adoptait le sytème américain, y aurait-il des fiefs acquis à la droite et à la gauche ? quels seraient les départements pivots ? La question est assez complexe, mais nous allons tenter de donner quelques éléments de réponse. Tout d’abord, le gif suivant montre l’évolution des votes par département depuis 1974 :

C’est assez difficile à lire, mais on peut en tirer plusieurs enseignements :

• Il semblerait que le vote soit moins hétérogène entre les départements français qu’aux États-Unis, car l’évolution est plus globale quand la majorité est renversée.
• On remarque néanmoins que certains fiefs électoraux se dessinent avec par exemple le sud-ouest de la France pour la gauche, et un arc ouest/sud-est de la Bretagne à Nice en passant par Paris pour la droite.

Pour étudier plus précisément ce second point, nous allons regarder quelques autres indicateurs. Tout d’abord, les deux cartes suivantes indiquent les départements avec lesquels chaque parti a toujours gagné, c’est à dire que, pour la droite, ils ont remporté ces départements en 65, 74, 95 et 2007, et pour la gauche en 81, 88 et 2012. On retrouve les fiefs évoqués précédemment.

On peut faire plus largement une typologie des départements en comptant combien de fois ils ont voté à droite ou à gauche lors de ces dernières élections. Les départements en bleu ont bien plus fréquemment voté majoritairement à droite qu’à gauche, ceux en rose pour la gauche, et ceux en gris n’ont pas un comportement partisan qui se dégage clairement des sept élections considérées.

Ce sont ces département en gris, les plus indécis, qui sont les plus proches conceptuellement des swing states américains ! En termes de grands électeurs :

• 213 grands électeurs sont “acquis” à la droite ;
• 182 sont “acquis” à la gauche ;
• les 147 restants sont indécis.

Parmi les départements pivot les plus peuplés, on retrouve les Bouches-du-Rhône, qui seraient un peu notre Floride à nous. Qui sait, peut-être que les candidats français seraient tous obligés dans ce système de concourir avec un vice-président (ou premier ministre) qui aurait l’accent du sud ? Je ne sais pas si les campagnes électorales gagneraient en crédibilité.

Si vous voulez utiliser les données : https://nc233.com/wp-content/uploads/2016/11/FranceAmericanSystem.csv

Today I found via FiveThirtyEight a riddle about arithmetic progressions: it’s called “Dodging 9s”. The question is to find the longest arithmetic progression (which means a collection of numbers in which each number is equal to the precedent plus some constant number (called the common difference), for instance 4 7 10 13 16) in which there is no 9 in any number. The repartition of the integers which contain a 9 is shown in the following figure, where the first row is 1 to 100, the second 101 to 200 and the last 9 901 to 10 000.

This repartition leads me to think that the progression must be built around the idea that it should avoid the black areas by making a “jump” over the portion of the integers which contains a 9. For instance, the progression 8 32 56 80 104 128 152 176 200 224 248 272 avoids the 90s and the 190s (but not the 290s, sadly). In order to determine the best progression, I will use R to calculate the length of the acceptable progression for multiple starting points and common difference. The following functions use regex in order to compute the length of the longest acceptable progression with these parameters:

nine  0) {return(1)}
  else {return(0)}
}

progression_length

Using this function on values bewteen 1 and 10 000 for the starting point and the common difference of the progression allows us to determine the maximum length achievable (within these parameters!). It appears that the longest one is the progression starting at 1 with a common difference of 125, which is :

1  126  251  376  501  626  751  876 1001 1126 1251 1376 1501 1626 1751 1876 2001 2126 2251 2376 2501 2626 2751 2876
3001 3126 3251 3376 3501 3626 3751 3876 4001 4126 4251 4376 4501 4626 4751 4876 5001 5126 5251 5376 5501 5626 5751 5876
6001 6126 6251 6376 6501 6626 6751 6876 7001 7126 7251 7376 7501 7626 7751 7876 8001 8126 8251 8376 8501 8626 8751 8876

and which is represented in the following graph by the grey tiles:

Adding one more term to the progression leads to 9001, which obviously contains a 9. This little exploration is of course no proof of any maximum length, but it shows that my hypothesis of some “jumps” over the 9 areas wasn’t wrong!

Comme certains ont pu le dire à l’époque des débats sur le mariage gay, en 2012, il y avait une crainte que cette nouvelle loi amène l’apocalypse et la fin de la civilisation en France. Il semblerait que, deux ans et quelques jours après, l’apocalypse ne soit pas encore arrivée, et que seuls quelques dizaines de milliers de mariage aient été célébrés. Mais on n’en est qu’à deux ans après l’adoption de la loi : que pourrait-il bien se passer à plus long terme ?

Pour éviter de recevoir trop de mails d’insultes et autres réjouissances, je vais vous rassurer de suite : il ne s’agira pas dans cet article de s’intéresser à l’impact sur les enfants, la société, ou que sais-je, du fait d’avoir autorisé deux hommes ou deux femmes à se marier. Non, ce qui m’a frappé dans cette loi, c’est son article 11. Celui-ci dit :

« En cas de désaccord entre les parents, signalé par l’un d’eux à l’officier de l’état civil, au plus tard au jour de la déclaration de naissance ou après la naissance, lors de l’établissement simultané de la filiation, l’enfant prend leurs deux noms, dans la limite du premier nom de famille pour chacun d’eux, accolés selon l’ordre alphabétique. »

Je résume (sans aucune mauvaise foi) : blablabla, le nom des enfants sera celui des parents accolés dans l’ordre alphabétique. C’est bien, l’ordre alphabétique, non ? C’est neutre, c’est pour l’égalité homme-femme, homme-homme et femme-femme, tout ça. Mais ce qui me perturbe, personnellement, c’est que si monsieur A épouse madame B (+1 point hétérocentrisme), leurs enfants s’appelleront A-B. Et si ils épousent les enfants de C et D, soient les C-D, eh bien leurs enfants à eux (les petits-enfants de monsieur A et madame B) auront A-C comme patronyme. Vous avez bien vu, les noms de famille B et D ont disparu. Pourquoi ? Parce qu’ils sont plus loin dans l’ordre alphabétique. Le mariage va donc bien détruire notre civilisation, en s’attaquant à nos patronymes ! Peut-on essayer d’évaluer la vitesse de cette décadence ?

Quelle sont les noms de famille les plus courants ?

La question du nom de famille le plus courant n’est pas compliquée : c’est Martin, avec une très large avance. Certains sites comme celui-ci permettent de le savoir, bien que leurs sources ne soient pas très clairement précisées. Mais ce qui nous intéresse ici est une distribution plus générale des noms de famille en France. Pour cela, nous allons utiliser les données du Bac 2014, en faisant des statistiques sur les noms des candidats. Cela peut créer quelques biais, parce que cela concerne une seule génération et non pas la population toute entière, et parce que toute la génération en question ne se présente pas au bac (qu’il soit général, professionnel ou technologique). Néanmoins, c’est une des sources les plus solides pour ce genre de questions, d’autant plus que leur âge uniforme (et leur absence d’enfants, a priori) va permettre de les considérer comme la première génération. La distribution, rapportée à 10.000 personnes, est la suivante :

On a représenté la distribution des noms de famille suivant les initiales. On remarque déjà que c’est la lettre B qui est la plus courante (vous connaissez beaucoup de personnes dont le nom de famille commence par B ? C’est normal), et qu’il y a de fortes disparités entre les différentes lettres : pas grand monde n’a un patronyme commençant par Q, U ou X, du moins en France.

Avec un peu de mauvaise foi

Maintenant que nous connaissons la situation initiale de la répartition des noms de famille en France, du moins de leurs initiales, il est temps de s’intéresser à l’impact qu’aurait le fait d’attribuer aux enfants les deux noms de leurs parents 1 et 2 (-1 point hétérocentrisme), ordonnés dans l’ordre alphabétique, dans la limite d’un nom par parent. Pour cela nous allons utiliser un modèle très simple de générations : parmi les N individus de notre population, les N/2 premiers vont se marier avec les N/2 autres, au hasard (du moins au hasard selon l’initiale du nom de famille, d’autres facteurs pouvant jouer). Ensuite, on va supposer que chacun des couples aura deux enfants : leurs noms de familles commenceront par l’initiale du nom des deux parents qui est le premier dans l’ordre alphabétique. Evidemment, comme le mariage gay est autorisé, on ne s’intéressera pas au sexe des marié(e)s : ils auront leurs enfants de la façon qui leur convient, cela n’est pas la question soulevée ici.

À quoi va ressembler la distribution des noms de familles dans la génération suivante, pour les bacheliers de 2040 ? Les simulations donnent le résultat suivant :

On remarque déjà une belle modification de la distribution des noms de famille. Beaucoup plus de personnes ont un nom qui commence par une lettre de début de l’alphabet, et c’est évidemment l’inverse pour les noms dans le milieu et la fin de l’alphabet. Mais la modification est encore mineure : que se passera t-il dans 5 générations, soit dans 125 ans environ ?

Impressionnant. La distribution n’a plus rien à voir : tous les patronymes commencent par A, B, voire C pour quelques chanceux. La totalité de la culture présente dans nos patronymes a été anéantie. C’est véritablement l’apocalypse annoncée.

Soyons plus réalistes

J’ai un peu joué sur les mots dans la partie précédente. L’article de loi ne force personne à donner comme nom de famille à ses enfants les deux noms de ses parents dans l’ordre alphabétique, elle donne seulement un cadre pour toute situation où il y aurait désaccord ou problème. Il s’agit donc d’appliquer cette règle uniquement dans ces cas. Nous évaluons à environ 10% des cas cette règle : que ce soit par erreur, par désaccord, pour éviter tout problème dans le couple, il nous semble crédible qu’un couple sur 10 environ suive la règle édictée par la loi. Pour les 90% autres, il y a un accord entre les parents : on peut raisonnablement penser que cet accord se fait la moitié du temps en faveur du parent 1, et la moitié du temps en faveur du parent 2 (-1 point hétérocentrisme, j’espère finir en négatif). Dans ce cas, l’évolution d’une génération à l’autre est évidemment moins marquée que dans le cas précédent. Mais que se passe t-il à long terme ?

Ce (magnifique) graphe s’intéresse à l’évolution générale des initiales des noms de familles, entre ceux commençant par A, qui commencent à environ 4%, pour monter très haut génération après génération, ceux par B qui connaissent un pic aux alentours de la 25ème génération, tandis que toutes les autres lettres tendent à disparaître à plus ou moins long terme. Plus précisément, ce graphe dynamique montre l’évolution d’une génération à l’autre de la distribution des noms de famille :

Même avec des hypothèses plus réalistes, il n’y a que le délai avant l’apocalypse qui change. De manière plus précise, nous pouvons estimer à partir de combien de générations il n’y aura plus de noms commençant par chacune des lettres (sauf A, qui ne disparaît jamais, et B qui persiste de nombreuses générations) :

Légende : Sous chaque lettre est indiquée le nombre de générations nécessaires avant la disparition de la totalité des noms de famille commençant par cette lettre. Par exemple, il faut attendre 46 générations pour que tous les patronymes commençant par Z disparaissent.

Les noms en X sont les premiers à disparaître, après 13 générations, soit un peu plus de 3 siècles, ce qui nous laisse tout de même le temps de voir venir. Mais, en parlant de noms de famille commençant par X, vous en connaissez beaucoup ? Xavier, d’accord, mais à part celui-là ? La plupart d’entre eux sont des noms d’origine étrangère, et donc viennent de l’immigration. Ce qui est précisément le facteur que nous avons oublié.

L’immigration va-t-elle nous sauver ?

Il serait plus correct de dire l’un des deux facteurs : pour être tout à fait exact, il faudrait mentionner que pas tout le monde ne se marie et n’a des enfants, mais ce comportement n’a aucune raison d’être lié au nom de famille, du moins pas directement. On peut donc supposer que 15% des gens n’ont pas d’enfants (selon le Figaro, c’est un homme sur 5, mais à 50 ans ce qui laisse un peu de marge – on peut aussi aller jeter un oeil sur fivethirtyeight (en) sur la question aux États-Unis).

Mais revenons à l’immigration. Comme nous n’avons aucune envie de nous lancer dans le débat sur le nombre d’immigrés arrivant ou repartant, laissons ça aux spécialistes. Ce qui nous intéresse ici est une étude à long terme, et un modèle fréquemment utilisé en démographie pour cela est celui de population stationnaire, où la taille n’évolue plus. On va donc supposer que les 15% d’enfants qui ne sont pas nés d’après l’hypothèse précédente sont remplacés par une immigration entrante de même taille.

Reste une question de taille : si l’on s’intéresse aux noms de famille des personnes venant vivre en France, comment connaître leur répartition ? On pourrait imaginer récupérer des données sur l’ensemble des pays du monde, et les pondérer selon le pourcentage d’arrivants par pays, qui n’est pas très bien connu, en prenant en compte des évolutions pour chacune des générations successives. Mais c’est très compliqué, et cela n’aurait concrètement rien apporté de tangible. Nous allons nous limiter à deux hypothèses qui sont aussi peu crédibles l’une que l’autre, mais qui ont le bénéfice d’être simples à mettre en oeuvre.

Tout d’abord, supposons que la totalité des pays du monde a la même distribution des noms de famille que la France. Dans ce cas, les noms des immigrants suivent la même répartition que celle de la France avant l’application de la loi, c’est à dire celle des bacheliers 2014. L’évolution est alors la suivante :

Une autre hypothèse est de dire que comme les noms de familles peuvent provenir de pays, de cultures et même d’alphabets très différents, il y a autant de chance que le nom de famille commence par chacune des lettres de l’alphabet latin. Autrement dit, la répartition des initiales des noms des arrivants est uniforme. L’évolution est alors la suivante :

Dans les deux cas, la situation ne semble plus se dégrader à moyen terme : les noms de familles commençant par toutes les lettres hormis les toutes les premières ne vont pas disparaître d’ici quelques siècles, bien qu’il y ait une légère hausse des noms commençant par A et B dans le cas d’une répartition des noms mondiale similaire à celle de la France. Cas très improbable, on le rappelle.

Il semblerait donc que l’immigration nous sauvera de l’apocalypse causée par l’adoption du mariage gay. Quel retournement de situation, n’est-ce pas ?

image source : Wikimedia, Le mariage de Sigebert Ier et de Brunehaut

I spend a lot of time in the Parisian subway, as I use it everyday to go to work, and sometimes to meet some friends of mine. I usually spend my time listening to music and asking myself lots of questions about its organisation : how the time frequencies of subways are decided ? How can empty trains become completly full within minutes ? I guess there are people working on that, but there are some sillier questions I doubt anyone is paid to look for an answer to.

One of these came recently into my mind when I was on the “ligne 13”, between “Montparnasse Bienvenue” and “Porte de Vanves”. I realized that I passed through 4 stations which were in alphabetical order.

So now I wonder : using only the subway, what is the maximal number of stations in alphabetical order you could go through? I already know it is at least 4 because I do that every morning or so, but could we go up to 5, 6, 7, or maybe more ? Let’s do some research!

5 stations in a row…

I’m a very lazy person, so I’m not going to do it by looking at all the lines in the Paris Metro, but I’d rather ask gently my computer to do it for me. First, I need to gather some data about the stations’ name on every line of the metro. These informations are available at different places, such as Wikipedia and “data.gouv”, which is the official French governement website on open data.

All left to do is an easy computation of the maximum number of stations in alphabetical order for each line, going back and forth. The algorithm used is thereby (in pseudocode):

maximum_number <- function(Line) {
    for Station in Line {
    if (Station > Station_prec) {Counter <- Counter + 1}
    else {Maximum = max(Maximum,Counter) ; Counter = 1}	
     }
  Maximum = max(Maximum,Counter);
  return(Maximum)
}

The results obtained are compiled in this graph:

The answer to my question seems to be 5 stations: "ligne 2" (Belleville / Couronnes / Ménilmontant / Père Lachaise /Philippe Auguste), "ligne 5" (Bobigny-Pablo Picasso / Bobigny-Pantin-Raymond Queneau / Église de Pantin / Hoche / Porte de Pantin) or "ligne 12" (Falguière / Montparnasse-Bienvenüe / Notre-Dame-Des-Champs / Rennes / Sèvres-Babylone).

... or maybe more?

Ok, so I was right 4 wasn't the best I could do. But I feel like I'm forgetting something... Of course, the connections between the lines! The Paris Metro is organized around huge hubs such as "Montparnasse-Bienvenüe" which belong to plenty of lines, so I guess using these big stations might get us to better than 5, right?

As you may know, the organization of the subway is quite complex. To simplify my study, I will consider that two lines are connected at a station iff the station's name is the same on the two lines. For instance, on the map previously shown, I consider "La Chapelle" and "Gare du Nord" not to form a connection, but "Gare du Nord" to be one on its own, between Line 4 and 5.

The algorithm I use is a more complex than the previous one. It requires to browse through all the subway network in order to find the higher number of stations in alphabetical order. For those with some computing background who are used to recursive functions, here is my pseudocode :

 max_length <- function(Station) {
	Connections = connection_list(Station)
        Values = void()
	for (Line in Connections) 
		{ Next_Station = Line[id_Station + 1]
                  Values = c(Values, max_length(Next_Station) }
	return(max(Values))
}

And the result is... 6! Well, I though that using the connections might lead to an higher number of stations, but whatever. There are numerous ways to achieve the maximum number:

• Belleville (2) / Colonel Fabien (2) / Jaurès (2->5) / Laumière (5) / Ourcq (5) / Porte de Pantin (5)
• Duroc (13) / Montparnasse Bienvenue (13->12) / Notre-Dame des-Champs (12) / Rennes (12) / Sèvres Babylone (12->10) / Vaneau (10)
• Gaité (13) / Montparnasse Bienvenue (13->12) / Notre-Dame des-Champs (12) / Rennes (12) / Sèvres Babylone (12->10) / Vaneau (10)
• Edgar Quinet (6) / Montparnasse Bienvenue (6->12) / Notre-Dame des-Champs (12) / Rennes (12) / Sèvres Babylone (12->10) / Vaneau (10)
• Falguière (12) / Montparnasse Bienvenue (12) / Notre-Dame des-Champs (12) / Rennes (12) / Sèvres Babylone (12->10) / Vaneau (10)

Well, there are at least two completly different ways to achieve the record of 6 stations in a row: the first one, in the northeastern part of Paris, and the 4 others located near Montparnasse. Fun fact: before 1942, Montparnasse and Bienvenüe were two different stations (see there), and "Porte de Pantin" station wasn't built (see there): therefore the only possible circuit was :

• Falguière (12) / Montparnasse Bienvenue (12) / Notre-Dame des-Champs (12) / Rennes (12) / Sèvres Babylone (12->10) / Vaneau (10)

But I guess there were more urgent things to deal with at this time.

Let's simulate some graphs!

I'm now wondering what would happen if I did this kind of analysis for all the subway network all around the world. But as I mentionned before, I'm kind of lazy, so I won't try to gather all the data about all these networks. Another approach is to try to know if the Paris Metro network is particular, or if it behaves like an average graph. So I'll try to simulate some networks, compute the maximum number of ordered nodes, and compare the mean value obtained to 6.

A graph is a representation of a set of objects, denoted the vertices, which are the stations here, and the relations between them. Each time two vertices A and B are in relation, there is a link, denoted an edge, going from A to B. In our subway example, it will mean that you can go directly from station A to station B without any stop. We will consider it as a symmetric graph, which means that when you can go from A to B you can also go back to A from B, even if in the Paris Métro there is some absurd lines (for instance, the West part of the "ligne 10").

Unfortunately, simulating a subway network is quite hard (citation needed). As I only have small knowledge of graph theory, I'll try the simplest way to simulate a graph, which happens to be the Erdos-Renyi method: we first generate 300 vertices (because there is about 300 stations in Paris), numbering them from 1 to 300. Then, for each possible link between two stations, we roll a (odd) dice to determine if there is an edge or not. The dice is designed in order to obtain an average of 371 edges, because there is 371 links in the parisian network.

Using R, I simulated 1000 graphs with this method. Then for each of them I apply an algorithm, similar to the one previously presented, to get the maximum number of ordered vertices, using the label given to them. I obtain the following results:

It seems that 6 is at the bottom of the distribution of the maximum number of ordered stations (average is about 7.8), which may lead us to think that we are unlucky in Paris. But we have to keep in mind a few things :

• First, the model used here isn't at all a good model for subway network. So this comparison is a little fallacious, and we shouldn't jump to any conclusion.
• Someting else that may explain the difference between the simulations and Paris Métro is that the names of the stations aren't really uniformly distributed: there are some spatial correlations between the names, for instance all the "Porte de" are located near Paris' exits, and "Bobigny-Pablo Picasso" and "Bobigny-Pantin-Raymond Queneau" are obviously close stations. This might lead to less randomness and biased results.

I guess I have to do the job for all the other subways. I think I will start with this one!

Image titre : Paris Métro Entrance, Abbesses