Editing Birthday problem (section)

==Other birthday problems==

===First match===
A related question is, as people enter a room one at a time, which one is most likely to be the first to have the same birthday as someone already in the room?  That is, for what {{mvar|n}} is {{math|''p''(''n'') − ''p''(''n''&nbsp;−&nbsp;1)}} maximum?  The answer is 20—if there is a prize for first match, the best position in line is 20th.{{citation needed|date=September 2019}}

===Same birthday as you===
[[Image:Birthday paradox.svg|thumb|right|upright=1.4|Comparing {{math|''p''(''n'')}} = probability of a birthday match with {{math|''q''(''n'')}} = probability of matching ''your'' birthday]]
In the birthday problem, neither of the two people is chosen in advance. By contrast, the probability {{math|''q''(''n'')}} that ''at least one other person'' in a room of {{mvar|n}} other people has the same birthday as a ''particular'' person (for example, you) is given by

: <math> q(n) = 1 - \left( \frac{365-1}{365} \right)^n </math>
and for general {{mvar|d}} by
: <math> q(n;d) = 1 - \left( \frac{d-1}{d} \right)^n. </math>

In the standard case of {{math|''d'' {{=}} 365}}, substituting {{math|''n'' {{=}} 23}} gives about 6.1%, which is less than 1 chance in 16.  For a greater than 50% chance that ''at least'' one other person in a roomful of {{mvar|n}} people has the same birthday as ''you'', {{mvar|n}} would need to be at least 253. This number is significantly higher than {{math|{{sfrac|365|2}} {{=}} 182.5}}: the reason is that it is likely that there are some birthday matches among the other people in the room.

=== Number of people with a shared birthday ===
For any one person in a group of ''n'' people the probability that he or she shares his birthday with someone else is <math> q(n-1;d) </math>, as explained above. The expected number of people with a shared (non-unique) birthday can now be calculated easily by multiplying that probability by the number of people (''n''), so it is:
: <math> n\left(1 - \left( \frac{d-1}{d} \right)^{n-1}\right) </math> 
(This multiplication can be done this way because of the linearity of the [[expected value]] of indicator variables). This implies that the expected number of people with a non-shared (unique) birthday is:
: <math> n \left( \frac{d-1}{d} \right)^{n-1} </math> 
Similar formulas can be derived for the expected number of people who share with three, four, etc. other people.

