1
$\begingroup$

I am trying to learn more about probability and came across an interesting question that I am stuck on and can no longer find online. There are 20 numbered balls and 10 bins. Someone is trying to assign the balls to the bins, but does it with replacement on accident.

So they did the following: Place a ball in bin 1, record it, then remove ball (with replacement remember). Place a ball in bin 2, record it, then remove ball. Place a ball in bin 3, record it, then remove ball. So for each bin, you have put in 1 ball. There are ten bins, therefore you do that process once for every bin. Once you have done that the experiment is over.

What is the probability exactly 1 ball was assigned to exactly 4 bins? What is the probability at least 2 bins received the same ball?

A) 1 Ball in 4 Bins:

We have ${20 \choose 1}$ being the different ways we can choose the 1 ball that was assigned. Also, we have ${19 \choose 6}$ being the different ways the other 19 balls can be picked for assignment. However, what is the sample size? Would it be $20^{10}$? Thus the answer would be $\frac{{20 \choose 1}{19 \choose 6}}{20^{10}}$.

B) Probability of at least 2 repeated can be represented as $1-P(\text{Zero Repeated})- P(\text{One Repeated})$. So $P(0) = {20 \choose 10}/20^{10}$ and $P(1) = \frac{{20 \choose 1}{19 \choose 9}}{20^{10}}$. Then we can plug and chug.

Are these right? Is this how to think about this type of problem?

$\endgroup$
15
  • $\begingroup$ What is the min/max number of bins each ball can be assigned to? I assume all bins are distinguishable $\endgroup$
    – Alex
    Jun 4, 2020 at 14:46
  • $\begingroup$ The min and max number of balls to a bin is 1. But as the question stated, it was done with replacement by accident. So the user put a ball into one bin, recorded it, took it out, and moved onto the next bin. I know it sounds odd. $\endgroup$ Jun 4, 2020 at 14:51
  • $\begingroup$ For A, you mean exactly 4 bins or at least 4 bins? Also, are the bins numbered? Or indistinguishable? $\endgroup$
    – Phicar
    Jun 4, 2020 at 15:20
  • $\begingroup$ exactly 4 bins for A. So for example, Ball 1 was placed in bins 1-4 and Balls 2-19 placed in bins 5-10 would be 1 way this event occured from my understanding. $\endgroup$ Jun 4, 2020 at 15:21
  • $\begingroup$ "but does it with replacement on accident." The key question is: how many assignments is done? To understand that this is important imagine that there were only one assignment. $\endgroup$
    – user
    Jun 4, 2020 at 16:59

2 Answers 2

1
$\begingroup$

After clarification of the question it can be answered as following:

  1. What is the probability that exactly 1 ball was assigned to exactly 4 bins?

We have $\binom{20}{1}$ ways to choose the "4-fold" ball and $\binom{10}{4}$ ways to choose the bins where it should go. The other 6 bins can be arbitrarily filled with remaining 19 balls. Hence the overall number of combinations is: $$ \binom{20}{1}\binom{10}{4}19^6. $$ In this way we however double-count the cases where there are two balls each assigned to exactly 4 bins. There are $\binom{20}{2}$ such pairs and $\binom{10}4\binom{6}4$ ways to choose corresponding bins. The other 2 bins can be filled arbitrarily with remaining 18 balls. Bringing everything together the final result is: $$ \frac{\binom{20}{1}\binom{10}{4}19^6-\binom{20}{2}\binom{10}{4}\binom{6}{4}18^2}{20^{10}}. $$

  1. What is the probability at least 2 bins received the same ball?

The simplest way to answer this question is to use complementary probability of the event "all bins receive different balls": $$ 1-\frac{\frac{20!}{10!}}{20^{10}}. $$ Replacement of $\frac{20!}{10!}$ with $\binom{20}{10}$ would be wrong here, since after choosing $10$ balls out of $20$ there are still $10!$ ways to assign the balls to certain bins.

$\endgroup$
4
  • $\begingroup$ This makes sense. However, for 1, why do we care about the 10c4 ways to choose the bins? We do not care about the order of those bins. Also can you explain why there are 20c2 pairs and 10c4*6c4 ways to choose corresponding bins? $\endgroup$ Jun 5, 2020 at 13:20
  • 1
    $\begingroup$ In 1 all these bins "contain" the same ball. Therefore permutation of the balls between the bins does not change anything. In 2 all bins contain different balls and any permutation creates a new arrangement. The fact that $\binom{20}2$ is the number of ways to choose a pair from 20 elements is due to combinatorial definition of the binomial coefficients. $\binom{10}{6}\binom{6}4$ is because you choose first 4 bins (out of 10) for one ball and then 4 (out of 6 remaining) for the other ball. $\endgroup$
    – user
    Jun 5, 2020 at 13:34
  • $\begingroup$ For 1, why is number of events not the same as 2? You have $10!*20^10$ and $20^10$. Also what if the probability was at least 3 bins received the same ball? Is there a general formula? $\endgroup$ Jun 5, 2020 at 15:18
  • 1
    $\begingroup$ The number of events is the same. If you'd like I can rewrite the expression as $1-\frac{\frac{20!}{10!}}{20^{10}}$. $\endgroup$
    – user
    Jun 5, 2020 at 15:25
0
$\begingroup$

The way I understand from the comments is that you are modeling this is by a function $f:\{\text{bins}\}\longrightarrow \{\text{balls}\}$ in which you take a bin and you assign a ball to it, they can have the same ball(replacement). so there are indeed $20^{10}$ possible functions.

Now, for A, you pick the ball in $\binom{20}{1}=20$ ways and then you choose the other $6$ bins. But you are assuming those are going each to a different bin and you are not considering different orderings. This contradicts the supposition of replacement. This seems a little more involved that what you propose, because you need to know that you are not overcounting possibilities. I would use the Inclusion Exclusion Principle to compute $\left |\bigcup _{i=1}^{20}A_i\right |,$ where $A_i = \{\text{The i-th ball was assigned to 4 bins}\}.$ Notice that $|A_i|=\binom{10}{4}19^{6}.$ For 2 $|A_i\cap A_j|=\binom{10}{4}\binom{6}{4}(20-2)^{2}.$ Can you have $3$ balls going to $4$ bins? No, so you just have to combine this two possibilities.

For B, You want to take out the functions that are one to one because if a function is not one to one then 2 bins were going to the same ball. So the probability would be $$1-\frac{\binom{20}{10}}{20^{10}}$$

$\endgroup$
4
  • $\begingroup$ Only 1 ball goes into 1 bin at a time. So the user put a ball into one bin, recorded it, took it out, and moved onto the next bin. I know it sounds odd. $\endgroup$ Jun 4, 2020 at 16:46
  • $\begingroup$ Yes, that is why the function goes from bins to balls and not backwards. $\endgroup$
    – Phicar
    Jun 4, 2020 at 16:52
  • $\begingroup$ okay, I was answering the can you have 3 balls in 4 bins question. $\endgroup$ Jun 4, 2020 at 16:53
  • 1
    $\begingroup$ Sorry, the question is could you have recorded $3$ different balls each one in $4$ possible different bins? Well, no, because you would need $12$ bins at least. $\endgroup$
    – Phicar
    Jun 4, 2020 at 17:01

You must log in to answer this question.

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