A winning strategy at the lottery

tl;dr – It is possible to construct a winning strategy at the lottery by choosing the numbers that other people rarely select. We discuss this and prove it on a small example.

 

There are many things I don’t like with so-called math reasoning and lotteries, and I wanted to write about it for a very long time. So, on the one hand we have the classic scammers who try to sell you the “most probable numbers” (or alternatively the “numbers that are due”). Of course, neither strategy is mathematically valid (because the draws are independent). On the other hand, many “educated” and “rational” people argue that, given that the expected value of a lottery ticket is negative (because the probability of wining a prize at the lottery is very low), smart people should never buy lottery tickets.

Comic by Zach Wiener, http://www.smbc-comics.com
Comic by Zach Wiener, http://www.smbc-comics.com

Now what if we could find a (mathematically correct!) strategy to make the expected value of our ticket positive? The idea is to choose the numbers that other players choose the least often, so that when we win a prize, it will be divided among fewer other players. But will it be enough to make a significant difference?

The example

Let’s consider a lottery where players have to choose 6 numbers out of 19. The total number of players is 10000. The favorite numbers of the players are 1, 2, 3, 4, 5 and the least favorite are 15, 16, 17, 18, 19. They are respectively selected 2 times more often and 2 times less often than the other numbers 6 –  14. The company who runs the lottery decides to give the players back 90 percent of the amount of the tickets (thus ensuring a 10% profit) depending on the number of numbers they have chosen that also are in the right combination:

  • 0 or 1 correct number: 0%
  • 2 correct numbers: 42%, shared with other winners
  • 3 correct numbers: 10%, shared with other winners
  • 4 correct numbers: 3%, shared with other winners
  • 5 correct numbers: 4%, shared with other winners
  • 6 correct numbers (the jackpot): 40%, shared with (the eventual) other winners

Then we compute the expected value for each ticket that was bought. You can find the R code I used on my GitHub page. I plotted the expected gains against an indicator of the rarity of the combination chosen by each player (the harmonic mean of the inclusion probabilities):

 

Expected gains wrt a measure of the frequency of the combination chosen

As we predicted, the expected gains are higher if you chose an “unpopular” combination. But what impresses me most is the order of magnitude of the effect. It is indeed possible to find a combination that yields a positive expected value (points on the left that are above the red line)!

Further work

I have no idea how all this works when we change the parameters of the problem: numbers to choose from (49 in France for example), number of players, choices of the players (inclusion probabilities of the numbers), payoffs, etc. I bet that the shape of the curve remains the same, but I wonder how high the expected value can get for the rarest combinations, and if it is always possible to find a winning strategy. I might try to work on an analytical solution when I find some time because I believe it involves some sampling theory.

Finally, a question to all people who never play the lottery because the expected value is negative, would you start buying tickets now that you know there exists a strategy with positive expected value?

Comic by Zach Wiener, http://www.smbc-comics.com
Comic by Zach Wiener, http://www.smbc-comics.com

PS: Henri pointed out chapter 11 of Jordan Ellenberg’s “How not to be wrong” which deals with interesting mathematical facts about the lottery, including a similar discussion as this post. Be sure to check it out, it’s really great!

[Games] Quels mots faut-il jouer à Motus ?

Après avoir tenté de percer les mystères des mots des Chiffres et des Lettres, nous allons nous attaquer à un autre jeu emblématique de France Télévisions : Motus ! Est-ce que l’analyse statistique du dictionnaire français va nous permettre de trouver des astuces pour mieux jouer à ce jeu et plus facilement trouver les mots cachés ?

Un bref rappel des règles

Le jeu de motus est basé sur un mélange entre les jeux de lettres (Scrabble, etc.) et le jeu de Mastermind, qui consiste à deviner une combinaison de couleurs en le moins de coup possibles : à chaque étape, le joueur tente une combinaison et le maître de jeu indique si des couleurs font partie de la combinaison choisie et si elles sont à la bonne position.

Pour motus, le principe est adapté de la façon suivante : un mot est à deviner. Il peut faire 7, 8, 9 ou 10 lettres (parfois 6 dans certaines variantes du jeu, par exemple pour les enfants). La première lettre du mot est toujours donnée : il faut deviner le mot le plus rapidement possible, et toujours en moins de 6 coups. Pour cela, lorsqu’un mot acceptable (c’est à dire dans le dictionnaire, commençant par la bonne lettre, et de la bonne longueur) est donné, des informations sur chacune des lettres sont donnés. Si la lettre est à la bonne place dans le mot à deviner, elle est encadrée de rouge. Si elle n’est pas à la bonne place, mais qu’elle est bien dans le mot à deviner, elle est encerclée de jaune. Par exemple, pour le mot suivant :

