3
$\begingroup$

This is an interview question. i am not sure how to solve such problems.

Problem:

You are given $n$ white balls in the beginning.Each day you pick up a ball randomly color it red and put it back. If it is already colored, you simply put it back. This operation is performed for $d$ days. What is the probability that after $d$ days you will have greater than $k$ balls colored?

$\endgroup$
  • 1
    $\begingroup$ You can also see this as a counting problem. In how many ways will you have greater than $k$/less than $k$ balls colored? And how many different results can you get? $\endgroup$ – TMM Aug 12 '12 at 16:09
1
$\begingroup$

The easiest way is on a spreadsheet using a recurrence for $p(n,d,x)$ the probability that starting with $n$ balls, then after $d$ days you have exactly $x$ balls coloured. Starting with $p(n,0,0) = 1 $ and $p(n,0,x) = 0 $ for $x\gt 0$ then each day you either increase the number you have coloured or you don't so $$ p(n,d,x) = \frac{n-x+1}{n} p(n,d-1,x-1) + \frac{x}{n} p(n,d-1,x).$$

To have the probability of greater than $k$ balls coloured , you just take the sum $$\sum_{x=k+1}^{n} p(n,d,x) .$$

(There is actually a formula $$p(n,d,x) = S_2(d,x) \frac{ n! }{ (n-x)! \; n^d}$$ where $S_2(d,x)$ is a Stirling number of the second kind, but I think it would be unreasonable to expect this in an interview.)

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.