# Bins and balls problem: expected number of balls placed given number of empty and non-empty bins?

Given are $m$ bins with equal probability of choosing one of them. Unknown number of balls $n$ is placed into the bins, and, at the end of placement, we observe number of empty bins $m_e$ and non-empty bins $m_{n}$.

Given $m$, $m_e$, $m_n$, what is the most likely number of balls $n$, which have been placed into bins?

(UPD) possible additional information: number of bins with exactly one ball can be also known.

• @ChristianBlatter I agree that the guess might make no sense in certain cases, however, I think for many possible cases the problem is solvable. I'm thinking of a possible approach: find a conditional probability of observing $m_e$ and $m_n$ partition given $n$, that is $\mathbb{P}[m_e, m_n | n ]$, plug in the observed numbers, and find $n$ maximízing this probability. Does this make sense? – mck Jul 12 '17 at 9:24
• How are the balls placed in the bins? For every ball, do we select a bin in a uniform and random way? Some other way? – Thanassis Jul 12 '17 at 9:29
• @Thanassis a bin is selected with a uniform probability – mck Jul 12 '17 at 9:29
• There is a difference between the maximum likelihood estimate of $n$ and the expectation of $n$ – Henry Jul 12 '17 at 9:58
• @Henry sorry, I've meant maximum likelihood estimate, not expectation. – mck Jul 12 '17 at 10:13

## 3 Answers

Presumably $m=m_e+m_n$.

The likelihood of seeing $m_n$ out of $m$ occupied is $\dfrac{S_2(n,m_n)\, m!}{m^n \;(m-m_n)!}$ where $S_2(x,y)$ is a Stirling number of the second kind. I do not know an easy way of finding the $n$ which maximises this in general but it is easy enough to calculate for given reasonably small $m$.

One possible alternative estimator is $\dfrac{\log(m)-\log(m-m_n)}{\log(m)-\log(m-1)}$, which follows from saying $E[m_n \mid m, n] = m\left(1 -\left(\frac{m-1}{m}\right)^n\right)$. This is neither a maximum likelihood estimator nor an unbiased estimator for $n$, and it is usually not an integer, but it comes fairly close to the maximum likelihood estimator; it is slightly biased upwards when $1 \lt n \lt m$. The table below compares the values when $m=10$ for different $m_n$

 m      m_n   n_MLE    n_alt.est
10       0     0        0
10       1     1        1
10       2     2        2.12
10       3     3        3.39
10       4     4 or 5   4.85
10       5     6        6.58
10       6     8        8.70
10       7    11       11.43
10       8    15       15.25
10       9    22       21.85
10      10    infinite  n/a


1) Premise

Randomly throw (put) $n$ balls into $m$ bins (of unlimited capacity)
means that you consider as equiprobable and indipendent events the
launch the $k$-th ball into the $j$-th bin
i.e., a sequence of $n$ independent events, each having $m$ equiprobable results.
Thus the space of elementary events is the $n$D (hyper)cube of side $1\dots m$, containing $m^n$ points (i.e. sequences).

2) the Problem

Let's call $m_e$ as $q$ to simplify notation. Let's then call $N(n,m,q)$ the number of configurations with exactly $q$ bins empty, and clearly with the other $m-q$ containing at least one ball.
The probability of having a configuration with exactly $q$ bins empty, out of $m$ bins in total and after having placed the $n$th ball is $$\bbox[lightyellow] { P(n,m,q) = {1 \over {m^{\,n} }}N(n,m,q) }$$ Keeping $m$ fixed, with some "abuse" of notation, but helping to make the development clear, allow to write the above as $$\bbox[lightyellow] { P(n,m,q) = \wp (q|n) = {{\wp (q \wedge n)} \over {\wp (n)}} }$$

Then the question is to find $$\bbox[lightyellow] { \wp (n|q) = {{\wp (q \wedge n)} \over {\wp (q)}} = {{\wp (q \wedge n)} \over {\sum\limits_n {\wp (q|n)\;\wp (n)} }} = {{P(n,m,q)\wp (n)} \over {\sum\limits_n {\wp (q|n)\;\wp (n)} }} } \tag {1}$$

This clearly show that we are missing an information in order to solve the problem: the P(n).
That is we have to know the probability that the balls launched are $(0),\, 1,\, 2,\, \cdots$.

Supposing it to be a uniform probability, between $0$ and, say, $u$, then it is constant and simplifies out, leaving $$\bbox[lightyellow] { \wp (n|q)\left| {\;n\,{\rm uniform}\;{\rm distr}.} \right. = Q(n,m,q) = {{P(n,m,q)} \over {\sum\limits_{n\, \in \;{\rm range}} {P(n,m,q)} }} } \tag {1.a}$$

3) P(n,m,q) and Q(n,m,q) formula

In this other post it is explained how we arrive to demonstrate that \bbox[lightyellow] { \eqalign{ & N(n,m,q) = \left( \matrix{ m \cr q \cr} \right)N(n,m - q,0) = {{m!} \over {q!}}\left\{ \matrix{ n \cr m - q \cr} \right\}\quad \Rightarrow \cr & \Rightarrow \quad P(n,m,q) = \left[ {0 = n} \right]\left[ {0 = m} \right]\left[ {0 = q} \right] + \left[ {1 \le m} \right]{{m!} \over {m^{\,n} \;q!}}\left\{ \matrix{ n \cr m - q \cr} \right\} \cr} } \tag {2} where $[P]$ is the Iverson bracket $$\left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right.$$

