¿Aproximación simple de la distribución acumulativa de Poisson en cola larga?

Quiero decidir la capacidad de una tabla para que tenga probabilidades residuales inferiores a para desbordarse para , suponiendo que el número de entradas sigue una ley de Poisson con una determinada expectativa . $C$ $2^{-p}$ $p\in[40\dots 120]$ $E\in[10^3\dots 10^{12}]$

Idealmente, quiero el número entero más bajo Ctal que 1-CDF[PoissonDistribution[E],C] < 2^-ppara dado py E; pero estoy contento con algunos un Cpoco más altos que eso. Mathematica está bien para el cálculo manual, pero me gustaría calcular Cdesde py Een tiempo de compilación, lo que me limita a la aritmética de enteros de 64 bits.

Actualización: en Mathematica (versión 7) e = 1000; p = 40; c = Quantile[PoissonDistribution[e], 1 - 2^-p]está 1231y parece correcto (gracias @Procrastinator); sin embargo, el resultado para ambos p = 50y p = 60es 1250, lo cual es incorrecto en el lado inseguro (y es importante: mi experimento se repite como veces o más, y quiero demostrablemente menos de probabilidades generales de falla). Quiero una aproximación cruda pero segura usando solo aritmética de enteros de 64 bits , como está disponible en C (++) en tiempo de compilación. $2^{25}$ $2^{-30}$

poisson-distribution fgrieu
fuente

¿Qué tal C = Quantile[PoissonDistribution[E],1-2^p]?

El término principal de la función de masa de probabilidad del Poisson domina en la cola.

Cardenal

@Procrastinator: sí, eso funciona en Mathematica (excepto por pcuestiones de signos y precisión, y nombres Ey Cque están reservados). PERO necesito una aproximación simple de eso, posiblemente cruda (pero en el lado seguro) usando aritmética de enteros de 64 bits solamente.

fgrieu

Re la actualización: Mathematica 8 devuelve 1262 para y 1290 para . Re Aproximación normal (@Proc): no se puede esperar que esto funcione bien en las colas, lo cual es crucial para el cálculo.

p = 50

$p=50$

p = 60

$p=60$

whuber

Quizás deberías preguntar en stackoverflow. No estoy familiarizado con las limitaciones que tienes. No sé qué le impide usar la asignación de memoria dinámica, o si puede usar la ramificación para decidir el tamaño de la matriz, o cuáles son los costos de definir una matriz que sea el doble del tamaño que necesita (y luego no usar todo de eso). Si alguna función como (solo como ejemplo) dio Si responde exactamente, ¿podría implementar una aproximación bajo sus restricciones o no? Parece un problema de programación ahora.

μ + \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

Respuestas:

Una distribución de Poisson con una media grande es aproximadamente normal, pero debe tener cuidado de querer un límite de cola y la aproximación normal es proporcionalmente menos precisa cerca de las colas.

Un enfoque utilizado en esta pregunta de MO y con distribuciones binomiales es reconocer que la cola disminuye más rápidamente que una serie geométrica, por lo que puede escribir un límite superior explícito como una serie geométrica.

\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}$

La línea 2 línea 3 estaba relacionada con la fórmula de Stirling. En la práctica, creo que quiere resolver numéricamente mediante la búsqueda binaria. El método de Newton comienza con una suposición inicial deTambién debería funcionar. $\to$ $-p \log 2 = \log(\text{bound})$ $D = \mu + c \sqrt \mu.$

Por ejemplo, con y , la solución numérica que obtengo es 1384.89. Una distribución de Poisson con media toma los valores de a con probabilidadLos valores de a ocurren con probabilidad $p=100$ $\mu = 1000$ $1000$ $0$ $1384$ $1-1/2^{100.06}.$ $0$ $1383$ $1-1/2^{99.59}.$

Douglas Zare
fuente

+1. Otro enfoque relaciona las probabilidades de cola de Poisson (a la derecha) con las probabilidades de cola de las distribuciones Gamma (a la izquierda), que se pueden estimar (sobre) de cerca con una aproximación de punto de silla de montar.

whuber

Hay un largo camino desde eso hasta algo restringido a la aritmética de enteros de 64 bits (sin exp, log, sqrt ...) pero trabajaré en ello; ¡gracias a todos!

fgrieu

(+1) Hasta la invocación de la aproximación de Stirling (que es irrelevante), este es exactamente el límite que estaba (opacamente) haciendo referencia en mi comentario al OP. (Por ejemplo, ver aquí .)

cardenal

Puede ver P. Harremoës: límites agudos en las probabilidades de cola para las variables aleatorias de Poisson https://helda.helsinki.fi/bitstream/handle/10138/229679/witmse_proc_17.pdf Las principales desigualdades son las siguientes. Sea una variable aleatoria de Poisson con parámetro . Ponga Let denota la función de distribución acumulativa para la ley normal estándar. Entonces, para todos los enteros , que es equivalente a para todos los enteros $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$ . Además, que implica que para todos los enteros .

Φ (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
fuente

Si pudiera escribir la ecuación clave (suponiendo que solo haya una o dos) que ayudaría en caso de que el enlace se bloquee en algún momento.

jbowman