Vantagens do Box-Muller sobre o método CDF inverso para simular a distribuição normal?

Para simular uma distribuição normal a partir de um conjunto de variáveis uniformes, existem várias técnicas:

O algoritmo de Box-Muller , no qual se amostram duas variáveis uniformes independentes em e as transforma em duas distribuições normais padrão independentes via: $(0,1)$
$Z_{0} = \sqrt{- 2 ln U_{1}} cos (2 π U_{0}) Z_{1} = \sqrt{- 2 ln U_{1}} sin (2 π U_{0})$ $Z_0 = \sqrt{-2\text{ln}U_1}\text{cos}(2\pi U_0)\\ Z_1 = \sqrt{-2\text{ln}U_1}\text{sin}(2\pi U_0)$
o método CDF , onde se pode equiparar o cdf normal a uma variável uniforme: e derivar $(F(Z))$
$F (Z) = U$ $F(Z) = U$ $Z = F^{- 1} (U)$ $Z = F^{-1}(U)$

Minha pergunta é: qual é computacionalmente mais eficiente? Eu acho que é o último método - mas a maioria dos artigos que li usa Box-Muller - por quê?

Informação adicional:

O inverso do CDF normal é conhecido e dado por:

F^{- 1} (Z) = \sqrt{2} \erf^{- 1} (2 Z - 1), Z \in (0, 1) .

$F^{-1}(Z)\; =\; \sqrt2\;\operatorname{erf}^{-1}(2Z - 1), \quad Z\in(0,1).$

Portanto:

Z = F^{- 1} (U) = \sqrt{2} \erf^{- 1} (2 U - 1), U \in (0, 1) .

$Z = F^{-1}(U)\; =\; \sqrt2\;\operatorname{erf}^{-1}(2U - 1), \quad U\in(0,1).$

normal-distribution simulation uniform user2350366
fonte

Qual é o inverso do cdf normal? Não pode ser calculado analiticamente, apenas se o CDF original for aproximado com a função linear por partes.

Artem Sobolev

Os dois não estão intimamente relacionados? Box Muller, acredito, é um caso particular para a geração de 2 variáveis.

precisa saber é o seguinte

Oi Barmaley, eu adicionei mais algumas informações acima. O CDF inverso tem uma expressão - no entanto, o

deve ser calculado computacionalmente -, e pode ser por isso que a caixa Muller é preferida? Presumi que

seria calculado em tabelas de pesquisa, bem como valores de

? Portanto, não é muito mais caro computacionalmente? Eu posso estar errado no entanto.

{erf}^{- 1}

$\text{erf}^{-1}$

{erf}^{1}

$\text{erf}^1$

sin

$\text{sin}$

cosine

$\text{cosine}$

user2350366

Existem versões do Box-Muller sem pecado e cosseno.

Xian

@Dilip Para aplicações de precisão muito baixa, como gráficos de computador, seno e cosseno, de fato, pode ser otimizado usando tabelas de pesquisa adequadas. Para aplicações estatísticas, porém, essa otimização nunca é usada. Em última análise, não é realmente mais difícil calcular o

que o

ou o

, mas nos sistemas modernos de computação as funções básicas relacionadas à

- incluindo as funções trigonométricas - tendem a ser otimizadas (

eram instruções básicas na Intel) Chip 8087!), Enquanto erf não está disponível ou foi codificado em um nível mais alto (= mais lento).

{erf}^{- 1}

$\text{erf}^{-1}$

\log

$\log$

sqrt

$\text{sqrt}$

\exp

$\exp$

\cos

$\cos$

\log

$\log$

whuber

De uma perspectiva puramente probabilística, ambas as abordagens são corretas e, portanto, equivalentes. De uma perspectiva algorítmica, a comparação deve considerar a precisão e o custo da computação.

O Box-Muller conta com um gerador uniforme e custa aproximadamente o mesmo que este gerador uniforme. Como mencionado no meu comentário, você pode sair sem chamadas seno ou cosseno, se não sem o logaritmo:

gerar até $U_{1}, U_{2} \overset{iid}{\sim} U (- 1, 1)$ $U_1,U_2\stackrel{\text{iid}}{\sim}\mathcal{U}(-1,1)$ $S=U_1^2+U_2^2\le 1$
toma e defina $Z=\sqrt{-2\log(S)/S}$ $X_{1} = Z U_{1}, X_{2} = Z U_{2}$ $X_1=ZU_1\,,\ X_2=Z U_2$

