Use closed-form for calculations

[dbarowy]

Right now we use a monte carlo calculator based on Emery's proof-of-concept C++ code that I transliterated into Java. The current calculators generally work well, but they are expensive which is an issue when we have many threads, and they introduce nondeterminism into our test suite, which occasionally pops up for cases sensitive to edge effects.

Andrew supplied us with closed forms for the paper. We should use the closed forms instead.

[emeryberger]

The closed form unfortunately is not going to be fast -- IIRC the closed form depends on a binomial calculation, which is also not going to be cheap (but we should check). I propose a quick and dirty fix for now: make it deterministic by using our own RNG (e.g., the Marsaglia one I use in DieHard and friends), with a fixed seed. Improve the performance by memoizing a range of values.

[dbarowy]

Since we're already memoizing values, then initializing with a fixed seed is probably the easiest solution.

For the strictly binomial case, we could use the Poisson approximation. I don't know if this generalizes to multinomials. There's also Stirling's approximation although it may not approximate well enough for small n.

[dbarowy]

While chatting about some of the formulas in the paper (since we're revisiting them for CACM), @ccurtsinger pointed out that one of the terms, \sum_{j=m}^{\infinity} (p\lambda)^j/j! is guaranteed to converge since j! grows faster than x^j. Dropping the term into Wolfram Alpha reveals that there is indeed an easily computable alternate expression using the gamma function:

http://www.wolframalpha.com/input/?i=sum+from+n%3Dm+to+infinity+of+%28%28p*lambda%29^n%2Fn!%29

There's a nice explanation here that explains how the gamma function can be used in place of factorials:

http://en.wikipedia.org/wiki/Gamma_function#Calculating_products

As for the other, non-infinite sums, with a little monkeying around in Wolfram, I get:

http://www.wolframalpha.com/input/?i=sum+from+n%3D0+to+m-1+of+%28%28p*lambda%29^n%2Fn!%29

Note that unlike the Stirling approximation I suggested before, these alternate expressions are exact.