patternMinor
Fast Poisson quantile computation
Viewed 0 times
fastquantilecomputationpoisson
Problem
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?
$$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?
Solution
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)$.
$$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)$.
Context
StackExchange Computer Science Q#1796, answer score: 4
Revisions (0)
No revisions yet.