Suppose that there are n guests at a Halloween party, and that each is wearing one of 200 possible costumes available at local store, uniformly at random and independently of all other guests. Using Poisson approximation and the value $\sqrt{\log{2}}$ = $0.83$, show that only about n = 17 guests are needed to ensure that some pair of guests are wearing the same costume with probabiliy at least 50%.
The hint I received for this question was: "This approximation is quite accurate. It can be shown that, when $n = 17$, the true probability of a match is $1 − (200)_{17}/200^{17}$ = 50.3%."
I interpreted this question as one similar to the "Birthday Problem" often discussed in probability theory courses. But I'm not sure how to handle/incorporate the Poisson approximation and 'uniformly at random' aspects of this problem. It would be great to hear any insight as to how I could possibly structure this problem—thank you!
$\mathrm{Uniformly \ at \ random}$ means the exact same thing as in the birthday problem : you have $n$ people, and each person's costume can be any of the $200$ available costumes with equal probability (so for example, if you were among the people , then a Hulk costume with crusted diamonds on the sleeves would appeal to you as much as a clown costume made of flimsy material with the nose cut off). Furthermore, each person's costume is independent of the others : for example, if you, your friend and your enemy are among the people, then your choice should not be influenced by either of them, and their choices by you.
The approach for the birthday problem is also the same : we find the probability that any pair of two people do not have the same costume. The opposite of this is what we seek, and we easily obtain it by subtracting the probability of the undesired event from $1$.
So let us try to calculate the size of the event that no two have the same costume out of $n$ people. This is simple : choose $n$ costumes out of $200$ in $^{200}P_n = \frac{(200)!}{(200-n)!}$ ways (we require permutations here, because in the sample space we choose , order matters), and distribute these costumes to the $n$ people in some order . This ensures that no pair has the same costume.
Conversely, if no two people have the same costume, then the set of all costumes chosen is a set of $n$ costumes, so belongs in the choice above.
In short, we have shown that the unfavourable event has size $^{200}P_{n}$.
Now, the entire sample space has size $(200)^{n}$, because each person can choose $200$ costumes and there are $n$ of them. (Note that the sample space is ordered, because any element of the sample space is a tuple, consisting of what the first person chose, what the second person chose and so on. This is why we need permutations in the event calculation as well.)
So the undesirable has probability $\frac{^{200}P_n}{200^n}$. The desirable has probability $1 - \frac{^{200}P_n}{200^n}$.
The Poisson approximation to the binomial provides a good estimate of binomial quantities in terms of exponential ones. In particular, if the number of trials $n$ is large, this approximation is suitable.
In the context of this problem, we have Binomial trials with different success probabilities going on. Let me explain.
Let us call a person's choice as "success" if it does not match with any of the previous people's choices. Then, the first person always succeeds. The second person succeeds with probability $\frac {199}{200}$. The third person succeeds with probability $\frac {198}{200}$ if the previous two succeed, and so on.
Finally, the probability that $n$ people succeeds is the product of these : $\frac{200 \times 199 \times 198 \times ... \times (200-n+1)}{200}$. However, this is also the success probability of $n$ Bernoulli trials, where the first fails with probability $0$, the second with probability $\frac{1}{200}$ and so on. (The reason I changed succeeds to fails in the context will be made clear shortly.)
Each of these can be approximated by the Poisson random variable.
Recall that $\mbox{Bin}(n,p) \approx \mbox{Poi}(np)$. We have various trials with different $p$, so in each we would have $n=1$. The first is $n=1,p=0$. The second is $n=1,p=\frac{1}{200}$ and so on.
So, the probability that each such trial succeeds(which is to say , that Binomial random variable equals one), is the probability that the Poisson random variable approximating that trial has outcome $0$. This is easily found as $e^{-p}$ from the definition of the PRV. So each trial succeeds with probability $e^{-p}$.
Finally, the answer would just be $$ e^{-0}e^{-\frac{1}{200}}e^{-\frac{2}{200}} \ldots e^{-\frac{n-1}{200}} = e^{-\frac{n(n-1)}{400}} $$
Now, we must check when this crosses $0.5$. Let us write it down as equality and manipulate it: $$ e^{\frac{-(n-2)(n-1)}{400}} = 0.5 \implies n(n-1) = 400 \ln 2 \approx 275.56 $$
from the given data. Now, one easily checks that $17 \times 16 = 272$ is just to the left of this figure. So the answer should be very close to $17$, as predicted.
NOTE : The Poisson approximation to the binomial , in this context is essentially the use of the approximation $1-x \approx e^{-x}$ used with $x = 0, x= \frac 1{200}$ and so on.