Dardos, dados e moedas: algoritmos de distribuição discreta

Certa vez, fiz à Stack Overflow uma pergunta sobre a estrutura de dados para trapacear dados . Em particular, eu estava interessado na resposta a essa pergunta: “Se temos um osso n-faceta, cuja face i tem probabilidade de cair p _i . Qual é a estrutura de dados mais eficaz para simular os rolos desse osso? ”

Essa estrutura de dados pode ser usada para muitas tarefas. Por exemplo, você pode usá-lo para simular rolos hexagonais honestos, atribuindo probabilidade $$$\ frac {1} {6}$ cada lado do osso, ou para simular uma moeda justa por imitação de um osso bilateral, cuja probabilidade de cair de cada lado é igual a $$$\ frac {1} {2}$ . Você também pode usar essa estrutura de dados para simular diretamente a soma de dois ossos hexagonais honestos criando um osso de 11 lados (com faces 2, 3, 4, ..., 12), cada face com um peso de probabilidade correspondente aos rolos de dois ossos honestos. No entanto, você também pode usar essa estrutura de dados para simular trapaceiros. Por exemplo, se você joga craps com um osso, o que, como você sabe, não é perfeitamente honesto, pode usar essa estrutura de dados para simular muitos rolos de osso e analisar a estratégia ideal. Você também pode tentar simular a mesma forma imperfeita roleta .

Se você for além dos jogos, poderá aplicar essa estrutura de dados na simulação de robôs cujos sensores possuem níveis de falha conhecidos. Por exemplo, se um sensor de faixa tiver 95% de probabilidade de retornar o valor correto, 4% de probabilidade de um valor muito pequeno e 1% de probabilidade de um valor muito alto, você poderá usar essa estrutura de dados para simular a leitura das leituras do sensor, gerando um resultado aleatório e simular a leitura do sensor resultado.

A resposta que recebi no Stack Overflow me impressionou por dois motivos. Primeiramente, na solução, fui aconselhado a usar uma técnica poderosa chamada método de alias , que, com certas suposições razoáveis ​​sobre o modelo da máquina, é capaz, após um simples estágio de preparação preliminar, simular rolos de ossos ao longo do tempo $$$O (1)$ . Em segundo lugar, fiquei ainda mais surpreso que esse algoritmo seja conhecido há décadas, mas nunca o conheci! Dado quanto tempo computacional é gasto na simulação, seria de esperar que essa técnica seja muito mais conhecida. Algumas consultas no Google me deram muitas informações sobre essa técnica, mas não consegui encontrar um único site em que um entendimento e uma explicação intuitivos dessa técnica se reunissem.

Este artigo é minha tentativa de fornecer uma breve visão geral das diferentes abordagens da simulação de trapaça, desde técnicas simples e pouco práticas até um método de alias muito otimizado e eficaz. Espero poder transmitir várias maneiras de entender intuitivamente a tarefa e como cada uma delas enfatiza algum novo aspecto da simulação de um osso trapaceiro. Meu objetivo para cada abordagem é estudar uma ideia motivadora, um algoritmo básico, prova de fidelidade e análise de tempo de execução (em termos de tempo, memória e aleatoriedade necessários).

Entrada

Antes de passar para os detalhes específicos das várias técnicas, primeiro padronizamos a terminologia e a notação.

Na introdução do artigo, usei o termo "trapaça" para descrever um cenário generalizado em que há um conjunto finito de resultados, cada um com uma probabilidade. Formalmente, isso é chamado de distribuição de probabilidade discreta , e a tarefa de simular um trapaça é chamada de amostragem de uma distribuição discreta .

Para descrever nossa distribuição discreta de probabilidade (osso trapaceiro), assumiremos que temos um conjunto de n probabilidades $$$p_0, p_1, ..., p_ {n - 1}$ relacionado aos resultados $$ . Embora os resultados possam ser quaisquer (águia / cauda, ​​número de ossos, cores etc.), por simplicidade, considerarei o resultado como algum tipo de número real positivo correspondente a um determinado índice.

Trabalhar com números reais em um computador é a "área cinzenta" da computação. Existem muitos algoritmos rápidos, cuja velocidade é fornecida apenas pela capacidade de calcular a função de um número real arbitrário em um tempo constante, e imprecisões numéricas na representação de números de ponto flutuante podem destruir completamente alguns algoritmos. Portanto, antes de iniciar qualquer discussão sobre algoritmos que trabalhem com probabilidades, ou seja, entrando no mundo sombrio dos números reais, devo esclarecer o que um computador pode ou não fazer.

A seguir, assumirei que todas as operações a seguir podem ser executadas em tempo constante:

• Adição. subtração, multiplicação, divisão e comparação de números reais arbitrários . Precisamos fazer isso para manipular probabilidades. Isso pode parecer uma suposição ousada, mas se assumirmos que a precisão de qualquer número real é limitada por algum polinômio do tamanho da palavra da máquina (por exemplo, um duplo de 64 bits em uma máquina de 32 bits), mas não acho que isso seja irracional demais.
• Geração de um número real uniforme no intervalo [0, 1). Para simular a aleatoriedade, precisamos de alguma fonte de valores aleatórios. Suponho que possamos gerar um número real de precisão arbitrária em tempo constante. Isso excede em muito as capacidades de um computador real, mas parece-me que, para os propósitos desta discussão, isso é aceitável. Se concordarmos em sacrificar uma parte da precisão dizendo que um IEEE-754 duplo arbitrário está no intervalo [0, 1], perderemos a precisão, mas o resultado provavelmente será preciso o suficiente para a maioria das aplicações.
• Cálculo do piso inteiro (arredondamento para baixo) de um número real. Isso é aceitável se assumirmos que estamos trabalhando com o IEEE-754 duplo, mas, em geral, esse requisito para um computador não é viável.

Vale a pena fazer a pergunta - é razoável supor que podemos realizar todas essas operações com eficiência. Na prática, raramente usamos probabilidades indicadas com um nível de precisão com o qual o erro de arredondamento inerente ao duplo IEEE-754 pode causar sérios problemas, para que possamos atender a todos os requisitos acima simplesmente trabalhando exclusivamente com o IEEE duplo. No entanto, se estivermos em um ambiente em que as probabilidades sejam indicadas exatamente como números racionais de alta precisão, essas restrições poderão ser irracionais.

Simulação óssea honesta

Antes de prosseguirmos para o caso mais geral de lançar um trapaceiro arbitrário, vamos começar com um algoritmo mais simples que servirá como base para os seguintes algoritmos: simulação de um osso n-face honesto. Por exemplo, dados hexagonais honestos rolam ao jogar Monopólio ou Risco, ou jogam uma moeda honesta (dados de dupla face) etc. podem ser úteis para nós.

Para este caso em particular, existe um algoritmo simples, elegante e eficaz para simular o resultado. O algoritmo é baseado na seguinte ideia: suponha que possamos gerar números reais realmente aleatórios e uniformemente distribuídos no intervalo $$$[0, 1)$ . Esse intervalo pode ser ilustrado da seguinte maneira:


Agora, se queremos sair $$$n$ osso facetado, então uma maneira é dividir o intervalo $$$[0, 1)$ em $$$n$ áreas de tamanho igual, cada uma com um comprimento $$$\ frac {1} {n}$ . É assim:


Em seguida, geramos um número real escolhido aleatoriamente no intervalo $$$[0, 1)$ que certamente cai em uma dessas pequenas áreas. A partir disso, podemos calcular o resultado do rolamento do osso observando a área em que o número caiu. Por exemplo, se nosso valor selecionado aleatoriamente se enquadra neste local:


então podemos dizer que 2 caíram no osso (se assumirmos que as bordas do osso estão indexadas do zero).

É graficamente fácil ver qual região possui um valor aleatório, mas como codificamos isso em um algoritmo? E aqui aproveitamos o fato de que este é um osso honesto. Como todos os intervalos são de tamanho igual, $$$\ frac {1} {n}$ , então podemos ver qual é o maior valor $$$i$ é tal que $$$\ frac {i} {n}$ não mais que um valor gerado aleatoriamente (vamos chamar esse valor x). Você pode perceber que, se quisermos encontrar o valor máximo, tal que $$$\ frac {i} {n} \ le x$ , isso é semelhante a encontrar o valor máximo $$$n$ tal que $$$i \ le xn$ . Mas isso, por definição, significa que $$$i = \ piso xn \ piso$ , o maior número inteiro positivo não é maior que xn. Portanto, isso nos leva a este algoritmo de simulação óssea n facetada (muito simples) honesto:

Algoritmo: Simulação óssea honesta

1. Gere um valor aleatório distribuído uniformemente $$$x$ no intervalo $$$[0, 1)$ .
2. Retorno $$$\ lfloor xn \ r $ pis$ .

Dadas as nossas suposições acima sobre cálculos, esse algoritmo é executado no tempo $$$O (1)$ .

Duas conclusões podem ser tiradas desta seção. Primeiro, podemos dividir o intervalo $$$[0, 1)$ em parte para que um número real aleatório distribuído uniformemente nesse intervalo se reduz naturalmente a uma das muitas opções discretas disponíveis para nós. No restante deste artigo, exploraremos ativamente essa técnica. Em segundo lugar, pode ser difícil determinar a qual intervalo específico um valor aleatório pertence, mas se soubermos algo sobre as partes (nesse caso, elas são do mesmo tamanho), então podemos matematicamente simplesmente determinar qual parte se refere a uma determinada ponto.

Trapaceando simulação óssea com osso honesto

Com um algoritmo de simulação óssea honesto, podemos adaptá-lo para simular um osso trapaceiro? Curiosamente, a resposta é sim, mas uma solução exigirá mais espaço.

