sequencing in n-bins and m-balls quesiton

Question

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:

1. there could be either one or no ball in each single bin.
2. $n$ is much much larger than $m$.
3. the balls have numbers on them like ball $1$, ball $2$ , ..., ball $m$.
4. the bins have numbers on them like bin $1$, bin $2$, ..., bin $n$.
5. 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$.
6. 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

Answer 1

There is not enough information to answer this question. One might try to give bounds for the results, but even those are so broad as to be practically useless.

---

To appreciate the difficulty, set $m=3, n=4$ and consider the probability distributions that assign equal probabilities to each element of the following sets of configurations. The notation ijkl with symbols in the set {1,2,3,.} gives the left-right sequence of balls; the position of the empty bin is located by ..

1. {123., 21.3, 3.12, .321}

2. {123., .123, 3.12, 23.1}

In each case $p(i,j)=1/4$ for all $i$ and $j$. But in (1), the chance that ball 1 occupies a middle position is $1/2$ whereas in (2) it has only a $1/4$ chance of being in the middle.

As $m$ and $n$ grow large the situation only gets worse. For instance, consider the following equiprobable configurations. There are $n$ of them, indexed by $k=1, 2, \ldots, n$. Place ball $i$ in bin $k+i \mod n$. The marginal distributions are uniform: $p(i,j)=1/n$ for all $i$ and $j$. (This generalizes case (2) above.) The chance that ball 1 is the leftmost equals $(n-m)/n$. If instead we were to assign equal probabilities to every one of the $n(n-1)\cdots(n-m+2)(n-m+1)$ possible configurations, then again the marginal distributions would be uniform but now the chance that ball 1 is the leftmost is just $1/m$. The gap between $(n-m)/n$ and $1/m$ grows huge when $n\gg m\gg 0$.

In short, you need to specify the full joint distribution of the configurations: giving the marginal distributions is inadequate.

(Note that, unlike in many other situations, we cannot make the simplifying assumption that the ball distributions are independent. The at-most-one-ball-in-each-bin restriction creates an inherent lack of independence.)

---

I suspect that this question is attempting to abstract some specific process. Perhaps some essential feature of that process has been lost in the abstraction. It would be better to describe the actual problem you have and leave it to your readers to make abstractions.

Please be aware that even asymptotic solutions to problems like this can be impossible to obtain unless there are definite relationships among the $p(i,j)$. It is therefore important to describe your problem in enough detail that such relationships can be discerned and exploited.