Obtenue

Il faut donc deviner un mot de 7 lettres commençant par O. Notre tentative, OBTENUES, nous permet d’apprendre que le mot commence par OB, et qu’il y a un E dans le mot à deviner. Mais nous apprenons aussi que le mot à deviner n’a pas de T, de N ou de U, et qu’il n’y a qu’un seul E. C’est déjà beaucoup d’informations ! En rajoutant un autre mot, on a un peu de chance :

Obliger

On a 6 des 7 lettres, et il reste donc deux mots possibles : OBLIGES et OBLIGÉE. Or, on a appris avec le premier mot qu’il n’y a qu’un seul E. Le mot à deviner est donc :

Obligés

Le meilleur mot

On voit bien que le choix du premier mot nous a permis de choisir le bon mot au troisième essai. La question que nous allons nous poser ici est la suivante : existe t-il des mots meilleurs que d’autres à utiliser en “ouverture”, c’est à dire au premier coup ? Pour y répondre, il va falloir bien définir ce que nous entendons par “meilleur”. L’approche que nous allons utiliser ici est celle de la minimisation du nombre de possibles une fois que le mot est joué. Concrètement, plaçons nous dans un exemple simple où les codes qu’on pourrait deviner sont les suivants :

1112
1113
1114
1234
1999

Si l’on joue 1999, hormis si l’on a un coup de chance et que c’était le code à deviner, on va avoir comme information que le premier “1” est bien placé, mais que les trois “9” ne sont pas présents dans le code à deviner : on n’a aucune information utile pour la suite du jeu. En revanche, si on joue 1234, les réponses possibles seront les suivantes :

Codes

On voit alors qu’avec un seul coup, on sait exactement quel est le code caché. Le choix de 1234 plutôt que 1999 semble ainsi meilleur. Dans le cas de Motus, on va regarder si certains mots à jouer en premier permettent de limiter les choix parmi lesquels le mot caché peut se retrouver. Concrètement, on s’attend à ce que AUTORISE, qui contient plusieurs voyelles différentes, un T, un R, et un S, sera plus informatif que AGARAGAR, qui est une répétition des mêmes voyelles et avec des G qui sont des consonnes rares.

Nous allons donc parcourir tous les mots possibles à jouer au premier coup. Pour chacun d’entre eux, on souhaite calculer un score qui correspond au nombres de mots moyens qui restent possibles après les informations obtenues après avoir joué son premier coup. Concrètement, ce score se calcule en regardant tous les mots cachés possibles, et on compte à chaque fois combien de mots sont encore possibles.

Mais nous n’allons pas nous limiter à un seul mot, car pour certaines des lettres, cela n’est pas suffisant ! Nous poursuivons ainsi en analysant pour les meilleurs “premiers coups”, quels sont les bons seconds choix, puis troisièmes, afin de garantir une facilité de découverte du mot final.

Résultats

