$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?
4
-
4$\begingroup$ 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 $\endgroup$– Gerhard PasemanCommented Mar 17, 2015 at 15:53
-
$\begingroup$ 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. $\endgroup$– marcellaCommented Mar 17, 2015 at 16:22
-
$\begingroup$ 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)? $\endgroup$– Ben BarberCommented Mar 17, 2015 at 17:16
-
$\begingroup$ The average number of balls per occupied bin will be 1 in this case. $\endgroup$– marcellaCommented Mar 17, 2015 at 17:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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?
-
$\begingroup$ 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? $\endgroup$– marcellaCommented Mar 20, 2015 at 20:48
-
$\begingroup$ Right, I was being stupid, edited my answer. $\endgroup$ Commented Mar 21, 2015 at 19:24
-
$\begingroup$ 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! $\endgroup$– marcellaCommented Mar 22, 2015 at 0:27
$\begingroup$
$\endgroup$
1
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?
answered Mar 17, 2015 at 16:13
-
$\begingroup$ 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. $\endgroup$– marcellaCommented Mar 17, 2015 at 16:48