1
$\begingroup$

Problem definition:

There are $n$ bins, labeled with $1, 2, \ldots, n$. Let $X_i$ be a random variable denoting the number of balls contained in the $i$-th bin. The collection of random variables $X_i$ is independent and identically distributed, with the same probability distribution (in which $\lambda$ and $\mu$ are two different positive integers)

$$ p_x = \mathbb{P}(X_i = x) = \left\{ \begin{array}{ll} \frac{1}{2} \big( 1 + (\frac{\lambda}{\mu + \lambda})^2 \big)& \textrm{if $x = 0$} \\ \frac{(2 \lambda + \mu)^2}{2(\mu + \lambda)^2} \cdot (\frac{1}{2} \frac{\mu}{\mu + \lambda})^{x}& \textrm{if $x \geq 1$}\\ \end{array} \right. $$

Problem: What is the probability of the event, denoted $E_{n,m}$, that there are in total $m$ balls in these $n$ bins?


My solution:

For convenience, we write $$ r \triangleq \frac{(2 \lambda + \mu)^2}{2(\mu + \lambda)^2} \textrm{ and } s \triangleq \frac{1}{2} \frac{\mu}{\mu + \lambda}. $$

There are two cases according to whether there are empty bins.

  • There are no empty bins (denoted as an event $E_{\forall X_i > 0}$).

    In this case, we are partitioning integer $m$ into a sum of $n$ positive integers. There are ${m-1 \choose n-1}$ ways of partitions. For each partition

    $$ m = m_1 + m_2 + \cdots + m_n \quad (m_i > 0, 1 \le i \le n), $$

    the probability that the $i$-th bin contains $m_i$ balls is

    $$ (r \cdot s^{m_1}) (r \cdot s^{m_2}) \cdots (r \cdot s^{m_n}) = r^n s^m $$

    Thus, the probability of the case there are no empty bins is

    $$ \mathbb{P}(E_{\forall X_i > 0}) = {m-1 \choose n-1} r^n s^m $$

  • There exist empty bins (denoted as an event $E_{\exists X_i = 0}$).

    Suppose there are $k$ empty bins. In this case, we are partitioning integer $m$ into a sum of $n$ integers such that $k$ of them are 0 and $n-k$ of them are positive. There are ${n \choose k} {m-1 \choose n-k-1}$ ways of partitions. For each partition

    $$ m = m_1 + m_2 + \cdots + m_n \quad (\textrm{exactly } k \textrm{ of them are } 0), $$

    the probability that the $i$-th bin contains $m_i$ balls is

    $$ p_0^{k} \cdot r^{n-k} \cdot s^{m} $$

    Thus, the probability of the case there exist empty bins is

    $$ \mathbb{P}(E_{\exists X_i = 0}) = \sum_{k=1}^{k=n} {n \choose k} {m-1 \choose n-k-1} p_0^{k} r^{n-k} s^{m} $$

Combining these two cases together, it yields

\begin{align*} \mathbb{P}(E_{n,m}) &= \mathbb{P} (E_{\forall X_i > 0}) + \mathbb{P} (E_{\exists X_i = 0}) \\ &= {m-1 \choose n-1} r^n s^m + \sum_{k=1}^{k=n} {n \choose k} {m-1 \choose n-k-1} p_0^{k} r^{n-k} s^{m} \end{align*}


My questions:

This probabilistic (balls-and-bins) model is an abstraction of a problem I am working on. Therefore, I am wondering

Questions: Is this probability problem well-defined and is my solution correct?

Specifically,

  • For well-defined, did I miss some conditions or assumptions for the calculation of $\mathbb{P}(E_{n,m})$?

  • For correctness, as a probability distribution, it is necessarily that $\sum_{m=0}^{m=\infty} \mathbb{P}(E_{n,m}) = 1$. Is this correct?

EDIT: Using Mathematica, it does sum to 1.

$\endgroup$
1
$\begingroup$

I don't think it's necessary to distinguish the two cases, the $E_{\forall X_i > 0}) $ is just a particular case of the other (as the final formula shows). Further, you should restrict the last sum to $n-1$

A slightly simpler derivation:

First: assume, $m>0$; given a set of $c>0$ particular cells, the probability that all them are non-empty and that they sum $m$ is given (as you deduced) as the sum over all compositions (ordered non-empty partitions) of $m$ into $c$ parts of the (here constant) probability $r^c s^m$.

Let $C$ be the number of non-empty cells. Then

$$P(E_{n,m})=\sum_{c=1}^{n} P(E_{n,m} ,C=c)$$

$$ P(E_{n,m} ,C=c) = {n \choose c} p_0^{n-c} {m-1 \choose c-1} r^c s^m $$

Or, changing $k=n-c$:

$$P(E_{n,m})=\sum_{k=0}^{n-1} {n \choose k} p_0^{k} {m-1 \choose n-k-1} r^{n-k} s^m$$

For the special case $m=0$, $P(E_{n,0})=p_0^n$.

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