7 lettres
ACTIONS AMPLEUR ABREGEE
BURSITE BALCONS BRIDGER
CARTONS CHIPEUR COMBLEE
DIRECTS DEVALUE DUMPING
ENCULES ETIRAGE EPOXYDE
FARINES FLUCTUE FIBROME
GRATINS GOLFEUR GAMBADE
HURLANT HOSPICE
INSURGE IMPACTS IDOINES
JESUITE JOURNAL
KASCHER KARTING
LUTINER LASCIVE
MARTINS MODULEE
NAUTILE NOCIVES
OBSTRUE ORDINAL
PASTOUR PELVIEN PROCEDE
QUALITE QUINTES
RANIMES RECOLTE REPERDU
SAURETS SINOPLE SMICARD
TAMISER TOLUENE TRICARD
URBAINS UNICITE
VALIDES VENGEUR
WILDCAT WALLABY
YAOURTS YAKUZAS
ZAIROIS ZAPPANT
8 lettres
ADROITES ANTICLUB AMPERAGE
BASCULER BEOTIENS BOURGADE
CARLISTE COMPOUND CHANVRES
DECLINER DOMPTAGE DEFAVEUR
ENTOURES EMPILAGE EXCEDENT
FAUTRICE FIGNOLES
GALIOTES GONFLEUR
HUMANITE HARCELES
INSULTES IMPAVIDE INCONGRU
JALOUSER JUNGIENS
KALMOUKS KACHOUBE
LUSTRAGE LINOLEUM
MANITOUS MORCELEE
NATURELS NEGOCIEE
OCULAIRE OBSEDANT
PRALINES POUCETTE PEGAMOID
QUANTITE QUELQUES
RALINGUE REPORTES RECESSIF
SARDOINE SCULPTES
TAULIERS TRONCHER
URANISTE UFOLOGIE
VAURIENS VITILIGO
WARNINGS WAGONBAR
XIPHOIDE
YACHTMAN YACHTING
ZAIROISE ZAIBATSU
9 lettres
ANTICORPS AMPLITUDE
BOUCLIERS BADMINTON
CONTIGUES CHAMELIER
DECANTEUR DIPLOMEES
ENTOURAGE ECLIPSEES
FORMALITE FECONDEES
GALOPINES GRATITUDE
HURLANTES HEDONISTE
INTERLUDE IPSOFACTO
JAPONISER JOUISSIFS
KAYAKISTE KAMIKAZES
LANGOUSTE LUCRATIVE
MAROCAINS MULTITUDE
NATURISME NORMALITE
OUTRANCES OLYMPIADE
PRODUITES PLACEMENT
QUANTIEME QUENOTTES
RALINGUES RECOMPTER
SURACTIVE SOULIGNES
TRACTIONS TELEGUIDE
ULTRASONS UKRAINIEN
VIRULENTS VAGABONDE
WAGNERIEN
XENOPHOBE
YACHTCLUB
ZIGOUILLE ZAIROISES
10 lettres
ANTIODEURS ACCEPTABLE
BRILLANCES BOUGREMENT
CONSTITUER CALVINISME
DESACTIVER DECOUPLAGE
ENCAGOULES EXPEDITEUR
FIGURANTES FALCIFORME
GRIMPANTES GRENOUILLE
HONORAIRES HEMATOCELE
INTERLOPES INDICATEUR
JANISSAIRE JACASSANTE
KANGOUROUS
LUXURIANTS LOCOMOBILE
MATRICULES MODERNISME
NOVATRICES NAPHTALENE
ORIENTEURS OMBILICALE
PREDICANTS PORTEPLUME
QUANTIEMES QUADRANGLE
RECAPITULE REVIGOREES
SARDONIQUE SIMPLISTES
TRAINGLOTS TUMESCENCE
ULTRACHICS UKRAINIENS
VARIATIONS VALDINGUER
WAGONSALON
XENOPHOBES XENOGENESE
YACHTWOMAN
ZENITHALES

[Games] Pourquoi la France perd toujours à l’Eurovision ?

Spoiler alert : C’est parce que nous sommes directement qualifiés en finale alors que la plupart des autres pays sont sélectionnés en demi-finale.

“L’Eurovision c’est un concours européen de chanson et à la fin c’est la France qui perd”

Cette année a beau avoir été meilleure pour la France à l’Eurovision que la précédente, de nombreux articles n’ont pas manqué de souligner la contre performance de la représentante française à Vienne. Celle-ci (qui, selon ses propres mots, “a les boules”) a terminé à la 25ème place sur 27, avec un score de 4 points, tandis que la Suède finit première avec 365 points. C’est assez décourageant, mais nous allons voir ici que cela est entièrement dû aux règles de qualification et pas à France 3.

Un bref rappel des règles

L’Eurovision est donc un concours musical créé en 1956 auquel peuvent participer la plupart des pays européens. Ceux-ci envoient un artiste ou un groupe pour interpréter une chanson sur scène lors d’une soirée qui a généralement lieu fin mai, chaque année. Ensuite, chaque pays vote pour les chansons et les interprètes qu’il a préférés, et attribue ainsi de 1 à 12 points à un autre pays. Les points attribués sont affichés comme suit (profitons-en pour remercier l’Arménie !).

Points Arménie 2015

Ces votes sont pour moitié issus d’un jury de spécialistes réunis par la chaîne de télévision diffusant l’Eurovision dans le pays en question, et pour l’autre moitié viennent du vote par téléphone au sein du pays. N’oubliez pas que bien que le but soit de sélectionner la chanson préférée des européens, de nombreux votes vont en direction des pays frontaliers et alliés, ce qui permet de réviser sa géopolitique à peu de frais.

C’est d’ailleurs souvent un des arguments avancés pour expliquer nos échecs répétés de ces dernières années : nous n’aurions pas de véritable “bloc” de vote comme pourraient en avoir les pays scandinaves, ou les pays de l’ex-bloc soviétique. L’étude des votes permet de détecter des cliques de votants, et ainsi de faire émerger ces structures de bloc : on peut lire par exemple cette étude sur le sujet.

