4
$\begingroup$

Stars and bars is a common technique used in combinatorics. It asserts that the number of ways to put $n$ indistinguishable balls into $k$ distinguishable bins is given by:

$$ n + k - 1 \choose k - 1 $$

I've seen this count used frequently to calculate probabilities but after some thought, I am slightly skeptical as to whether or not each of the counts given by the stars and bars has a equal probability of occurring.

Lets consider the case with 3 balls and 2 bins. I will represent different arrangements of balls with $(n_1, n_2)$ being the case where there are $n_1$ balls in bin 1 and $n_2$ balls in bin 2. Naturally, we have $0 \leq n_1, n_2 \leq 3$ and $n_1 + n_2 = 3$.

We can compute the probability of $P(0,3)$, $P(1,2)$, $P(2,1)$, and $P(3,0)$ as follows. Label each of the balls so that there are $2^3 = 8$ different equally likely arrangements.

Of these arrangements, there is only $1$ way to put $0$ balls in bin 1. There are $3$ ways to $1$ ball into bin 2, and the other two cases are symmetrical. Hence:

$$P(0,3) = 1/8 \qquad P(1,2) = 3/8$$

This shows that the different items counted in stars and bars do not occur with equal probability.

If someone would be so kinda, could you confirm this work? I believe that I have seen the usage of stars and bars to count the number of possibilities for use in the denominator of probability problems. Am I right in thinking that such a practices is incorrect?

$\endgroup$
  • 4
    $\begingroup$ It is not necessarily incorrect. But I would agree that it is often incorrect. We have to start with a probabilistic model of how the balls got into the bins. In many (most?) cases has the balls thrown towards the bins one at a time, independently, with a ball equally likely to land in any bin. For that model, the various possibilities counted by Stars and Bars are, as you point out, not equally likely. $\endgroup$ – André Nicolas Oct 15 '15 at 18:42
  • $\begingroup$ Stars and bars is just used to count the ways to put the balls into the bins. Didn't you just do the same thing when you determined the probabilities $P(n_1,n_2)$? $\endgroup$ – John Douma Oct 15 '15 at 19:10
1
$\begingroup$

It's hard to say something specific, since you merely say (you believe) you've seen this and there's no specific calculation to analyze. You're certainly right that if classical balls are placed into bins independently and uniformly, it would be wrong to consider the bin count tuples counted by the binomial coefficient you mention as equiprobable.

It may be worthwhile mentioning, however, that bosons are correctly described by these statistics, the so-called Bose–Einstein statistics. They are more fundamentally "indistinguishable" than classical balls, and the permutation symmetry constraint on their collective state makes each bin count tuple an equiprobable state that can be realized in only one way, unlike the bin count tuples for the balls that can be realized in various ways related by permutations of the balls.

$\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.