Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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? –  TMM Aug 12 '12 at 16:09

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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