Mais ce n’est pas le sujet dont je veux parler ici – bien que j’espère pouvoir en faire une autre note de blog très bientôt ! Je n’ai en effet pas fini d’expliquer les règles de la compétition. Ces dernières années, de plus en plus de pays souhaitent participer à l’Eurovision. Or, la soirée n’était pas extensible, il est nécessaire de limiter le nombre de prestations ayant lieu avant les votes. C’est pourquoi il a été décidé d’organiser deux demi-finales avant la soirée finale afin de présélectionner les pays. Cette année, 40 pays (dont l’Australie !) participaient au concours se déroulant à Vienne. Les deux demi-finales qui ont lieu les jours précédents ont départagé 17 et 16 pays respectivement (ce qui a conduit à quelques malheureuses pertes…). Si vous avez bien suivi, vous avez du remarquer que 17 + 16 ne font pas 40 : c’est qu’il existe une règle spéciale pour les membres du Big Five, c’est à dire la France, l’Espagne, le Royaume-Uni, l’Allemagne et l’Italie, qui sont automatiquement qualifiés pour la finale en raison de leur contribution plus importante au financement du concours. Un autre pays est automatiquement qualifié : il s’agit de l’organisateur, qui est le gagnant de l’année précédente. Enfin, pour ne pas déséquilibrer les demi-finales, l’Australie a également été automatiquement qualifiée en finale. Cela fait donc un total de 7 qualifiés pour la finale sans passer par les demi-finales.

Tant mieux ?

Je vous voir venir : “Mais c’est une bonne nouvelle, parce que vu notre niveau ridicule, on n’aurait aucune chance de jamais passer les demi-finales !”. Mais est-ce vraiment une si bonne nouvelle pour les performances de la France (et des autres pays qualifiés) ? Pour comprendre en quoi cela peut être une explication pour nos résultats catastrophiques, prenons un exemple très simple.

Imaginons un jeu entre 3 personnes, André, Bernard et Carine. Chacun tire une carte au hasard parmi 1-2-3, et celui ou celle qui a la plus grande valeur gagne. Dans ce cadre de figure, chacun a 1 chance sur 3 de gagner, et 2 chances sur 3 de perdre. Supposons maintenant que par galanterie, les hommes, André et Bernard, décident de jouer d’abord entre eux le droit de jouer contre Carine. Dans ce cas, chacun d’eux a 1/2 de gagner contre l’autre et d’accéder à la “finale” contre Carine. Une fois qu’André ou Bernard est qualifié en finale, quelle est la chance que Carine gagne contre lui ?

Une réponse naïve serait de dire qu’elle a toujours une chance sur 2, parce qu’elle ne saurait pas qu’il y a eu une compétition préliminaire entre les deux garçons. C’est faux, comme on peut le voir si on énumère les différentes possibilités :

André Bernard Qualifié Carine Gagnant
1 2 Bernard (2) 3 Carine
1 3 Bernard (3) 2 Bernard
2 3 Bernard (3) 1 Bernard
2 1 André (2) 3 Carine
3 2 André (3) 1 André
3 1 André (3) 2 André

On voit bien que Carine ne gagne son duel qu’une fois sur 3, uniquement quand elle a tiré le 3, ce qui est assez logique. Si on revient à l’Eurovision, que peut-on en déduire pour les pays qui sont qualifiés automatiquement ? Et bien, comme Carine, ils ont une tendance à perdre plus souvent que ce à quoi on s’attendrait (la fameuse chance sur 2), car ils sont directement en finale, sans que leur score ait été testé avant. Est-ce que cela pourrait expliquer pourquoi nous avons l’impression de toujours être en bas du tableau de scores ?

Nous allons faire quelques simulations (le calcul exact serait possible, mais je suis un flemmard…) pour évaluer l’impact que pourrait avoir cette qualification d’office sur le classement de la France et des autres pays du Big Five. Pour cela, nous reproduisons l’expérience des trois cartes évoquée précédemment en la généralisant : imaginons que chaque pays ait un carton avec un numéro de 1 à 40 indiquant quelle serait sa place si tout le monde participait à la finale (qui finirait alors à 3h du matin…).

Reproduisons ensuite le processus de sélection : parmi les 16 pays participant à la première demi-finale, les 10 meilleurs sont qualifiés pour la finale. Puis de façon analogue, parmi les 17 pays participant à la deuxième demi-finale, les 10 meilleurs sont qualifiés pour la finale.

Une fois ces phases de sélection terminées, la finale oppose 27 pays, les 20 qualifiés en demi-finale auxquels on rajoute la France, l’Espagne, le Royaume-Uni, l’Allemagne, l’Italie, l’Autriche et l’Australie. On peut maintenant en rangeant les cartons dans l’ordre connaître le tableau final de l’Eurovision. En reproduisant plusieurs centaines de milliers de fois ce processus, nous pouvons obtenir des résultats en moyenne sur les places des différents pays en finale, en utilisant la loi des grands nombres.