Na seção anterior, é intuitivamente claro que, para simular um rolo de osso trapaceiro, precisamos apenas dividir $$$[0, 1)$ em pedaços e, em seguida, determine qual parte atingimos. No entanto, no caso geral, isso pode ser muito mais complicado do que parece. Digamos que temos um tetraedro com probabilidades de face $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ e $$$\ frac {1} {12}$ (podemos garantir que essa é a distribuição de probabilidade correta, porque $$$\ frac {1} {2} + \ frac {1} {3} + \ frac {1} {12} + \ frac {1} {12} = \ frac {6} {12} + \ frac {4 } {12} + \ frac {1} {12} + \ frac {1} {12} = \ frac {12} {12}$ ) Se dividirmos o intervalo $$$[0, 1)$ em quatro partes desses tamanhos, obtemos o seguinte:


Infelizmente, nesta etapa, estamos presos. Mesmo se soubéssemos um número aleatório no intervalo $$$[0, 1)$ , não há truques matemáticos simples para determinar automaticamente em qual parte esse número se enquadra. Não quero dizer que isso é impossível - como você verá, podemos usar muitos truques excelentes - mas nenhum deles tem a simplicidade matemática do algoritmo honesto de arremesso de ossos.

No entanto, podemos adaptar a técnica usada para ossos honestos para funcionar também neste caso. Vamos pegar o osso discutido acima como exemplo. A probabilidade de queda de arestas é $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ e $$$\ frac {1} {12}$ . Se reescrevermos isso para que todos os membros tenham um divisor comum, obteremos os valores $$$\ frac {6} {12}$ , $$$\ frac {4} {12}$ , $$$\ frac {1} {12}$ e $$$\ frac {1} {12}$ . Portanto, podemos perceber esta tarefa da seguinte forma: em vez de lançar um osso tetraédrico com probabilidades ponderadas, por que não lançar um osso honesto de 12 lados, nas bordas das quais existem valores duplicados? Como sabemos simular ossos honestos, isso será análogo à separação por intervalos $$$[0, 1)$ em pedaços desta maneira:


Em seguida, atribuímos a eles vários resultados da seguinte maneira:


Agora será muito simples simular um lançamento de osso - apenas lançamos esse novo osso honesto e depois olhamos para qual rosto caiu e lemos seu valor. Este primeiro passo pode ser realizado pelo algoritmo apresentado acima, que nos dará um número inteiro de números no intervalo $$ . Para vincular esse número inteiro a uma das faces do osso do trapaceiro original, armazenaremos uma matriz auxiliar de doze elementos que conectam cada um desses números ao resultado original. Isso pode ser representado graficamente da seguinte maneira:


Para formalizar isso na forma de um algoritmo, descrevemos o estágio de inicialização (obtendo a tabela) e o estágio de geração (simulando um lançamento aleatório do osso). É importante considerar essas duas etapas neste e nos algoritmos subsequentes, porque o tempo de preparação deve ser excelente.

No estágio de inicialização, começamos procurando o múltiplo menos comum de todas as probabilidades dadas para as bordas do osso (em nosso exemplo, o LCL é 12). O NOC é útil aqui, porque corresponde ao menor divisor comum que podemos usar para todas as frações e, portanto, o número de faces do novo osso honesto que iremos rolar. Depois de receber esse NOC (nós o denotamos por L), devemos determinar quantas faces do novo osso serão distribuídas em cada uma das faces do osso trapaceiro original. No nosso exemplo, o rosto com probabilidade $$$\ frac {1} {2}$ recebe seis lados do novo osso desde $$$\ frac {1} {2} \ vezes 12 = 6$ . Da mesma forma, a parte com probabilidade $$$\ frac {1} {3}$ recebe 4 caras desde $$$\ frac {1} {3} \ vezes 12 = 4$ . De uma forma mais generalizada, se L é um LCL de probabilidades, e $$$p_i$ é a probabilidade de um rosto $$$i$ ossos, então destacamos os rostos $$$i$ osso sharpie original $$$L \ cdot p_i$ facetas de ossos honestos.

Aqui está o pseudocódigo do algoritmo acima:

Algoritmo: simulando trapaça com osso honesto

• Inicialização :
  
  1. Encontre os NOCs dos denominadores de probabilidade $$$p_0, p_1, ..., p_ {n-1}$ ; denotá-lo $$$L$
  2. Selecione uma matriz $$$A$ o tamanho $$$L$ comparar os resultados de rolos honestos de ossos com os rolos originais do osso.
  3. Para cada rosto $$$i$ do osso inicial, realizamos o seguinte em qualquer ordem:
     
     1. Atribuímos da seguinte forma $$$L \ cdot p_i$ elementos $$$A$ valor $$$i$ .
• Geração :
  
  1. Geramos um lançamento de osso honesto para $$$L$ osso da face; chame o rosto $$$S$ .
  2. Retorno $$$A [S]$ .

Esse algoritmo pode ser simples, mas qual é a eficiência? A geração de rolos ósseos é bastante rápida - todo rolo ósseo requer $$$O (1)$ tempo de execução para gerar dados aleatórios usando o algoritmo anterior, além de mais $$$O (1)$ horário de trabalho para pesquisar na tabela. Isso nos dá o tempo total de trabalho. $$$O (1)$ .

No entanto, a etapa de inicialização pode ser extremamente cara. Para que esse algoritmo funcione, precisamos alocar espaço para uma matriz do tamanho do NLC dos denominadores de todas as frações de entrada. No nosso exemplo ( $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ ), é 12, para outros valores de entrada, os valores podem ser patologicamente incorretos. Por exemplo, vejamos frações $$$\ frac {999999} {1.000.000}$ e $$$\ frac {1} {1000000}$ . O NOC dos denominadores é igual a um milhão, portanto deve haver um milhão de elementos em nossa tabela!

Infelizmente, as coisas podem ser ainda piores. No exemplo anterior, podemos pelo menos "esperar" que o algoritmo consuma muita memória, pois os dois denominadores de frações são iguais a um milhão. No entanto, podemos ter muitas probabilidades para as quais o NOC é significativamente maior que cada denominador individual. Por exemplo, vejamos as probabilidades $$$\ frac {1} {15}$ , $$$\ frac {1} {10}$ , $$$\ frac {5} {6}$ . Aqui, o NOC dos denominadores é 30, o que é mais do que qualquer um dos denominadores. O design funciona aqui porque $$$15 = 3 \ vezes 5$ , $$$10 = 2 \ vezes 5$ e $$$6 = 2 \ vezes 3$ ; em outras palavras, cada denominador é um produto de dois números primos selecionados de um conjunto de três valores. Portanto, o NOC deles é o produto de todos esses números primos, uma vez que cada denominador deve ser um divisor do NOC. Se generalizarmos essa construção e considerarmos qualquer conjunto de $$$k$ primos e tomar uma fração para cada um dos produtos em pares desses primos, o NOC será muito mais do que cada denominador individual. De fato, um dos melhores limites superiores que podemos obter para o NOC será $$$O (\ prod_ {i = 0} ^ n {d_i})$ onde $$$d_i$ É o denominador $$$i$ essa probabilidade. Isso não permite o uso desse algoritmo em condições reais, quando as probabilidades são desconhecidas antecipadamente, uma vez que a memória necessária para armazenar a tabela de tamanhos $$$O (\ prod_ {i = 0} ^ n {d_i})$ , Pode facilmente ser mais do que o volume que cabe na RAM.

Em outras palavras, em muitos casos, esse algoritmo se comporta bem. Se todas as probabilidades são iguais, todas as probabilidades obtidas na entrada são iguais $$$\ frac {1} {n}$ para alguns $$$n$ . Então os denominadores NOC são iguais $$$n$ ou seja, como resultado, o osso honesto lançado terá $$$n$ faces e cada faceta do osso original corresponderá a uma faceta do osso honesto. Portanto, o tempo de inicialização é $$$O (n)$ . Isso pode ser representado graficamente da seguinte maneira:


Isso nos fornece as seguintes informações sobre o algoritmo:

Algoritmo	Tempo de inicialização		Tempo de geração		Memória ocupada
	O melhor	O pior	O melhor	O pior	O melhor	O pior
Osso de honestidade	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Teta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$

Outro detalhe importante sobre esse algoritmo: assume que receberemos probabilidades convenientes na forma de frações com bons denominadores. Se as probabilidades forem especificadas como IEEE-754 duplas, é provável que essa abordagem seja desastrosa devido a pequenos erros de arredondamento; Imagine que temos as probabilidades 0,25 e 0,250000000001! Portanto, é melhor não usar essa abordagem, exceto em casos especiais em que as probabilidades se comportam bem e são especificadas em um formato correspondente a operações com números racionais.

Simulação de moedas assimétrica

Nossa explicação de um primitivo aleatório simples (osso honesto) levou a um algoritmo de simulação de osso trapaceiro simples, mas potencialmente terrivelmente ineficaz. Talvez o estudo de outras primitivas aleatórias simples possa esclarecer outras abordagens para resolver esse problema.

Uma tarefa simples, mas surpreendentemente útil, é simular uma moeda assimétrica usando um gerador de números aleatórios. Se temos uma moeda com a probabilidade de uma águia $$$p_ {chefes}$ , então como podemos simular o lançamento de uma moeda assimétrica?

Anteriormente, desenvolvemos uma abordagem intuitiva: particionamento por intervalo $$$[0, 1)$ em uma sequência de regiões que, ao escolher um valor aleatório no intervalo, ele aparece em alguma região com uma probabilidade igual ao tamanho da região. Para simular uma moeda assimétrica usando um valor aleatório distribuído uniformemente no intervalo $$$[0, 1)$ devemos quebrar o intervalo $$$[0, 1)$ da seguinte maneira:


