vdb@hou2g.UUCP (R.VANDERBEI) (08/25/85)
> Suppose you begin with a bag containing O openable pistachios, > and U unopenable pistachios. A trial consists of selecting a nut at random, > and eating it (if possible), or returning it to the bag. > How many trials, on the average, are required to consume all the "openable" > pistachios? Express the answer in terms of U and O. Let T[j] denote the expected amount of time to finish given that there are j openable ones left (and u unopenable ones - which is fixed). Then by asking ourselves what can happen on selecting the next nut, we arrive at the following recurrance relation: T[j] = 1 + (j/(j+u))*T[j-1] + (u/(j+u))*T[j]. The first term represents the fact that time has progressed one unit, the second term the possibility of selecting an openable nut, and the last one the possibility of selecting an unopenable one. This difference equation is easy to solve. The solution is: j T[j] = j + u*sum (1/i). i=1 This is very close to j + u ln j. To find the distribution of the time, you can apply similar reasoning but you will get a recurrence relation in two variables. I haven't written it down so I don't know how hard it is to solve. P.S. I forgot to mention that the boundary condition is T[0] = 0. Isn't math fun!