5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ @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 $λ$) $\endgroup$
    – jmad
    May 11 '12 at 20:54
4
$\begingroup$

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

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