Fist I'll explain the problem I had to solve (and which I solved), and then ask a related question.

We have a bin with 2 balls: black and white. We take one from the bin and put back. Than we add a black ball into the bin (so there are 3 balls: 1 white and 2 blacks). Then we take a ball from the bin and put back. These adding balls and taking one of them repeats again and again, until we exhaust all the attempts we have.

I had to calculate the probability that the overall count of taken white balls is bigger than the one of black balls.

For simplicity lets take 4 attempts (in the real task this figure was much bigger).

To solve the problem I decided to use generating function. For the first attempt the probability to pick white is $p=1/2$, and to pick a black is $q=1/2$.

The second attempt gives this figures: $p=1/3$, $q=2/3$.

Third: $p=1/4$, $q=3/4$.

And so on.

So, the generating function is: $$G = (1/2+1/2 \cdot z)(2/3+1/3 \cdot z)(3/4+1/4 \cdot z)(4/5+1/5 \cdot z) = \\ =1/5+5/12 \cdot z+7/24 \cdot z^2+1/12 \cdot z^3+1/120 \cdot z^4$$

To calculate that we took more white balls than black we sum up coefficients before $z^3$ and $z^4$ and get $11/120$.

I implemented it into the algorithm for it to be able to process arbitrary number of attempts. To extract the coefficients I calculated corresponding derivatives and calculated them at $z=0$. For example to get $1/12$ before $z^3$, I did this: $$\frac {1}{3!} \cdot\frac {d^{3}G}{dz^{3}}\bigg|_{z=0} = 1/12$$.

Then I summed all the needed coefficients.

The problem is that I had to use symbolic math.

How I can avoid using symbolic calculation and use just numeric calculation to calculate the needed coefficients?

May be there is a way to do it without a generating function at all? Maybe there exist other formulas, which are better for numeric calculations?


You can find numerical approximations to derivatives of a function $G$ by observing that e.g. $\frac1h(G(h)-G(0))$ is an approximation for $G'(0)$. In fact, $\frac1h(G(h)-G(0))=G'(\xi)$ for some $\xi$ with $0<\xi<h$ by the mean value theorem. Approximations for higher derivatives can be obtained from higher differences, e.g. $\frac{G(2h)-2G(h)+G(0)}{h^2}\approx G''(0)$ and similar alternating sums with binomial coefficients work for even higher derivatives. Note however, that you should not simply plug in a very small value of $h$ and take the calculated value for granted. Because of the nearly cancelling subtractions, a lot of precision is lost this way! Rather make calculations for several small but not too small values of $h$ and use methods of numerical extrapolation.


you can calculate the coefficient using conv in matlab for example a= [1/2 1/2] b= [2/3 1/3] c = conv(a,b) then d = [3/4 1/4] e = conv(c,d)

continue ( you can write as for loop) Then you get coefficients for all terms from high power to low power

  • $\begingroup$ Thank you! This it closer to an answer I would like to accept. Still, I expect that there could be a way to completely get rid of generating function (as I understand it's designed just to simplify things for those who make by-hand calculations), as there might be other formulas using for example binomial coefficients (it's just a guess). $\endgroup$ – ovgolovin Dec 19 '12 at 6:09
  • $\begingroup$ But yes, conv is much closer to numeric calculation of the probabilities than resorting to numeric approximate calculations of derivatives of the generating function as suggested in the other answer. $\endgroup$ – ovgolovin Dec 19 '12 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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