Ainsi, nous observons que sur 27 pays participants, un pays automatiquement qualifié comme la France arrive en moyenne à la 18ème place (17,7 pour être précis), tandis qu’un pays qui a du passer par la demi-finale finit en moyenne à la 13ème place (12,7) quand il réussit à accéder à la finale. Ainsi, être qualifié directement nous fait perdre 5 places en moyenne au classement final. Cela peut expliquer pourquoi nous avons tendance à rester dans les tréfonds du classement…

Plus spécifiquement, et cela a été un traumatisme pour nous l’an dernier, il est démoralisant de finir dernier du concours. Toujours en suivant ce processus de simulations, il est possible d’estimer la probabilité qu’un des 7 pays directement qualifiés soit dernier à l’Eurovision 2015. Nous obtenons le résultat assez impressionnant de 93,7% de chances pour un de ces 7 pays d’être dernier. Si l’on se restreint à un unique pays, au hasard la France, nous avions 13,5% de chance d’être derniers. En revanche, la probabilité pour un pays d’être premier est toujours de 1/27, peu importe que l’on soit directement qualifié ou pas : tout le monde a donc ses chances pour la prochaine organisation (cf l’Allemagne en 2010). Enfin, encore une fois, c’est en oubliant toutes les subtilités du vote géopolitique…

Et depuis 2000…

D’ailleurs, il est temps de comparer ces résultats avec la réalité. On se concentrera ici sur la période 2000-2015 car si l’on remonte trop loin dans le temps, il y a bien moins de pays participants et cette étude n’a donc plus vraiment de pertinence.

Quels ont été les scores moyens de la France ? et du Royaume-Uni, nos ennemis jurés ? Les données sont disponibles sur Wikipedia, pour la France et pour les Anglais. Un rapide calcul de moyenne nous permet d’obtenir les résultats suivants : la France a eu une place moyenne de 17,63 et le Royaume-Uni de 18,13. Bim les Anglais, retournez dans vos avions !

Toutes considérations de conflit franco-anglais mises à part, on s’aperçoit que nos simulations sont assez proches de la réalité, surtout pour la France. Ainsi, il semblerait que l’hypothèse communément admise que nos artistes ne sont pas adaptés au concours soit fausse : si nous réalisons de mauvais scores, c’est uniquement dû au système de qualification automatique. Le graphe suivant montre les résultats moyens des pays du Big Five pour les comparer avec les autres :

Graphe Eurovision

On voit bien qu’en moyenne les pays directement qualifiés sont bien derrière au classement, et que l’écart au classement varie chaque année, mais toujours en faveur des pays qui sont qualifiés par les demi-finales. Sur les 9 dernières éditions, les pays du Big Five ont été en moyenne 6 à 7 places derrières les autres, ce qui est un peu plus que prévu. Cela peut venir du vote géopolitique évoqué précédemment, ou juste d’une mauvaise série…

Qu’en est-il pour la dernière place ? Le tableau suivant récapitule les éditions depuis 2000 pour lesquels le pays arrivé dernier était automatiquement qualifié en finale :

2015 Autriche
2014 France
2010 Royaume-Uni
2008 Royaume-Uni
2005 Allemagne
2003 Royaume-Uni

(Remarque personnelle : Cette chanson de 2005 méritait vraiment de perdre. Bref.)

On a donc 6 chansons sur 16 qui sont à la dernière place qui viennent d’un des pays du Big Five ou de l’organisateur, soit 37,5% ce qui est bien loin des 93,7% estimés. On peut donc bien supposer que nos chansons sont moins nulles que ce à quoi on pourrait s’attendre. À part celles des Anglais, qui sont derniers 3 fois sur les 16, soit 18,8% du temps, alors qu’on avait estimé le risque à 13,5%. You suck, England!

[Games] Les mots les plus probables à “Des chiffres et des lettres”

Pour changer un peu, aujourd’hui, un post écrit en français ! De temps à autres pendant mes congés, je prends le temps de regarder la célèbre émission “Des chiffres et des Lettres”. Je m’assois devant ma télévision avec une bonne tasse de thé bien chaud, du papier et un crayon pour compter les points, et je tente de terminer avec le score le moins éloigné possible du vainqueur du jour. Sur la partie “Le compte est bon” (les chiffres, donc), je crois m’en tirer honorablement. “Le mot le plus long” (les lettres) est pour moi un exercice beaucoup plus difficile ; il n’est pas rare que je n’aie rien à proposer, quand les candidats ont de leur côté trouvé le même “8 lettres” dont j’ignore la signification !

