Quickly estimating a probability

Question

Suppose I have five bins into which I want to place 15 balls. The bins have capacities $2$, $2$, $3$, $3$, and $7.$ I place the balls one at a time in the bins, randomly and uniformly amongst the bins that are not full (so for example, if after placing four balls, both of the bins with capacity $2$ are already full, the next ball is placed with probability $1/3$ in each of the remaining three bins).

My question is if there is a an efficient way to estimate the probability that the bin with capacity $7$ is full at the end of this process (it would be great if the technique generalizes in the obvious way).

Answer 1

It seems to me like a good way to solve the general problem would be to use generating functions. Essentially, the total number of ways of distributing the balls to $\textit{distinct}$ bins can be thought of the number of solutions to $$k_1+k_2+k_3+k_4+k_5=15$$ such that $$0\leq k_1,k_2\leq 2$$ $$0\leq k_3,k_4\leq 3$$ $$0\leq k_5\leq 7$$

I believe the correct way to solve this using generating functions would be to find the coefficient of $x^{15}$ in the expanded form of $$(1+x+x^2)^2(1+x+x^2+x^3)^2(1+x +...+x^7)$$

Now, we need to know how many of these solutions have a full bin of $7$. This is just the number of solutions to $$k_1+k_2+k_3+k_4=8$$ with the same restrictions on all $k$. Once again you can use generating functions for this.

The ratio of these two counts should be the probability of a full bin of 7.

Answer 2

This is just a generalization of the answer by Bryce

Suppose there are $m$ bins with capacities $n_i, i\in\{1,2,\ldots,m\}$. Suppose $N$ balls are to be placed in these bins randomly one at a time, such that each non-full bin has an equal chance of getting filled with the next ball. Suppose we were to find the probability that $k$th bin is full after all $N$ balls are placed.

Assuming $\sum_{i=1}^{m}n_i \geq N$, number of ways in which $N$ balls can be placed in $m$ bins is equal to the number of integral solutions of the equation,

$$x_1+x_2+\ldots+x_m = N$$

such that $0 \leq x_i \leq n_i$. The number of integral solutions of this equation can be found by finding the coefficient of $x^N$ in,

$$\prod_{i=1}^{m}(1+x+\ldots+x^{n_i})$$

Let the coefficient of $x^N$ in above polynomial be $C$.

Now, the number of ways in which $N$ balls can be filled in $m$ bins such that $k$th bin is full, is equal to the number of integral solutions of the equation,

$$x_1+x_2+\ldots+n_k+x_{k+1}+\ldots+x_m = N$$

such that $0 \leq x_i \leq n_i$. The number of integral solutions of this equation can be found by finding the coefficient of $x^{N-n_k}$ in,

$$\prod_{\substack{i=1\\i\neq k}}^{m}(1+x+\ldots+x^{n_i})$$

Let the coefficient of $x^{N-n_k}$ in above polynomial be $C_k$.

Then the required probability is $\frac{C_k}{C}$.