29 novembre 2009

Mathématiques des papillotes (1/2)

A l'approche des fêtes de fin d'année, c'est l'occasion pour moi de vous parler d'un problème qui m'obsède depuis le collège, et que j'ai enfin résolu, celui de l'estimation du nombre de citations de papillotes (oui, oui, trois compléments du nom successifs, c'est moche).

Alors je ne parle pas des papillotes en tissu de Linette ou de celles brodées par Brodstitch pour les fêtes, encore moins de la meilleure façon de préparer le poisson, mais de cette délicieuse friandise en chocolat enrobée d'un petit papier contenant blague ou citation, le tout dans un papier extérieur brillant. Ce concept (associé en plus à la charmante légende du sieur Papillot et de son apprenti chocolatier) m'a toujours passionné, et je lis toujours la citation avec autant d'attention que je mastique le chocolat (je ne suis visiblement pas le seul dans ce cas). Et c'est assez frustrant de retomber sur une citation déjà lue quelques papillotes plus tôt. Voilà pourquoi j'ai commencé à enquêter sur le nombre total de citations de papillotes différentes, pour celles de la marque Révillon (traditionnelle dans ma famille au moment des fêtes, vous comprendrez pourquoi en comparant avec d'autres... et non, ce billet n'est pas sponsorisé :p).

C'est comme ça que depuis le collège, chaque année, j'essaie plus ou moins de garder les citations de papillotes au moment des fêtes, pour résoudre ce problème, avec les moyens du bord. Alors comme sur un papier, on arrive à lire deux citations (au moins partiellement), après avoir remarqué que deux citations qui se suivaient dans un papier étaient systématiquement consécutives, j'ai commencé par les scotcher pour espérer reconstruire un jour la séquence intégrale des citations. Au gré des déménagements, ces données ont été perdues, retrouvées, et une année j'ai constaté avec horreur que la consécutivité d'une année précédente n'était plus respectée : la liste de citations avait changé et tout le travail était à refaire !

En licence, devant quelques éléments de proba, je me suis dit qu'il serait certainement possible d'estimer mathématiquement la probabilité de trouver plusieurs fois une même citation en tirant un certain nombre de papillotes, et que ceci me permettrait certainement d'évaluer le nombre total de papillotes en comparant la probabilité théorique et celle trouvée en pratique. C'est seulement l'an dernier que j'ai trouvé une meilleure façon de formuler le problème en terme de probabilités, et j'ai pu finir les calculs cette année. C'est cette approche que je vais maintenant présenter (qui pourrait donner un sympathique exo de khôlle de math sup), j'évoquerai aussi une approche statistique qui donne les mêmes résultats. Pour mes lecteurs qui veulent éviter l'indigestion mais sont intéressés par le résultat de cette enquête mathématique, n'hésitez pas à sauter les paragraphes plus formels pour aller à la réponse en fin de billet, juste après l'image de la courbe.

L'idée consiste à évaluer la probabilité Pd,k(n) de tirer d citations différentes, parmi un total de n citations, au bout de k tirages de citations (en supposant que le tirage de chaque citation a la même probabilité). Par la dégustation de papillotes, on obtient un échantillon de citations où on connaît d et k, et la stratégie va consister à trouver la valeur de n qui maximise Pd,k(n) . Il faut donc calculer trouver une expression de cette valeur, que l'on peut exprimer en terme de mots dans un alphabet. En considérant chaque papillote comme une lettre, et chaque tirage de k papillotes comme un mot de k lettres, la probabilité Pd,k(n) est égale au nombre ad,k(n) de mots de k lettres contenant d lettres différentes divisé par le nombre de mots de k lettres (les lettres étant choisies dans un alphabet de n lettres), c'est à dire nk.

J'ai un peu bloqué sur le calcul de ad,k(n) : on peut le définir de manière récursive, ce qui permet de faire les calculs pour des valeurs assez petites de n, je le détaille dans ce document, mais une remarque de Gergely m'a permis de faire les calculs de manière plus élégante. Ce nombre ad,k(n) peut en effet s'exprimer uniquement en fonction de ad,k(d) : puisque le mot a d lettres différentes, on peut en effet se restreindre à un alphabet de d lettres, en multipliant le résultat par le nombre de projections possibles de ces d lettres sur les n lettres de l'alphabet original (un exemple pour comprendre ça est donné en slide 9 de ce diaporama). Ainsi :
ad,k(k)=ad,k(d).Cnd

Et là, magie, comme on cherche uniquement à trouver le maximum par rapport à n et que ad,k(d) ne dépend pas de n (si vous voulez savoir comment calculer ad,k(d), allez voir par là) :
maxn (Pd,k(n)) = maxn (ad,k(n) / nk) = maxn (Cnd / nk)

Gilles m'a expliqué comment modéliser le problème par une approche statistique, en considérant que le tirage suit une loi multinomiale, et en considérant comme statistique de l'échantillon le n-uplet donnant pour chaque citation son nombre de tirages. Le calcul d'un estimateur de maximum de vraisemblance pour la valeur de n fournit le même résultat, mais cette approche permettrait d'aller plus loin en calculant non seulement une valeur ponctuelle du maximum de vraisemblance mais également un intervalle de confiance. Je ne me suis toutefois pas encore plongé assez longtemps dans le Fourgeaud & Fuchs pour comprendre comment procéder.

Cette formule permet d'effectuer facilement les calculs (même si je bloque encore pour trouver une expression directe de ce maximum) pour localiser le maximum de vraisemblance, en traçant par exemple dans un tableur la courbe de Cnd / nk en fonction de n. L'an dernier, après dégustation de 52 papillotes, j'avais trouvé 40 citations différentes. J'ai voulu compléter mes données, mais les papillotes Révillon ne sont pas vendues au printemps et en été (ils arrêtent apparemment la production à cette période) et j'ai dû patienter jusqu'à cet hiver pour acheter et engloutir deux paquets (ma ligne aura un peu pâti de cette expérience, mais bon... je sers la science et c'est ma joie) : le premier m'a fourni 33 citations différentes sur 42, le second 33 différentes sur 41, l'union des deux 58 citations différentes sur 83. Ceci me donne les quatre courbes suivantes pour P40,52, P33,42, P33,41 et P58,83 en fonction de n :


Le maximum de la courbe est atteint respectivement à 93, 81, 89 et 107. Remarquez que plus l'échantillon est grand, plus le pic est fin : la précision de la méthode s'améliore...

Après avoir obtenu mes premières données, j'avais contacté Révillon pour demander confirmation de l'ordre de grandeur de 93. Ils m'ont répondu qu'il y a en fait 108 citations différentes pour les paquets de la collection "Festive" que j'avais testés. Mes collages font apparaître des cycles de 18 citations, j'ai pu en reconstituer 3 sur 6 :
Bien sûr, j'aimerais appliquer cette méthode d'estimation à d'autres données, par exemple les billets en euros (le site EuroBillTracker permet de récupérer le nombre total, et le nombre de billets différents, de l'échantillon constitué par les billets relevés par les participants au site) ou les blagues Carambar que j'évoque dans cette présentation :


Toutefois, pour ces deux estimations, outre le problème technique de calcul de très grands coefficients binomiaux pour le premier (je cherche un document de référence sur la méthode qui consiste à utiliser des logs pour ce type de calculs sur des grands nombres !), une hypothèse raisonnable (si si, Guyslain !) pour les papillotes ne fonctionne plus : le tirage de chaque billet, ou blague Carambar, n'est pas équiprobable. En effet, pour les billets, je pense que les visiteurs d'EuroBillTracker notent sur le site une plus grosse proportion de la totalité des billets de 5 euros, que de la totalité des billets de 500 euros imprimés. Pour les Carambars, le problème est que les blagues n'ont pas le même nombre de lignes. Ainsi, les blagues les plus longues ont une plus forte probabilité d'apparaître, et donc créent plus de paires que prévu dans un modèle équiprobable...