=== Number of people until every birthday is achieved ===
The expected number of people needed until every birthday is achieved is called the [[Coupon collector's problem]]. It can be calculated by {{math|''nH<sub>n</sub>''}}, where {{math|''H<sub>n</sub>''}} is the {{mvar|n}}th [[harmonic number]]. For 365 possible dates (the birthday problem), the answer is 2365.

===Near matches===
Another generalization is to ask for the probability of finding at least one pair in a group of {{mvar|n}} people with birthdays within {{mvar|k}} calendar days of each other, if there are {{mvar|d}} equally likely birthdays.<ref name="abramson">M. Abramson and W. O. J. Moser (1970) ''More Birthday Surprises'', [[American Mathematical Monthly]] '''77''', 856–858</ref>

:<math> \begin{align} p(n,k,d) &= 1 - \frac{ (d - nk -1)! }{ d^{n-1} \bigl(d - n(k+1)\bigr)!}\end{align} </math>

The number of people required so that the probability that some pair will have a birthday separated by {{mvar|k}} days or fewer will be higher than 50% is given in the following table:

:{| class="wikitable" style="text-align: center"
! {{mvar|''k''}} !! {{mvar|n}}<br />for {{math|''d'' {{=}} 365}}
|-
|0 || 23
|-
|1 || 14
|-
|2 || 11
|-
|3 || 9
|-
|4 || 8
|-
|5 || 8
|-
|6 || 7
|-
|7 || 7
|}

Thus in a group of just seven random people, it is more likely than not that two of them will have a birthday within a week of each other.<ref name="abramson"/>

=== Number of days with a certain number of birthdays ===

==== Number of days with at least one birthday ====
The expected number of different birthdays, i.e. the number of days that are at least one person's birthday, is:
:<math>d - d \left (\frac {d-1} {d} \right )^n </math>
This follows from the expected number of days that are no one's birthday:
:<math>d \left (\frac {d-1} {d} \right )^n </math>
which follows from the probability that a particular day is no one's birthday, {{math|{{pars|s=150%|{{sfrac|''d'' − 1|''d''}}}}{{su|p=''n''|b=&nbsp;}}}}, easily summed because of the linearity of the expected value.

For instance, with {{math|1={{var|d}} = 365}}, you should expect about 21 different birthdays when there are 22 people, or 46 different birthdays when there are 50 people. When there are 1000 people, there will be around 341 different birthdays (24 unclaimed birthdays).

==== Number of days with at least two birthdays ====
The above can be generalized from the distribution of the number of people with their birthday on any particular day, which is a [[Binomial distribution]] with probability {{math|{{sfrac|1|''d''}}}}. Multiplying the relevant probability by {{mvar|d}} will then give the expected number of days. For example, the expected number of days which are shared; i.e. which are at least two (i.e. not zero and not one) people's birthday is:

<math display="block">d - d \left (\frac {d-1} {d} \right )^n - d \cdot \binom{n}{1} \left (\frac {1} {d} \right )^1\left (\frac {d-1} {d} \right )^{n-1} = d - d \left (\frac {d-1} {d} \right )^n - n \left (\frac {d-1} {d} \right )^{n-1} </math>

===Number of people who repeat a birthday===
The probability that the {{mvar|k}}th integer randomly chosen from {{math|[1,''d'']}} will repeat at least one previous choice equals {{math|''q''(''k'' − 1; ''d'')}} above. The expected total number of times a selection will repeat a previous selection as {{mvar|n}} such integers are chosen equals<ref>{{cite web|last1=Might|first1=Matt|title=Collision hash collisions with the birthday paradox|url=http://matt.might.net/articles/counting-hash-collisions/|website=Matt Might's blog|access-date=17 July 2015}}</ref>

:<math>\sum_{k=1}^n q(k-1;d) = n - d + d \left (\frac {d-1} {d} \right )^n</math>
This can be seen to equal the number of people minus the expected number of different birthdays.

===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.

===Reverse problem===
The reverse problem is to find, for a fixed probability {{mvar|p}},
the greatest {{mvar|n}} for which the probability {{math|''p''(''n'')}} is smaller than the given {{mvar|p}}, or the smallest {{mvar|n}} for which the probability {{math|''p''(''n'')}} is greater than the given {{mvar|p}}.{{citation needed|date=September 2019}}

Taking the above formula for {{math|''d''&nbsp;{{=}}&nbsp;365}}, one has

:<math>n(p;365)\approx \sqrt{730\ln\left(\frac{1}{1-p}\right)}.</math>

The following table gives some sample calculations.
:{| class="wikitable"
|-----
! {{mvar|p}} || {{mvar|n}}
! {{math|''n''↓}} || {{math|''p''(''n''↓)}} || {{math|''n''↑}} || {{math|''p''(''n''↑)}}
|-----
| <span style="color:maroon">0.01</span>
| 0.14178{{sqrt|365}} = <span style="color:maroon">2.70864</span>
| align="right" | 2 || 0.00274 || align="right" | 3
| <span style="color:maroon">0.00820</span>
|-----
| 0.05 || 0.32029{{sqrt|365}} = 6.11916
| align="right" | 6 || 0.04046 || align="right" | 7 || 0.05624
|-----
| <span style="color:maroon">0.1</span>
| 0.45904{{sqrt|365}} = <span style="color:maroon"> 8.77002</span>
| align="right" | 8 || 0.07434 || align="right" | 9
| <span style="color:maroon">0.09462</span>
|-----
| <span style="color:maroon">0.2</span>
| 0.66805{{sqrt|365}} = <span style="color:maroon">12.76302</span>
| align="right" | 12 || 0.16702 || align="right" | 13
| <span style="color:maroon">0.19441</span>
|-----
| 0.3 || 0.84460{{sqrt|365}} = 16.13607
| align="right" | 16 || 0.28360 || align="right" | 17 || 0.31501
|-----
| 0.5 || 1.17741{{sqrt|365}} = 22.49439
| align="right" | 22 || 0.47570 || align="right" | 23 || 0.50730
|-----
| 0.7 || 1.55176{{sqrt|365}} = 29.64625
| align="right" | 29 || 0.68097 || align="right" | 30 || 0.70632
|-----
| 0.8 || 1.79412{{sqrt|365}} = 34.27666
| align="right" | 34 || 0.79532 || align="right" | 35 || 0.81438
|-----
| 0.9 || 2.14597{{sqrt|365}} = 40.99862
| align="right" | 40 || 0.89123 || align="right" | 41 || 0.90315
|-----
| 0.95 || 2.44775{{sqrt|365}} = 46.76414
| align="right" | 46 || 0.94825 || align="right" | 47 || 0.95477
|-----
| <span style="color:maroon">0.99</span>
| 3.03485{{sqrt|365}} = <span style="color:maroon">57.98081</span>
| align="right" | 57
| <span style="color:maroon">0.99012</span>
| align="right" | 58 || 0.99166
|}
Some values falling outside the bounds have been <span style="color:maroon">colored</span> to show that the approximation is not always exact.