Différences

Ci-dessous, les différences entre deux révisions de la page.

--- teaching:exos:paradoxe_anniversaires [2012/10/22 13:27] – créée villersd
+++ teaching:exos:paradoxe_anniversaires [2020/07/14 13:06] (Version actuelle) – villersd
@@ Ligne 16: / Ligne 16: @@
 ===== Programme Python =====
-<sxh python;>
+<code python multiples-occurences-anniversaires.py>
 #!/usr/bin/python
 # -*- coding: UTF-8 -*-
@@ Ligne 32: / Ligne 32: @@
 # nombre de possibilités différentes
 # (= nombre de jours d'une année dans les exemples)
-poss=365
+poss = 365
 # nombre d'items (personnes présentes)
-n=40
+n = 40
 # solution : p = poss ! / ( (poss-n) !  * poss^n)
-pcomp=1.
+pcomp = 1.
 for i in range(poss, poss-n, -1):
-    pcomp=pcomp*i/poss
+    pcomp = pcomp * i / poss
-print "calcul exact : ",pcomp, 1.-pcomp
+print("calcul exact : ", pcomp, 1.-pcomp)
 # calcul suivant l'approximation de Stirling ( ln(j!) ~= j ln(j) - j
 # l'approximation est d'autant plus valable que poss est grand et n << poss
-pcomps=exp(poss*log(poss)-poss - (poss-n)*log(poss-n) + (poss-n) - n*log(poss))
+pcomps = exp(poss*log(poss)-poss - (poss-n)*log(poss-n) + (poss-n) - n*log(poss))
-print "Approximation de Stirling : ",pcomps, 1.-pcomps
+print("Approximation de Stirling : ", pcomps, 1.-pcomps)
-</sxh>
+</code>
 ===== Problème analogue =====
   * Quelle est la probabilité de recevoir 40 cartes cadeaux différentes (aucun "double") sur 216 types différents de cartes distribuées comme jeu-concours aux caisses d'un supermarché
@@ Ligne 57: / Ligne 57: @@
 ===== Références =====
-  * [[http://fr.wikipedia.org/wiki/Paradoxe_des_anniversaires]]
+  * [[wp>fr:Paradoxe_des_anniversaires|Paradoxe des anniversaires]]
-  * [[http://en.wikipedia.org/wiki/Birthday_problem]]
+  * [[wp>Birthday_problem|Birthday problem]]
+  * [[https://www.reddit.com/r/dataisbeautiful/comments/7l9ef7/i_simulated_and_animated_500_instances_of_the/]], simulation
+  * [[https://towardsdatascience.com/using-the-birthday-paradox-to-teach-probability-fundamentals-c08bbcb351d1|Using the birthday paradox to teach probability fundamentals - What are the odds that two of your friends share a birthday?]] Cassie Kozyrkov, Medium, 08/10/2019
+  * [[wp>fr:Principe_des_tiroirs|Principe des tiroirs]]
+  * [[wp>Pigeonhole_principle|Pigeonhole principle]]
+  * Cryptanalyse (informatique)
+    * [[wp>fr:Attaque_des_anniversaires|Attaque des anniversaires]]
+    * [[wp>Birthday_attack|Birthday attack]]
+  * Twitter
+    * [[https://threadreaderapp.com/thread/1192570973439946754.html|Thread by @3blue1brown: "The birthday paradox is very famous in probability. If you take 23 people, there's about a 50/50 chance that two of them share a birthday."]]
+    * [[https://twitter.com/AnecdotesMaths/status/1282691879197450242]]
+Extrait du thread twitter de @3blue1brown et des commentaires :
+<blockquote>
+The birthday paradox is very famous in probability. If you take 23 people, there's about a 50/50 chance that two of them share a birthday. With 50 people, it's a 97% chance. We could make many other fun examples to illustrate the same counterintuitive phenomenon :
+  * Choose a random card from a deck of 52 cards. Put it back, shuffle well, and choose another. Do this for only 9 draws, and more likely than not, you've pulled the same card twice. Do it 16 times, and your chances are over 90%. Try it!
+  * Next time you're in an event with more than 118 people, think to yourself that there's a >50% chance that two people there have phone numbers with the same last four digits (assuming those are uniformly distributed). With more than 250 people, its >95%. Ditto for ATM pin codes.
+  * The number of possible poker hands is 2,598,960. One hand for every person in Chicago, or 10 for each mile between the earth and the moon. How many hands would you think you'd have to draw before you've likely had the same *exact* hand twice?  It's around 1,900 hands that it becomes more likely than not to have held the same hand twice. That's just 19 evenings with 100 hands each. Many (most?) of you reading this have held the same exact poker hand twice!
+  * You can think of the birthday paradox by asking the probability of drawing 23 people successively so that each one has a birthday not yet seen. This gives the probability of no collision, so the probability of a collision is 1 minus this. The general formula for the probability of a collision when making k choices from a collection of N possibilities looks like $1-\frac{N!/(N-k)!}{N^k}$. By using some approximations for the factorials, it so happens that the inflection point where things shift from collisions being very unlikely to instead being likely is around sqrt(N). More specifically, it happens a little above sqrt(N). For example, sqrt(365) = 19.105..., and it's at 23 people that you're more likely to have a birthday collision than not. In the phone numbers example, sqrt(10,000) = 100, and the 50% point happens with 118 people. In the card example, sqrt(52) = 7.2, and it took 9 draws. Specifically, if you have a hash function with N possible outputs (say 2^128), and your system's security depends on collisions never happening, you might initially think an attacker needs around 2^128 brute force attempts, but really it's much *much* smaller: 2^64.
+</blockquote>