Proste przybliżenie skumulowanego rozkładu Poissona w długim ogonie?

Chcę zdecydować o pojemności $C$ tabeli, aby miała ona szanse resztkowe mniejsze niż na przelanie dla danego , zakładając, że liczba wpisów jest zgodna z prawem Poissona z danym oczekiwana . $2^{-p}$ $p\in[40\dots 120]$ $E\in[10^3\dots 10^{12}]$

Idealnie chciałbym, aby najniższa liczba całkowita była Ctaka, że 1-CDF[PoissonDistribution[E],C] < 2^-pdla danego pi E; ale jestem zadowolony z niektórych Cnieco wyżej. Matematyka jest odpowiednia do obliczeń ręcznych, ale chciałbym obliczać Cod pi Ew czasie kompilacji, co ogranicza mnie do 64-bitowej arytmetyki liczb całkowitych.

Aktualizacja: In Mathematica (wersja 7) e = 1000; p = 40; c = Quantile[PoissonDistribution[e], 1 - 2^-p]jest 1231i wydaje się mieć rację (dzięki @Prastrastinator); jednak wynik dla obu jest p = 50i , co jest niewłaściwe po niebezpiecznej stronie (i ma znaczenie: mój eksperyment powtarza się razy lub więcej i chcę wyraźnie mniej niż ogólnych szans na porażkę). Chcę pewne przybliżone, ale bezpieczne przybliżenie przy użyciu tylko 64-bitowej arytmetyki liczb całkowitych , jak to jest dostępne w C (++) w czasie kompilacji.p = 601250 $2^{25}$ $2^{-30}$

poisson-distribution

— fgrieu
źródło

Jak o C = Quantile[PoissonDistribution[E],1-2^p]?

W ogonie dominuje termin wiodący funkcji masy prawdopodobieństwa Poissona.

— kardynał

@ Procrastinator: tak, działa w Mathematica (z wyjątkiem znaków pi problemów z precyzją oraz nazw Ei Czastrzeżonych). ALE potrzebuję prostego przybliżenia tego, być może surowego (ale po bezpiecznej stronie), używając tylko 64-bitowej liczby całkowitej arytmetyki!

— fgrieu

Re aktualizacja: Mathematica 8 zwraca 1262 dla

i 1290 dla

. Re Normalne przybliżenie (@Proc): nie można oczekiwać, że zadziała to dobrze w ogonach, co ma kluczowe znaczenie dla obliczeń.

p = 50

$p=50$

p = 60

$p=60$

— whuber

Być może powinieneś zapytać o przepełnienie stosu. Nie znam ograniczeń, które masz. Nie wiem, co powstrzymuje cię od korzystania z dynamicznej alokacji pamięci, ani czy możesz użyć rozgałęzienia, aby zdecydować o wielkości tablicy, ani jakie są koszty zdefiniowania tablicy, która jest dwa razy większa niż potrzebujesz (a następnie nie używasz wszystkich tego). Jeśli niektóre działają jak

(tylko jako przykład) dał ci dokładną odpowiedź, czy byłbyś w stanie zastosować przybliżenie pod swoimi ograniczeniami, czy nie? Wygląda teraz na problem z programowaniem.

μ + \sqrt{\log \log μ} \log μ \sqrt{μ} + p \frac{\sqrt{μ}}{\log μ}

$\mu + \sqrt{\log\log \mu} \log \mu \sqrt \mu + p \frac{\sqrt{\mu}} {\log \mu}$

— Douglas Zare

Odpowiedzi:

Rozkład Poissona z dużą średnią jest w przybliżeniu normalny, ale musisz uważać, aby chcieć związać ogon, a normalne przybliżenie jest proporcjonalnie mniej dokładne w pobliżu ogonów.

Jednym podejściem zastosowanym w tym pytaniu MO i przy rozkładach dwumianowych jest rozpoznanie, że ogon zmniejsza się szybciej niż seria geometryczna, więc można napisać wyraźną górną granicę jako serię geometryczną.

