### try_succeed's blog

By try_succeed, history, 5 weeks ago, ,

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).

• +14

 » 5 weeks ago, # |   +25 N/1 + N/2 + N/3 + ... + N/N
 » 5 weeks ago, # |   +26 $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)$. $T(n, 0) = 0$ $T(n, x) = \frac{x}{n}T(n, x - 1) + \frac{n - x}{n}T(n, x) + 1$ $\Rightarrow$ $\frac{n - n + x}{n}T(n, x) = \frac{x}{n}T(n, x - 1) + 1$ $\Rightarrow$ $T(n, x) = T(n, x - 1) + \frac{n}{x}$ $\Rightarrow$ $T(n, x) = \sum\limits_{i = 1}^{x}{\frac{n}{i}}$ $\Rightarrow$ $T(n, n) = \sum\limits_{i = 1}^{n}{\frac{n}{i}}$
•  » » 5 weeks ago, # ^ |   0 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)
•  » » » 5 weeks ago, # ^ |   +3 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)$.
•  » » 5 weeks ago, # ^ |   0 Thanks for the explanation.
 » 5 weeks ago, # |   +7 This is known as the coupon collector's problem (https://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Calculating_the_expectation)
•  » » 5 weeks ago, # ^ |   0 Thanks.
 » 5 weeks ago, # |   +3 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
•  » » 5 weeks ago, # ^ |   +3 Thanks for the explanation.