# Calculating coefficients of generating function

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.
• 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. – ovgolovin Dec 19 '12 at 6:10