0
$\begingroup$

I want to determine (in an algorithm) the approximate surprisal of getting an outcome "as extreme as $k$" from the $Poisson(\lambda)$ distribution.

My original plan was to use $-log_2(1/2-|1/2-F_{Poisson(\lambda)}(k)|)$ but calculating $F_{Poisson(\lambda)}(k)$ requires the incomplete Gamma function which uses an iterative numerical algorithm. I am hoping to find a simple approximation (of the CDF, or even better, of the surprisal itself) that will allow me to speed things up, because I'm doing this for each pixel in a video.

The fact that erf has such simple rational function approximations made me think $F_{Poisson}$ might have something similar (though we have a 2D domain here so perhaps that was wishful thinking.) As a last resort, I might create a 2D lookup table with a log-log-spaced grid and use bilinear interpolation (on the surprisal directly).

Error

The surprisal only needs to be accurate to within about 1 bit for all surprisals less than about 15 bits, translating to the requirement that $F_{Poisson(\lambda)}(k)$ is approximated to within about 50% of the distance from whichever of 0 or 1 is closer until the remaining tail probability is about $2^{-15}$. I'm just making up these specifications to give a rough idea.

Previous related questions

My original question on SO involved a very skew Binomial distribution (of unknown N), but it is so skew that I lose nothing by approximating that with the Poisson distribution, thereby getting rid of one domain variable.

To be honest, I don't feel comfortable asking such an asker-specific question here, but the discussion here is what encouraged me to post it anyway. Any pointers or advice would be helpful.

$\endgroup$
0
$\begingroup$

For closure:

$$ F_{Poisson(\lambda)}(x) \approx \Phi(z) $$

where

$$ z = \frac{x-\lambda+\frac{2}{3}}{\sqrt{\lambda(1+0.68w+(0.12-signum(w)0.0325)w^2)}} $$

where

$$ w = \sqrt{\frac{x+\frac{1}{2}}{\lambda}}-1 $$

Using this approximation, the surprisal can then be calculated directly from $z$.

$\endgroup$

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.