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

Question

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

Idealmente, quiero el menor número entero C tal que 1-CDF[PoissonDistribution[E],C] < 2^-p para un determinado p y E ; pero me conformo con algunos C un poco más alto que eso. Mathematica está bien para el cálculo manual, pero me gustaría calcular C de p y E en 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] es 1231 y parece más o menos correcto (gracias @Procrastinator); sin embargo, el resultado para ambos p = 50 y p = 60 es 1250 que está mal en el lado inseguro (e importa: mi experimento se repite como $2^{25}$ veces o más, y quiero demostrar menos que $2^{-30}$ probabilidades generales de fracaso). Quiero alguna aproximación cruda pero segura utilizando sólo aritmética de enteros de 64 bits como el disponible en C(++) en tiempo de compilación.

Answer 1

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

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

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

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

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

Answer 2

Puede ver P. Harremoës: Sharp Bounds on Tail Probabilities for Poisson Random Variables https://helda.helsinki.fi/bitstream/handle/10138/229679/witmse_proc_17.pdf Las principales desigualdades son las siguientes. Sea $Y$ sea una variable aleatoria de Poisson con parámetro $\lambda$ . Poner $$G(x)= \sqrt{2\left(x\ln \frac{x}{\lambda} +\lambda-x\right)} \ \ {\rm sign} \left(x-\lambda\right).$$ Dejemos que $\Phi$ denotan la función de distribución acumulativa para la ley normal estándar. Entonces, para todo número entero $k\ge 0$ , $${\bf P}(Y<k)\le \Phi(G(k)) \le {\bf P}(Y\le k),$$ lo que equivale a $$\Phi(G(k-1)) \le {\bf P}(Y<k)\le \Phi(G(k))$$ para todos los enteros $k>0$ . Además, $\Phi(G(k+(1/2))) \le {\bf P}(Y\le k)$ lo que implica que $$\Phi(G(k-1/2)) \le {\bf P}(Y<k)\le \Phi(G(k))$$ para todos los enteros $k>0$ .