Generalized expression for balls and bins problem

$n$ number of balls are thrown randomly to $m$ number of bins, standing in a row. The balls are labeled as $1,2,3,....n$ and bins are also labeled as $1,2,3,...,m$. The probability of $i_{th}$ ball enters in the $j_{th}$ bin is $p_{ij}$ where $\sum_{j=1}^{m}p_{ij}=1$ for all $i$. What is the expected number of balls per occupied bin when all $n$ balls are thrown simultaneously?

• They had better have different speeds. My experience otherwise is that the balls hit each other and miss the bins entirely. Gerhard "Hopefully Simultaneity Is No Issue" Paseman, 2015.03.17 – Gerhard Paseman Mar 17 '15 at 15:53
• I think simultaneity can be an issue here. Tossing two coins is different than tossing one coin. We can assume that balls entering into bins are independent events to avoid the disturbance while throwing simultaneously. – marcella Mar 17 '15 at 16:22
• If there are two bins and one ball is thrown into them with uniform probability, are you expecting the answer to be $1/2$ (the average number of balls per bin) or $1$ (the average number of balls among the set of bins with at least one ball)? – Ben Barber Mar 17 '15 at 17:16
• The average number of balls per occupied bin will be 1 in this case. – marcella Mar 17 '15 at 17:26

The odds of having all the balls in bins $j_1, \cdots, j_d$ is $\Pi_{i\leq n}(p_{ij_1} + \cdots + p_{ij_d})$; call this number $q_{j_1, \cdots, j_d}$

By inclusion/exclusion we get that the odds the that set of nonempty bins is exactly $J = \{j_1, \cdots, j_d\}$ are $\sum_{S \subset J} (-1)^{d - |S|} q_S$; call this number $p_J$.

So, the expected number $E$ of balls per nonempty bin is given by $E = \sum_{J} {n \over |J|} p_J$ where the sum is taken over all subsets of $\{1,\dotsc,m\}$.

Were you looking for something nicer?

• I completely agree with your idea. However, when I try to compute for 2 boxes and 2 balls with equal probability(i.e $p_{11}=p_{12}=p_{21}=p_{22}=0.5$)I am getting different answers. E(x=#of balls per occupied bin)=(0.25+0.25).1 + (0.25+0.25).2=1.5; E(Y=#of non empty bins)=0.5x1+0.5x2=1.5, so Average #of balls per occupied bin=n/E(Y)=2/1.5=1.33. What I'm doing wrong here? – marcella Mar 20 '15 at 20:48
• Right, I was being stupid, edited my answer. – Sam Clearman Mar 21 '15 at 19:24
• Thank you so much for the solution. Is it possible to make the expression of $E$ a bit more code friendly which will be easier to compute! – marcella Mar 22 '15 at 0:27

By the additivity of expectation, the expected number of balls in bin $j$ is $\sum_{i=1}^n p_{ij}$. Is this what you're asking?

• I solved the problem for $n=2;m=2$ in the following way $E(x=$number of balls enter in the same bin$)=((p_{11}.p_{12})+(p_{12}.p_{21})).1 + ((p_{11}.p_{21})+(p_{12}.p_{22})).2$ If $m=3,n=3$ then $E(x)=P(x=1).1+p(x=2).2+p(x=3).3$ where $P(x=k)$ is the probability of $k$ number of balls in the same bin. I don't know how to express the above procedure for $n$ balls and $m$ bins in a generalized way. – marcella Mar 17 '15 at 16:48