Блог пользователя try_succeed

Автор try_succeed, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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}}$$$
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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) $$$.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the explanation.

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +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