Bien que je n’aie que trop rarement l’occasion de regarder l’émission, il me semble que l’on retrouve assez souvent les mêmes mots parmi les solutions. De plus, certains mots rares semblent connus de beaucoup de candidats : si je comprends bien, il s’agit quand on s’entraîne de procéder un peu comme au Scrabble, en apprenant à reconnaître des types de combinaisons, et les listes de mots associés. Je me suis donc demandé si l’on pourrait construire des probabilités de tirage pour chaque mot, et en déduire la liste des mots les plus probables.

En cherchant sur les interwebs, je suis tombé sur beaucoup de solveurs “Le mot le plus long” programmés en javascript, quelques fanblogs avec des conseils pour joueurs en herbe, mais rien qui ne ressemble à un début de réponse à la question que je me posais (pour une analyse de la partie “Le compte est bon”, je vous renvoie à l’excellent post sur le blog Datagenetics).

Le problème

Il s’agit donc de dresser une liste des mots valides dans le jeu, et de leur attribuer à chacun une probabilité de tirage. Intuitivement, cette probabilité de tirage doit prendre en compte la fréquence des lettres tirées par l’ordinateur de l’émission, ainsi que la fréquence d’occurrence des voyelles relativement aux consonnes.

En effet, si vous avez bien compris le principe de l’émission (sinon, rassurez-vous, vous n’êtes pas les seuls), chaque candidat choisit à tour de rôle “consonne” ou “voyelle”, et l’ordinateur tire ensuite une lettre correspondant au choix du candidat. Les choix des candidats doivent donc logiquement influencer la probabilité que l’on attribue à chaque mot.

Afin de ne pas trop surcharger ce post, je n’écrirai pas ici le code utilisé pour chaque étape. Mon programme est écrit en R, et je le mettrai probablement à disposition sur mon gitorious prochainement.

Les données

Pour commencer, nous avons bien entendu besoin d’un dictionnaire adapté, c’est-à-dire contenant uniquement les mots valides selon la règle du “mot le plus long”. Le dictionnaire Lexique contient des informations qui permettent d’identifier la nature grammaticale des mots, ce qui va nous permettre de retirer de la liste les mots interdits par le règlement. Le fichier contient également quelques informations utiles sur chaque mot (sa fréquence d’usage, par exemple), ce qui devrait nous permettre de faire quelques statistiques intéressantes. La dernière mise à jour du dictionnaire Lexique semble dater de 2007. Même si des mots apparaissent et disparaissent chaque année du dictionnaire, un intervalle de 7 ans me semble largement acceptable pour répondre à mes besoins.

Il faut ensuite trouver la probabilité d’appartition de chaque lettre, conditionnellement au choix “Voyelle” ou “Consonne”. Le règlement de l’émission n’est pas très explicite à ce sujet, et après une petite recherche google, il semble que personne ne connaisse réellement les probabilités de sélection des lettres. Qu’à cela ne tienne, nous allons les estimer à l’aide de la loi des grands nombres et d’une base de données ! Jacques Colard tient à jour sur sa page une base de données recensant tous les tirages depuis 1997. Ce travail très impressionnant nous sera également utile pour analyser les choix “voyelle” ou “consonne” des candidats. Le dernier changement dans les règles de jeu date de fin 2011. Afin d’éviter tout problème, mon étude porte sur toutes les émissions diffusées entre janvier 2012 et décembre 2014. Le nombre de tirages dans la base (4671) me semble largement suffisant pour obtenir une bonne précision sur les estimations qui m’intéressent.

Le modèle de probabilité

Nous allons expliciter notre raisonnement à l’aide d’un exemple. Supposons que le jeu se joue avec 4 lettres, et que les candidats ont choisi “Consonne” – “Voyelle” – “Consonne” – “Voyelle” (que je note par le suite le pattern CVCV). Calculons la probabilité de sortie du mot “CAVE” avec ce choix. Commençons par les voyelles : A et E. Pour trouver la probabilité de sélection étant donné la probabilité d’apparition de A et E parmi les voyelles, on peut fonctionner avec un arbre de probabilités (la méthode qui est enseignée au lycée, il me semble) :

arbre_proba_horizontal.svg

En suivant le chemin A, puis E, on obtient :

\Pr(A) \cdot \Pr(E)

Mais nous aurions pu tout aussi bien choisir d’abord “E”, ensuite “A”, ce qui nous aurait donné un autre chemin à suivre dans l’arbre de probabilités. On a finalement :

\Pr(A,E) = 2 \cdot \Pr(A) \cdot \Pr(E)

On peut procéder exactement de même avec les consonnes, ce qui donne finalement :

\Pr(C,A,V,E) = (2 \cdot \Pr(A) \cdot \Pr(E)) \cdot (2 \cdot \Pr(C) \cdot \Pr(V))

