Gerando números aleatórios manualmente

30

Como posso gerar manualmente um número aleatório a partir de uma determinada distribuição, como por exemplo, 10 realizações da distribuição normal padrão?

Dan ish
fonte
10
Você pode explicar por que deseja fazer isso e quais outras restrições existem em você?
mdewey
2
Você pode obter uma tabela de números aleatórios (usados ​​para publicá-los entre outros).
Batman
4
@ Batman: sim, de fato, e o livro RAND de 10⁶ números aleatórios recebeu 655 comentários na Amazon. Tudo previsível, é claro.
Xi'an
10
(Estou surpreso que ninguém tenha comentado isso anteriormente). A menos que seja absolutamente essencial , não se deve tentar usar implementações personalizadas para gerar números aleatórios. Sim, é ótimo saber como fazer isso e provavelmente é a primeira coisa que você verá em uma classe " Métodos de MC " (e isso é ótimo!), Mas não o faz em nenhum projeto da vida real. Rotinas especializadas de geração de números aleatórios existem por um motivo: implementar um algoritmo básico a partir do zero é perda de tempo, fonte de bugs e baixo esforço de reconhecimento de campo.
usεr11852 diz Reinstate Monic
2
@ Xi'an: Sim, concordo que é uma presunção segura. Como mencionado, este é apenas um comentário para advertir as pessoas de usarem seu próprio RNG sem perceber que o design do RNG é um negócio muito sério. Para citar von Neumann : "Qualquer um que considere métodos aritméticos de produzir dígitos aleatórios está, é claro, em um estado de pecado".
usεr11852 diz Reinstate Monic

Respostas:

46

Se "manualmente" incluir "mecânico", você terá muitas opções disponíveis. Para simular uma variável de Bernoulli com probabilidade metade, podemos jogar uma moeda: para coroa, 1 para cara. Para simular uma distribuição geométrica, podemos contar quantas jogadas de moeda são necessárias antes de obtermos as cabeças. Para simular uma distribuição binomial, podemos jogar nossa moeda n vezes (ou simplesmente jogar n moedas) e contar as cabeças. O "quincunx" ou "bean machine" ou "Galton box" é uma alternativa mais cinética - por que não colocar uma em ação e ver por si mesmo ? Parece,0 01 1nn não existe uma "moeda ponderada"mas se quisermos variar o parâmetro de probabilidade de nossa variável Bernoulli ou binomial para valores diferentes de , a agulha de Georges-Louis Leclerc, conde de Buffon , nos permitirá fazê-lo. Para simular a distribuição uniforme e discreta em { 1 , 2 , 3 , 4 , 5 , 6 } , rolamos um dado de seis lados. Os fãs de role-playing games terão encontrado dados mais exóticos , por exemplo, dados tetraédricos para amostrar uniformemente de { 1 , 2 , 3 , 4 }p=0,5{1 1,2,3,4,5,6}{1 1,2,3,4}, enquanto com uma roda giratória ou roleta, é possível ir ainda mais longe. ( Crédito de imagem )

Variedade de dados

Teríamos que ficar loucos para gerar números aleatórios dessa maneira hoje, quando há apenas um comando em um console de computador - ou, se tivermos uma tabela adequada de números aleatórios disponível, uma incursão nos cantos mais empoeirados da estante? Bem, talvez, embora exista algo agradavelmente tátil em um experimento físico. Porém, para as pessoas que trabalhavam antes da Era do Computador, de fato antes das tabelas de números aleatórios em larga escala amplamente disponíveis (das quais mais tarde), a simulação manual de variáveis ​​aleatórias tinha mais importância prática. Quando Buffon investigou o paradoxo de São Petersburgo- o famoso jogo de arremesso de moedas em que o valor que o jogador ganha dobra toda vez que uma cabeça é lançada, o jogador perde nas primeiras caudas e cuja recompensa esperada é contra-intuitivamente infinita - ele precisava simular a distribuição geométrica com . Para fazer isso, parece que ele contratou uma criança para jogar uma moeda para simular 2048 peças do jogo de São Petersburgo, registrando quantos lançamentos antes do jogo terminar. Essa distribuição geométrica simulada é reproduzida em Stigler (1991) :p=0,5

