Can someone help me with this occupancy problem? Given n-bins what is the expected number of balls to be thrown so that each bin has atleast one ball. (Consider the ball thrown has equal probability to go in any of the bins).

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | apiadu | 3397 |

4 | TLE | 3374 |

5 | Um_nik | 3358 |

6 | 300iq | 3317 |

7 | maroonrk | 3232 |

8 | Benq | 3230 |

9 | LHiC | 3229 |

10 | 1919810 | 3203 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 191 |

2 | Errichto | 186 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 169 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 163 |

9 | 300iq | 155 |

10 | Petr | 153 |

Can someone help me with this occupancy problem? Given n-bins what is the expected number of balls to be thrown so that each bin has atleast one ball. (Consider the ball thrown has equal probability to go in any of the bins).

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/02/2020 16:45:02 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

N/1 + N/2 + N/3 + ... + N/N

$$$T(n, x)$$$ — expected number of balls to be thrown so that each of $$$n$$$ bins has at least one ball and there are $$$x$$$ empty bins.

Answer for the problem is $$$T(n, n)$$$.

I am unable to understand definition of T(n, x). What is x exactly?

If x means number of empty bins, then shouldn't our answer be T(n, 0)? (because we want all the bins to contain at least 1 ball — leaving no bin empty)

The $$$x$$$ in $$$T(n,x)$$$ is the number of empty bins before starting the process. So, initially when all bins are empty, you want to find the expected number of balls to be thrown, which is $$$ T(n,n) $$$.

Thanks for the explanation.

This is known as the coupon collector's problem (https://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Calculating_the_expectation)

Thanks.

consider an array $$$a$$$ where $$$a_x$$$ is the expected number of balls to be thrown where $$$x$$$ bins are empty and $$$n-x$$$ bins has at least one ball.

let's start from $$$x=n$$$ to $$$x=0$$$. we can notice that $$$a_n = 0$$$ because the expected number of balls to be thrown when all the bins has at least one ball is $$$0$$$.

now $$$a_x = 1 + \frac{x}{n} \times a_x + \frac{n-x}{n} \times a_{x+1}$$$, that's because there is a probability equals $$$\frac{x}{n}$$$ that you'll throw a ball into a bin that has at least one ball already and a probability equals $$$\frac{n-x}{n}$$$ that you'll throw a ball into an empty bin. plus one for the ball you are throwing now.

now for the previous equation, we can modify it so that $$$a_x = \frac {1 + \frac{n-x}{n} \times a_{x+1}} { 1 - \frac{x}{n}}$$$. now your answer is $$$a_0$$$. I hope everything I said is clear

Thanks for the explanation.