1
$\begingroup$

If there is 3 distinguishable boxes and 5 indistinguishable balls, by dropping the balls into boxes randomly, then there will be 21 combinations profile of ball number in each box.

{{5, 0, 0}, {0, 5, 0}, {0, 0, 5}, {4, 1, 0}, {4, 0, 1}, {1, 4, 0}, {1, 0, 4}, {0, 4, 1}, {0, 1, 4}, {3, 2, 0}, {3, 0, 2}, {2, 3, 0}, {2, 0, 3}, {0, 3, 2}, {0, 2, 3}, {3, 1, 1}, {1, 3, 1}, {1, 1, 3}, {2, 2, 1}, {2, 1, 2}, {1, 2, 2}}

I am interested in the probability to get each profile, eg {3, 2, 0}(3 balls in in $B_1$, 2 balls in $B_2$, 0 ball in $B_3$).


Thus, the problem can be generalized as:

given $n$ distinguishable box and $k$ indistinguishable balls, what is the probability to get profile $\{k_1, k_2, k_3, ... , k_n\}$ in all trials?

More generally, if the boxes are different in size (by weights, $w_1, w_2, w_3, ... , w_n$), what will the probability become?

$\endgroup$
3
  • $\begingroup$ You are missing cases in your example: $(5, 0, 0), (0, 5, 0), (0, 0, 5), (4, 1, 0), (4, 0, 1), (1, 4, 0), (1, 0, 4), (0, 4, 1), (0, 1, 4)$. $\endgroup$ Jul 11, 2019 at 8:21
  • $\begingroup$ If we let $x_i, 1 \leq i \leq 3$, denote the number of balls placed in the $i$th box, the number of distributions is the number of solutions of the equation $x_1 + x_2 + x_3 = 5$ in the nonnegative integers. A particular solution of the equation corresponds to the placement of $3 - 1 = 2$ addition signs in a row of five ones. For instance, $1 1 1 1 + + 1$ corresponds to $(4, 0, 1)$. The number of such solutions is $\binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} = 21$ since we must choose which $2$ of the $7$ positions required for five ones and two addition signs will be filled with additon signs. $\endgroup$ Jul 11, 2019 at 8:22
  • $\begingroup$ @N.F.Taussig sorry for the mistake, I missed the case that ball number > 3... have update the example now. Thank you very much. $\endgroup$
    – Chang Ye
    Jul 11, 2019 at 8:26

2 Answers 2

1
$\begingroup$

This is the multinomial distribution.

If you consider all $n^k$ outcomes for which ball goes in which box, there are $\frac{k!}{k_1! \cdots k_n!}$ outcomes that correspond to the profile $(k_1, \ldots, k_n)$. If each ball is equally likely to go in each box, then the probability is $\frac{k!}{k_1! \cdots k_n!} \frac{1}{n^k}$. More generally, if the probability of a ball going into box $i$ is $w_i$, then it is $\frac{k!}{k_1! \cdots k_n!} w_1^{k_1} \cdots w_n^{k_n}$.

$\endgroup$
3
  • $\begingroup$ sounds reasonable, a little weird... if there is one box(n=1) for ten balls(k=10), then, the probability is 1/10! ? Shouldn't that be 1? $\endgroup$
    – Chang Ye
    Jul 11, 2019 at 8:20
  • $\begingroup$ The numerator should be $k!$, where $k = k_1 + k_2 + \cdots + k_n$. $\endgroup$ Jul 11, 2019 at 8:41
  • $\begingroup$ @N.F.Taussig Thanks for catching that egregious typo! $\endgroup$
    – angryavian
    Jul 11, 2019 at 16:50
0
$\begingroup$

Each "occupancy histogram" corresponds to a $n$-tuple, which geometrically translates into a point in the ${\mathbb N}^n$ space, that is, in the non-negative portion of a $n$-dimensional grid.

When the number of balls is fixed (let me indicate it with $s$, to reserve $k$ for use as index), the points will lay on the diagonal plane $x_1+x_2+ \cdots +x_n=s$.

If the capacity of each bin is unlimited, or however higher than the number of balls, the plane will extend on all the non-negative portion, and its "area" will be equal to the number of weak compositions of $s$ into $n$ parts, i.e. $$ N_b(s,n) = \binom{s+n-1}{s} $$

