3
$\begingroup$

I know that the solution I have is wrong but I'd like to give you my thought process in the hopes that someone can point out the flaw in my thinking:

Since there has to be $j$ balls in the first bucket, I remove $j$ balls from $n$ and one bucket from $k$ and then find the number of ways $n-j$ balls can be randomly distributed into $k-1$ buckets instead.

Using the stars and bars method where there are $n-j$ stars and $k-2$ bars, we get that there are ${n-j+k-2} \choose {k-2}$ ways to find the number of ways $n-j$ balls can be randomly distributed into $k-1$ buckets.

Then I need to find the total number of random ball distributions of all the balls and all the buckets. There are ${n+k-1} \choose {k-1}$ ways to do that using the stars and bars method.

Putting it all together, we get that the probability is ${n-j+k-2} \choose {k-2}$ all over ${n+k-1} \choose {k-1}$.

Where did I go wrong? Is the entire reasoning flawed to begin with or can it be recovered with some tweaks?

I should note that these balls are indistinguishable.

Edit: If I could checkmark everyone's answer I would, but the least I could do is upvote them, thanks everyone for the clarification.

$\endgroup$
  • $\begingroup$ Why do you think your answer is wrong? $\endgroup$ – Joey Kilpatrick Nov 10 '18 at 2:39
  • $\begingroup$ @JoeyKilpatrick this question is very similar to another question found in the textbook Mathematical Statistics and Data Analysis by John Rice, and I found solutions to the question (Ch 1 Q24) here: stat.rice.edu/~kabagg/Stat310/HW/hw1key.pdf The question in the textbook is: If $n$ balls are distributed randomly into $k$ urns, what is the probability that the last urn contains $j$ balls? After subbing in random values for the variables into both equations (mine and the solutions), they result in different probabilities. $\endgroup$ – Hugh N. Nov 10 '18 at 2:45
1
$\begingroup$

Depending on how you mean the balls are "randomly distributed", your answer could be correct or incorrect.

If by "randomly distributed" you mean that each way to distribute the indistinguishable balls is equally likely (i.e. the "stars and bars" distribution $***|*|*|*$ has equal probability to $*|*|**|**$), then your answer is perfect.

If by "randomly distributed" you mean that each ball has a $\frac{1}{n}$ chance of being placed in each of the $n$ buckets, then your answer is not correct. In this case, each "stars and bars" distribution does not have an equal chance of appearing (let me know if you need more clarification).

This is not at all clear in your question or the linked answer key. Let me know if you need more clarification.

$\textbf{EDIT:}$ Consider the "stars and bars" distribution $*|***$ with $2$ buckets and $4$ balls. To make this distribution, we could throw the first ball into the first bucket and the rest into the second bucket. Or we could throw the second ball into the first bucket and the rest into the second bucket. Same with the third and fourth ball. These are four seperate equally likely events with probability $(\frac{1}{n})^4$ each, so this distribution has probability of $4*(\frac{1}{n})^4=\frac{4}{n^4}$. For the distribution $**|**$, we could throw the first and second balls into the first bucket and the rest into the second bucket. Or we could throw the first and third. Or the second and fourth. There are $\binom{4}{2}=6$ options to make this distribution, each with probability $(\frac{1}{n})^4$, so this distribution has probability of $6*(\frac{1}{n})^4=\frac{6}{n^4}$. So these distributions have different probabilities.

$\endgroup$
  • $\begingroup$ I would love for more clarification, thank you! $\endgroup$ – Hugh N. Nov 10 '18 at 2:52
  • $\begingroup$ Also, going through the textbook and coming across a question like 24, how would you know whether or not the stars and bars approach is applicable? Because the question: imgur.com/6TwJgJS does not explain what they mean by randomly distributed. $\endgroup$ – Hugh N. Nov 10 '18 at 2:54
  • $\begingroup$ @HughN. Edited. $\endgroup$ – Joey Kilpatrick Nov 10 '18 at 3:02
  • $\begingroup$ I noticed that you recently (unintentionally) answered a cheating attempt. If you would like to avoid that in the future, one way is to simply not answer any questions that don't include context and effort, because almost every cheating attempt is of that sort, since cheaters are generally lazy. $\endgroup$ – user21820 Nov 10 '18 at 3:30
1
$\begingroup$

The issue is that some distributions of balls will be more likely than others.

For example consider flipping a coin two times. You are more likely to have 1 heads and 1 tails then 2 heads.

Note that I assume that when you say randomly distributed you mean that each ball is independently and uniformly put into one of the bins, one ball at a time.

Basically the idea is this. Each ball has a $\frac 1k$ chance of landing in the first bin and a $\frac {k-1}k$ chance of landing in some other bin. So the number of balls in the first bin is a binomial random variable (https://en.wikipedia.org/wiki/Binomial_distribution). Hence the probability that we have $j$ balls in the first bin is $\binom nj (\frac 1k)^j (\frac {k-1}{k})^{n-j}$

$\endgroup$
  • $\begingroup$ Could you expand on that? If the issue is that some distributions are more likely, how would I account for that in my solution? Is do you have a separate solution entirely? $\endgroup$ – Hugh N. Nov 10 '18 at 2:51
  • $\begingroup$ Hint: Think of the balls as labeled. $\endgroup$ – Mohit Nov 10 '18 at 2:53
1
$\begingroup$

I should note that these balls are indistinguishable.

Consider this: should the result depend on whether the balls are distinguishable or not? It's clear, I think, that it shouldn't. The assumption of distinguishable/indistinguishable balls should only change the counting, not the final result.

Let's first apply your reasoning with distinguishable balls.

For the first bucket we have $\binom{n}{j}$ alternatives, for the rest we have $(k-1)^{n-j}$. Because the total number of alternatives is $k^n$, the result is

$$ p= \frac{\binom{n}{j} (k-1)^{n-j}}{k^n}$$

Assuming instead undistinguishable balls, we get your result. Which is wrong, the above is the correct one.

Why? Because your counting is right, but the computation of probability as favorable cases over total cases is wrong, the events counted (the configurations) are not equiprobable.

Consider for example $n=3$, $j=1$, $k=3$. You get, for the counting of ways of placing 2 (undistinguishable) balls in 2 buckets, the number ${{n-j+k-2} \choose {k-2}}={{3} \choose {1}}=3$. Which is right: ([x x ] [ ]) ([x] [x]) ([] [x x]). But these are not equiprobable. It's readily seen (by considering the balls distinguishable) that the second configuration has double probability.

Now, you might be wondering: why is it ok to consider each (distinguishable) configuration equiprobable? Because of the problem statement. If each of the $n$ balls is placed randomly in one of the $k$ buckets, then each "distinguishable-balls configuration" has the same probability ($k^n$). And because each "undistinguishable-balls configuration" maps to a non-constant number of "distinguishable-balls configuration" (example in previous paragraph), then these configurations are not equiprobable.

Your procedure would be justified only if the balls are thrown in such a way that each "undistinguishable-balls configuration" is equiprobable. But this does not correspond to the (typical) "place $n$ balls randomly into $k$ buckets" scenario.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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