3
$\begingroup$

Suppose we have $n$ bins and $k<n$ is some natural number. Each turn we select at random $k$ distinct bins out of the $n$ bins in which we place a ball. How many turns does it take on average until there is at least $1$ ball in each of the bins? This part has been solved in the comments (as it turned out to be a duplicate).

Related to this : If we call a collection of $k$ balls a winner if one of the balls is the first one to enter a bin, how many winners are there on average. So the first batch of ball has a 100$\%$ chance of being a winner and then the probability of being a winner decreases as more balls are added. For the coupon collector's problem mentioned in the comments (with $k=1$) it is obvious that there will always be exactly $n$ winning batches.

$\endgroup$
  • 1
    $\begingroup$ When $k=1$ this is the coupon collector's problem, so you might start by researching that. $\endgroup$ – saulspatz Nov 13 '18 at 22:55
  • $\begingroup$ Thank you for this reference, it gives me a good idea of how difficult the problem is and a good starting point to investigate further! $\endgroup$ – Darkwizie Nov 13 '18 at 23:07
  • $\begingroup$ "Each turn we select at random k distinct bins out of the n bins in which we place a ball." Does it mean that $k $ balls are placed in (randomly chosen) $k $bins each turn? $\endgroup$ – user Nov 13 '18 at 23:14
  • $\begingroup$ @user : Yes exactly $\endgroup$ – Darkwizie Nov 13 '18 at 23:21
  • $\begingroup$ The first part is essentially the same as math.stackexchange.com/questions/2147576/… which has two good responses $\endgroup$ – Henry Nov 13 '18 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.