2
$\begingroup$

The following, rephrased problem is from the book "Introduction to Probability" on p.35.

I have no solution to this problem and I'm not sure if my solution is correct.

No homework, independent self-study!

Problem: The telephone numbers of k people are randomly and independently assigned to n locations with equal probability (one location can contain more than one number). What is the probability that at least one location contains more than one number?

My solution: Solve the problem by computing the probability that exactly 0 and exactly 1 location(s) contain more than one number, respectively.

  • number of possible outcomes: $n^k$
  • number of favourable outcomes for exactly 0 location containing more than one number: $\binom{n}{k}k!= n \binom{n-1}{k-1}(k-1)!$
  • number of favourable outcomes for exactly 1 location containing more than one number: $\sum_{\color{red}{i=2}}^{k} n \binom{n-1}{k-i}(k-i)!$

Thus, the result should be: $1 - \frac{1}{n^k} \sum_{\color{red}{i=1}}^{k} n \binom{n-1}{k-i}(k-i)!$

Here is some R code for the case $n=10$ and $k=5$, giving a probability of 0.639. Of course, that will blow up for large n, but not the matter here.

n <- 10
k <- 5
sum <- 0.0
for(i in 1:k) sum <- sum + n*choose(n-1, k-i)*factorial(k-i)
1.0 - sum/n^k
> 0.639

Question: Is my approach correct?

EDIT

As Henry said, I'm calculating the probability that at least two locations contain more than one number. Hence, the correct solution should be $1-\frac{1}{n^k} \binom{n}{k}*k!$, I guess.

$\endgroup$
  • $\begingroup$ Probability theory is about the measure-theoretic foundations of stochastics. The tag (probability-theory) should be used for questions concerning this subject, not for questions about calculating a specific probability. Use (probability) instead, see also meta. $\endgroup$ – AlexR Dec 6 '14 at 21:06
  • $\begingroup$ You seem to answering the the question that at least two locations contain more than one number $\endgroup$ – Henry Dec 6 '14 at 21:10
  • $\begingroup$ @ Henry: Damn, you are right! That's why it was harder than first expected. $\endgroup$ – NoBackingDown Dec 6 '14 at 21:52
3
$\begingroup$

Your correction looks correct.

If you want to simulate this in R, the following will do so rather inefficiently

people <- 5
locations <- 10
samplesize <- 10000
atleast1 <- 0
set.seed(2014)
for (i in 1:samplesize){
   if(length(unique(sample(locations, people , replace=TRUE))) != people){
       atleast1 <- atleast1 + 1 
       }
   }
atleast1 / samplesize
1 - choose(locations, people) * factorial(people) / locations^people

giving

> atleast1 / samplesize
[1] 0.7007
> 1 - choose(locations, people) * factorial(people) / locations^people
[1] 0.6976

which are reasonably close

$\endgroup$
  • $\begingroup$ Nice, to just simulate it didn't occur to me, although it's pretty straightforward. Reminds me that I can often use simulation to check for the correctness of a solution. $\endgroup$ – NoBackingDown Dec 7 '14 at 11:57
1
$\begingroup$

Provided that both the "telephone numbers" and the "locations" are distinct, your solution (after Henry's remark) is absolutely correct. It is probably stated in the problem, but it must be true that $k \leq n$, else the probability is $1$. This is commonly known as the Birthday problem. You can read more if you're interested.

If the telephone numbers are considered not distinct, then the number of arrangements such that every location contains at most $1$ number (i.e. the complementary event) is $\displaystyle \binom{n}{k}$ and the total number of arrangements is $\displaystyle \binom{n + k - 1}{k - 1}$ (look at stars and bars), giving us a result of $\displaystyle 1 - \frac{\binom{n}{k}}{\binom{n + k - 1}{k - 1}}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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