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?

  • 1
    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?2012-08-12

1 Answers 1

1

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