E, em seguida, gere um valor aleatório distribuído uniformemente no intervalo $$$[0, 1)$ para ver em que área está. Felizmente, temos apenas um ponto de divisão, por isso é muito fácil determinar em qual área o ponto está; se o valor for menor $$$p_ {chefes}$ , então a águia caiu sobre a moeda, caso contrário - caudas. Pseudocódigo:

Algoritmo: simule uma moeda assimétrica

1. Gere um valor aleatório distribuído uniformemente no intervalo $$$[0, 1)$ .
2. Se $$$x <p_ {cabeças}$ , retorne a "águia".
3. Se $$$x \ ge p_ {heads}$ , caudas de retorno.

Como podemos gerar um valor aleatório distribuído uniformemente no intervalo $$$[0, 1)$ a tempo $$$O (1)$ , e também podemos comparar números reais para $$$O (1)$ , então esse algoritmo é executado no tempo $$$O (1)$ .

Simulando ossos honestos usando moedas assimétricas

A partir da discussão anterior, sabemos que podemos simular um osso trapaceiro usando um osso honesto, se assumirmos que estamos prontos para gastar espaço de memória extra. Como podemos perceber uma moeda assimétrica como um osso bilateral trapaceiro, isso significa que podemos simular uma moeda assimétrica com a ajuda de um osso honesto. É interessante que o oposto também possa ser feito - para simular um osso honesto usando uma moeda assimétrica.O design é simples, elegante e pode ser facilmente generalizado para simular um osso trapaceiro usando uma variedade de moedas assimétricas.

O projeto para simular uma moeda assimétrica divide o intervalo$$$[0, 1)$ em duas áreas - a área de “águias” e a área de “caudas” com base na probabilidade de as águias caírem sobre os ossos. Já vimos um truque semelhante usado para simular$$$n$osso facetado n : intervalo$$$[0, 1)$ foi dividido em$$$n$ áreas iguais. Por exemplo, ao jogar um osso tetraédrico, obtivemos a seguinte separação:


Agora, suponha que estamos interessados ​​em simular um rolo desse osso honesto usando um conjunto de moedas assimétricas. Uma solução é a seguinte: imagine que percorremos essas áreas da esquerda para a direita, perguntando sempre se queremos parar na área atual ou se seguiremos em frente. Por exemplo, digamos que queremos selecionar aleatoriamente uma dessas áreas. Começando na área mais à esquerda, jogaremos uma moeda assimétrica, que nos diz se devemos parar nessa área ou continuar seguindo em frente. Como precisamos escolher todas essas áreas de maneira uniforme com probabilidade$$$\frac{1}{4}$ , podemos fazer isso jogando uma moeda assimétrica, as águias nas quais caem com probabilidade$$$\frac{1}{4}$ .Se uma águia cair, paramos na área atual. Caso contrário, passamos para a próxima área.

Se as moedas caírem, então nos encontramos na segunda área e novamente perguntamos se devemos selecionar essa área novamente ou continuar em movimento. Você pode pensar que, para isso, temos que jogar outra moeda com a probabilidade de uma águia$$$\frac{1}{4}$ , mas na verdade isso não é verdade! Para ver a falha nesse raciocínio, devemos chegar a uma situação extrema - se em cada área jogarmos uma moeda na qual a águia cai com probabilidade$$$\frac{1}{4}$ , ou seja, há uma pequena chance de que em cada área a moeda caia coroa, ou seja, teremos que abandonar todas as áreas. Ao percorrer as regiões, precisamos, de alguma forma, continuar aumentando a probabilidade de uma águia cair em uma moeda. Em uma situação extrema, se nos encontramos na última área, a moeda deve ter uma águia com probabilidade$$$1$ , porque se rejeitarmos todas as áreas anteriores, a decisão certa seria parar na última área.

Para determinar a probabilidade com que nossa moeda assimétrica deve lançar uma águia após pular a primeira área, precisamos observar que, depois de pular a primeira área, restam apenas três. Ao rolar um osso honesto, precisamos que cada uma dessas três áreas seja selecionada com probabilidade$$$\frac{1}{3}$ . Portanto, intuitivamente, parece que deveríamos ter um segundo osso no qual a águia cai com probabilidade $$$\frac{1}{3}$ . Usando um raciocínio semelhante, pode-se entender que quando uma coroa aparece na segunda região da rede na terceira região, a moeda deve ser jogada pela águia com probabilidade $$$\frac{1}{2}$ , e na última área - com probabilidade$$$1$ .

Esse entendimento intuitivo nos leva ao seguinte algoritmo. Observe que não discutimos a correção ou falácia desse algoritmo; em breve faremos isso.

Algoritmo: simulando ossos honestos usando moedas assimétricas

1. Para $$$i = 0$ a$$$n - 1$ :
   
   1. Jogue uma moeda assimétrica com a probabilidade de uma águia $$$\frac{1}{n - i}$ .
   2. Se a águia cair, volte $$$i$ .

Esse algoritmo é simples e, na pior das hipóteses, é executado no tempo. $$$O (n)$ .Mas como verificamos se está correto? Para descobrir, precisamos do seguinte teorema:

Teorema: o algoritmo acima retorna o lado$$$i$ com probabilidade$$$\frac{1}{n}$ para qualquer selecionado$$$i$ .

Prova: considere qualquer constante$$$n \ge 0$ . Usando forte indução, provamos que cada um $$$n$ faces tem uma probabilidade de escolha$$$\frac{1}{n}$ .

Para o nosso exemplo, mostramos que o rosto $$$0$ dado tem probabilidade de escolha$$$\frac{1}{n}$ . Mas isso segue diretamente do próprio algoritmo - escolhemos a face 0 se em uma moeda assimétrica com a probabilidade de uma águia $$$\frac{1}{n}$ , $$$\frac{1}{n}$ .

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{1}{n - k}$ . $$$k$ $$$\frac{1}{n}$ , , $$$k$ é dado como$$$\frac{k}{n}$ . Isso significa que a probabilidade de o algoritmo não selecionar um dos primeiros $$$k$ enfrenta iguais$$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ . Ou seja, a probabilidade de escolher um rosto $$$k$ é dado como$$$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$ , que deve ser mostrado. Assim, cada face do osso é selecionada de maneira uniforme e aleatória.

Obviamente, o algoritmo é bastante ineficiente - usando a primeira técnica, podemos simular um lançamento de dados honestos com o tempo $$$O(1)$ ! Mas esse algoritmo pode ser usado como um trampolim para um algoritmo suficientemente eficaz para simular um trapaceiro usando moedas assimétricas.

Simulação óssea de shuler usando moedas assimétricas

O algoritmo apresentado acima é interessante, pois nos fornece uma estrutura simples para simular um osso usando um conjunto de moedas. Começamos jogando uma moeda para determinar se deve selecionar a primeira faceta do osso ou passar para o resto. Nesse processo, precisamos lidar com cuidado com a escala das probabilidades restantes.

Vamos ver como você pode usar essa técnica para simular um arremesso de osso. Usamos nosso exemplo com probabilidades$$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . Ele, se você não se lembra, divide o intervalo $$$[0, 1)$ como se segue:


Agora vamos pensar em como simular um osso trapaceiro usando moedas assimétricas. Podemos começar jogando uma moeda com a probabilidade de uma águia$$$\frac{1}{2}$ para determinar se devemos retornar a face 0. Se uma águia cair nessa moeda, tudo bem! Nós terminamos. Caso contrário, precisamos jogar outra moeda para decidir se deve selecionar a próxima faceta. Como antes, apesar do fato de a próxima faceta ter uma probabilidade de escolha$$$\frac{1}{3}$ , não queremos jogar uma moeda na qual a águia caia com probabilidade$$$\frac{1}{3}$ , porque metade da “massa” de probabilidades foi descartada quando não selecionamos uma linha com$$$\frac{1}{2}$ . De fato, como metade da massa de probabilidades desapareceu, se re-normalizarmos as probabilidades restantes, obteremos probabilidades atualizadas: $$$\frac{2}{3}$ , $$$\frac{1}{6}$ , $$$\frac{1}{6}$ . Portanto, a segunda moeda deve ser jogada com probabilidade $$$\frac{2}{3}$ . Se esta moeda também é coroa, então temos que escolher entre dois lados $$$\frac{1}{12}$ . Uma vez que nesta fase nos livraremos de $$$\frac{5}{6}$ massas de probabilidades, então podemos normalizar novamente as probabilidades das partes$$$\frac{1}{12}$ para que todos tenham uma chance$$$\frac{1}{2}$ gotas de uma águia, ou seja, a terceira moeda terá uma probabilidade$$$\frac{1}{2}$ . A última moeda, se alguma vez vier a ela, deve lançar a águia com probabilidade $$$1$ pois esta é a área mais recente.

Para resumir, as probabilidades de moedas serão as seguintes:

1. Primeiro rolo: $$$\frac{1}{2}$
2. Segundo rolo: $$$\frac{2}{3}$
3. Terceiro rolo: $$$\frac{1}{2}$
4. Quarto rolo: $$$1$

Pode ser intuitivo a origem desses números, mas, para transformar a seleção em um algoritmo, precisamos criar uma construção formal da escolha das probabilidades. A idéia será a seguinte - em cada estágio, lembramos o restante da massa de probabilidades. No início, antes que a primeira moeda seja lançada, é igual a$$$1$ . Depois de jogar a primeira moeda $$$1 - p_0$ . Depois de jogar uma segunda moeda $$$1 - p_0 - p_1$ . Mais geralmente após o lançamento $$$k$ restante da massa de probabilidade é$$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . Cada vez que jogamos uma moeda para determinar se uma área deve ou não ser selecionada $$$k$ , como resultado, jogamos uma moeda, a probabilidade de uma águia cair sobre a qual é igual à fração da probabilidade restante ocupada pela probabilidade$$$p_k$ , que é definido como o$$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ . Isso nos dá o seguinte algoritmo para enganar a simulação óssea com um conjunto de moedas assimétricas (provaremos sua correção e tempo de execução logo abaixo):

