What is the probability of certain profile in ball and box (Stars and bars) problem?

Question

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?

Answer 1

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

Answer 2

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)\;} $$