Plus généralement, pour tout mot, la probabilité de présence étant donnée le pattern s’écrit :

\Pr(mot | pattern) = NP(voyelles) \cdot \underset{lettre \in Voyelles}{\displaystyle{\prod}} \Pr(lettre | voyelle) \cdot NP(consonne) \cdot \underset{lettre \in Consonnes}{\displaystyle{\prod}} \Pr(lettre | consonne)

avec :

NP(mot) = \text{nombre de permutations des lettres du mot} = \dfrac{(nombre~lettres)!}{\underset{lettres~repetees}{\displaystyle{\prod}} (occurences~lettre)!}

Je ne détaille pas ici le calcul du nombre de permutations des lettres du mot, qui est un problème classique de combinatoire. Je précise simplement qu’il faut penser à prendre en compte le fait que permuter deux lettres identiques ne constitue pas une nouvelle permutation du mot (vous pouvez vous rendre ici pour une explication détaillée).

Il faut ensuite trouver à partir de la probabilité conditionnelle au pattern la probabilité générale sur tous les patterns. On considère que tous les patterns sont des événements disjoints, ce qui permet d’écrire :

\Pr(mot) = \sum_{pattern} \Pr(mot | pattern)

Estimation des probabilités de tirages des lettres

B C D F G H J K L M N P Q R S T V W X Z
N 777 1664 1075 647 960 666 104 109 2094 1248 2901 1196 232 3562 4152 2846 479 32 197 98
% 0.031 0.0665 0.0429 0.0258 0.0383 0.0266 0.0042 0.0044 0.0836 0.0498 0.1159 0.0478 0.0093 0.1423 0.1658 0.1137 0.0191 0.0013 0.0079 0.0039
A E I O U Y
N 4097 8320 3849 2821 2267 317
% 0.1891 0.3839 0.1776 0.1302 0.1046 0.0146

La fréquence d’apparition de chaque voyelle (et de chaque consonne) est utilisée comme d’estimateur de la probabilité de tirage de chaque lettre. Comme attendu, les lettres rares (Y, Z, etc.) sont moins probables que les lettres courantes (A, E, S, etc.).

Estimation des probabilités des patterns

Mon idée était que les choix des candidats étaient différents suivant les lettres déjà tombées (imaginez un tirage où vous avez déjà obtenu Z,H,Y,U – je suppose que votre choix futur ne sera pas nécessairement le même que si vous avez obtenu E,R,S,A), mais les lettres dans la base semblent apparaître toujours dans le même ordre (à nombre de voyelles égal). La base a déjà dû être ordonnée, et je ne peux donc pas différencier les patterns par ordre d’apparition des voyelles et consonnes (bien que cela ne me semble pas être une approximation trop dramatique !). On s’aperçoit par contre que les fréquences ne sont pas du tout symétriques en nombre de voyelles et de consonnes :

CVCVCVCCCC CVCVCVCVCC CVCVCVCVCV VCVCVCVCVV VCVCVCVVVV VCVCVVVVVV
N 72.00 1805.00 2538.00 248.00 7.00 1.00
% 0.02 0.39 0.54 0.05 0.00 0.00

Note : cette façon de procéder suppose que les tirages sont effectués avec remise, ce qui ne semble pas vrai d’après le règlement de l’émission. On réalise donc en réalité une autre approximation. Cette approximation est potentiellement plus grave pour les lettres rares. En effet, supposons que l’on tire sans remise parmi 100 lettres, contenant 30 “E” et 2 “Z”. Si la première lettre tirée est un “E”, la probabilité de tirer un “E” en deuxième lettre est de 29/99 et la probabilité avec remise (celle que nous utilisons), est de 30/100, qui lui est pratiquement égal. Par contre, si l’on a tiré un “Z” en première lettre, la probabilité de tirer un “Z” en seconde lettre est de 1/99, qui est pratiquement deux fois inférieur à 2/100, la probabilité avec remise. Néanmoins, le nombre de mots avec deux “Z” dans le dictionnaire me semble suffisamment limité pour que l’on ne s’inquiète pas trop de cette approximation !

2,5% de chances qu’un tirage contienne un 10 lettres

Les tirages où il existe un 10 lettres semblent assez peu communs dans l’émission. Dans une des dernières émissions que j’ai pu suivre, les présentateurs de l’émission ont signalé la rareté de l’événement en félicitant un candidat qui avait trouvé un mot de 10 lettres. Essayons d’estimer la probabilité de cet événement en utilisant notre table. On peut utiliser la formule suivante : Si les An sont des événements deux à deux incompatibles, on a :