Algoritmo: Osso de Schuler de moedas assimétricas

• Inicialização :
  
  1. Mantemos probabilidades $$$p_i$ para uso futuro.
• Geração :
  Conjunto$$$mass = 1$
  Para$$$i = 0$ a$$$n - 1$ :
  
  1. Jogue uma moeda assimétrica com a probabilidade de uma águia $$$\frac{p_i}{mass}$ .
  2. Se a águia cair, volte $$$i$ .
  3. Caso contrário, definimos $$$mass = mass - p_i$

Do ponto de vista intuitivo, isso é lógico, mas é matematicamente verdadeiro? Felizmente, a resposta é sim, graças a uma generalização da prova acima:

Teorema: o algoritmo mostrado acima retorna uma face$$$i$ com probabilidade$$$p_i$ para qualquer selecionado$$$i$ .

Prova: considere qualquer constante$$$n \ge 0$ . , $$$n$ $$$p_i$ .

, $$$0$ $$$p_0$ . $$$0$ , , $$$\frac{p_0}{mass}$ . $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ . Isso significa que a probabilidade geral de escolher um rosto $$$k$ é dado como$$$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$, conforme necessário.

Agora vamos avaliar a complexidade do tempo desse algoritmo. Sabemos que o tempo de inicialização pode ser$$$\Theta(1)$ se mantivermos uma cópia de superfície da matriz de probabilidade de entrada, mas pode haver$$$\Theta(n)$ para que possamos salvar nossa própria versão da matriz (caso a função de chamada queira alterá-la mais tarde). A própria geração de um resultado de projeção óssea pode exigir no pior dos casos$$$\Theta(n)$ lança, e apenas um rolo no melhor dos casos.

No entanto, após a reflexão, fica claro que o número de lançamentos de moedas necessários é grandemente influenciado pela distribuição recebida. No melhor dos casos, teremos uma distribuição de probabilidade na qual toda a massa de probabilidades está concentrada na primeira extremidade do osso e todas as outras probabilidades são zero. Nesse caso, um sorteio é suficiente para nós. Na pior das hipóteses, toda a massa de probabilidades está concentrada na última faceta do osso e, em todas as outras faces, é igual a zero. Nesse caso, temos que jogar$$$n$ moedas.

Podemos caracterizar clara e matematicamente o número esperado de lançamentos de moedas neste algoritmo. Vamos imaginar uma variável aleatória$$$X$ , denotando o número de lançamentos de moedas para qualquer execução desse algoritmo para uma distribuição específica. Isso é$$$\mathbb{P}[X = 1]$ é a probabilidade de que, para completar o algoritmo, seja suficiente jogar uma moeda,$$$\mathbb{P}[X = 2]$ - a probabilidade de o algoritmo jogar duas moedas, etc. Nesse caso, o número esperado de lançamentos de moedas para o nosso algoritmo é determinado pelaexpectativa matemática $$$X$ indicado por$$$\mathbb{E}[X]$ . Por definição, entendemos isso

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

Qual o significado $$$\mathbb{P}[X = i]$ ?O algoritmo termina após a seleção de alguma borda do osso. Se ele escolher um rosto$$$0$ , depois jogue uma moeda. Se ele escolher um rosto$$$1$ , então ele jogará duas moedas - uma para entender que ele não quer escolher um rosto$$$0$ , outro para entender que ele quer escolher um rosto$$$1$ . Se for mais generalizado, se o algoritmo selecionar uma face $$$i$ então ele vai sair$$$i + 1$ : $$$i$ , , $$$i - 1$ , , , $$$i$ . , $$$i$ $$$p_i$ , ,

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]} = \sum_{i = 1}^n{i \cdot p_{i - 1}} = \sum_{i = 1}^n{((i - 1) p_{i - 1} + p_{i - 1})} = \sum_{i = 1}^n{((i - 1) p_{i - 1})} + \sum_{i = 1}^n{p_{i - 1}}$$

Observe que na última simplificação, o primeiro termo é equivalente $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ o que é equivalente $$$\ mathbb {E} [p]$ , o resultado esperado de um lançamento de dados! Além disso, o segundo termo é igual a $$$1$ porque esta é a soma de todas as probabilidades. Isso significa que $$$\ mathbb {E} [X] = \ mathbb {E} [p] + 1$ . Ou seja, o número esperado de rolos de moedas é igual a um mais a expectativa matemática de um rolo de dado!

Algoritmo	Tempo de inicialização		Tempo de geração		Memória ocupada
	O melhor	O pior	O melhor	O pior	O melhor	O pior
Osso de honestidade	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Teta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Osso de Schuler de moedas assimétricas	$$$\ Theta (n)$		$$$\ Teta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$

Generalizando moedas assimétricas: simulando um osso trapaceiro

No exemplo mostrado acima, fomos capazes de simular efetivamente uma moeda assimétrica, pois precisamos levar em conta apenas um ponto de divisão. Como podemos efetivamente generalizar essa idéia para um osso trapaceiro no qual o número de faces pode ser arbitrário?

Como você pode ver, uma moeda assimétrica é um osso trapaceiro, com apenas duas faces. Portanto, podemos perceber uma moeda assimétrica simplesmente como um caso especial de um problema mais geral que queremos resolver. Ao resolver o problema de moedas assimétricas, dividimos o intervalo $$$[0, 1)$ em duas áreas - uma para a águia e a segunda para caudas - e, em seguida, para encontrar a área, usamos o fato de que existe apenas um ponto de divisão. Se tivermos um osso com face n, haverá mais áreas e, portanto, vários pontos de divisão. Suponha, por exemplo, que tenhamos um osso de sete lados com probabilidades $$$\ frac {1} {4}$ , $$$\ frac {1} {5}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ . Se queremos dividir o intervalo $$$[0, 1)$ em sete partes, fazemos o seguinte:


Observe onde essas áreas estão localizadas. A primeira área começa com $$$0$ e termina $$$\ frac {1} {4}$ . A segunda área começa com $$$\ frac {1} {4}$ e termina em $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ . De maneira mais geral, se as probabilidades são iguais $$$p_0, p_1, ..., p_ {n - 1}$ , então as áreas terão intervalos $$$[0, p_0)$ , $$$[p_0, p_0 + p_1)$ , $$$[p_0 + p_1, p_0 + p_1 + p_2)$ etc. Essa é a área $$$i$ limitado pelo intervalo

$$

$$[\ sum_ {j = 0} ^ {i - 1} {p_j}, \ sum_ {j = 0} ^ {i} {p_j})$$

Observe que a diferença entre esses dois valores é $$$p_i$ ou seja, a área total da região é $$$p_i$ conforme necessário.

Agora sabemos onde estão as áreas. Se quisermos escolher um valor aleatório distribuído uniformemente $$$x$ no intervalo $$$[0, 1)$ , então como determinamos em que intervalo ele cai? Se usarmos o algoritmo de moeda assimétrico como ponto de partida, a idéia será a seguinte: a partir do ponto final da primeira região, mova-se constantemente por todas as áreas até encontrarmos um ponto final cujo valor seja maior que o valor $$$x$ . Se fizermos isso, encontraremos a primeira região que contém o ponto $$$x$ e, portanto, nosso valor. Por exemplo, se escolhermos um valor aleatório $$$x = \ frac {27} {40}$ , execute a seguinte pesquisa:


A partir do qual podemos concluir que a faceta 3 caiu nos dados com a indexação do zero.

Esse algoritmo de varredura linear nos dará um algoritmo de tempo $$$O (n)$ para encontrar a borda ejetada do osso. Entretanto, podemos melhorar significativamente seu tempo de execução usando a seguinte observação: uma série de pontos finais de regiões forma uma sequência crescente (já que sempre adicionamos mais e mais probabilidades, nenhuma das quais pode ser menor que zero). Portanto, queremos responder à seguinte pergunta: com uma sequência crescente de valores e algum ponto de verificação, precisamos encontrar o primeiro valor no intervalo estritamente maior que o ponto de verificação. Este é o momento perfeito para usar a pesquisa binária ! Por exemplo, aqui está uma pesquisa binária na matriz acima para encontrar a área à qual ela pertence $$$x = \ frac {39} {40}$ :


Isso nos dá um algoritmo ao longo do tempo. $$$\ Theta (\ log n)$ para vincular um valor aleatório distribuído uniformemente no intervalo $$$[0, 1)$ à beira de um osso abandonado. Além disso, o tempo de pré-processamento é suficiente para criar a tabela de terminais $$$\ Theta (n)$ ; simplesmente calculamos somas parciais de probabilidades à medida que avançamos.

Às vezes, esse algoritmo é chamado de algoritmo de seleção de roleta porque seleciona uma área aleatória usando uma técnica semelhante a uma roleta - jogando a bola em um intervalo e observando onde ela para. No pseudo-código, o algoritmo se parece com isso:

Algoritmo: seleção de roleta

• Inicialização :
  
  1. Selecione uma matriz $$$A$ o tamanho $$$n$
  2. Montamos $$$A [0] = p_0$ .
  3. Para todas as probabilidades $$$i$ de $$$1$ antes $$$n - 1$ :
     
     1. Montamos $$$A [i] = A [i - 1] + p_i$
  
  
