When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

try_succeed's blog

By try_succeed, history, 4 years ago, In English

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

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

$$$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}}$$$
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the explanation.

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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