\Pr(\displaystyle{\cup}_n A_n ) = \displaystyle{\sum}_n \Pr(A_n)

En considérant l’union de tous les mots de 10 lettres, sont-ils deux-à-deux incompatibles ? Non, car des anagrammes peuvent coexister au sein d’un même tirage. Il suffit donc de retirer les anagrammes de notre dictionnaire, afin de pouvoir sommer les probabilités de chaque mot de 10 lettres pour obtenir la probabilité qu’il existe un 10 lettres dans le tirage. On obtient :

\Pr(existe~un~10~lettres) \approx 2.49 \%

Une vérification sur la période 2012 – 2014 montre qu’il y a eu 120 tirages avec existence d’au moins un 10 lettres sur 4671 tirages dans notre base. Ce qui donne une fréquence de 2.57% : pas trop mal !

Pour donner un ordre de grandeur de cette probabilité : en partant d’une émission diffusée à un instant t, il y a presque 40% de chances qu’aucun 10 lettres ne sorte avant 40 tirages, c’est-à-dire presque 7 émissions.

Les mots les plus probables (par nombre de lettres)

odalisque.jpg
Enfin, nous y voici ! Nous sommes désormais capables d’attribuer une probabilité à chaque mot valable pour “Le mot le plus long”. Le mot les plus probable est IE (qui est référencé comme nom dans le dictionnaire Lexique, mais n’est peut-être pas accepté par le dictionnaire de référence, étant une abréviation). Le deuxième mot le plus probable est “EU”, participe passé du verbe “avoir”.

Quelques mots ont une probabilité strictement nulle, car ils contiennent 2 voyelles et 7 ou 8 consonnes, patterns inexistants dans notre base 2012-2014, et donc réputés de probabilité nulle : BLANCSBECS, CULSBLANCS, FRANCFORTS, GRANDSDUCS, HALFTRACKS, NIGHTCLUBS, PLATSBORDS, SCHILLINGS, SCHTROUMPF, SCRATCHING,
SCRIPTGIRL, SHRAPNELLS, SPHINCTERS, SPRINKLERS, STRESSANTS, STRETCHING, TCHATCHANT, TRANCHANTS, TRANSCRITS, TRANSFERTS, TRANSPORTS, TREMBLANTS.

Le mot le moins probable à probabilité strictement positive est BOWWINDOWS. Sa probabilité vaut de l’ordre de 10^-15, ce qui signifie que l’on peut espérer le voir apparaître environ une fois toutes les… 26 000 milliards d’émissions !

Comme on peut s’y attendre, la probabilité est fonction décroissante du nombre de lettres, comme le montre ce graphe en échelle logarithmique :

proba_nombre_lettres.png

Je termine en donnant les mots les plus probables par nombre de lettres (de 6 à 10) :

Mots de 6 lettres

mot probabilite (%) anagrammes
AINEES 0.22 ANISEE
OISEAU 0.21
AEREES 0.20
AERIEN 0.19 ANERIE
SOIREE 0.19

Mots de 7 lettres

mot probabilite (%) anagrammes
OSERAIE 0.11
AERIENS 0.10 ANERIES
ATRESIE 0.09
SATINEE 0.08
REALISE 0.07 SALIERE

Mots de 8 lettres

mot probabilite (%) anagrammes
ARTESIEN 0.04 TANIERES,TRAINEES
ARLESIEN 0.03 LANIERES
ALTIERES 0.03 ATELIERS,REALISTE,REALITES
RATISSEE 0.03
EURASIEN 0.03 RAINEUSE

Mots de 9 lettres

mot probabilite (%) anagrammes
INALTERES 0.02 RALENTIES
NOTARIEES 0.02
INSTAUREE 0.01
CARTESIEN 0.01 CERTAINES,SENATRICE
ENLIASSER 0.01

Mots de 10 lettres

mot probabilite (%) anagrammes
ORIENTALES 0.01 ORLEANISTE
INALTEREES 0.01
NEUTRALISE 0.01 RELUISANTE
INSTAUREES 0.01 TRAINEUSES
RATIONNEES 0.01

Certains de ces mots m’étaient inconnus ou ne me seraient jamais venus à l’esprit dans le cadre du jeu (OSERAIE, ATRESIE, ENLIASSER, RAINEUSE, etc.) !

To be continued…

J’arrête ici ce post déjà bien long… mais je ne manque pas d’idée pour exploiter ma nouvelle base de données (que je vous livre en format texte csv) ! Je vous donne donc rendez-vous d’ici quelques jours pour la deuxième partie de cette analyse des mots les plus probables à “Des chiffres et des lettres”.

Télécharger la base des probabilités des mots

Image titre : logo “Des chiffres et des lettres”, © France 3