• Geração :
  
  1. Gere um valor aleatório distribuído uniformemente $$$x$ no intervalo $$$[0, 1)$
  2. Usando uma pesquisa binária, encontramos o índice $$$i$ menor elemento $$$A$ o que é menos $$$x$ .
  3. Retorno $$$i$ .

A comparação entre esse algoritmo e o dado anteriormente parece bastante impressionante:

Algoritmo	Tempo de inicialização		Tempo de geração		Memória ocupada
	O melhor	O pior	O melhor	O pior	O melhor	O pior
Osso de honestidade	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Teta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Osso de Schuler de moedas assimétricas	$$$\ Theta (n)$		$$$\ Teta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Seleção de roleta	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$

Obviamente, agora temos um algoritmo muito melhor que o original. A discrição das probabilidades apenas a princípio parecia promissora, mas essa nova abordagem, baseada em valor contínuo e pesquisa binária, parece muito melhor. No entanto, ainda é possível melhorar esses indicadores com o uso inteligente de um conjunto de técnicas híbridas, que discutiremos a seguir.

Um detalhe interessante desse algoritmo é que, embora o uso da pesquisa binária garanta o pior momento possível para gerar números aleatórios $$$O (\ log n)$ , também não permite uma pesquisa mais rápida; isto é, o tempo de geração também será igual $$$\ Omega (\ log n)$ . Pode ser melhorado? Acontece que você pode.

Suponha que passemos de uma pesquisa binária em uma lista de probabilidades cumulativas para o uso de uma árvore de pesquisa binária . Por exemplo, tendo o conjunto de probabilidades fornecido acima, podemos construir a seguinte árvore de pesquisa binária para sua distribuição cumulativa:


Agora, se queremos simular um rolo de osso, podemos gerar um número uniformemente distribuído no intervalo $$$[0, 1)$ e, em seguida, observe qual intervalo está nesta árvore de pesquisa binária (BST). Como essa é uma árvore de pesquisa binária equilibrada, o melhor tempo de pesquisa é $$$O (1)$ e o pior $$$O (\ log n)$ .

No entanto, supondo que sabemos mais sobre a distribuição de probabilidade, podemos fazer muito melhor. Por exemplo, suponha que nossas probabilidades sejam iguais $$$\ frac {99} {100}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ . Ou seja, a distribuição de probabilidade é extremamente distorcida e quase toda a massa de probabilidades está concentrada em uma face. Podemos criar um BST balanceado para essas probabilidades:


Embora essa árvore de pesquisa binária seja perfeitamente equilibrada, ela não é muito adequada para nossas tarefas. Como sabemos que em 99 dos 100 casos, o valor aleatório estará na faixa $$$[0, \ frac {99} {100})$ , não há sentido em armazenar o nó para esse intervalo em que ele está localizado agora. De fato, isso significa que, quase o tempo todo, faremos duas comparações desnecessárias com as áreas azul e amarela. Como com uma probabilidade muito alta, deveríamos ser os primeiros a verificar o maior intervalo, seria lógico desequilibrar a árvore para tornar o caso médio muito melhor devido aos restantes. Isso é mostrado aqui:


Agora provavelmente concluiremos a pesquisa encontrando imediatamente a área desejada após a primeira tentativa. No caso muito improvável de a área desejada estar no restante $$$(\ frac {99} {100}, 1]$ descemos calmamente até o final da árvore, que é realmente bem equilibrada.

De uma forma generalizada, queremos resolver o seguinte problema:

Dado um determinado conjunto de probabilidades, encontre uma árvore de pesquisa binária para essas probabilidades que minimize o tempo esperado de pesquisa.

Felizmente, este problema tem sido extensivamente estudada e é chamado o problema da árvore de pesquisa ideal binário . Existem muitos algoritmos para resolver esse problema; sabe-se que a solução exata pode ser encontrada a tempo $$$O (n ^ 2)$ usando programação dinâmica e que existem bons algoritmos de tempo linear que podem encontrar soluções aproximadas. Além disso, para obter um fator constante da solução ideal, você pode usar a estrutura de dados da árvore de reprodução (árvore em expansão) (árvore de pesquisa binária com auto balanceamento).

É interessante que o melhor argumento para o comportamento dessas árvores de pesquisa binária otimizada ocorra quando as distribuições de probabilidade são extremamente distorcidas, porque podemos simplesmente mover os nós que contêm a grande maioria da massa de probabilidade para a raiz da árvore, e o pior caso é quando a distribuição é equilibrada, porque a árvore deve ser larga e raso. Isso é o oposto do comportamento do algoritmo anterior, no qual um método honesto foi usado para simular uma trapaça!

No melhor dos casos, temos um osso trapaceiro no qual uma face sempre cai (ou seja, tem uma probabilidade de 1 e todas as outras faces têm uma probabilidade de 0). Este é um exagero extremo do nosso exemplo anterior, mas, neste caso, a pesquisa sempre terminará após a primeira tentativa. Na pior das hipóteses, todas as probabilidades são iguais e obtemos uma pesquisa BST padrão. Chegamos ao seguinte:

Algoritmo	Tempo de inicialização		Tempo de geração		Memória ocupada
	O melhor	O pior	O melhor	O pior	O melhor	O pior
Osso de honestidade	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Teta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Osso de Schuler de moedas assimétricas	$$$\ Theta (n)$		$$$\ Teta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Seleção de roleta	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
Seleção ideal de roleta	$$$O (n ^ 2)$		$$$\ Teta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$

Arremesso de dardo

Até agora, estamos considerando duas primitivas que nos ajudaram a criar algoritmos para simular um osso trapaceiro: osso honesto e moeda assimétrica. Usando apenas ossos honestos, chegamos a um algoritmo (infelizmente, impraticável) para trapacear ossos e, começando com moedas assimétricas, fomos capazes de inventar um algoritmo rápido para trapacear ossos. Essas duas abordagens podem ser combinadas para criar um algoritmo baseado em ossos honestos e moedas assimétricas? Acontece que sim, e de fato o algoritmo resultante é melhor do que as duas abordagens.

Até esse momento, visualizamos o intervalo $$$[0, 1)$ e probabilidades de faces ósseas como um intervalo unidimensional. Ambos os algoritmos selecionam algum ponto no intervalo $$$[0, 1)$ e coloque-o em um segmento de linha reta, cujo comprimento corresponda a algum tipo de probabilidade. Quanto mais longos os segmentos que criamos, maior a probabilidade de escolher esse segmento. Mas e se você tentar pensar não em uma, mas em duas dimensões? E se tomarmos probabilidade $$$p_i$ não o comprimento de um segmento de linha reta, mas a área de um retângulo?

Vamos começar retornando ao nosso exemplo anterior com probabilidades $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ . Representamos essas probabilidades na forma de retângulos com uma largura $$$w$ (com algumas arbitrárias $$$w> 0$ ) e altura $$$p_i$ (assim, a área do retângulo será igual a $$$w \ cdot p_i$ ):


Observe que a área total desses retângulos é $$$w$ desde a área

$$

$$\ sum_ {i = 0} ^ {n - 1} {w p_i} = w \ sum_ {i = 0} ^ {n - 1} {p_i} = w$$

Agora, suponha que desenhemos um retângulo delimitador em volta desses retângulos cuja largura é $$$4w$ (já que existem quatro quadrângulos) e a altura é $$$\ frac {1} {2}$ (já que o retângulo mais alto tem uma altura $$$\ frac {1} {2}$ ):


Podemos imaginar que esse retângulo é dividido em cinco áreas - quatro áreas correspondem a probabilidades diferentes e uma área indica espaço não utilizado. Fazendo essa pausa, podemos pensar no algoritmo de simulação de lançamento aleatório de dados como um jogo de dardos. Suponha que jogemos um dardo (perfeitamente distribuído uniformemente) nesse alvo. Se ele cair no espaço não utilizado, retiramos o dardo e o jogamos novamente, repetindo o processo até entrarmos em um dos retângulos. Como quanto maior a probabilidade, maior o retângulo, maior a probabilidade de lançar a borda do osso, maior a probabilidade de cair em seu retângulo. De fato, se definirmos a condição de que já caímos em algum tipo de retângulo, obtemos o seguinte:

$$

$$\ mathbb {P} [\ mbox {retângulo de acerto para o lado i} | \ mbox {pressione algum retângulo}] = \ frac {\ mbox {área do retângulo para i}} {\ mbox {área total do retângulo}} = \ frac {w p_i} {w} = p_i$$

Em outras palavras, quando finalmente caímos em algum tipo de retângulo com nosso dardo distribuído uniformemente, selecionamos o retângulo da face $$$i$ osso trapaceiro com probabilidade $$$p_i$ , isto é, com a probabilidade de que precisamos! Ou seja, se pudermos encontrar uma maneira eficaz de simular o lançamento de dardos aleatórios nesse retângulo, teremos uma maneira eficaz de simular o lançamento de dados aleatórios.

Uma maneira de simular arremessos de dardo nesse retângulo é selecionar dois valores uniformemente distribuídos no intervalo $$$[0, 1)$ escalando-os para a largura e altura apropriadas, seguido pela verificação da área sob o dardo. No entanto, isso causa o mesmo problema que tivemos quando tentamos determinar a região unidimensional em que o valor aleatório está localizado. No entanto, há uma série verdadeiramente maravilhosa de observações, graças à qual determinar o local do impacto pode ser uma tarefa simples, se não trivial.

Primeira observação: mostramos que a largura desses retângulos pode ser escolhida arbitrariamente, porque todos eles têm largura igual. As alturas, é claro, dependem das probabilidades das faces dos ossos. No entanto, se escalarmos uniformemente todas as alturas por algum número real positivo $$$h$ , as áreas relativas de todos os retângulos serão as mesmas. De fato, para qualquer número real positivo $$$h$ área total de todos os retângulos após escalar suas alturas em $$$h$ calculado como

