algorithm - Estructura de datos para dados cargados?

language-agnostic data-structures

Question

Supongamos que tengo un dado cargado con n lados, donde cada lado k tiene cierta probabilidad p _k de aparecer cuando lo enrollo. Tengo curiosidad de 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 manera 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 "adaptativa" en su tiempo de ejecución?

EDITAR : En base a las respuestas a esta pregunta, he escrito un artículo que describe muchos enfoques de este problema , junto con sus análisis. Parece que la implementación de Vose del método de alias proporciona Θ (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

Está buscando el método de alias que proporciona un método O (1) para generar una distribución de probabilidad discreta fija (suponiendo que puede acceder a entradas en una matriz de longitud n en tiempo constante) con una configuración O (n) única. . Puede encontrarlo documentado en el capítulo 3 (PDF) de "Generación de Variedades Aleatorias No Uniformes" por Luc Devroye.

La idea es tomar su matriz de probabilidades p _k y producir tres nuevas matrices de n elementos, q _k , a _k y b _k . Cada q _k es una probabilidad entre 0 y 1, y cada a _k y b _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, entonces devuelve un _i else devuelve b _i . El trabajo en el método de alias consiste en descubrir cómo producir q _k , a _k y b _k .

Answer 2

Estoy pensando en granular tu mesa.

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

Llene 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 elegiré una longitud simple, por ejemplo 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, para obtener la probabilidad, simplemente aleatorice un número entre 0 y 10 y simplemente acceda 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.