1
$\begingroup$

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?

2 Answers 2

1

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 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.

1

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

  • 0
    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.2012-12-19