Tosses Frequency
1      1061
2      494
3      232
4      137
5      56
6      29
7      25
8      8
9      6

No mesmo ensaio em que ele publicou essa investigação empírica sobre o paradoxo de São Petersburgo, Buffon também introduziu a famosa " agulha de Buffon ". Se um plano é dividido em tiras por linhas paralelas distantes e uma agulha de comprimento l d é jogada sobre ele, a probabilidade de a agulha cruzar uma das linhas é de 2 ldeud .2euπd

Experiência com agulhas de Buffon

A agulha de Buffon pode, portanto, ser usada para simular uma variável aleatória ouXBinomial(n,2lXBernoulli(2euπd), e podemos ajustar a probabilidade de sucesso alterando o comprimento de nossas agulhas ou (talvez mais convenientemente) a distância em que governamos as linhas. Um uso alternativo das agulhas de Buffon é uma maneira terrivelmente ineficiente de encontrar uma aproximação probabilística paraπ. A imagem (crédito) mostra 17 palitos de fósforo, dos quais 11 cruzam uma linha. Quando a distância entre as linhas regidas é definida igual ao comprimento do palito, como aqui, a proporção esperada de palitos cruzados é2XBinomial(n,2euπd)π e, portanto, pode-se estimar π como duas vezes o inverso da fracção observado: aqui obtemos π =2172ππ^. Em 1901 Mario Lazzarini reivindicou ter realizado a experiência usando agulhas de 2,5 cm com linhas 3 cm entre si, e depois 3408 jogadas obtido π =355π^=217113.1. . Este é um racional bem conhecido paraπ, com precisão de seis casas decimais. Badger (1994) fornece evidências convincentes de que isso era fraudulento, não menos importante: para ter 95% de confiança em seis casas decimais de precisão usando o aparelho de Lazzarini, devem ser lançadas 134 trilhões de agulhas que desgastam a paciência! Certamente a agulha de Buffon é mais útil como gerador de números aleatórios do que como método para estimarπ.π^=355113ππ


Até agora, nossos geradores têm sido decepcionantemente discretos. E se quisermos simular uma distribuição normal? Uma opção é obter dígitos aleatórios e usá-los para formar boas aproximações discretas de uma distribuição uniforme em e depois executar alguns cálculos para transformá-los em desvios normais aleatórios. Uma roda giratória ou roleta pode fornecer dígitos decimais de zero a nove; um dado pode gerar dígitos binários; se nossas habilidades aritméticas puderem lidar com uma base mais divertida, mesmo um conjunto padrão de dados serviria. Outras respostas abordaram esse tipo de abordagem baseada em transformação em mais detalhes; Adio qualquer discussão sobre o assunto até o fim.[0 0,1 1]

No final do século XIX, a utilidade da distribuição normal era bem conhecida e, portanto, havia estatísticos interessados ​​em simular desvios normais aleatórios. Escusado será dizer que cálculos manuais longos não seriam adequados, exceto para configurar o processo de simulação em primeiro lugar. Uma vez estabelecido, a geração dos números aleatórios tinha que ser relativamente rápida e fácil. Stigler (1991) lista os métodos empregados por três estatísticos desta época. Todos estavam pesquisando técnicas de suavização: desvios normais aleatórios eram de interesse óbvio, por exemplo, para simular erros de medição que precisavam ser suavizados.

O notável estatístico americano Erastus Lyman De Forest estava interessado em suavizar as tabelas de vida e encontrou um problema que exigia a simulação dos valores absolutos dos desvios normais. No que provará ser um tema corrente, De Forest estava realmente amostrando uma distribuição meio normal . Além disso, em vez de usar um desvio padrão de um (o que estamos acostumados a chamar de "padrão"), De Forest queria um "erro provável" (desvio médio) de um. Este foi o formulário fornecido na tabela "Probabilidade de erros"ZN(0 0,1 12) nos apêndices de "Um manual de astronomia esférica e prática, volume II" deWilliam Chauvenet . A partir dessa tabela, De Forest interpolou os quantis de uma distribuição semi-normal, de a p = 0,995 , que ele considerou "erros de igual frequência".p=0,005p=0,995

Tabela De Forest de erros de igual frequência

Se desejar simular a distribuição normal, seguindo De Forest, você pode imprimir esta tabela e cortá-la. De Forest (1876) escreveu que os erros "foram inscritos em 100 bits de cartão de tamanho igual, que foram sacudidos em uma caixa e todos desenhados um a um".

O astrônomo e meteorologista Sir George Howard Darwin (filho do naturalista Charles) deu uma guinada diferente, desenvolvendo o que chamou de "roleta" por gerar desvios normais aleatórios. Darwin (1877) descreve como:

Um pedaço de cartão circular foi graduado radialmente, de modo que uma graduação marcada com era 720xgraus distantes de um raio fixo. O cartão foi feito para girar em torno de seu centro, próximo a um índice fixo. Foi então girado várias vezes e, ao interrompê-lo, o número oposto ao índice foi lido. [Darwin acrescenta em uma nota de rodapé: É melhor parar o disco quando ele gira tão rápido que as graduações ficam invisíveis, em vez de deixá-lo seguir seu curso.] Pela natureza da graduação, os números assim obtidos ocorrerão exatamente da mesma maneira que erros de observação ocorrem na prática; mas eles não têm sinais de adição ou subtração prefixados. Então, jogando uma moeda repetidamente e chamando cara+e coroa-, os sinais720π0 0xe-x2dx+- ou - são atribuídos por acaso a essa série de erros.+-

O "índice" deve ser lido aqui como "ponteiro" ou "indicador" (consulte "dedo indicador"). Stigler ressalta que Darwin, como De Forest, estava usando uma distribuição cumulativa semi-normal em torno do disco. Posteriormente, o uso de uma moeda para anexar um sinal aleatoriamente torna essa distribuição normal completa. Stigler observa que não está claro o quão finamente a escala foi graduada, mas presume que a instrução para interromper manualmente a rotação intermediária do disco foi "diminuir o viés potencial em direção a uma seção do disco e acelerar o procedimento".

Sir Francis Galton , aliás, meio-primo de Charles Darwin, já foi mencionado em relação ao seu quincunce. Enquanto isso simula mecanicamente uma distribuição binomial que, pelo teorema de De Moivre – Laplace, tem uma semelhança impressionante com a distribuição normal (e é ocasionalmente usada como uma ajuda didática para esse tópico), Galton realmente produziu um esquema muito mais elaborado quando desejava amostra de uma distribuição normal. Ainda mais extraordinário do que os exemplos não convencionais no topo desta resposta, Galton desenvolveu dados normalmente distribuídos- ou mais precisamente, um conjunto de dados que produz uma excelente aproximação discreta a uma distribuição normal com desvio médio. Esses dados, datados de 1890, são preservados na Galton Collection na University College London.

Dados normais de Galton

Em um artigo de 1890 na Nature, Galton escreveu que:

Como instrumento para selecionar aleatoriamente, não encontrei nada superior aos dados. É mais entediante embaralhar as cartas completamente entre cada sorteio sucessivo, e o método de misturar e mexer bolas marcadas em uma bolsa ainda é mais entediante. É preferível um teetoto ou alguma forma de roleta, mas os dados são melhores que todos. Quando são sacudidos e jogados em uma cesta, jogam-se tão variadamente um contra o outro e contra as costelas da cesta que caem loucamente, e suas posições desde o início não oferecem nenhuma pista perceptível do que serão depois de um tempo. único bom shake e atirar. As chances oferecidas por um dado são mais variadas do que se supõe; existem 24 possibilidades iguais, e não apenas 6, porque cada face tem quatro arestas que podem ser utilizadas, como mostrarei.

+-1 11 14

Projeto normal de dados de Galton

O Laboratório de Experimentos Estatísticos Matemáticos de Raazesh Sainudiin inclui um projeto estudantil da Universidade de Canterbury, na Nova Zelândia, reproduzindo os dados de Galton . O projeto inclui investigação empírica ao lançar os dados várias vezes (incluindo um CDF empírico que parece tranquilizadoramente "normal") e uma adaptação das pontuações dos dados para que eles sigam a distribuição normal padrão. Usando as pontuações originais de Galton, há também um gráfico da distribuição normal discretizada que as pontuações dos dados realmente seguem.

Distribuição discreta dos dados de Galton


Em grande escala, se você estiver preparado para esticar o "mecânico" ao elétrico, observe que o épico A Million Random Digits da RAND com 100.000 desvios normais foi baseado em um tipo de simulação eletrônica de uma roleta. A partir do relatório técnico (de George W. Brown, originalmente em junho de 1949), encontramos:

Assim motivado, o pessoal da RAND, com a assistência do pessoal de engenharia da Douglas Aircraft Company, projetou uma roda de roleta elétrica com base na variação de uma proposta feita por Cecil Hastings. Para os propósitos desta palestra, uma breve descrição será suficiente. Uma fonte de pulso de frequência aleatória foi bloqueada por um pulso de frequência constante, cerca de uma vez por segundo, fornecendo, em média, cerca de 100.000 pulsos em um segundo. Os circuitos de padronização de pulsos passaram os pulsos para um contador binário de cinco posições, de modo que, em princípio, a máquina é como uma roleta com 32 posições, gerando em média cerca de 3000 rotações a cada turno. Foi utilizada uma conversão binária em decimal, jogando fora 12 das 32 posições, e o dígito aleatório resultante foi alimentado em um punch IBM, resultando em tabelas de cartões perfurados de dígitos aleatórios.

χ2testes das frequências de dígitos pares e ímpares revelaram que alguns lotes apresentaram um leve desequilíbrio. Isso foi pior em alguns lotes do que em outros, sugerindo que "a máquina estava inoperante no mês desde que foi ajustada ... As indicações nesta máquina exigiam manutenção excessiva para mantê-la em perfeito estado". No entanto, foi encontrada uma maneira estatística de resolver esses problemas:

Nesse ponto, tínhamos nosso milhão de dígitos originais, 20.000 cartões IBM com 50 dígitos para um cartão, com o pequeno, mas perceptível viés ímpar-par divulgado pela análise estatística. Decidiu-se agora re-aleatorizar a mesa, ou pelo menos alterá-la, com uma roleta brincando com ela, para remover o viés impar e impar. Adicionamos (mod 10) os dígitos de cada cartão, dígito por dígito, aos dígitos correspondentes do cartão anterior. A tabela derivada de um milhão de dígitos foi então submetida a vários testes padrão, testes de frequência, testes seriais, testes de pôquer etc. Esses milhões de dígitos têm um atestado de integridade e foram adotados como a tabela moderna de dígitos aleatórios da RAND.

Obviamente, havia boas razões para acreditar que o processo de adição faria algum bem. De maneira geral, o mecanismo subjacente é a abordagem limitadora de somas de variáveis ​​aleatórias, modulando o intervalo unitário na distribuição retangular, da mesma forma que somas irrestritas de variáveis ​​aleatórias se aproximam da normalidade. Este método foi usado por Horton e Smith, da Comissão Interestadual do Comércio, para obter alguns bons lotes de números aparentemente aleatórios a partir de lotes maiores de números muito aleatórios.

[0 0,1 1]você[0 0,1 1]FF-1 1(você)

Zigurate para meia-normal

Referências


()"Qualquer um que considere métodos aritméticos de produção de dígitos aleatórios está, é claro, em estado de pecado. Pois, como foi apontado várias vezes, não existe um número aleatório - existem apenas métodos para produzir números aleatórios. , e um procedimento aritmético estrito, é claro, não é esse método ".

Silverfish
fonte
5
Você deve estar brincando ... (mas, sim, isso é realmente manualmente +1)
nalzok
8
Quanto trabalho nisso!
Richard Hardy
3
Observe que dados fora do padrão podem ser injustos, por isso é bom testá-los primeiro, por exemplo, youtube.com/watch?v=VI3N4Qg-JZM
Tim
2
@RichardHardy Paradoxalmente, é realmente mais fácil escrever todas essas coisas enquanto está na minha frente, e pelo menos temporariamente alojado em minha memória, do que tentar carregá-las na minha cabeça!
quer
2
De qualquer forma, acho impressionante!
Richard Hardy
44

X=-2registrovocê1 1porque(2πvocê2)
Y=-2registrovocê1 1pecado(2πvocê2)X

Por exemplo, no meu sistema operacional Linux, posso verificar

$ date +%s.%N
1479733744.077762986
$ date +%s.%N
1479733980.615056616

você1 1=.077762986, você2=.615056616
X
> sqrt(-2*log(.077762986))*cos(2*pi*.615056616)
[1] -1.694815

Adendo: como a computação de logaritmos e cossenos pode ser considerada não manual o suficiente, existe uma variante de Box-Müller que evita o uso dessas funções transcendentais (consulte o Exercício 2.9 em nosso livro Monte Carlo Statistical Methods ):

uma variante do Box-Muller

Agora, pode-se argumentar contra essa versão por causa das variáveis ​​exponenciais. Mas também existe uma maneira muito inteligente de simular essas variáveis sem a necessidade de funções transcendentais , devido a von Neumann, conforme resumido neste algoritmo reproduzido das Variações Aleatórias Não Uniformes de Luc Devroye :

insira a descrição da imagem aqui

É certo que requer o cálculo de 1 / e, mas apenas uma vez.

(0 0,1 1)2(0 0,1 1)(0 0,2π)

Usar o CLT para aproximar a normalidade certamente não é um método que eu recomendaria, já que (1) você ainda precisa de outras variáveis ​​para alimentar a média, portanto, pode usar uniformes no algoritmo de Box-Müller e (2) a precisão aumenta bastante lentamente com o número de simulações. Especialmente se estiver usando uma variável aleatória discreta como o resultado de um dado, mesmo com mais de seis faces . Para citar Thomas et al. (2007), uma pesquisa sobre os prós e contras dos geradores aleatórios gaussianos:

O teorema do limite central, é claro, é um exemplo de método "aproximado" - mesmo que seja usada aritmética perfeita, para K finito a saída não será gaussiana.

Aqui está um experimento rápido para ilustrar o problema: gerei 100 vezes a média de 30 resultados dos dados:

dies=apply(matrix(sample(1:6,30*100,rep=TRUE),ncol=30),1,mean)

normalizou essas médias em zero médio - variância uma varia

stdies=(dies-3.5)/sqrt(35/12/30)

e analisou o ajuste normal [ou a falta dele] desta amostra:

qqnorm (stdies, col = "gold2", pch = 19); abline (a = 0, b = 1, col = "steelblue", lwd = 2, lty = 2)

dies76/30122/30DEu

você=Eu=1 1kDEu-1 16Eu
com k=15 (observe que 6¹⁵> 10¹¹, portanto, eu gere mais de 11 dígitos verdadeiramente aleatórios) e aplique a transformação Box-Müller acima para transformar pares de uniformes em pares de variáveis ​​N (0,1),
dies=matrix(apply(matrix(sample(0:5,15*200,rep=TRUE),nrow=15)/6^(1:15),2,sum),ncol=2) 
norma=sqrt(-2*log(dies[,1]))*c(cos(2*pi*dies[,2]),sin(2*pi*dies[,2]))

o ajuste é tão bom quanto o esperado para uma amostra normal do tamanho 200 (basta plotar outro para uma amostra normal verdadeira norma=rnorm(100)):

insira a descrição da imagem aqui

como demonstrado em mais detalhes por um teste de Kolmogorov-Smirnov:

> ks.test(norma,pnorm)

        One-sample Kolmogorov-Smirnov test

data:  norma
D = 0.06439, p-value = 0.3783
alternative hypothesis: two-sided
Xi'an
fonte
3

Isso não é exatamente aleatório, mas deve estar próximo o suficiente, pois você parece querer uma experiência difícil.

Use seu telefone para configurar um cronômetro. Após 10 segundos, pare (quanto mais você espera, mais se aproxima de um resultado verdadeiramente "aleatório", mas 10 segundos são bons). Pegue os últimos dígitos (por exemplo, 10,67 segundos fornecerão 67). Aplique a tabela de percentis para a distribuição normal. Neste exemplo, basta procurar 0,67 e você encontrará o número. Nesse caso, seu valor é de cerca de 0,45. Isso não é perfeitamente preciso, mas fornecerá uma estimativa sólida.

Se você rolar abaixo de 50, faça 100- [Your Result] e use a tabela. Seu resultado será o mesmo, com um sinal de menos, devido à simetria de N (0,1).

Thalantas
fonte
3

Vamos jogar uma moeda imparcial nvezes. Começando em zero, contamos+1 1 se cabeças, -1 1se caudas. Depois den moedas, dividimos o contador por n. Usando o teorema do limite central , sen for suficientemente grande, deveríamos ter uma "realização aproximada" do padrão gaussiano normalizado N(0 0,1 1).


Por quê? Deixei

Xk: ={+1 1 E se k-a moeda virar é cara-1 1 E se k-a moeda flip é coroa

iid Bernoulli variáveis ​​aleatórias com P(Xk=±1 1)=1 12. Conseqüentemente,

E(Xk)=0 0Var(Xk)=1 1

Deixei Y: =X1 1+X2++Xn. Conseqüentemente,

E(Y)=0 0Var(Y)=n

Normalizando,

Z: =Yn

obtemos uma variável aleatória com variância unitária

E(Z)=0 0Var(Z)=1 1
Rodrigo de Azevedo
fonte
11
Como discutido em minha resposta, temo que o CLT não seja um uso eficiente da aleatoriedade nos lançamentos de moedas: eles seriam melhor explorados como dígitos binários de uma variável pseudo-aleatória U (0,1) com precisão simples ou dupla.
Xi'an
@ Xi'an Eu li sua resposta antes de postar a minha, e sua objeção ao CLT parecia basear-se em convergência lenta. Como este é um experimento mental, jogar uma moeda 10 bilhões de vezes não custa nada. E é realmente um procedimento manual que não requer computadores, computação de logaritmos, raízes quadradas ou cossenos. Claro, pode-se usar uma regra de slide, mas isso pode estar indo longe demais.
Rodrigo de Azevedo
11
:}}: 10 bilhões de lançamentos de moedas não me parecem muito manuais ...!
Xi'an
Manual = manualmente. Computar logaritmos e cossenos manualmente também leva tempo.
Rodrigo de Azevedo
0

Vale a pena notar que, uma vez que você pode gerar um uniforme (0,1), pode gerar qualquer variável aleatória para a qual o cdf inverso é calculável, simplesmente conectando a variável aleatória uniforme ao CDF inverso.

Então, como alguém pode calcular um uniforme (0,1) manualmente? Bem, como mencionado pelo @Silverfish, há uma variedade de dados usados ​​pelos jogadores tradicionais de RPG. Um deles é um dado de dez lados. Assumindo que este é um dado justo, agora podemos gerar um uniforme discreto (0, 9).

Também podemos usar esse uniforme (0,9) para representar um único dígito de uma variável aleatória. Portanto, se usarmos dois dados, obtemos uma variável aleatória uniforme que pode assumir valores0,01,0,02,...,0,99,1,00. Com três dados, podemos obter uma distribuição uniforme em0,001,0,002,...,0,999,1.000.

Assim, podemos chegar muito perto de um uniforme contínuo (0,1) aproximando-o com uma distribuição uniforme discreta com finas grades, com alguns dados de 10 lados. Isso pode ser conectado a um CDF inverso para produzir a variável aleatória de interesse.

Cliff AB
fonte