Is this probabilistic balls-and-bins problem well-defined and is my solution correct?

233 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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