Chcę zdecydować o pojemności 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 . p ∈ [ 40 … 120 ] E ∈ [ 10 3 … 10 12 ]
Idealnie chciałbym, aby najniższa liczba całkowita była C
taka, że 1-CDF[PoissonDistribution[E],C] < 2^-p
dla danego p
i E
; ale jestem zadowolony z niektórych C
nieco wyżej. Matematyka jest odpowiednia do obliczeń ręcznych, ale chciałbym obliczać C
od p
i E
w 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 1231
i wydaje się mieć rację (dzięki @Prastrastinator); jednak wynik dla obu jest p = 50
i , co jest niewłaściwe po niebezpiecznej stronie (i ma znaczenie: mój eksperyment powtarza się 2 25 razy lub więcej i chcę wyraźnie mniej niż 2 - 30 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 = 60
1250
źródło
C = Quantile[PoissonDistribution[E],1-2^p]
?p
i problemów z precyzją oraz nazwE
iC
zastrzeż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!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ą.
źródło
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. LetY be a Poisson random variable with parameter λ . Put
G(x)=2(xlnxλ+λ−x)−−−−−−−−−−−−−−−√ sign(x−λ).
Let Φ denote the cumulative distribution function for the standard normal law. Then, for all integer k≥0 ,
P(Y<k)≤Φ(G(k))≤P(Y≤k),
which is equivalent to
Φ(G(k−1))≤P(Y<k)≤Φ(G(k))
for all integer k>0 .
Moreover, Φ(G(k+(1/2)))≤P(Y≤k) which implies that
Φ(G(k−1/2))≤P(Y<k)≤Φ(G(k))
for all integer k>0 .
źródło