$$

$$\ sum_ {i = 0} ^ {n - 1} {w h p_i} = w h \ sum_ {i = 0} ^ {n - 1} {p_i} = w h$$

Agora consideraremos a probabilidade de escolher qualquer retângulo individual, limitando-nos à condição de que definitivamente atingimos algum tipo de retângulo. Usando os mesmos cálculos, obtemos o seguinte:

$$

$$\ mathbb {P} [\ mbox {retângulo de acerto para o lado i} | \ mbox {pressione algum retângulo}] = \ frac {\ mbox {área do retângulo para i}} {\ mbox {área total do retângulo}} = \ frac {w h p_i} {w h} = p_i$$

De fato, a probabilidade de escolher um único retângulo não muda se os dimensionarmos de maneira linear e uniforme.

Como podemos escolher qualquer fator de escala adequado, por que não dimensionamos esses retângulos para que a altura da caixa delimitadora seja sempre 1? Como a altura da caixa delimitadora é determinada pelo valor máximo $$$p_i$ probabilidades de entrada, então podemos começar escalando cada um dos retângulos por um fator $$$\ frac {1} {p_ {max}}$ onde $$$p_ {max}$ É a probabilidade máxima de todas as probabilidades de entrada. Graças a isso, obtemos a altura do retângulo 1. Da mesma forma, como podemos escolher qualquer largura arbitrária para os retângulos, vamos usar a largura 1. Isso significa que, para $$$n$ as probabilidades da largura total da caixa delimitadora são $$$n$ e a altura total é 1. Isso é mostrado na figura:


Agora estamos prontos para pensar em como podemos lançar um dardo aleatório em um retângulo e determinar em que ele caiu. O mais importante é que podemos dividir o retângulo para que ele não consista em vários retângulos menores e em um espaço vazio de uma forma estranha. Em vez disso, a área é cortada em um conjunto de $$$2n$ retângulos, dois em cada um $$$n$ probabilidades de entrada. Isso é mostrado aqui:


Observe como esse retângulo se forma. Para cada face do osso do trapaceiro, temos uma coluna com uma largura de 1 e uma altura de 1, dividida em dois espaços - um meio espaço "sim" correspondente a um retângulo desse tamanho e um meio espaço "não" correspondente à parte restante da coluna.

Agora vamos pensar em como podemos lançar um dardo. Um dardo perfeitamente uniforme lançado neste retângulo terá componentes $$$x$ e $$$y$ . Aqui componente $$$x$ que deve estar no intervalo $$$[0, 1)$ , corresponde a qual coluna o dardo atinge. Componente $$$y$ que deve estar no intervalo $$$[0, 1)$ , corresponde a quão alto estamos na coluna. Seleção de componentes $$$x$ afeta qual face do osso trapaceiro estamos considerando e a escolha do componente $$$y$ corresponde se escolhemos ou não essa faceta. Mas espere - já conhecemos essas duas idéias! Seleção de coordenadas $$$x$ correspondente à coluna, semelhante a lançar um osso honesto para decidir sobre a escolha da coluna. Seleção de coordenadas $$$y$ corresponde ao lançamento de uma moeda assimétrica para determinar se uma face deve ser selecionada ou lançada novamente! Essa observação é tão importante que a tornamos absolutamente compreensível:

A escolha de um ponto aleatório nesse intervalo é semelhante a jogar um osso honesto e jogar uma moeda assimétrica.

De fato, esse resultado pode ser percebido como uma oportunidade muito mais poderosa. Para simular um osso trapaceiro, construímos um conjunto de moedas assimétricas, uma para cada face do osso, e depois rolamos um osso honesto para determinar qual moeda jogar. , , , , .

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ . , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ .
  2. $$$Coins$ $$$n$ , «» .
  3. $$$i$ $$$0$ antes $$$n - 1$ :
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$i$ $$$[0, n)$ .
     2. , $$$Coins[i]$ .
     3. , $$$i$ .

. $$$O (n)$ , $$$O (n)$ $$$Coins$ , $$$O (n)$ . , $$$O(1)$ . ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$i$ $$$\frac{p_i}{p_{max}}$ , -

$$

$$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ . ? $$$p_{max}$ . $$$p_{max}$ $$$1$ ( ). $$$n$ , $$$n$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . Se $$$p_{max} = \frac{1}{n}$ , 1. . Se $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$n$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ . , «» $$$\frac{1}{n \cdot p_{max}}$ . , , «», $$$p_{max}$ . , , .

:

Algoritmo
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . , $$$\frac{1}{4}$ . , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ? , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ . , :


, , $$$\frac{1}{2}$ e $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ? , - , :


, , . , $$$\frac{1}{2}$ e $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ . $$$n$ . , alias , ( ). , . - - $$$i$ . $$$Prob[i]$ . , , $$$i$ , , $$$Alias[i]$ . alias :

Alias

Agora precisamos provar formalmente que a capacidade de criar tabelas $$$Alias ​​$ e $$$Prob$ sempre existe. Para provar que isso sempre é possível, precisamos mostrar que é sempre possível fazer o seguinte:

• Criar retângulos $$$(n \ cdot p_i) \ vezes 1$ para cada uma das probabilidades $$$p_i$ ,
• corte-os horizontalmente em pedaços menores e
• distribuí-los para $$$n$ as colunas
  
  • para que a altura de cada coluna seja igual $$$1$ ,
  • nenhuma coluna possui mais de dois retângulos e
  • retângulo correspondente à face $$$i$ localizado na coluna $$$i$ .

Antes de passar para a prova de que isso sempre é possível, vejamos um exemplo. Digamos que temos quatro probabilidades $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ . Este é um conjunto de quatro probabilidades ( $$$k = n = 4$ ), cuja soma é igual $$$1 = \ frac {4} {4}$ . Embora tenhamos mostrado experimentalmente como preencher a tabela de alias acima, agora vamos ver sua criação com mais detalhes e começar com uma tabela completamente vazia e começar a preenchê-la. Começamos escalando todas essas probabilidades por um fator de 4, o que nos dá essas probabilidades e uma tabela vazia:


Observe que dois dos quatro retângulos que precisamos distribuir ( $$$\ frac {1} {3}$ , $$$\ frac {1} {3}$ ) menor que 1. Isso significa que eles não serão capazes de preencher completamente a coluna e de preencher o restante, precisamos de outra probabilidade. Vamos pegar um dos dois (digamos amarelo) e colocá-lo na coluna correspondente:


Agora, de alguma forma, precisamos cobrir a diferença no topo da coluna. Para fazer isso, percebemos que dois retângulos ainda não distribuídos têm uma altura maior que 1 (ou seja, $$$2$ e $$$\ frac {4} {3}$ ) Vamos escolher um deles aleatoriamente; deixe estar $$$\ frac {4} {3}$ . Em seguida, distribuiremos uma porção suficiente de $$$\ frac {4} {3}$ em uma coluna para preenchê-lo completamente; como resultado, nos envolvemos $$$\ frac {2} {3}$ de $$$\ frac {4} {3}$ como mostrado abaixo:


Agora vamos ver como é o nosso circuito. Temos três retângulos cuja área total é $$$3$ , e três colunas livres, ou seja, parece que você pode distribuir esses retângulos nessas três colunas. Para fazer isso, usaremos o mesmo truque de antes. Observe que há pelo menos um retângulo cuja altura é menor que $$$1$ , então escolheremos um de uma maneira arbitrária (por exemplo, um retângulo $$$\ frac {2} {3}$ ) e coloque-o na sua coluna:


Agora precisamos preencher a coluna até o fim, para obtermos uma probabilidade que não seja menor que 1 e usá-la para complementar o restante da coluna. Aqui temos apenas uma opção (use $$$2$ ), então tomamos $$$\ frac {1} {3}$ de $$$2$ e coloque no topo da coluna:


Agora, ele se resume a dois retângulos, cuja área total é dois. Repetimos esse processo, encontrando um retângulo cuja altura não exceda 1 (aqui está $$$\ frac {1} {3}$ ) e colocá-lo nesta coluna:


Agora vamos encontrar um retângulo não inferior a $$$1$ para complementar a coluna. A única opção para nós é $$$\ frac {5} {3}$ :


Agora, temos apenas um retângulo restante e sua área é 1. Portanto, podemos simplesmente concluir a criação colocando esse retângulo em sua própria coluna:


E pronto! Nós preenchemos a mesa.

Observe que o design desta tabela é baseado em um padrão comum:

• Encontramos um retângulo cuja altura não é maior que 1 e o colocamos em sua própria coluna, configurada na tabela $$$Prob$ a altura deste retângulo.
• Encontramos um retângulo cuja altura não é menor que 1, usamos para preencher a coluna, configurada na tabela $$$Alias ​​$ coincidir com a face do osso que esse retângulo representa.

É possível provar que essa construção é sempre possível no caso geral? Ou seja, não estamos "presos" ao distribuir as probabilidades dessa maneira? Felizmente, há evidências. Isso pode ser explicado da seguinte forma: escalamos todas as probabilidades para que o valor médio das novas probabilidades seja igual a 1 (já que inicialmente era igual a $$$\ frac {1} {n}$ e multiplicamos tudo por $$$n$ ) Sabemos que o mínimo de todas as probabilidades escaladas não deve ser maior que a média e que o máximo de todas as probabilidades escaladas não deve ser menor que a média; portanto, quando começamos aqui, sempre devemos ter pelo menos um elemento de não mais que 1 (ou seja, a menor de todas as probabilidades escaladas) e um elemento de pelo menos 1 (ou seja, a maior das probabilidades escaladas). Portanto, podemos emparelhar esses elementos. Mas o que acontece se removermos os dois? Quando fazemos isso, como resultado, removemos uma probabilidade do total e reduzimos a soma total das probabilidades escaladas em um. Isso significa que o novo valor médio não mudou, porque a probabilidade média escalada é igual. Podemos repetir esse procedimento repetidamente até finalmente parear todos os elementos.

