Find the probability of having k red balls after d days 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?
 A: Hmm, tough for an interview question. Condition the probability of being finished on the d+1-th draw on already having exactly k-1 red balls in the bag. The probability of being finished with the next draw is $1-\frac{k-1}{n}$. Now we just need to find the probability of having exactly k-1 red balls after d draws and multiply. 
This is identical to the probability of drawing exactly k-1 different balls from an urn with n balls after d draws with replacement. The probability of drawing at most k-1 different balls should be given by $\frac{(k-1)^d}{n^d}$. 
Drawing exactly k-1 is then given by subtracting the chance of drawing at most k-2, so we get
$\frac{(k-1)^d}{n^d}-\frac{(k-2)^d}{n^d}$. So we get a total probability of
$(1-\frac{k-1}{n})(\frac{(k-1)^d}{n^d}-\frac{(k-2)^d}{n^d})$. Note that this only holds for $d>=k$. I might also have made a mistake along the way. There is also probably a faster way to do this. And one might be able to simplify the result. Might help anyway.  
A: This is a Markov chain exercise. Consider the vector $P_{d} = (p_d^0, p_d^1, \ldots, p_d^n) \in [0,1]^{n+1}$ where $p_d^k$ is the probability that there are exactly $k$ red ball in the bag after $d$ draws. Now, since $p_{d+1}^{k} = \frac{n-(k-1)}{n}p_{d}^{k-1} + \frac{k}{n}p_{d}^{k}$ one can immediately find a matrix $A \in M_{{n+1} \times {n+1}}$ such that 
$P_{d+1}=A \cdot P_d$ and solve the problem by computing $P_d = A^d P_0$ with $P_0=(1,0,0,\ldots,0)$.
In conclusion, an algorithm to compute $p_d^k$ with complexity $\mathcal{O}(pk)$ is the following.


*

*Define $(p_0^0, p_0^1, \ldots, p_0^k)=(1,0,\ldots,0)$.

*Compute $(p_{j+1}^0, p_{j+1}^1, \ldots, p_{j+1}^k)$ using the formula  $p_{j+1}^{i} = \frac{n-(i-1)}{n}p_{j}^{i-1} + \frac{i}{n}p_{i}^{j}$ for $j=0, \ldots, d-1$.

*The result is given by $p^k_d$.

A: I think you have to set up this problem using Markov Chains theory, are you familiar with it?
The system you are considering is a discrete system which can be in any of the (n+1) states
{ [0], [1], [2], ... ,[n] }
where [j] is the state with j red balls. The system starts from the state [0] and evolves over time with a transition matrix, (probability of going from state i to state j)
$T_{ij}=\frac{n-i}{n}$ if j=i+i
$T_{ij}=\frac{i}{n}$ if j=i
$T_{ij}=0$ otherwise
Now this Markov chain is stationary and you know the initial distribution (which is a delta function peaked on the state [0])
You can get the distribution at a future time k (in this case you are interested in time k, which means after k steps) by multiplying the transition matrix by itself k times and then multiplying the result times the initial distribution
$p_k=T^k p_0$
where $p_k$ is the vector of probabilities (indexed by the state) at time k and $p_0$ is the vector of probabilities at time 0 (delta function at 0).
Now, since the product fo a matrix ($T^k$) times a vector ($p_0$) which has a 1 at the first element and 0 everywhere else (your delta function) is just the first column of the matrix and since you are interested in the probability of $d$ red balls then what you are looking for is the matrix element 
$(T^k)_{d+1,0}$
I've put d+1 because we take [0] balls to be the first element.
So all you have to do is to do the matrix product and look for that element. Possibly, since the matrix is nearly diagonal, you will find that you can calculate it analytically, give it a go
