balls in bins in a multinomial setting

101 Views Asked by At

Probability of observing $m_k$ bins over $m$ total bins that have $k$ balls inside each after $n$ identical balls have been launched in bins in a multinomial setting.

More precisely, The occupancy problem consist in assigning the $n$ balls randomly in $m$ bins. Typically, the assignment is done by throwing each ball into a uniformly random bin independently, this is the case of single-choice process. Another variant is the multiple-choice process, where each ball can pick one out of randomly selected bins, and then use some rule to decide which bin to go. In this setting to every $i$th bin there is a probability of a ball following into it to be $\nu_i$ where $(\nu_1, \ldots , \nu_m)$ which is the probability distribution of the $m$ bins. The balls and bins setting entails some $m$ bins, and we throw $n$ balls into the bins with respective probabilities. Let us first assume that the types of the balls does not affect the choice of the bins, and this is equivalent to consider the balls to be identical (indistinguishable). Moreover, we assume infinitely large capacities of bins respect to the number of balls, i.e. every bin size is always enough to contain all the balls\footnote{Or equivalently balls have dimension zero}. Consequently, we have $n$ draws from a Multinomial Distribution of $m$ outcomes: for given bin capacities the joint probability of a number of balls $\{k_1,\ldots,k_m\}$ are the observed counts for each bin capacity, is given by the Multinomial distribution: \begin{equation} P(k_1, k_2, \ldots, k_m) = \binom{n}{k_1, k_2, \ldots, k_m} \nu_1^{k_1} \nu_2^{k_2} \ldots \nu_m^{k_m} \end{equation} where $n$ is the number of trials (launch a ball randomly in bins) with $n=\sum_{i=1}^{m}k_i$ and $\sum_{i=1}^{m}\nu_i=1$. Moreover, the multinomial coefficient $ \binom{n}{k_1, k_2, \ldots, k_m} =\frac{n!}{k_1!k_2!\ldots k_m!}$ represents the number of ways that $n$ objects can be divided into $m$ groups. An important approximation of using the bin probabilities $\nu_i$, in terms of bin capacities, is that the capacity will never reach is limit cap, and that is equivalent to assume sampling balls with replacement. To find the expected number of bins having $k$ balls, let (Z_i) represent the number of balls in bin (i), and let (M_k) be the number of bins that have (k) balls. We want to calculate the expected value of (M_k), denoted as (E[M_k]). In the multinomial distribution, the probability of having (k) balls in a particular bin is given by the probability mass function: $$P(Z_i = k) = \frac{n!}{k! \cdot (n-k)!} \cdot \nu_i^k \cdot (1 - \nu_i)^{n-k}$$

What is the probability of having (k) balls in exactly (M_k) bins?

is it an expected value?