Les anniversaires de vos amis sur Facebook

Tous ceux qui ont un compte Facebook savent qu’il est devenu impossible d’oublier l’anniversaire de leurs amis. Et plus on a d’amis, plus on a d’anniversaires à souhaiter… Pour un peu, on devra souhaiter au moins un anniversaire par jour. Littéralement. Littéralement, vraiment ?

Si vous possédez strictement moins de 365 amis alors vous êtes sûrs d’avoir au moins un jour sans anniversaire à souhaiter dans l’année. Génial, au moins un jour où vous serez tranquille ! Mais en général ? Si vous êtes très « popular » et que vous avez tellement d’amis que vous ne savez plus quoi en faire ? Voici donc la question que nous allons examiner dans cet article:

Si je possède n amis, quelle est la probabilité qu’il y ait au moins un jour dans l’année où je n’ai pas d’anniversaire à souhaiter ?

Quelques suppositions…

Dans cet article, nous ferons au moins deux suppositions de taille:

  • Tout d’abord, on supposera que les dates d’anniversaire se répartissent de manière uniforme dans l’année. On supposera donc qu’on a la même probabilité d’avoir un ami né le 1er Janvier que d’avoir un ami né le 12 Juillet. En général, on sait que cela n’est pas tout à fait exact.
  • On se limite au cas d’une année de 365 jours et on oublie sans pitié les années bissextiles et les gens nés un 29 Février (décidément, ils n’ont vraiment pas de chance ceux-là).

Cardinal de l’univers

L’expérience aléatoire que nous allons étudier est donc celle qui consiste à tirer n personnes au hasard et à regarder la liste de leurs dates de naissances. Chaque issue de cette expérience revient donc à associer à chaque personne (ou ami) une date d’anniversaire. Il y a donc autant d’issues possibles qu’il y a d’applications de l’ensemble des n amis dans l’ensemble des 365 dates d’anniversaires possibles. Dit autrement, il y a autant d’issues qu’il y a de n-listes à valeurs dans \{1;2; ...;365 \}. Il y a donc 365^n issues possibles (résultat classique qui fut enseigné autrefois en Terminale S, mais qui ne l’est plus dorénavant).

Je fais un rêve, qu’un jour on n’ait aucun annif’ à souhaiter

Ce qui nous intéresse dans cet article, c’est donc de calculer la probabilité de l’événement « Il existe un jour de l’année qui n’est l’anniversaire d’aucun de mes n amis ». Nous noterons p(n) cette probabilité dans la suite. La probabilité de cet événement n’étant pas évidente à trouver, nous allons classiquement d’abord calculer la probabilité de son événement contraire, qui se trouve être: « Tous les jours de l’année, il y a au moins un anniversaire à souhaiter ».

Mais que veut dire que chaque jour de l’année il y a au moins un anniversaire à souhaiter ? Cela signifie que chaque date de l’année est l’anniversaire d’au moins un ami (remarque très profonde…). En termes mathématiques, cela veut dire  il y a autant d’issues dans lesquelles il y a au moins un anniversaire à souhaiter chaque jour qu’il y a de surjections de l’ensemble des n amis dans l’ensemble des 365 jours de l’année. Si vous avez suivi l’article précédent de ce blog (intitulé Stirling 2 – Le retour), vous devez savoir que le nombre de surjections d’un ensemble à n éléments dans un ensemble à 365 éléments est égal à 365! . S(n,365)S(n,365) est le nombre de Stirling de seconde espèce associé à n et 365.

Si n est inférieur strictement à 365, ce nombre vaut 0 et donc la probabilité est nulle, ce qui entraîne p(n)=1-0=1 dans ce cas. Sinon, nous avions prouvé l’égalité:

\displaystyle{S(n,365)= \frac{1}{365!} \sum_{j=0}^{365} (-1)^{365-j} {365 \choose j} j^n}

c’est-à-dire

\displaystyle{365!. S(n,365)= \sum_{j=0}^{365} (-1)^{365-j} {365 \choose j} j^n}

Ainsi, en divisant par le nombre total d’issues (365^n), on obtient la probabilité qu’il y ait au moins un anniversaire par jour à souhaiter:

\displaystyle\frac{1}{365^n} \sum_{j=0}^{365} (-1)^{365-j} {365 \choose j} j^n = \sum_{j=0}^{365} (-1)^{365-j} {365 \choose j} (\frac{j}{365})^n

On en déduit donc que, pour tout n \geq 365, la probabilité qu’il existe au moins un jour sans qu’il y ait d’anniversaire à souhaiter est:

\boxed{\displaystyle p(n) =1- \sum_{j=0}^{365} (-1)^{365-j} {365 \choose j} \left( \frac{j}{365} \right)^n }

Je sais pas pour vous, mais ce résultat n’a rien d’évident.

Quelques valeurs numériques…

Ce blog ne serait pas ce blog s’il n’y avait pas dans cet article au moins un (presque joli) graphe. D’autant plus que cette belle formule trouvée pour p(n) ne nous parle pas vraiment concrètement…

Sur Facebook, on peut avoir entre 0 et 5000 amis au maximum. J’ai donc essayé de programmer le calcul de la probabilité p(n) pour n compris entre ces deux valeurs. Le programme en lui-même n’est pas difficile à écrire, mais les nombres en jeu sont à la fois très grands ({365 \choose j}) et très petits (\frac{j}{365}^n). N’ayant pas réussi à installer la librairie GMP,  j’ai donc dû choisir un autre langage de programmation que le C++. J’ai donc pour la première fois écrit un programme en Python. L’avantage du Python, c’est qu’il permet de base de faire des calculs avec des entiers aussi grands que l’on veut. Preuve: voici 365!

factorielle 365Et voici donc le graphe obtenu en calculant p(n) en fonction de n (obtenu grâce à la librairie matplotlib):

graphe des probabilités

On voit donc que jusqu’à 1500-1600 amis environ, on est à peu près certain qu’il y aura au moins un jour dans l’année où il n’y aura aucun anniversaire à souhaiter. A contrario, à partir de 4000 amis, on est presque certain de n’avoir aucun jour sans anniversaire. Qui l’eut cru ?

Un petit zoom sur une partie de la courbe nous informe que pour qu’on ait une chance sur deux pour qu’il y ait au moins un jour sans anniversaire à souhaiter, il faut avoir environ 2285 amis:

0.5

Corollaire

Vous vous souvenez du club Dorothée ? Chaque jour (ou presque) était diffusée en fin d’émission une liste de noms des membres du club Dorothée qui fêtaient leur anniversaire ce jour-là. Nous voyons sur le graphe précédent que s’il y avait plus de 5000 enfants inscrits au club Dorothée (ce qui est très probable…), la probabilité qu’il y ait un jour de l’année où la liste des anniversaires soit vide est quasi-nulle. Dorothée pouvait donc bien dormir sur ses deux oreilles.

Note

Voici le programme en Python pour calculer p(n): http://pastebin.com/0bjdaWHW

La formule utilisée est mise sous une forme différente, tout simplement pour profiter du fait que le calcul avec les entiers est exact en Python (quelque soit le nombre de chiffres) alors que le calcul de décimaux se fait avec un arrondi à 20 chiffres après la virgule…

Rendons à César ce qui est à César: l’idée de cet article m’a été inspiré par cette question posée sur Reddit.

Advertisements
Cet article, publié dans Dénombrement, Probabilités, est tagué , , , , . Ajoutez ce permalien à vos favoris.

6 commentaires pour Les anniversaires de vos amis sur Facebook

  1. dom dit :

    Bonjour, c’est chouette ! Petite faute de frappe. Formule donnant p(n) valable pour n supérieur à 365 et non 265.

  2. Gaston Rachlou dit :

    Bonjour, félicitations pour votre blog.

    Cet article évoque irrésistiblement le « problème du collectionneur de coupons ». Cet individu a un cahier contenant k cases numérotées de 1 à k sur chacune desquelles il doit coller un coupon portant le numéro correspondant. Il reçoit un coupon par jour dont le numéro (entre 1 et k) est aléatoire, chaque numéro ayant probabilité 1/k de sortir chaque jour.

    Question : au bout de combien de jours est-il a peu près sûr d’avoir rempli son cahier?
    Réponse : au bout de n=k ln(k) +ck jours, avec c grand (si c=5, la proba est > 99%)
    Démonstration : étude du comportement asymptotique des nombres de Stirling de seconde espèce.

    Si k=365, on a k ln(k)= 2150 : on est à peu près au milieu de votre toboggan ; et k ln(k)+5k=3980, on est bien tout en bas du toboggan!

    Bref, au bout de 10 ans, il est à peu près sûr d’y arriver:-)

    référence :

    http://en.wikipedia.org/wiki/Coupon_collector%27s_problem

  3. Hello! I’m at work surfing around your blog from my new apple iphone! Just wanted to say I love reading your blog and look forward to all your posts! Keep up the outstanding work!

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s