# Find probability that after $d$ days you will have greater than $k$ balls colored?

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?

• 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? – TMM Aug 12 '12 at 16:09

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