Einfache Annäherung der kumulativen Poisson-Verteilung im langen Schwanz?

Ich möchte die Kapazität einer Tabelle so bestimmen , dass sie für ein gegebenes eine Restwahrscheinlichkeit von weniger als zum Überlaufen aufweist , vorausgesetzt, die Anzahl der Einträge folgt einem Poisson-Gesetz mit einer gegebenen Erwartung . $C$ $2^{-p}$ $p\in[40\dots 120]$ $E\in[10^3\dots 10^{12}]$

Idealerweise möchte ich die niedrigste Ganzzahl, Cso dass 1-CDF[PoissonDistribution[E],C] < 2^-pfür gegeben pund E; aber ich bin zufrieden mit Cetwas höherem. Mathematica eignet sich gut für die manuelle Berechnung, aber ich möchte Cvon pund Ezur Kompilierungszeit berechnen , was mich auf 64-Bit-Ganzzahlarithmetik beschränkt.

Update: In Mathematica (Version 7) e = 1000; p = 40; c = Quantile[PoissonDistribution[e], 1 - 2^-p]ist 1231und scheint es ungefähr richtig (danke @Procrastinator); Das Ergebnis ist jedoch für beide p = 50und p = 60ist 1250, was auf der unsicheren Seite falsch ist (und wichtig ist: Mein Experiment wiederholt sich wie Mal oder mehr, und ich möchte nachweislich weniger als allgemeine Ausfallwahrscheinlichkeiten). Ich möchte eine grobe, aber sichere Annäherung, die nur 64-Bit-Ganzzahlarithmetik verwendet , wie sie zur Kompilierungszeit in C (++) verfügbar ist. $2^{25}$ $2^{-30}$

poisson-distribution fgrieu
quelle

Wie wäre es C = Quantile[PoissonDistribution[E],1-2^p]?

Der Leitterm der Wahrscheinlichkeitsmassenfunktion des Poisson dominiert im Schwanz.

Kardinal

@Procrastinator: ja , das funktioniert in Mathematica ( mit Ausnahme von Zeichen pund Präzision Fragen und Namen Eund Cdie reserviert ist). ABER ich brauche eine einfache Annäherung daran, möglicherweise grob (aber auf der sicheren Seite), wenn nur eine 64-Bit-Ganzzahl-Arityhmetik verwendet wird!

fgrieu

p = 50

$p=50$

p = 60

$p=60$

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

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

Antworten:

Eine Poisson-Verteilung mit großem Mittelwert ist ungefähr normal, aber Sie müssen darauf achten, dass Sie eine Schwanzbindung wünschen und die normale Näherung in der Nähe der Schwänze proportional weniger genau ist.

Ein Ansatz, der in dieser MO-Frage und bei Binomialverteilungen verwendet wird, besteht darin, zu erkennen, dass der Schwanz schneller abnimmt als eine geometrische Reihe, sodass Sie eine explizite Obergrenze als geometrische Reihe schreiben können.

\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
quelle

+1. Ein anderer Ansatz bezieht Poisson-Schwanzwahrscheinlichkeiten (rechts) auf Schwanzwahrscheinlichkeiten von Gamma-Verteilungen (links), die mit einer Sattelpunktnäherung genau (über) geschätzt werden können.

whuber

Davon ist ein langer Weg zu etwas, das auf 64-Bit-Ganzzahlarithmetik beschränkt ist (ohne exp, log, sqrt ..), aber ich werde daran arbeiten. Danke an alle!

fgrieu

(+1) Bis zum Aufruf von Stirlings Näherung (was irrelevant ist) ist dies genau die Grenze, auf die ich mich (undurchsichtig) in meinem Kommentar zum OP bezogen habe. ( Siehe zum Beispiel hier .)

Kardinal

$Y$ $\lambda$

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

Φ

$\Phi$

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

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

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

k > 0

$k>0$

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

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

Φ (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))$

k > 0

$k>0$

Pavel Ruzankin
quelle

Wenn Sie die Schlüsselgleichung aufschreiben könnten (vorausgesetzt, es gibt nur eine oder zwei), würde dies helfen, falls die Verbindung irgendwann unterbrochen wird.

Jbowman