O algoritmo de inversão genérico requer a chamada para o cdf normal inverso, por exemplo qnorm(runif(N))em R, que pode ser mais caro do que o descrito acima e, o que é mais importante, pode falhar nas caudas em termos de precisão, a menos que a função quantil seja bem codificada.

Para acompanhar os comentários feitos pela whuber , a comparação rnorm(N)e qnorm(runif(N))está na vantagem do cdf inverso, ambos em tempo de execução:

> system.time(qnorm(runif(10^8)))
sutilisateur     système      écoulé
 10.137           0.120      10.251 
> system.time(rnorm(10^8))
utilisateur     système      écoulé
 13.417           0.060      13.472` `

e em termos de ajuste na cauda: enter image description here

Após um comentário de Radford Neal no meu blog , quero salientar que o padrão rnormem R faz uso do método de inversão, portanto a comparação acima está refletindo na interface e não no próprio método de simulação! Para citar a documentação R no RNG:

‘normal.kind’ can be ‘"Kinderman-Ramage"’, ‘"Buggy
 Kinderman-Ramage"’ (not for ‘set.seed’), ‘"Ahrens-Dieter"’,
 ‘"Box-Muller"’, ‘"Inversion"’ (the default), or ‘"user-supplied"’.
 (For inversion, see the reference in ‘qnorm’.)  The
 Kinderman-Ramage generator used in versions prior to 1.7.1 (now
 called ‘"Buggy"’) had several approximation errors and should only
 be used for reproduction of old results.  The ‘"Box-Muller"’
 generator is stateful as pairs of normals are generated and
 returned sequentially.  The state is reset whenever it is selected
 (even if it is the current normal generator) and when ‘kind’ is
 changed.

Xi'an
fonte

\log

$\log$

\sqrt{}

$\sqrt{}$

Φ^{- 1}

$\Phi^{-1}$

Φ^{- 1}

$\Phi^{-1}$

X_{1}

$X_1$

X_{2}

$X_2$

U_{i}

$U_i$

- 1

$-1$ e

1

$1$ ao invés de

0

$0$ e

1

$1$ .

whuber

No meu sistema, executando R 3.0.2, o método Box-Mueller (sem seno e cosseno e codificado usando rowSumspara calcular

S

$S$ muito rapidamente) é, no entanto, 75% mais lento que qnorm(runif(N)). Ao executar o Mathematica 9, o Box-Mueller é dez vezes mais rápido que o direto InverseCDF[NormalDistribution[], #] &. O ponto é que a resposta depende dos recursos da plataforma computacional (bem como das habilidades de codificação de alguém). Isso está de acordo com o que você diz no primeiro parágrafo, mas pode levar os leitores a reinterpretar o restante de sua resposta.

whuber

Concordo, qnorm(runif(N))é até 20% mais rápido do quernorm(N)

Xian

+1 para as novas informações. (Na verdade, sua postagem original valeu a pena ser votada por si mesma.) Gostaria de enfatizar novamente, porém, que as conclusões podem mudar em uma plataforma diferente. Por exemplo, eu definitivamente usaria o Box-Mueller se codificasse na linguagem C, Fortran ou Assembly, onde teria acesso a implementações extremamente rápidas de funções transcendentais algébricas e elementares, que seriam muito mais rápidas do que qualquer implementação de

Φ^{- 1}

$\Phi^{-1}$ , mesmo aproximado. Desde a

\sin

$\sin$ e

\cos

$\cos$ seria tão eficiente que eu também os usaria em vez da amostragem por rejeição.

whuber

Para efeito de comparação, utilizando um i7-3740QM @ 2.7GHz e R 3,12, para as seguintes chamadas:

RNGkind(kind = NULL, normal.kind = 'Inversion');At <- microbenchmark(A <- rnorm(1e5, 0, 1), times = 100L);RNGkind(kind = NULL, normal.kind = 'Box-Muller');Bt <- microbenchmark(B <- rnorm(1e5, 0, 1), times = 100L)

eu recebo mean 11.38363 median 11.18718de inversão e mean 13.00401 median 12.48802de Box-Muller

Avraham

Vantagens do Box-Muller sobre o método CDF inverso para simular a distribuição normal?

Respostas: