2
$\begingroup$

I have to calculate the probability of n people out of N that choose the exact same object, among k objects. I am trying to figure out if this could be a modified version of the Birthday problem, or if it is a Bernoulli process.

What I have at the moment is the following:

$P = 1 - \frac{k!}{k^n(k-n)!}$

Since the first people will choose an object with probability $\frac{k}{k} = 1$, the second person not to choose the same number will have $\frac{k-1}{k}$ and so on. So, if I do 1 - this probability, I should get my answer.

I am not sure whether this is right or not. Does somebody have an idea about this?

$\endgroup$
4
  • $\begingroup$ If everyone has made a choice then $n_{i}$ of the $N$ persons will have chosen for object $i$. This with $n_{1}+\cdots+n_{k}=N$. Can you say what condition must be satisfied in terms of the $n_{i}$? Do you want to find the probability that $n\in\left\{ n_{1},\dots,n_{k}\right\} $? $\endgroup$
    – drhab
    Apr 29, 2014 at 9:19
  • $\begingroup$ I want to find the probability that $k$ persons choose $i$. $\endgroup$
    – lbedogni
    Apr 29, 2014 at 9:24
  • $\begingroup$ In your question you speak of $n$ persons, not $k$. $\endgroup$
    – drhab
    Apr 29, 2014 at 9:25
  • $\begingroup$ Sorry, I want $n$ person, not $k$. $\endgroup$
    – lbedogni
    Apr 29, 2014 at 10:26

1 Answer 1

1
$\begingroup$

This seems like a Binomial probability problem. Ignore the first person for the moment. Each person after them picks an object independently, and you want exactly $n - 1$ of them to pick a particular object (the same one the first person picked). The probability of any one person doing that is just $\frac{1}{k}$. There's a total of $N - 1$ people (attempts), and $N - 1 - (n - 1) = N - n$, so we get:

$$P = {N-1 \choose n-1} \left(\frac{1}{k} \right)^{n-1} \left(\frac{k - 1}{k}\right)^{N - n} $$

Then we need to consider the first person again. I've assumed they are literally the first person to choose, when they could be any of the $N$ people. So, we need to multiply the above by $N$.

nb. All of this assumes that it doesn't matter what all of the other $N - n$ people pick, so long as it's different from the 'first' choice. I don't know exactly what would need to change if you need the $N - n$ people to choose different objects to each other as well.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .