6
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Is this homework? $\endgroup$
    – MånsT
    Apr 12, 2012 at 14:42
  • $\begingroup$ its an interview question $\endgroup$
    – anuja
    Apr 12, 2012 at 15:10
  • $\begingroup$ Though it may not at first appear like it, the following question is somewhat related. It is different in that it asks a little different question and, after drawing each red ball, one doesn't replace it, but throws it away. Related: stats.stackexchange.com/questions/19667 $\endgroup$
    – cardinal
    Apr 12, 2012 at 17:31
  • $\begingroup$ This is kind of a cheap answer so I offer it as a comment. Instead of replacing white balls, mark them as red. There are $n^{[k]}=n(n-1)\cdots(n-k+1)$ distinct marking sequences. Each marked ball determines the set of days in which it was marked, partitioning the days. The number of partitions is $S(d,k)$, the Stirling number of the second kind. The answer therefore is $n^{[k]}S(d,k)$ divided by $n^d$, the number of equiprobable sequences. Stirling numbers have simple generating functions and enjoy various relations, so we have made progress. $\endgroup$
    – whuber ♦
    Apr 12, 2012 at 17:54
  • $\begingroup$ Incidentally, the unavoidable appearance of $S(d,k)$ in the solution (it does not simplify further) indicates that although the Markov chain methods will work, it will be moderately difficult to carry them through in general and will not lead to nice closed formulas: it will be tantamount to rediscovering the Stirling numbers. $\endgroup$
    – whuber ♦
    Apr 12, 2012 at 17:57

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

  1. Define $(p_0^0, p_0^1, \ldots, p_0^k)=(1,0,\ldots,0)$.
  2. 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$.
  3. The result is given by $p^k_d$.
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ And the solution is? $\endgroup$
    – whuber ♦
    Apr 12, 2012 at 16:49
  • $\begingroup$ the solution is computable in $O(kd)$ operations. $\endgroup$
    – Alekk
    Apr 12, 2012 at 21:12
  • $\begingroup$ Alekk, It appears that the solution, in the form you have left it, requires $d$ multiplications of an $n+1$ by $n+1$ matrix, or $O(n^2 d)$ operations: one might be better off just using the dynamic program, which indeed is $O(kd)$. Please remember, too, that the OP seeks a "general solution," not just a computational procedure. Although you are quite right that this can be viewed as a Markov chain problem, obtaining that general solution doesn't look quite as trivial as you seem to suggest. $\endgroup$
    – whuber ♦
    Apr 12, 2012 at 21:28
  • $\begingroup$ Yes: but the matrix has only elements on the main and lower diagonal + if one is interested in computing $p_d^k$, one does not need to compute $p_{j}^{l}$ for $j \leq d$ and $l \geq d+1$ -- this leads to an algorithm which requires only $O(kd)$ operations. This algorithm might be very similar to the dynamic programming approach, though. $\endgroup$
    – Alekk
    Apr 13, 2012 at 9:19
  • $\begingroup$ Very good! But what would be greatly welcome in any case is an explicit description of the algorithm. $\endgroup$
    – whuber ♦
    Apr 13, 2012 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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