# Birthday Problem: Justify Why $n$ is Greater Than $\frac{365}{2}$

Problem (skip to part d): Ignoring leap days, the days of the year can be numbered $$1$$ to $$365$$. Assume that birthdays are equally likely to fall on any day of the year. Consider a group of $$n$$ people, of which you are not a member. An element of the sample space $$Ω$$ will be a sequence of n birthdays (one for each person).

(a) Define the probability function $$P$$ for $$Ω$$.

(b) Consider the following events: $$A$$: “someone in the group shares your birthday” $$B$$: “some two people in the group share a birthday” $$C$$: “some three people in the group share a birthday” Carefully describe the subset of $$Ω$$ that corresponds to each event.

(c) Find an exact formula for $$P(A)$$. What is the smallest $$n$$ such that $$P(A) > .5$$?

(d) Justify why $$n$$ is greater than $$\frac{365}{2}$$ without doing any computation. (We are looking for a short answer giving a heuristic sense of why this is so.)

Solution provided for part d: While $$\frac{365}{2}$$ different birthdays would have a $$50$$ percent chance of matching your birthday, $$\frac{365}{2}$$ people probably don’t all have different birthdays, so they have a less than $$50$$ percent chance of matching.

My confusion: I get that a person's birthday has a 50% chance of landing in one half of all possible birthdays. How does other people having the same birthday as you affect this fact? And what is the justification for why $$n$$ is greater than $$\frac{365}{2}$$? I understood all other previous parts of the question but on this part I am now lost.

• Surely $n$ is less than $365/2$, not greater. Commented Sep 7, 2023 at 14:50

While $$\frac{365}{2}$$ different birthdays would have a $$50$$ percent chance of matching your birthday

You said that you get how a person's birthday has a $$50\%$$ chance of landing in one half of all possible birthdays. Imagine if $$\frac{365}{2}$$ distinct days were chosen, and then your birthday was randomly chosen (out of all possible days). There's a $$50\%$$ chance your birthday is one of those days. Other people having the same birthday as you doesn't affect this. However,

$$\frac{365}{2}$$ people probably don’t all have different birthdays, so they have a less than $$50$$ percent chance of matching.

There are almost definitely overlaps amongst themselves for the birthdays of the $$\frac{365}{2}$$ people, so they likely don't all have distinct birthdays. Instead, it's less than $$\frac{365}{2}$$ distinct birthdays. Thus, $$n > \frac{365}{2}$$ to make up for this discrepancy.

Given $$n$$ people, for $$k \in \{1,2,\cdots,n\},$$ let $$E_k$$ denote the event that person-$$k$$ shares your birthday. Suppose that you assume $$\color{red}{\text{(incorrectly)}}$$ that these are mutually exclusive events.

That is, you are assuming that it is impossible for any two of the people to both share your birthday. Then, you could reason as follows:

Each person has a $$\frac{1}{365}$$ probability of sharing your birthday. Since the events are mutually exclusive, the probabilities may be added together. Therefore, the probability that in a group of $$n$$ people, exactly one of them shares your birthday is $$~\displaystyle \frac{n}{365}.$$

This analysis, which is based on the incorrect assumption that the events $$E_1, E_2, \cdots, E_n$$ are mutually exclusive, would lead to the conclusion that if $$n = \dfrac{365}{2}$$, then the probability of one of the $$n$$ people sharing your birthday equals $$\dfrac{1}{2}.$$

However, the events $$E_1, E_2, \cdots, E_k$$ are not mutually exclusive. That is, it is possible for more than one person to share your birthday. That is why it is incorrect to simply add the probabilities.

So, now you have the question: if $$n = \dfrac{365}{2}$$ is not the exact answer, is this value of $$n$$ too high or too low? Looking at each person individually, the expectation is that each person has a $$\dfrac{1}{365}$$ probability of sharing your birthday.

This implies that if you have $$n$$ people, the total number of people that you expect to share your birthday is $$\dfrac{n}{365}.$$ Therefore, if $$~n = \dfrac{365}{2}~$$ people, the number of these people that you expect to share your birthday is $$(1/2).$$

That is, if you performed a simulation $$(1000)$$ times, where in each simulation you met with $$~\dfrac{365}{2}~$$ people, you would expect that in all $$1000$$ simulations combined, on average, a total of $$500$$ of these people would share your birthday. However, a small fraction of the time, in these $$1000$$ simulations, instead of there being only $$1$$ person in the group of $$~\dfrac{365}{2}~$$ people who shared your birthday, there would be more than one.

This means that in the $$1000$$ simulations, the $$500$$ people who shared your birthday would be in less than $$500$$ of the $$1000$$ simulations. This means that in the $$1000$$ simulations, you would expect that more than $$500$$ of these $$1000$$ simulations would result in no one sharing your birthday.

Therefore, when $$~n = \dfrac{365}{2},~$$ the probability is less than $$~\displaystyle \dfrac{1}{2}~$$ that someone in the group will share your birthday.

So, if you define $$M$$ as the number of people that need to be in the group such that the probability of (at least) one of these people sharing a birthday with you is $$~\dfrac{1}{2},~$$ then $$M$$ must be greater than $$~\dfrac{365}{2}.$$