Aproximação simples da distribuição cumulativa de Poisson na cauda longa?

Eu quero decidir a capacidade de uma tabela para que ela tenha chances residuais menores que para transbordar para um dado , assumindo que o número de entradas siga uma lei de Poisson com uma dada expectativa . $C$ $2^{-p}$ $p\in[40\dots 120]$ $E\in[10^3\dots 10^{12}]$

Idealmente, quero o número inteiro mais baixo de Ctal modo que 1-CDF[PoissonDistribution[E],C] < 2^-pfor dado pe E; mas estou contente com um Cpouco mais alto que isso. O Mathematica é bom para computação manual, mas eu gostaria de calcular a Cpartir pe Eem tempo de compilação, o que me limita à aritmética de número inteiro de 64 bits.

Atualização: No Mathematica (versão 7) e = 1000; p = 40; c = Quantile[PoissonDistribution[e], 1 - 2^-p]está 1231e parece certo (obrigado @Procrastinator); no entanto, o resultado para ambos p = 50e p = 60é 1250, o que é errado do lado inseguro (e importa: meu experimento se repete como vezes ou mais, e eu quero comprovadamente menos de chances gerais de falha). Eu quero alguma aproximação bruta, mas segura, usando apenas aritmética de número inteiro de 64 bits , como disponível em C (++) em tempo de compilação. $2^{25}$ $2^{-30}$

poisson-distribution fgrieu
fonte

Que tal C = Quantile[PoissonDistribution[E],1-2^p]?

O termo principal da função de massa de probabilidade do Poisson domina na cauda.

cardeal

@ Procrastinator: sim, que funciona no Mathematica (exceto problemas de sinal pe precisão, nomes Ee Creservados). MAS preciso de uma aproximação simples disso, possivelmente bruta (mas no lado seguro), usando apenas aritmética de número inteiro de 64 bits!

fgrieu

Re a atualização: O Mathematica 8 retorna 1262 para e 1290 para . Re Aproximação normal (@Proc): não se pode esperar que funcione bem nas caudas, o que é crucial para o cálculo.

p = 50

$p=50$

p = 60

$p=60$

whuber

Talvez você deva perguntar sobre o stackoverflow. Não estou familiarizado com as restrições que você tem. Não sei o que o impede de usar a alocação dinâmica de memória, ou se você pode usar a ramificação para decidir o tamanho da matriz ou quais são os custos de definir uma matriz com o dobro do tamanho necessário (e depois não usar todos os ). Se alguma função como (apenas como exemplo) forneceu você a resposta exata, você seria capaz de implementar uma aproximação sob suas restrições ou não? Parece um problema de programação agora.

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

Respostas:

Uma distribuição de Poisson com média alta é aproximadamente normal, mas é preciso ter cuidado para que você queira um rabo preso e a aproximação normal seja proporcionalmente menos precisa perto dos rabos.

Uma abordagem usada nesta questão MO e com distribuições binomiais é reconhecer que a cauda diminui mais rapidamente que uma série geométrica, para que você possa escrever um limite superior explícito como uma série 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}$

A linha 2 linha 3 estava relacionada à fórmula de Stirling. Na prática, acho que você deseja resolver numericamente usando a pesquisa binária. O método de Newton começando com um palpite inicial detambém deve funcionar. $\to$ $-p \log 2 = \log(\text{bound})$ $D = \mu + c \sqrt \mu.$

Por exemplo, com e , a solução numérica que recebo é 1384.89. Uma distribuição de Poisson com média leva os valores de a com probabilidadeOs valores de a ocorrem com probabilidade $p=100$ $\mu = 1000$ $1000$ $0$ $1384$ $1-1/2^{100.06}.$ $0$ $1383$ $1-1/2^{99.59}.$

Douglas Zare
fonte

+1. Outra abordagem relaciona as probabilidades de cauda de Poisson (à direita) às probabilidades de cauda de distribuições Gamma (à esquerda), que podem ser estimadas de perto (acima) com uma aproximação do ponto de sela.

whuber

Há um longo caminho desde algo restrito à aritmética de número inteiro de 64 bits (sem exp, log, sqrt ..), mas vou trabalhar nisso; obrigado a todos!

fgrieu

(+1) Até a invocação da aproximação de Stirling (que é irrelevante), esse é exatamente o limite que eu estava (opaca) referenciando em meu comentário ao OP. (Por exemplo, veja aqui .)

cardeal

Você pode ver P. Harremoës: limites agudos nas probabilidades de cauda para variáveis aleatórias de Poisson https://helda.helsinki.fi/bitstream/handle/10138/229679/witmse_proc_17.pdf As principais desigualdades são as seguintes. Seja uma variável aleatória de Poisson com o parâmetro . Coloque Let denota a função de distribuição cumulativa para a lei normal padrão. Então, para todo número inteiro , que é equivalente a para todo o inteiro $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$ . Além disso, que implica que para todo o número inteiro .

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

Se você pudesse escrever a equação chave (supondo que haja apenas uma ou duas) que ajudaria caso o link se esgotasse em algum momento.

jbowman