Podemos formalizar esse argumento no seguinte teorema:

Teorema: se houver $$$k$ retângulos de largura unitária com alturas $$$h_0$ , $$$h_1$ , ..., $$$h_ {k-1}$ tal que $$$\ sum_ {i = 0} ^ {k-1} {h_i} = k$ , sempre há uma maneira de separar os retângulos e distribuí-los em $$$k$ colunas, cada uma com uma altura de 1, para que cada coluna contenha não mais que dois retângulos diferentes e em $$$i$ esta coluna conterá pelo menos uma parte $$$i$ o retângulo.

Prova: por indução. No caso base, se $$$k = 1$ , então temos apenas um retângulo e sua altura deve ser igual a 1. Portanto, podemos colocá-lo em $$$0$ coluna. Portanto, cada coluna tem uma altura de 1, não contém mais de dois retângulos e, em $$$0$ -a coluna contém pelo menos uma parte $$$0$ o retângulo.

Para o estágio de indução, suponha que, para algum número natural $$$k$ o teorema é válido e considera qualquer $$$k + 1$ retângulos de largura $$$1$ e alturas $$$h_0$ , $$$h_1$ , ..., $$$h_ {k}$ tal que $$$\ sum_ {i = 0} ^ {k} {h_i} = k + 1$ . Primeiro, afirmamos que existe uma certa altura $$$h_l$ tal que $$$h_l \ le 1$ e alguma outra altura $$$h_g$ (tal que $$$l \ ne g$ ) tal que $$$h_g \ ge 1$ . Para verificar isso, vamos pelo contrário e suponha que não exista tal $$$h_l$ com $$$h_l \ le 1$ ; isso significa que $$$h_i> 1$ para todos os números naturais $$$i$ no intervalo $$$0 \ le i \ le k$ . Mas então nós entendemos isso $$$k + 1 = \ sum_ {i = 0} ^ k {h_i}> \ sum_ {i = 0} ^ k {1} = k + 1$ o que é obviamente impossível. Portanto, existe algum tipo de índice $$$l$ tal que $$$h_l \ le 1$ . Agora, novamente, vamos pelo contrário e suponha que não há outra altura $$$h_g$ (com $$$l \ ne g$ ) tal que $$$h_g \ ge 1$ . Então acontece que um ao outro $$$h_g <1$ , isto é (por lógica semelhante) $$$\ sum_ {i = 0} ^ {k} {h_i} <k + 1$ e chegamos a uma contradição. Portanto, $$$h_l \ le 1$ e $$$h_g \ ge 1$ .

Agora considere a seguinte construção. Coloque $$$h_l$ na coluna $$$l$ e preencha o espaço restante $$ em $$$l$ essa coluna faz parte do retângulo $$$h_g$ (esse espaço deve existir desde $$$0 \ le 1 - h_l \ le 1$ e $$$h_g \ ge 1$ ) Então, vamos preencher completamente a coluna. Agora temos um conjunto de $$$k$ partes diferentes de retângulos cujo valor total é igual a $$$k$ , já que removemos a área total dos retângulos $$$1$ e o total inicial foi $$$k + 1$ . Além disso, preenchemos completamente a coluna $$$l$ , ou seja, não precisamos mais colocar outras partes dos retângulos ali. Portanto, pela hipótese indutiva, podemos distribuir o restante $$$k$ em $$$k$ colunas para que satisfaça as condições acima. Combinado com o fato de que agora preenchemos a coluna $$$l$ , isso significa que temos uma maneira de preencher todas as colunas para que ele atenda às restrições. Isso completa a indução.

Essa é uma prova da possibilidade de construção, que afirma que não apenas sempre podemos construir a tabela de alias, mas também que o algoritmo acima para encontrar a altura de não mais que um e emparelhá-lo com um retângulo com uma altura de pelo menos um é sempre bem-sucedido. A partir disso, podemos começar a derivar algoritmos de cálculo de tabela de alias mais e mais complexos.

Geração de tabela de alias

Usando o descrito acima, podemos obter um algoritmo bastante bom para simular arremessos de ossos usando o método de alias. A inicialização consiste na varredura repetida das probabilidades recebidas para encontrar um valor não superior a 1 e um valor de pelo menos 1, seguido pela combinação deles em um par para preencher a coluna:

Algoritmo: Método do Naias Alias

• Inicialização :
  
  1. Multiplique todas as probabilidades $$$p_i$ em $$$n$ .
  2. Criar matrizes $$$Alias ​​$ e $$$Prob$ cada um dos quais tem um tamanho $$$n$ .
  3. Para $$$j = 1 \ mbox {para} n - 1$ :
     
     1. Encontre a probabilidade $$$p_l$ satisfazendo a condição $$$p_l \ le 1$ .
     2. Encontre a probabilidade $$$p_g$ (com $$$l \ ne g$ ) satisfazendo a condição $$$p_g \ ge 1$
     3. Montamos $$$Prob [l] = p_l$ .
     4. Montamos $$$Alias ​​[l] = g$ .
     5. Excluir $$$p_l$ da lista de probabilidades iniciais.
     6. Montamos $$$p_g: = p_g - (1 - p_l)$ .
     
     
  4. Vamos $$$i$ será a última probabilidade restante, que deve ter uma altura de 1.
  5. Montamos $$$Prob [i] = 1$ .
  
  
• Geração :
  
  1. Geramos um rolo ósseo honesto a partir de $$$n$ osso da face; chame o rosto $$$i$ .
  2. Jogue uma moeda assimétrica caindo por uma águia com probabilidade $$$Prob [i]$ .
  3. Se uma águia cair em uma moeda, retorne $$$i$ .
  4. Caso contrário, retorne $$$Alias ​​[i]$ .

A etapa de gerar esse algoritmo é exatamente igual ao método descrito acima e leva tempo $$$\ Teta (1)$ . A etapa de inicialização requer as várias iterações descritas acima. Primeiro, precisamos gastar tempo $$$\ Theta (n)$ escalando cada probabilidade por um fator $$$n$ e passar tempo $$$O (n)$ alocar duas matrizes. O loop interno está em execução $$$\ Theta (n)$ vezes, e a cada iteração o trabalho $$$O (n)$ varrendo a matriz, removendo um dos elementos da matriz e atualizando as probabilidades. Isso nos dá tempo $$$O (n ^ 2)$ inicialização geral. Se considerarmos esse algoritmo no contexto, obtemos o seguinte:

Algoritmo	Tempo de inicialização		Tempo de geração		Memória ocupada
	O melhor	O pior	O melhor	O pior	O melhor	O pior
Osso de honestidade	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Teta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Osso de Schuler de moedas assimétricas	$$$\ Theta (n)$		$$$\ Teta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Seleção de roleta	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
Seleção ideal de roleta	$$$O (n ^ 2)$		$$$\ Teta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$
Honestidade Osso / Moedas Assimétricas	$$$\ Theta (n)$		$$$\ Teta (1)$	$$$\ Theta (n)$ (esperado)	$$$\ Theta (n)$
Método do Naias Alias	$$$O (n ^ 2)$		$$$\ Teta (1)$		$$$\ Theta (n)$

Comparado a outros métodos de simulação eficazes, esse método de alias ingênuo tem altos custos de inicialização, mas pode simular rolos de ossos com extrema eficiência. Se pudéssemos reduzir de alguma forma os custos de inicialização (digamos, para $$$O (n)$ ), esse método seria definitivamente melhor do que todas as técnicas usadas aqui.

Uma maneira simples de reduzir os custos de inicialização é usar uma estrutura de dados mais apropriada para manter as alturas durante a execução. Na versão ingênua, usamos uma matriz não classificada para armazenar todas as probabilidades, ou seja, leva tempo para encontrar as duas probabilidades necessárias $$$O (n)$ . Uma alternativa mais adequada para armazenar valores seria uma árvore de pesquisa binária equilibrada. Nesse caso, podemos encontrar os valores $$$p_g$ e $$$p_l$ a tempo $$$O (\ log n)$ procurando os valores máximo e mínimo da árvore. Excluir $$$p_l$ pode ser feito a tempo $$$O (\ log n)$ e atualização de probabilidade $$$p_g$ também pode ser realizado em $$$O (\ log n)$ devido à sua simples remoção da árvore com subsequente reinserção. Isso nos dá o seguinte algoritmo:

Algoritmo: Método de alias

• Inicialização :
  
  1. Criar matrizes $$$Alias ​​$ e $$$Prob$ cada tamanho $$$n$ .
  2. Crie uma árvore de pesquisa binária equilibrada $$$T$ .
  3. Inserir $$$n \ cdot p_i$ em $$$T$ para toda probabilidade $$$i$ .
  4. Para $$$j = 1 \ mbox {para} n - 1$ :
     
     1. Encontre e exclua o menor valor em $$$T$ ; vamos ligar pra ele $$$p_l$ .
     2. Encontre e exclua o valor mais alto em $$$T$ ; vamos ligar pra ele $$$p_g$ .
     3. Montamos $$$Prob [l] = p_l$ .
     4. Montamos $$$Alias ​​[l] = g$ .
     5. Montamos $$$p_g: = p_g - (1 - p_l)$ .
     6. Adicionar $$$p_g$ para $$$T$ .
     
     
  5. Vamos $$$i$ será a última probabilidade restante, que deve ter um peso de 1.
  6. Montamos $$$Prob [i] = 1$ .
  
  