\begin{array}{rcl} \sum_{k = D}^{\infty} \exp (- μ) \frac{μ^{k}}{k!} & < & \sum_{k = D}^{\infty} \exp (- μ) \frac{μ^{D}}{D!} (\frac{μ}{D + 1})^{k - D} \\ = & \exp (- μ) \frac{μ^{D}}{D!} \frac{1}{1 - \frac{μ}{D + 1}} \\ < & \exp (- μ) \frac{μ^{D}}{\sqrt{2 π D} (D / e)^{D}} \frac{1}{1 - \frac{μ}{D + 1}} \\ = & \exp (D - μ) (\frac{μ}{D})^{D} \frac{D + 1}{\sqrt{2 π D} (D + 1 - μ)} \end{array}

$\begin{eqnarray}\sum_{k=D}^\infty \exp(-\mu)\frac{\mu^k}{k!} & \lt & \sum_{k=D}^\infty \exp(-\mu) \frac{\mu^D}{D!}\bigg(\frac \mu{D+1}\bigg)^{k-D} \\ & = & \exp(-\mu)\frac{\mu^D}{D!}\frac{1}{1-\frac{\mu}{D+1}} \\ & \lt & \exp(-\mu) \frac{\mu^D}{\sqrt{2\pi D}(D/e)^D} \frac{1}{1-\frac{\mu}{D+1}} \\ & = & \exp(D-\mu) \bigg(\frac{\mu}{D}\bigg)^D \frac{D+1}{\sqrt{2\pi D} (D+1-\mu)}\end{eqnarray}$

$\to$ $-p \log 2 = \log(\text{bound})$ $D = \mu + c \sqrt \mu.$

$p=100$ $\mu = 1000$ $1000$ $0$ $1384$ $1-1/2^{100.06}.$ $0$ $1383$ $1-1/2^{99.59}.$

— Douglas Zare
źródło

+1. Another approach relates Poisson tail probabilities (on the right) to tail probabilities of Gamma distributions (on the left), which can be closely (over)estimated with a saddlepoint approximation.

— whuber

There's a long way from that to something restricted to 64-bit integer arithmetic (without exp, log, sqrt..) but I will work on it; thanks all!

— fgrieu

(+1) Up to the invocation of Stirling's approximation (which is irrelevant), this is exactly the bound I was (opaquely) referencing in my comment to the OP. (For example, see here.)

— cardinal

You may see P. Harremoës: Sharp Bounds on Tail Probabilities for Poisson Random Variables https://helda.helsinki.fi/bitstream/handle/10138/229679/witmse_proc_17.pdf The main inequalities there are as follows. Let $Y$ be a Poisson random variable with parameter $\lambda$ . Put

G (x) = \sqrt{2 (x \ln \frac{x}{λ} + λ - x)} s i g n (x - λ) .

$G(x)= \sqrt{2\left(x\ln \frac{x}{\lambda} +\lambda-x\right)} \ \ {\rm sign} \left(x-\lambda\right).$ Let

Φ

$\Phi$ denote the cumulative distribution function for the standard normal law. Then, for all integer

k \geq 0

$k\ge 0$ ,

P (Y < k) \leq Φ (G (k)) \leq P (Y \leq k),

${\bf P}(Y<k)\le \Phi(G(k)) \le {\bf P}(Y\le k),$ which is equivalent to

Φ (G (k - 1)) \leq P (Y < k) \leq Φ (G (k))

$\Phi(G(k-1)) \le {\bf P}(Y<k)\le \Phi(G(k))$ for all integer

k > 0

$k>0$ . Moreover,

Φ (G (k + (1 / 2))) \leq P (Y \leq k)

$\Phi(G(k+(1/2))) \le {\bf P}(Y\le k)$ which implies that

Φ (G (k - 1 / 2)) \leq P (Y < k) \leq Φ (G (k))

$\Phi(G(k-1/2)) \le {\bf P}(Y<k)\le \Phi(G(k))$ for all integer

k > 0

$k>0$ .

— Pavel Ruzankin
źródło

If you could write out the key equation (assuming there are only one or two) that would help in case the link goes dead at some time.

— jbowman