Estructura de datos para dados cargados?

Question

Supongamos que tengo un dado cargado por n lados en el que cada lado k tiene cierta probabilidad de p _k que aparece cuando lo enrollo. Tengo curiosidad por saber si hay un buen algoritmo para almacenar esta información de forma estática (es decir, para un conjunto fijo de probabilidades), de manera que pueda simular de forma eficiente una tirada aleatoria del dado.

Actualmente, tengo una solución O (lg n) para este problema. La idea es almacenar una tabla de la probabilidad acumulada de los primeros k lados para todos los k, generar un número real aleatorio en el rango [0, 1) y realizar una búsqueda binaria sobre la tabla para obtener el índice más grande cuyo acumulativo el valor no es mayor que el valor elegido. Me gusta bastante esta solución, pero parece extraño que el tiempo de ejecución no tenga en cuenta las probabilidades. En particular, en los casos extremos de un lado siempre subiendo o los valores se distribuyen uniformemente, es posible generar el resultado de la tirada en O (1) usando un enfoque ingenuo, aunque mi solución todavía tomará muchos pasos logarítmicos.

¿Alguien tiene alguna sugerencia sobre cómo resolver este problema de una manera que de alguna manera es "adaptable" en su tiempo de ejecución?

EDITAR: Sobre la base de las respuestas a esta pregunta, he redactado an article describing many approaches to this problem, junto con sus análisis. Parece que la implementación de Vose del método de alias da Θ (n) tiempo de preprocesamiento y O (1) tiempo por tirada de dado, lo cual es realmente impresionante. ¡Espero que esto sea una adición útil a la información contenida en las respuestas!

Answer 1

Usted está buscando el alias method que proporciona un O (1) método para generar una distribución de probabilidad discreta fijo (suponiendo que se puede acceder a las entradas en una matriz de longitud n en tiempo constante) con una O de una sola vez (n) configuración. Puede encontrarlo documentado en chapter 3 (PDF) de "Non-Uniform Random Variate Generation" por Luc Devroye.

La idea es tomar su matriz de probabilidades p _k y producir tres nuevos arrays n-elemento, q _k, un _k, y b _k. Cada q _k es una probabilidad entre 0 y 1, y cada uno es _k yb _k es un número entero entre 1 y n.

Generamos números aleatorios entre 1 y n generando dos números aleatorios, rys, entre 0 y 1. Deje i = piso (r * N) +1. Si q _i < s, devuelva un _i else return b _i. El trabajo en el método de alias consiste en descubrir cómo producir q _k, _{k yb k.}

Answer 2

Estoy pensando en granular su mesa.

En lugar de tener una tabla con el acumulado para cada valor de matriz, puede crear una matriz entera de longitud xN, donde x es idealmente un número alto para aumentar la precisión de la probabilidad.

Complete esta matriz usando el índice (normalizado por xN) como el valor acumulado y, en cada "ranura" de la matriz, almacene la tirada de dados si aparece este índice.

Tal vez podría explicar más fácil con un ejemplo:

Usando tres dados: P (1) = 0.2, P (2) = 0.5, P (3) = 0,3

Crear una matriz, en este caso voy a elegir una longitud sencilla, digamos 10. (es decir, 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 

Luego de obtener la probabilidad, simplemente selecciona aleatoriamente un número entre 0 y 10, y simplemente acceder a ese índice.

Este método puede perder precisión, pero aumentar xy la precisión será suficiente.

Answer 3

Utilice un árbol de búsqueda binaria equilibrada (o búsqueda binaria en una matriz) y obtenga la complejidad O (log n). Tener un nodo para cada resultado del dado y tener las claves en el intervalo que desencadenará ese 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) 

Lo bueno de esta solución es que es muy simple de implementar pero aún tiene una buena complejidad.