Probability of finding "N" balls in a box

75 Views Asked by At

Suppose we have two boxes, box $1$ with $N_1$ balls, the other one (box $2$) with $N-N_1$.

At each time $\Delta t$, we choose a number between $1,N$: If the ball correspondent to the number we choose, $x$, is in box 1, it will jump to box 2. The same goes to the other case ($x$ in 2). What is the probability of finding $N_k$ balls at box 1 at time t? Given that, at $t=0, N_1 = N$.

I derived the following equation:

$$P_{(N_1,t+\Delta t)} = \frac{N-(N_1-1)}{N}P_{(N_1-1,t)} + \frac{N_1+ 1}{N} P_{(N_1+1,t)}$$

But have no idea how to solve it

1

There are 1 best solutions below

1
On BEST ANSWER

I have not come up with a clear idea to compute the probability, but computing the expectation is possible. Hope this may help. You may consider for each ball, how many times it is chosen. At the time $t$, we have done $t$ samplings, and for each ball $x$, it has been chosen $k$ times with probability (Binomial distribution) $$p(t, k) = \binom{t}{k}(1/N)^{k}(1-1/N)^{t-k}.$$

For each ball that is originally in box $1$, if it is chosen even times, then it is still in box $1$, and if it is chosen odd times, then it ends up in box $2$, and thus reduces the number of balls in box $1$ by one. Similarly, for each ball that is originally in box $2$, if it is chosen even times, then it is still in box $2$, otherwise, it ends up in box $1$ and thus increases the number of balls in box $1$ by one.

To conclude, we have the following formula: $$\mathbb{E}[\text{# final balls in box 1}] = N_1 - \mathbb{E}[\text{# balls originally in box 1 and chosen odd times}] + \mathbb{E}[\text{# balls originally in box 2 and chosen odd times}].$$

We have $$ \mathbb{E}[\text{# balls originally in box 1 and chosen odd times}] = N_1 \times \Pr[\text{chosen odd times}] = N_1 \sum_{\text{$k$ odd}} p(t,k) = N_1 (1 - (1 - 2/N)^{t}) / 2 $$ and similarly $$\mathbb{E}[\text{# balls originally in box 2 and chosen odd times}] = (N - N_1) \times \Pr[\text{chosen odd times}] = (N - N_1) \sum_{\text{$k$ odd}} p(t,k) = (N - N_1) (1 - (1 - 2/N)^{t}) / 2.$$ Therefore, $$\mathbb{E}[\text{# final balls in box 1}] = N_1 + (N - 2N_1) (1 - (1 - 2/N)^{t}) / 2.$$