Its an interview question..
Initially there are n white balls. Each day you are allowed to take a ball. If the ball in hand is white, replace it by red ball. If it is red in color, put that ball into bag without doing anything. The question is to find the probability to have k red balls after d days.Give the general solution
I started with making a binary tree.. initially on 1st day we have n white balls, when we pick 1 ball and apply the rule we get 1 red ball and (n-1) white balls on second day pick 1 ball, it could be white or red. if we pick white we are left with 2red and (n-2) white balls otherwise 1 red and (n-1) white balls. these two nodes again will each have two children each for the 3rd day.. 1 with 3 red balls and (n-3) white balls , other with 2 red balls and (n-2)white balls and so on
But this is a direct recursive formula, is there a better solution? I think it can be solved with dynamic programming, but I am unable to connect dynamic programming with probability. any idea how to do this ?
Also can someone help me with how the probability will be calculated in this question?
Last, Can someone give me a good resource to study probability based programming questions?