Estrutura de dados para dados carregados?

Suponha que eu tenha um dado carregado em frente e verso, em que cada lado k tenha alguma probabilidade _pk de aparecer quando eu o enrolar. Estou curioso para saber se existe um bom algoritmo para armazenar essas informações estaticamente (ou seja, para um conjunto fixo de probabilidades), para que eu possa simular com eficiência um teste aleatório do dado.

Atualmente, tenho uma solução O (lg n) para esse problema. A idéia é armazenar uma tabela da probabilidade cumulativa dos primeiros k lados para todos os k, para gerar um número real aleatório no intervalo [0, 1) e realizar uma pesquisa binária sobre a tabela para obter o maior índice acumulado O valor não é maior que o valor escolhido. Eu gosto bastante dessa solução, mas parece estranho que o tempo de execução não leve em conta as probabilidades. Em particular, nos casos extremos de um lado sempre aparecendo ou com os valores distribuídos uniformemente, é possível gerar o resultado do rolo em O (1) usando uma abordagem ingênua, embora minha solução ainda tome muitas etapas logarítmicas.

Alguém tem alguma sugestão de como resolver esse problema de uma forma que seja "adaptável" em seu tempo de execução?

EDIT : Com base nas respostas a esta pergunta, escrevi um artigo descrevendo muitas abordagens para esse problema , juntamente com suas análises. Parece que a implementação do método alias por Vose fornece Θ (n) tempo de pré-processamento e O (1) tempo por rolo de matriz, o que é realmente impressionante. Espero que este seja um complemento útil para as informações contidas nas respostas!

Você está procurando o método alternativo que fornece um método O (1) para gerar uma distribuição de probabilidade discreta fixa (supondo que você possa acessar entradas em uma matriz de comprimento n em tempo constante) com uma configuração única de O (n) . Você pode encontrá-lo documentado no capítulo 3 (PDF) de "Geração aleatória não uniforme de variáveis", de Luc Devroye.

A ideia é levar o seu leque de probabilidades p _k e produzir três novos conjuntos de n elementos, q _k , um _k , e b _k . Cada q _k é uma probabilidade entre 0 e 1, e cada a _k e b _k é um número inteiro entre 1 e n.

Geramos números aleatórios entre 1 e n, gerando dois números aleatórios, r e s, entre 0 e 1. Seja i = floor (r * N) +1. Se q _i <s, então retorne a _i else retorne b _i . O trabalho no método alias consiste em descobrir como produzir q _k , a _k e b _k .

Use uma árvore de pesquisa binária balanceada (ou pesquisa binária em uma matriz) e obtenha complexidade O (log n). Tenha um nó para cada resultado do dado e faça com que as chaves sejam o intervalo que acionará esse resultado.

function get_result(node, seed):
    if seed < node.interval.start:
        return get_result(node.left_child, seed)
    else if seed < node.interval.end:
        // start <= seed < end
        return node.result
    else:
        return get_result(node.right_child, seed)

A coisa boa dessa solução é que é muito simples de implementar, mas ainda tem boa complexidade.

Estou pensando em granular sua mesa.

Em vez de ter uma tabela com o acumulado para cada valor da matriz, você pode criar uma matriz inteira de comprimento xN, onde x é idealmente um número alto para aumentar a precisão da probabilidade.

Preencha essa matriz usando o índice (normalizado por xN) como valor cumulativo e, em cada 'slot' na matriz, armazene os dados em potencial se esse índice aparecer.

Talvez eu possa explicar mais facilmente com um exemplo:

Usando três dados: P (1) = 0,2, P (2) = 0,5, P (3) = 0,3

Crie uma matriz, neste caso, escolherei um comprimento simples, digamos 10. (ou seja, x = 3,33333)

arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3

Em seguida, para obter a probabilidade, escolha um número aleatório entre 0 e 10 e simplesmente acesse esse índice.

Esse método pode perder a precisão, mas o aumento x e a precisão serão suficientes.

Existem várias maneiras de gerar um número inteiro aleatório com uma distribuição personalizada (também conhecida como distribuição discreta ). A escolha depende de muitas coisas, incluindo o número de números inteiros para escolher, o formato da distribuição e se a distribuição será alterada ao longo do tempo.

Uma das maneiras mais simples de escolher um número inteiro com uma função de peso personalizada f(x)é o método de amostragem por rejeição . O seguinte pressupõe que o maior valor possível de fé max. A complexidade do tempo para amostragem de rejeição é constante, em média, mas depende muito da forma da distribuição e tem o pior caso de execução para sempre. Para escolher um número inteiro em [1, k] usando a amostragem por rejeição:

1. Escolha um número inteiro aleatório uniforme iem [1, k].
2. Com probabilidade f(i)/max, retorne i. Caso contrário, vá para a etapa 1.

Outros algoritmos têm um tempo médio de amostragem que não depende muito da distribuição (geralmente constante ou logarítmica), mas geralmente exige que você pré-calcule os pesos em uma etapa de configuração e os armazene em uma estrutura de dados. Alguns deles também são econômicos em termos do número de bits aleatórios que usam em média. Muitos desses algoritmos foram introduzidos após 2011 e incluem:

• a estrutura sucinta de dados de Bringmann – Larsen ("Amostra sucinta de distribuições discretas", 2012),
• Pesquisa em vários níveis de Yunpeng Tang ("Um estudo empírico de métodos de amostragem aleatória para alterar distribuições discretas", 2019) e
• o rolo de dados de carregamento rápido (2020).

Outros algoritmos incluem o método de alias (já mencionado em seu artigo), o algoritmo Knuth – Yao, a estrutura de dados MVN e muito mais. Veja minha seção " Uma observação sobre algoritmos de escolha ponderada " para uma pesquisa.