• Geração :
  
  1. Geramos um rolo ósseo honesto a partir de $$$n$ osso da face; chame o rosto $$$i$ .
  2. Jogamos uma moeda assimétrica na qual a águia cai com probabilidade $$$Prob [i]$ .
  3. Se uma águia cair em uma moeda, retorne $$$i$ .
  4. Caso contrário, retorne $$$Alias ​​[i]$ .

Agora a inicialização do nosso algoritmo é muito mais rápida. Criação $$$Alias ​​$ e $$$Prob$ ainda leva tempo $$$O (n)$ em cada tabela e adicionando probabilidades ao BST $$$T$ leva tempo $$$\ Theta (n \ log n)$ . Em seguida, realizamos $$$\ Theta (n)$ iterações para preencher a tabela, cada uma das quais leva tempo $$$O (\ log n)$ . Isso nos dá o tempo total de inicialização. $$$O (n \ log n)$ :

Algoritmo	Tempo de inicialização		Tempo de geração		Memória ocupada
	O melhor	O pior	O melhor	O pior	O melhor	O pior
Osso de honestidade	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Teta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Osso de Schuler de moedas assimétricas	$$$\ Theta (n)$		$$$\ Teta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Seleção de roleta	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
Seleção ideal de roleta	$$$O (n ^ 2)$		$$$\ Teta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$
Honestidade Osso / Moedas Assimétricas	$$$\ Theta (n)$		$$$\ Teta (1)$	$$$\ Theta (n)$ (esperado)	$$$\ Theta (n)$
Método do Naias Alias	$$$O (n ^ 2)$		$$$\ Teta (1)$		$$$\ Theta (n)$
Método de alias	$$$O (n \ log n)$		$$$\ Teta (1)$		$$$\ Theta (n)$

No entanto, existe um algoritmo que funciona ainda mais rápido. É surpreendentemente simples e provavelmente é o algoritmo mais limpo para implementar o método de alias. Esse algoritmo foi descrito pela primeira vez no artigo “Um algoritmo linear para gerar números aleatórios com uma determinada distribuição”, de Michael Woes, e se tornou o algoritmo padrão para a implementação do método de alias.

O algoritmo Woese baseia-se no uso de duas listas de trabalho: uma contém elementos com altura menor que 1, a outra contém elementos com altura mínima de 1. O algoritmo une constantemente os primeiros elementos de cada lista de trabalho em pares. A cada iteração, consumimos um elemento da lista de valores "pequenos" e potencialmente movemos o restante do elemento da lista de valores "grandes" para a lista de valores "pequenos". Esse algoritmo usa vários invariantes:

• Todos os itens em uma pequena lista de trabalho são menores que 1.
• Todos os elementos da lista de trabalho "grande" são pelo menos 1.
• A soma dos itens na lista de trabalho é sempre igual ao número total de itens.

Para simplificar, cada lista não armazena a probabilidade em si, mas um certo ponteiro para a lista de probabilidades iniciais, que informa em qual face do trapaceiro o link é feito. Tendo esses invariantes, obtemos o seguinte algoritmo:

Algoritmo: (instável) Woes Alias ​​method

Aviso: este algoritmo está sujeito a imprecisões numéricas. Um algoritmo mais numericamente estável é apresentado abaixo.

• Inicialização :
  
  1. Criar matrizes $$$Alias ​​$ e $$$Prob$ cada tamanho $$$n$ .
  2. Crie duas listas de trabalho $$$Pequeno$ e $$$Grande$ .
  3. Multiplique cada probabilidade por $$$n$ .
  4. Para cada probabilidade escalada $$$p_i$ :
     
     1. Se $$$p_i <1$ adicionar $$$i$ para $$$Pequeno$ .
     2. Caso contrário ( $$$p_i \ ge 1$ ) adicionar $$$i$ para $$$Grande$ .
     
     
  5. Tchau lista $$$Pequeno$ não está vazio:
     
     1. Exclua o primeiro item de $$$Pequeno$ ; ligue para ele $$$l$ .
     2. Exclua o primeiro item de $$$Grande$ ; ligue para ele $$$g$ .
     3. Montamos $$$Prob [l] = p_l$ .
     4. Montamos $$$Alias ​​[l] = g$ .
     5. Montamos $$$p_g: = p_g - (1 - p_l)$ .
     6. Se $$$p_g <1$ adicionar $$$g$ em $$$Pequeno$ .
     7. Caso contrário ($ p_g \ ge 1 $), adicionamos $$$g$ em $$$Grande$ .
     
     
  6. Tchau lista $$$Grande$ não está vazio:
     
     1. Exclua o primeiro item de $$$Grande$ ; ligue para ele $$$g$ .
     2. Montamos $$$Prob [g] = 1$ .
     
     
  
  
• Geração :
  
  1. Geramos um rolo ósseo honesto a partir de $$$n$ osso da face; chame o rosto $$$i$ .
  2. Jogamos uma moeda assimétrica na qual a águia cai com probabilidade $$$Prob [i]$ .
  3. Se uma águia cair em uma moeda, retorne $$$i$ .
  4. Caso contrário, retorne $$$Alias ​​[i]$ .

Dadas as três invariantes apresentadas acima, a primeira parte do algoritmo (tudo, exceto o último ciclo) deve ser bastante clara: constantemente emparelhamos algum pequeno elemento de $$$Pequeno$ com um elemento grande de $$$Grande$ e adicione o restante do item grande à lista de trabalho correspondente. O último ciclo do algoritmo requer explicação. Depois de esgotar todos os elementos da lista $$$Pequeno$ na lista $$$Grande$ pelo menos um elemento permanecerá (desde que cada elemento fosse $$$Pequeno$ , a soma dos elementos deve ter se tornado menor que o número de elementos restantes, o que viola as condições da última invariante). Uma vez que cada elmenrt $$$Grande$ não inferior a 1, e a quantidade $$$k$ itens em $$$Grande$ deve ser igual $$$k$ então cada elemento $$$Grande$ deve ser igual a 1, porque, caso contrário, o valor total será muito grande. Portanto, este último ciclo define a probabilidade de cada elemento grande como 1, de modo que todas as colunas que contêm o elemento grande sejam iguais a 1.

Nesse algoritmo, o tipo de lista de trabalho não é importante. No artigo original do Woof, as pilhas são usadas como uma lista de trabalho, porque podem ser efetivamente implementadas usando matrizes, mas, se quisermos, podemos usar a fila. No entanto, para simplificar, usaremos a pilha.

Antes de prosseguir com a análise do algoritmo, vamos analisar sua operação usando um exemplo. Considere um exemplo usando sete probabilidades $$$\ frac {1} {4}$ , $$$\ frac {1} {5}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ . Para enfatizar o fato de o algoritmo não classificar probabilidades e não exigir sua classificação, vamos organizá-las em ordem aleatória $$$\ frac {1} {8}$ , $$$\ frac {1} {5}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {4}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {8}$ . O algoritmo começa adicionando esses elementos a duas pilhas de trabalho:


Agora vamos colocar o topo da pilha $$$Pequeno$ em sua posição, movendo o retângulo roxo para sua posição final:


Agora usamos o topo da pilha $$$Grande$ (retângulo turquesa) para preencher o restante da coluna. Desde $$$\ frac {7} {4} - \ frac {1} {8} = \ frac {13} {8} \ ge 1$ deixamos o bloco turquesa no topo da pilha $$$Grande$ :


Então repetimos esse processo. Mova o retângulo da parte superior da pilha $$$Pequeno$ na coluna e, em seguida, complemente o topo da pilha que está faltando $$$Grande$ :


E novamente:


Na próxima vez que repetirmos esse processo, descobrimos que, embora possamos usar o bloco turquesa para preencher o espaço vazio da tabela, como resultado, a altura do bloco turquesa será menor que uma. Portanto, precisaremos mover o bloco turquesa para o topo da pilha de pequenos valores:


Agora, ao processar a lista $$$Pequeno$ , :


$$$Small$ , , :


, $$$Small$ , .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$ $$$Large$ , . , , $$$n$ , , $$$\frac{1}{n}$ , $$$1$ ( $$$Small$ , $$$Large$ )
2. , , . , , $$$Large$ , $$$Small$ .

, $$$Small$ $$$Large$ . , , $$$Small$ , $$$Large$ .

, . , , , $$$Large$ . -, , $$$1$ , , $$$1$ . , . :

: Alias-

• :
  
  1. $$$Alias$ e $$$Prob$ , $$$n$ .
  2. , $$$Small$ e $$$Large$ .
  3. $$$n$ .
  4. $$$p_i$ :
     
     1. Se $$$p_i < 1$ , $$$i$ em $$$Small$ .
     2. ( $$$p_i \ge 1$ ) $$$i$ em $$$Large$ .
     
     
  5. $$$Small$ e $$$Large$ : ( $$$Large$ )
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Large$ ; $$$g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := (p_g + p_l) - 1$ . ( . )
     6. Se $$$p_g < 1$ , $$$g$ em $$$Small$ .
     7. ( $$$p_g \ge 1$ ) $$$g$ em $$$Large$ .
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$g$ .
     2. $$$Prob[g] = 1$ .
     
     
  7. $$$Small$ : - .
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Prob[l] = 1$ .
     
     
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

, — . $$$\Theta(n)$ , . $$$\Theta(1)$ , , . $$$O (n)$ , () , . $$$O (n)$ , $$$Large$ e $$$Small$ $$$O (n)$ . $$$\Theta(n)$ , ( ) :

Algoritmo
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !