# Fast Poisson quantile computation

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?

• @FabioF. it does not depend of $n$. Given some precision it is indeed $O(1)$... But Joannes, Fabio's comment is still relevant: the complexity depends on the precision you want. For example you will probably need only a constant number of terms to reach the desired precision. (given some $λ$)
May 11 '12 at 20:54

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