I'm doing my graduate study in computer science and I faced the following question in my thesis.
Suppose there are $n$ bins and $m$ balls. We have the following assumptions:
- there could be either one or no ball in each single bin.
- $n$ is much much larger than $m$.
- the balls have numbers on them like ball $1$, ball $2$ , ..., ball $m$.
- the bins have numbers on them like bin $1$, bin $2$, ..., bin $n$.
- we suppose that the bins are orders from left to right, so the left-most bin's number is $1$ and the right-most bin's number is $n$.
- we show the probability of ball $i$ to be in bin $j$ as $p(i,j)$. We have the $p(i,j)$ for all the balls and bins.
We scatter the $m$ balls among the $n$ bins. Now the question is: What is the probability of ball $i$ to be the $k$th ball from the left?
for example:
$n = 4$ and $m = 3$
All possible cases for the ball $2$ be the first from left is as follows ("-" shows the empty bin):
ball2,ball1,ball3,-
ball2,ball3,ball1,-
ball2,ball1,-,ball3,
ball2,ball3,-,ball1,
ball2,-,ball1,ball3,-
ball2,-,ball3,ball1,-
-, ball2,ball1,ball3
-, ball2,ball3,ball1
I was wondering if you could tell me whether there is any general formula to calculate this probability when $n$ and $m$ are quite large?
A better definition of the question could be accessed through the following address: https://www.dropbox.com/s/61j6oh58wk8xx7w/report.pdf?dl=0