Now it is \bbox[lightyellow] { \eqalign{ & \sum\limits_{0\, \le \,k} {\left\{ \matrix{ k \hfill \cr n \hfill \cr} \right\}\;\left( {{1 \over z}} \right)^{\,k} } \;\left| {\;0 \le {\rm integer}\;n} \right.\quad = \cr & = {1 \over {\left( {z - 1} \right)\left( {z - 2} \right) \cdots \left( {z - n} \right)}} = {1 \over {\left( {z - 1} \right)^{\,\underline {\,n\,} } }} = z^{\,\overline {\, - n\,} } = {{\Gamma \left( {z - n} \right)} \over {\Gamma \left( z \right)}} \cr} } where $z^{\,\underline {\,n\,} }$ and $z^{\,\overline {\, n\,}}$ denote the falling and rising factorial respectively.

So that, for the range of $n$ going in the limit to $\infty$ we get (leaving apart the case $0=m$): $$\bbox[lightyellow] { \sum\limits_{0\, \le \,n} {P(n,m,q)} = \sum\limits_{0\, \le \,n} {{{m!} \over {\;q!}}\left\{ \matrix{ n \cr m - q \cr} \right\}\left( {{1 \over m}} \right)^{\,n} } = {{m!} \over {\;q!}}{{\Gamma \left( q \right)} \over {\Gamma \left( m \right)}} }$$ and $$\bbox[lightyellow] { \wp (n|q) = Q(n,m,q) = {1 \over {m^{\,n} \;}}{{\Gamma \left( m \right)} \over {\Gamma \left( q \right)}}\left\{ \matrix{ n \cr m - q \cr} \right\} } \tag {3}$$

It is worthy to note that, for $q=0$ and $1 \le m$, $Q(n,m,q)$ is null. That is because the information "there is no empty bin" just implies that $m \le n$, and the range assumed for $n$ extends to infinity.

4) expected value for $n$

Since $$\bbox[lightyellow] { \sum\limits_{0\, \le \,k} {k\left\{ \matrix{ k \hfill \cr n \hfill \cr} \right\}\;z^{\,k} } \; = z{d \over {dz}}\sum\limits_{0\, \le \,k} {\left\{ \matrix{ k \hfill \cr n \hfill \cr} \right\}\;z^{\,k} } = z{d \over {dz}}{{\Gamma \left( {1/z - n} \right)} \over {\Gamma \left( {1/z} \right)}} = {{\Gamma \left( {1/z - n} \right)} \over {z\;\Gamma \left( {1/z} \right)}}\left( {\psi (1/z) - \psi (1/z - n)} \right) }$$

Then, always in the case of a uniform distribution for $n$, with a range estending in the limit to $\infty$, we get \bbox[lightyellow] { \eqalign{ & E(n)\quad \left| {\,1 \le q \le m} \right.\quad = \cr & = \sum\limits_{0\, \le \,n} {n\;Q(n,m,q)} = {{\Gamma \left( m \right)} \over {\Gamma \left( q \right)}}\sum\limits_{0\, \le \,n} {n\;\left\{ \matrix{ n \cr m - q \cr} \right\}\left( {{1 \over {m\;}}} \right)^{\,n} } = \cr & = m\left( {\psi (m) - \psi (q)} \right) \cr} } \tag {4} which is plotted below

Again note that , for $q=0$ and $1 \le m$, the expected value of $n$ climbs to infinite, for the reason said above.

5) max probable value for $n$

You are requesting for the mode of $Q(n,m,q)$. Unfortunately its formula does not allow to find the mode analytically.
However, the plot of $Q$ vs. $n$, at fixed $m$ and $q$, is clearly positive skewed.
Therefore the mode will lay a little below the average, and thus the knowledge of $E[n]$ is of help in finding the mode numerically.

Let's say we have $m$ bins out of which $m_e$ are empty (and the non-empty bins are $m_n=m-m_e$). Let's also assume that $m_e > 0$, otherwise there is very little information we can get, as you discussed in the comments.

If we could compute the probability of having $i$ balls, given this observation, then we can compute the expected value of balls, or the maximum likelihood estimator, or other questions about estimating the number of balls. So we are looking for $P(\text{balls} = i | m_e,m )$.

Applying Bayes' rule we get:

$$P(\text{balls} = i | m_e,m ) = \frac{P(m_e,m|\text{balls}=i)\cdot P(\text{balls}=i)}{\sum_{i=m_n}^\infty P(m_e,m|\text{balls}=i)\cdot P(\text{balls}=i)}$$

Notice that the balls have to be at least as many as the non-empty bins.

We also notice the importance of knowing the prior probability of $P(\text{balls} =i)$. Without any other information on this, let's assume that the all values of $i$ are equiprobable, so that these terms can cancel out in the formula.

What is $P(m_e,m|\text{balls}=i)$? In other words, given that we distributed $i$ balls in the bins, what is the probability that we have exactly $m_e$ empty bins, out of $m$ total bins? If the distribution was done in a uniformly random way, then this probability is equal to $\dfrac{S_2(i,m_n)\cdot m!}{m^n \cdot m_e!}$.

Edit: Intially I thought that this was a simpler formula, that was more analytically tractable. After seeing Henry's answer I realised my mistake. I am afraid my analysis stops here. You can computationally calculate these probabilities for small number of balls and bins. You can also compute $P(\text{balls} = i | m_e,m )$, especially if you assume a maximum number of possible balls (so that the summation in the denominator of Bayes' rule becomes tractable).

• can you explain how do you arrive at $\dfrac{S_2(i,m_n)\cdot m!}{m^n \cdot m_e!}$ ? – G Cab Jul 13 '17 at 16:07