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}^nfrac{λ^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
