2
$\begingroup$

Suppose that $n$ people are each randomly assigned a number from $1$ to $m$ with replacement. What is the probability that exactly one number is assigned to more than one person?

What I have tried:

Defining the event $A$ to be 'exactly one number is assigned to more than one person', I can see that the probability of $A$ is $0$ when $m=n$ and $1$ when $m<n$. For $m>n$, the sample space would be $m^n$. I have written out the sample space for $n=3$ and $m=4$. In this case, $P(A)=40/64=5/8$. However, I cannot see how to compute the number of sample points in the general case.

$\endgroup$
6
  • 1
    $\begingroup$ It seems to be a homework, so you should add [self-study] tag and tell us what have you tried, where are you stuck, and what help you need. $\endgroup$
    – Tim
    Commented Feb 14, 2023 at 20:25
  • 1
    $\begingroup$ @Tim Thanks, I've added your suggestions $\endgroup$
    – Brandon
    Commented Feb 14, 2023 at 20:35
  • $\begingroup$ The probability of $A$ is not $0$ when $m=n$; consider $m=n=3$, with assignments $(1,1,2)$. It is also not $1$ when $m < n$; consider $m=3, n=4$ with assignments $(1,1,2,2)$. $\endgroup$
    – jbowman
    Commented Feb 14, 2023 at 20:42
  • $\begingroup$ See this related question on the occupancy statistic stats.stackexchange.com/questions/605146/… $\endgroup$ Commented Feb 14, 2023 at 20:44
  • $\begingroup$ @jbowman ah I see my error was only checking cases where m=1 $\endgroup$
    – Brandon
    Commented Feb 14, 2023 at 20:53

1 Answer 1

4
$\begingroup$

The sample space is \begin{align} \Omega = \{(N_1, N_2, \ldots, N_n): N_i \in \{1, \ldots, m\}, 1 \leq i \leq n\}. \end{align} Clearly, $|\Omega| = m^n$.

To determine the probability of interest $P(A) = |A|/|\Omega|$, it suffices to count $|A|$. Suppose $m \geq n$. Note that if $k \in \{1, \ldots, m\}$ is the "exactly one number" that is assigned to more than one person, then $k$ can be assigned to $2, 3, \ldots, n$ people. In view of this, $|A|$ can be then determined by applying the rule of product and the rule of sum.

In detail, there are $\binom{m}{1}$ ways of choosing $k$ that will be assigned to $j$ ($2 \leq j \leq n$) people. Once $k$ is chosen, there are $\binom{n}{j}$ ways to assign it to $j$ people picked randomly from a cohort of $n$ people, and $\binom{m - 1}{n - j} \times (n - j)!$ ways of assigning the remaining $n - j$ people each a distinct number. It then follows by the rule of product that the number of ways of assigning exactly one number to $j$ people ($2 \leq j \leq n$) is: \begin{align} \binom{m}{1} \times \binom{n}{j} \times \binom{m - 1}{n - j} \times (n - j)!. \end{align}

By the rule of sum: \begin{align} |A| = \binom{m}{1}\sum_{j = 2}^n \binom{n}{j}\binom{m - 1}{n - j}(n - j)!. \end{align}

I am not sure though, if $|A|$ can be further simplified.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.