Editing Birthday problem (section)

===Average number of people to get at least one shared birthday===
In an alternative formulation of the birthday problem, one asks the ''average'' number of people required to find a pair with the same birthday. If we consider the probability function Pr[{{mvar|n}} people have at least one shared birthday], this ''average'' is determining the [[mean]] of the distribution, as opposed to the customary formulation, which asks for the [[median]].  The problem is relevant to several [[hash function|hashing algorithms]] analyzed by [[Donald Knuth]] in his book ''[[The Art of Computer Programming]]''. It may be shown<ref name="knuth73">{{cite book |first=D. E. |last=Knuth |title=The Art of Computer Programming |volume=3, Sorting and Searching |publisher=Addison-Wesley |location=Reading, Massachusetts |year=1973 |isbn=978-0-201-03803-3 }}</ref><ref name="flajolet95">{{cite journal |first1=P. |last1=Flajolet |first2=P. J. |last2=Grabner |first3=P. |last3=Kirschenhofer |first4=H. |last4=Prodinger |year=1995 |title=On Ramanujan's Q-Function |journal=Journal of Computational and Applied Mathematics |volume=58 |pages=103–116 |doi=10.1016/0377-0427(93)E0258-N |doi-access=free }}</ref> that if one samples uniformly, with replacement, from a population of size {{math|''M''}}, the number of trials required for the first repeated sampling of ''some'' individual has [[expected value]] {{math|{{overline|''n''}} {{=}} 1 + ''Q''(''M'')}}, where

: <math>Q(M)=\sum_{k=1}^M \frac{M!}{(M-k)! M^k}.</math>

The function

: <math>Q(M)= 1 + \frac{M-1}{M} + \frac{(M-1)(M-2)}{M^2} + \cdots + \frac{(M-1)(M-2) \cdots 1}{M^{M-1}}</math>
<!-- Shouldn't this sum be up to M ? Without it the term M!/M^M is missing-->
has been studied by [[Srinivasa Ramanujan]] and has [[asymptotic expansion]]:

: <math>Q(M)\sim\sqrt{\frac{\pi M}{2}}-\frac{1}{3}+\frac{1}{12}\sqrt{\frac{\pi}{2M}}-\frac{4}{135M}+\cdots.</math>

With {{math|1=''M'' = 365}} days in a year, the average number of people required to find a pair with the same birthday is {{math|1={{overline|''n''}} = 1 + ''Q''(''M'') ≈ 24.61659}}, somewhat more than 23, the number required for a 50% chance. In the best case, two people will suffice; at worst, the maximum possible number of {{math|1=''M'' + 1 = 366}} people is needed; but on average, only 25 people are required

An analysis using indicator random variables can provide a simpler but approximate analysis of this problem.<ref>{{Cite book|title=Introduction to Algorithms|last=Cormen |display-authors=etal }}</ref> For each pair (''i'', ''j'') for k people in a room, we define the indicator random variable ''X<sub>ij</sub>'', for <math>1\leq i \leq j\leq k</math>, by

<math display="block">\begin{alignat}{2}
X_{ij} & 
= I \{ \text{person }i\text{ and person }j\text{ have the same birthday} \} \\[10pt] & 
= \begin{cases} 
1, & \text{if person }i\text{ and person }j\text{ have the same birthday;} \\ 
0, & \text{otherwise.}
\end{cases}
\end{alignat}</math>

<math display="block">\begin{alignat}{2}
E[X_{ij}] & 
= \Pr \{ \text{person }i\text{ and person }j\text{ have the same birthday} \} = \frac{1}{n}.
\end{alignat}</math>

Let ''X'' be a random variable counting the pairs of individuals with the same birthday.

<math display="block">X =\sum_{i=1}^k \sum_{j=i+1}^k X_{ij}</math>

<math display="block">\begin{alignat}{3}
E[X] 
& = \sum_{i=1}^k \sum_{j=i+1}^k E[X_{ij}]\\[8pt]
& = \binom{k}{2} \frac{1}{n}\\[8pt]
& = \frac{k(k-1)}{2n}
\end{alignat}</math>

For {{math|1=''n'' = 365}}, if {{math|1=''k'' = 28}}, the expected number of pairs of individuals with the same birthday is {{sfrac|28 × 27|2 × 365}}&nbsp;≈&nbsp;1.0356. Therefore, we can expect at least one matching pair with at least 28 people.

In the [[2014 FIFA World Cup]], each of the 32 squads had 23 players.  An analysis of the official squad lists suggested that 16 squads had pairs of players sharing birthdays, and of these 5 squads had two pairs: Argentina, France, Iran, South Korea and Switzerland each had two pairs, and Australia, Bosnia and Herzegovina, Brazil, Cameroon, Colombia, Honduras, Netherlands, Nigeria, Russia, Spain and USA each with one pair.<ref>{{cite web |url=https://www.bbc.co.uk/news/magazine-27835311 |title=The birthday paradox at the World Cup |last1=Fletcher |first1=James |date=16 June 2014 |website=bbc.com |publisher=BBC |access-date=27 August 2015 }}</ref>

Voracek, Tran and [[Anton Formann|Formann]] showed that the majority of people markedly overestimate the number of people that is necessary to achieve a given probability of people having the same birthday, and markedly underestimate the probability of people having the same birthday when a specific sample size is given.<ref>{{cite journal |last1=Voracek |first1=M. |last2=Tran |first2=U. S. |last3=Formann |first3=A. K. |year=2008 |title=Birthday and birthmate problems: Misconceptions of probability among psychology undergraduates and casino visitors and personnel |journal=Perceptual and Motor Skills |volume=106 |issue=1 |pages=91–103 |doi=10.2466/pms.106.1.91-103 |pmid=18459359 |s2cid=22046399 }}</ref> Further results showed that psychology students and women did better on the task than casino visitors/personnel or men, but were less confident about their estimates.