Como gerar números com base em uma distribuição discreta arbitrária?

Como faço para gerar números com base em uma distribuição discreta arbitrária?

Por exemplo, eu tenho um conjunto de números que quero gerar. Digamos que eles sejam rotulados de 1 a 3 da seguinte maneira.

1: 4%, 2: 50%, 3: 46%

Basicamente, as porcentagens são probabilidades de que elas aparecerão na saída do gerador de números aleatórios. Eu tenho um gerador de números aleatórios que gerará uma distribuição uniforme no intervalo [0, 1]. Existe alguma maneira de fazer isso?

Não há limites para quantos elementos posso ter, mas o% adicionará até 100%.

Um dos melhores algoritmos para amostragem de uma distribuição discreta é o método de alias .

O método de alias (eficientemente) pré-computa uma estrutura de dados bidimensional para particionar um retângulo em áreas proporcionais às probabilidades.

Neste esquema do local referenciado, um rectângulo de altura unidade foi dividida em quatro tipos de regiões - como diferenciadas pela cor - nas proporções , 1 / 3 , 1 / 12 , e 1 / 12 , em para amostrar repetidamente a partir de uma distribuição discreta com essas probabilidades. As faixas verticais têm uma largura (unidade) constante. Cada um é dividido em apenas uma ou duas peças. As identidades das peças e os locais das divisões verticais são armazenados em tabelas acessíveis através do índice da coluna.$1/2$$1/3$$1/12$$1/12$

A tabela pode ser amostrada em duas etapas simples (uma para cada coordenada), exigindo a geração de apenas dois valores uniformes independentes e cálculo de O ( 1 ) . Isso melhora a computação O ( log ( n ) ) necessária para inverter o CDF discreto, conforme descrito em outras respostas aqui.$O(1)$$O(\log(n))$

Você pode fazer isso facilmente no R, basta especificar o tamanho necessário:

sample(x=c(1,2,3), size=1000, replace=TRUE, prob=c(.04,.50,.46))

No seu exemplo, digamos que você desenhe seu valor pseudoaleatório Uniforme [0,1] e chame-o de U. Em seguida, imprima:

1 se U <0,04

2 se U> = 0,04 e U <0,54

3 se U> = 0,54

Se o% especificado for a, b, ..., basta imprimir

valor 1 se U

valor 2 se U> = ae U <(a + b)

etc.

Essencialmente, estamos mapeando a% em subconjuntos de [0,1], e sabemos que a probabilidade de um valor aleatório uniforme cair em qualquer intervalo é simplesmente o comprimento desse intervalo. Colocar os intervalos em ordem parece a maneira mais simples, se não única, de fazê-lo. Isso pressupõe que você esteja perguntando apenas sobre distribuições discretas; para contínuo, pode fazer algo como "amostragem por rejeição" ( entrada da Wikipedia ).

Suponha que existem possíveis resultados discretos. Você divide o intervalo [ 0 , 1 ] em subintervalos com base na função de massa de probabilidade cumulativa, F , para fornecer o intervalo particionado ( 0 , 1 $m$$[0,1]$$F$$(0,1)$

onde e F ( 0 ) ≡ 0 . No seu exemplo m = 3 e$I_{j} = (F(j-1), F(j))$$F(0) \equiv 0$$m = 3$

Como e F ( 2 ) = 0,54 e F ( 3 ) = 1 .$F(1) = .04$$F(2) = .54$$F(3) = 1$

Em seguida, você pode gerar com a distribuição F usando o seguinte algoritmo:$X$$F$

(1) gerar $U \sim {\rm Uniform}(0,1)$

(2) Se , então X = j .$U \in I_{j}$$X = j$

• Esta etapa pode ser realizada examinando se é menor que cada uma das probabilidades cumulativas e vendo onde ocorre o ponto de mudança (de para ), o que deve ser uma questão de usar um operador booleano em qualquer linguagem de programação usada e descobrindo onde o primeiro ocorre no vetor.$U$TRUEFALSEFALSE

Observe que estará exatamente em um dos intervalos I j, pois eles são disjuntos e particionam [ 0 , 1 ] .$U$$I_{j}$$[0,1]$

Um algoritmo simples é começar com seu número aleatório uniforme e, em um loop, subtrair primeiro a primeira probabilidade; se o resultado for negativo, você retornará o primeiro valor; se ainda positivo, passará para a próxima iteração e subtrairá a próxima probabilidade. , verifique se negativo, etc.

Isso é bom porque o número de valores / probabilidades pode ser infinito, mas você só precisa calcular as probabilidades quando se aproximar desses números (para algo como gerar a partir de uma distribuição binomial de Poisson ou negativa).

Se você tiver um conjunto finito de probabilidades, mas gerar muitos números a partir deles, poderá ser mais eficiente classificar as probabilidades para subtrair a maior primeiro, depois a segunda maior a seguir e assim por diante.

Antes de tudo, deixe-me chamar sua atenção para uma biblioteca python com classes prontas para uso, para geração de número aleatório inteiro ou de ponto flutuante que segue a distribuição arbitrária.

De um modo geral, existem várias abordagens para esse problema. Alguns são lineares no tempo, mas requerem grande armazenamento de memória, outros são executados no tempo O (n log (n)). Alguns são otimizados para números inteiros e outros são definidos para histogramas circulares (por exemplo: gerar pontos de tempo aleatórios durante um dia). Na biblioteca acima mencionada, usei este artigo para casos com números inteiros e esta receita para números de ponto flutuante. (Ainda) não possui suporte circular ao histograma e geralmente é confuso, mas funciona bem.

Eu tive o mesmo problema. Dado um conjunto em que cada item tem uma probabilidade e cujas probabilidades somam um, eu queria desenhar uma amostra com eficiência, ou seja, sem classificar nada e sem repetir a iteração sobre o conjunto .

A função a seguir desenha o menor de números aleatórios distribuídos uniformemente dentro do intervalo [ a , 1 ) . Seja r um número aleatório entre [ 0 , 1 ) .$N$$[a,1)$$r$$[0,1)$

$(a_i)$$N$$N = 10$

a 1 = próximo ( 9 , a $a_0 = \text{next}(10, 0)$
$a_1 = \text{next}(9, a_0)$
$a_2 = \text{next}(8, a_1)$
$\dots$
$a_9 = \text{next}(1, a_8)$

$(a_i)$$P$$0 \leq k < |P|$$p_k \in P$$a_i$$k$$\sum p_0 \dots p_k > a_i$$p_k$$a_{i+1}$

$\{(1, 0.04), (2, 0.5), (3, 0.46)\}$$N = 10$

i a_i k Sorteio
0 0,031 0 0,04 1
1 0,200 1 0,54 2
2 0,236 1 0,54 2
3 0,402 1 0,54 2
4 0,488 1 0,54 2
5 0,589 2 1,0 3
6 0,625 2 1,0 3
7 0,638 2 1,0 3
8 0,738 2 1,0 3
9 0,942 2 1,0 3

Amostra: $(1, 2, 2, 2, 2, 3, 3, 3, 3, 3)$

$\text{next}$$N$$[a, x)$$x \leq 1$