If the capacity of each bin is constant and equal to $r$, then the plane will be limited inside a $n$-cube with sides $[0,r]$, and the intercepted area will be $$ N_b (s,r,n) = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm 0} \le {\rm integer}\;x_{\,j} \le r \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,n} = s \hfill \cr} \right. $$ which, as explained in this related post, is given by $$ N_b (s,r,n)\quad \left| {\;0 \leqslant \text{integers }s,n,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,n} \right)} {\left( { - 1} \right)^k \binom{n}{k} \binom { s + n - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$

If the capacity of each bin is different, then the plane is limited inside a $n$-parallepiped with sides $[0,r_k]$, and a closed expression for the intercepted area would be in general quite complicated.

Premised the above, we have then to make clear that the process of "pouring" the balls is different than that of "throwing" the balls into the bin.
While we can understand the "pouring" as the process in which each point ($n$-tuple) is equiprobable, in "throwing" it is normally understood that we have have $n^s$ equi-probable outcomes (for unlimited capacity) which is not the same as the $N_B(s,n)$ given above.
That is because the process of throwing, implies a succession and thus a distinction among the balls given by the order in which they are thrown. You can convince yourself of the difference by taking examples with a small number of bins and balls.
The throwing process shall be examined through the Stirling development of $n^s$ $$ n^{\,s} = \sum\limits_k {\left\{ \matrix{ s \cr k \cr} \right\}n^{\,\underline {\,k\,} } } = \sum\limits_k {k!\left\{ \matrix{ s \cr k \cr} \right\}\left( \matrix{ n \cr k \cr} \right)} $$ that is through the number of ways of partitioning a set of $s$ elements into $k$ non empty sub-sets, and distribute the $k$ subsets into the $n$ bins.

The multinomial approach $$ \begin{array}{l} \left( {x_{\,1} + x_{\,2} + \cdots + x_{\,n} } \right)^{\,s} = \cdots + x_{\,l_{\,1} } x_{\,l_{\,2} } \cdots x_{\,l_{\,s} } + \cdots \quad \left| {\;\,l_{\,j} \in \left[ {1,n} \right]} \right. = \\ = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,l} } \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,s} \\ \end{array}} \right.\;} {\left( \begin{array}{c} s \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \\ \end{array} \right)\;x_{\,1} ^{j_{\,1} } \;x_{\,2} ^{j_{\,2} } \; \cdots \;x_{\,n} ^{j_{\,n} } } \\ \end{array} $$ also captures the "throwing" process: $$ x_{\,l_{\,1} } x_{\,l_{\,2} } \cdots x_{\,l_{\,s} } $$ stands in fact for 1st ball in bin $l_1$, .., s-th ball in bin $l_s$.
That is more "straight" to deal when setting upper limits to the $j_k$ indices.
In the unlimited case it is equivalent to the Stirling development, since $$ n!\left\{ \begin{array}{c} s \\ n \\ \end{array} \right\} = \sum\limits_{\left\{ {\begin{array}{*{20}c} {1\, \le \,j_{\,l} } \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,s} \\ \end{array}} \right.\;} {\left( \begin{array}{c} s \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \\ \end{array} \right)\;} $$

$\endgroup$
4
  • $\begingroup$ Does "pouring" correspond to any natural model of (generalized) balls into (generalized) boxes? It's always struck me as nothing more than a way to turn two counting problems into a single "probability" problem by declaring distinguishable outcomes to be equally likely when there's no natural model under which that happens. There is a way to do it: make the probability of next ball going into box $j$ proportional to ($1 +$ [number of balls in box $j$]). Then starting with all empty boxes, after $s$ balls, the distinguishable stars and bars outcomes (unlimited capacity) are equally likely. $\endgroup$
    – Ned
    Jul 11, 2019 at 14:49
  • $\begingroup$ @Ned: by "pouring" I mean to launch the (undist.) balls all at the same time, with a mechanism that ensures even distribution among the bins, which done in the reverse would be that of "throwing the bins to the balls", more practically that of placing "bars" in between "stars", or random paths $(0,0) \to (n,s)$ with north-steps uniform in $[0,s]$, etc. $\endgroup$
    – G Cab
    Jul 11, 2019 at 16:47
  • $\begingroup$ @G Cab Thanks for your reply. I admit I don't follow it -- ensuring a (more) even distribution of balls in bins [compared to the usual "uniform and independent'] will make the stars and bars outcomes less equally likely than they were before. Totally trying to get throwing bins at balls, but not able to understand. My original point is that equally likely stars-and-bars outcomes isn't modeled by balls in boxes in any natural way -- the weird model I mentioned, which does give equally likely stars-and-bars outcomes after every ball, is not "natural". $\endgroup$
    – Ned
    Jul 11, 2019 at 21:34
  • $\begingroup$ @Ned: I agree with you that "stars and bars" and "balls in bins" are hard to concile. $\endgroup$
    – G Cab
    Jul 12, 2019 at 13:50

You must log in to answer this question.

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