Birthday Attack
Q&A1
Q:How many people must be there in a room to make the probability 100% that at-least two people in the room have same birthday?
A: 367 (since there are 366 possible birthdays, including February 29).
The above question was simple. Try the below question yourself.
Q&A2
Q:How many people must be there in a room to make the probability 50% that at-least two people in the room have same birthday?
A: 23
What is the probability that two persons among n have same birthday?
Let the probability that two people in a room with n have same birthday be \(P_{same}\). \(P_{same}\) can be easily evaluated in terms of \(P_{diff}\) where \(P_{diff}\) is the probability that all of them have different birthday.
Persons from first to last can get birthdays in following order for all birthdays to be distinct:
The first person can have any birthday among 365;
The second person should have a birthday which is not same as first person ;
The third person should have a birthday which is not same as first two persons.;
…
The nth person should have a birthday which is not same as any of the earlier considered (n-1) persons.
Then We get the following expression:
\[P_{same} = 1 – P_{diff}\\ P_{diff} = 1\times \dfrac{364}{365} \times \dfrac{363}{365}\times \cdots \times \dfrac{366-n}{365} \]Approximation of above expression
The above expression can be approximated using Taylor’s Series.
$e^{x}=1+x+\frac{ x^{2} }{2!}+\cdots $
provides a first-order approximation for \(e^x\) for \(x << 1\):
\(e^{x}\approx 1+x\)
To apply this approximation to the first expression derived for \(P_{diff}\), set \(x = -\dfrac{a}{365}\). Thus,
\(e^{-\frac{a}{365}}\approx 1-\dfrac {a}{365}\)
The above expression derived for \(P_{diff}\) can be written as
\(1\times (1-\dfrac{1}{365})\times (1-\dfrac{2}{365}) \times \cdots \times (1-\dfrac{n-1}{365})\)
By putting the value of \(1-\dfrac{i}{365}\)as \(e^{-\frac{i}{365}}\), we get following.
\[\begin{aligned} P_{diff} &= 1\times (1-\dfrac{1}{365})\times (1-\dfrac{2}{365}) \times \cdots \times (1-\dfrac{n-1}{365})\\ &\approx 1\times e^{-\frac{1}{365}}\times e^{-\frac{2}{365}}\times \cdots \times e^{-\frac{n-1}{365}}\\ &\approx e^{-\frac{n(n-1)/2}{365}} \end{aligned} \]Therefore,
\[P_{same} = 1- P_{diff} \approx 1 - e^{-\frac{n(n-1)/2}{365}} \approx 1- e ^{-\frac{n^2}{365\times 2}} \]By taking Log on both sides, we get the reverse formula.
\[n \approx \sqrt{2\times 365\ln\left(\frac{1}{1-P_{same}}\right)} \]Using the above approximate formula, we can approximate number of people for a given probability.
Code implementation
# Approximate number of people in Birthday Paradox problem
import math
def birthAttack1(p: float) -> int:
n = 0
pt = 1
num = 365
while pt > (1-p):
pt *= (num / 365)
num -= 1
n += 1
return n
def birthAttack2(p: float) -> int:
return math.ceil(math.sqrt(2 * 365 * math.log(1/(1-p))));
if __name__ == "__main__":
print(birthAttack1(0.5))
print(birthAttack2(0.5))