Gerar com precisão variáveis ​​a partir da distribuição discreta da lei de energia

Quais são os melhores métodos para gerar com precisão números inteiros aleatórios distribuídos de acordo com uma lei de energia? A probabilidade de obter ( k = 1 , 2 , … ) deve ser igual a p k = k - γ / ζ ( γ ) e o método deve funcionar bem para qualquer γ > 1 .$k$$k=1,2,\ldots$$p_k = k^{-\gamma} / \zeta(\gamma)$$\gamma > 1$

Eu posso ver duas abordagens ingênuas:

1. Calcular até alguns grande k max para que Σ k max K = 1 é "suficientemente perto" para 1, em seguida, gerar números inteiros de acordo com estas probabilidades. Isso simplesmente não funcionará se γ for próximo de 1, pois k max precisaria ser enorme.$p_k$$k_\text{max}$$\sum_{k=1}^{k_\text{max}}$$\gamma$$k_\text{max}$

2. Desenhe números reais de uma distribuição contínua da lei de energia (um problema mais fácil que eu sei resolver) e arredonde-os para números inteiros de alguma maneira. É possível calcular analiticamente a probabilidade precisa de obter cada número inteiro com o método acima. I podem utilizar rejeição para corrigir estes para (que também pode ser calculado sempre que possa avaliar o ζ função). (Isso seria um pouco complicado, pois eu teria que arredondar de forma a obter números inteiros com maior probabilidade que p k para k maior que algum valor pequeno e manipular k menos que isso separadamente.)$p_k$$\zeta$$p_k$$k$$k$

Existe um método melhor que também seja preciso (não aproximado)?

Eu acho que (uma versão ligeiramente modificada) do método 2 é bem direto, na verdade

Usando a definição da função de distribuição Pareto dada na Wikipedia

se você tomar eα=γentão a razão depxparaqx=FX(x+$x_m=\frac{1}{2}$$\alpha=\gamma$$p_x$$q_x=F_X(x+\frac{1}{2})-F_X(x-\frac{1}{2})$$x=1$$x=1$

$x_m=\frac{1}{2}$$\alpha=\gamma$$M = p_1/q_1$$x$$\frac{p_x}{Mq_x}$

$M$

$x_m$$\alpha$$\alpha=\gamma-a$$a$

$\gamma$

O método 1 também pode ser adaptado para ser exato, executando o método 1 quase sempre e aplicando outro método para lidar com a cauda. Isso pode ser feito de maneiras que podem ser muito rápidas.

$\lfloor 256 p_1\rfloor$1$\lfloor 256 p_2\rfloor$2$256 p_i <1$

O remanescente esquerdo pode ser feito por várias abordagens (mesmo com, digamos, 'esquadrando o histograma' se for automatizado, mas não precisa ser tão eficiente quanto isso), e a cauda direita pode ser feita usando algo como a abordagem de aceitação / rejeição acima.

O algoritmo básico envolve a geração de um número inteiro de 1 a 256 (o que requer apenas 8 bits da rng; se a eficiência é primordial, as operações de bits podem tirar aqueles 'fora do topo', deixando o restante do número uniforme (seria melhor esquerda como um valor inteiro não normalizado até este ponto) capaz de ser usado para lidar com o remanescente esquerdo e a cauda direita, se necessário.

$2^k$$2^{16}$

No mesmo exemplo zeta (2) que acima, você teria 212 1, 26 2, 7 3, 3 4, 1 5e os valores de 250-256 lidariam com o restante. Mais de 97% do tempo você gera um dos valores na tabela (1-5).

$y$

Outras abordagens aproximadas para gerar números inteiros, como arredondar para baixo (truncar) o valor de y, fornecem resultados substancialmente piores e não devem ser usadas.

$r \in [0,1)$$x= P^{-1}(1-r)$$P(x) = \sum_{a=x}^\infty P(X=a)$$P(x)$$P(x) = 1-r$