Alguém pode me dizer como simular , onde , usando um sorteio (quantas vezes você precisar) com ?
Eu estava pensando em usar amostras de rejeição, mas não consegui identificá-las.
Alguém pode me dizer como simular , onde , usando um sorteio (quantas vezes você precisar) com ?
Eu estava pensando em usar amostras de rejeição, mas não consegui identificá-las.
[self-study]
tag e leia seu wiki . Observe que não há necessidade de pedir ajuda no final de sua pergunta - sabemos que todos os que postam aqui estão esperando por ajuda!Respostas:
Como existem inúmeras soluções, vamos encontrar uma eficiente .
A idéia por trás disso começa com uma maneira padrão de implementar uma variável de Bernoulli: compare uma variável aleatória uniforme com o parâmetro . Quando , retorne ; caso contrário, retorne .U a/b U<a/b 1 0
Podemos usar a moeda como um gerador uniforme de números aleatóriosp . Para gerar um número uniformemente dentro de qualquer intervalo , jogue a moeda. Quando estiver no cabeçalho, gere recursivamente um valor uniforme na primeira parte do intervalo; quando for coroa, gere recursivamente a partir da última parte de do intervalo. Em algum momento, o intervalo de destino se tornará tão pequeno que realmente não importa como você escolhe um número: é assim que a recursão começa. É óbvio que esse procedimento gera variáveis uniformes (até a precisão desejada), como é facilmente comprovado por indução.U [x,y) X p X 1−p
Essa ideia não é eficiente, mas leva a um método eficiente. Como em cada estágio você desenha um número de um determinado intervalo , por que não verificar primeiro se é necessário desenhá-lo? Se o seu valor-alvo estiver fora desse intervalo, você já saberá o resultado da comparação entre o valor aleatório e o alvo. Assim, esse algoritmo tende a terminar rapidamente. (Isso pode ser interpretado como o procedimento de amostragem por rejeição solicitado na pergunta.)[x,y)
Podemos otimizar ainda mais esse algoritmo. Em qualquer estágio, na verdade, temos duas moedas que podemos usar: ao re-rotular nossa moeda, podemos transformá-la em uma que tem cara de chance . Portanto, como precomputação, podemos escolher recursivamente qualquer remarcação que leve ao menor número esperado de inversões necessárias para a rescisão. (Este cálculo pode ser uma etapa cara.)1−p
Por exemplo, é ineficiente usar uma moeda com para emular diretamente uma variável de Bernoulli : são necessários quase dez movimentos em média. Mas se usarmos uma moeda , em apenas dois lançamentos teremos certeza de que será feito e o número esperado de lançamentos será de apenas .p=0.9 (0.01) p=1−0.0=0.1 1.2
Aqui estão os detalhes.
Particionar qualquer intervalo semi-aberto nos intervalosI=[x,y)
Isto define as duas transformações es(∗,H) s(∗,T) que operam em intervalos de semi-abertas.
Enquanto {Jogue a moeda para produzir . Defina Incremento .}(t∈In) Xn+1 In+1=S(In,Xn+1). n
Se , defina . Caso contrário, defina .t>In+1 Z=1 Z=0
Implementação
Para ilustrar, aqui está umat [x,y) [0,1) s
R
implementação do aloritmo como a funçãodraw
. Seus argumentos são o valor alvo o intervalo , inicialmente . Ele usa a função auxiliar implementando . Embora não seja necessário, também rastreia o número de lançamentos de moedas. Retorna a variável aleatória, a contagem de lançamentos e o último intervalo inspecionado.s
Como um exemplo da sua utilização e ensaio da sua exactidão, assumir o caso e . Vamos desenhar valores usando o algoritmo, relatar a média (e seu erro padrão) e indicar o número médio de inversões usadas.t=1/100 p=0.9 10,000
fonte
Aqui está uma solução (um pouco bagunçada, mas é minha primeira facada). Você pode realmente ignorar WLOG assumem . Por quê? Existe um algoritmo inteligente para gerar um lançamento de moeda imparcial a partir de dois lançamentos de moedas tendenciosos. Portanto, podemos assumir .P(H)=p P(H)=1/2 P(H)=1/2
Para gerar um , posso pensar em duas soluções (a primeira não é minha, mas a segunda é uma generalização):Bernoulli(ab)
Solução 1
Vire a moeda imparcial vezes. Se cabeça não estiver presente, comece de novo. Se cabeças estão presentes, o retorno se a primeira moeda é uma ou cabeças não (porque )b a a P(first coin is heads | a heads in b coins)=ab
Solução 2
Isso pode ser estendido para qualquer valor de . Escreva em formato binário. Por exemplo,Bernoulli(p) p 0.1=0.0001100110011001100110011...base 2
Criaremos um novo número binário usando lançamentos de moedas. Comece com e adicione dígitos, dependendo se uma cara (1) ou coroa (0) aparecer. Em cada flip, compare seu novo número binário com a representação binária de até o mesmo dígito . Eventualmente, os dois divergem e retornam se o for maior que o seu número binário.0. p bin(p)
Em Python:
Alguma prova:
é de cerca de 0,4 (no entanto, não é rápido)
fonte
Vejo uma solução simples, mas sem dúvida há muitas maneiras de fazê-lo, algumas presumivelmente mais simples que isso. Essa abordagem pode ser dividida em duas etapas:
Gerando a partir de dois eventos com igual probabilidade, dado um procedimento injusto de lançamento de moeda (a combinação da moeda específica e o método pelo qual ela é lançada, gerando uma cabeça com probabilidade ). Podemos chamar esses dois eventos igualmente prováveis e . [Existe uma abordagem simples para isso, que exige fazer pares de arremessos e para produzir dois resultados igualmente prováveis, com todos os outros resultados levando à geração de um novo par de rolos para tentar novamente.]p H∗ T∗ H∗=(H,T) T∗=(T,H)
Agora você gera uma caminhada aleatória com dois estados absorventes usando a moeda justa simulada. Ao escolher a distância dos estados de absorção da origem (um acima e outro abaixo), você pode definir a chance de absorção, digamos que o estado de absorção superior seja a proporção desejada de números inteiros. Especificamente, se você colocar a barreira de absorção superior em e a inferior em (e iniciar o processo a partir da origem) e executar a caminhada aleatória até a absorção, a probabilidade de absorção na barreira superior é .a −(b−a) aa+(b−a)=ab
(Existem alguns cálculos a serem feitos aqui para mostrá-lo, mas você pode obter facilmente as probabilidades trabalhando com relações de recorrência ... ou pode fazê-lo somando séries infinitas ... ou de outras maneiras.)
fonte