[Solved]: Fast Poisson quantile computation

Problem Detail: 

I am seeking a fast algorithm to compute the following function, a quantile of the Poisson distribution: $$f(n, \lambda) = e^{-\lambda} \sum_{k=0}^{n} \frac{\lambda^k}{k!} $$

I can think of an algorithm in $O(n)$, but considering the structure of the series, there is probably a $O(1)$ solution (or at least a good $O(1)$ approximation). Any take?

Asked By : Joannes Vermorel

Answered By : jmad

Given a precision $ε>0$ you want to compute $f(n,λ)$. When $n≤m$, let $g$ be the error function, that is the difference, between the sum of the $m-1$ first terms and the actual value $f(n,λ)$.

$$g(n,λ,m)=e^{-λ}\sum_{k=m}^n\frac{λ^k}{k!}$$

You want to find a $m$ big enough to have $g(n,λ,m)≤ε$. Then you just have to remark that the following terms are not very big so you can go a little bit further:

$$g(n,λ,m)<e^{-λ}\sum_{k=m}^∞\frac{λ^k}{k!}=h_λ(m)$$

Since the well-known corresponding series converges, $\lim h_λ = 0$. So for all $ε$ and $λ$ you can find a $m_{ε,λ}$ such that $m_{ε,λ}$ steps are enough to compute $f(n,λ)$ with precision $ε$.

Given $ε$ and $λ$ your problem is in $O(1)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1796