Cómo hacer una selección aleatoria ponderada discreta en tiempo constante

Creo que la solución ‘clásica’ a este problema sería usar una búsqueda binaria en tiempo O (logN) mientras se almacena la distribución acumulativa, usando memoria O (n). Puedo dar más detalles si es necesario, pero esto debería estar disponible en Internet en algún lugar.

Si realmente necesita tiempo constante (n debe ser bastante grande y / o debe estar haciendo MUCHAS consultas / simulaciones de desplazamiento), puede aumentar la memoria para acelerar la consulta. Digamos, tenga una matriz de tamaño M, y para cada valor j entre [0, M [precalcule el ‘rollo’ para la probabilidad 1 / j. Tenga en cuenta que es posible que M tenga que ser bastante grande si desea representar con precisión su distribución.

Sin embargo, en la práctica, casi siempre es mejor seguir el enfoque logN y, si es necesario, precalcule una gran cantidad de rollos aleatorios durante la noche, paralelícelo o comprométase con un valor menor de M (por ejemplo, 10000, distorsionando potencialmente su distribución de probabilidad pero necesita poca memoria).

La solución más elegante que conozco es construir un árbol Huffman para su distribución.

Editar: ¡el método al que se hace referencia en los comentarios de las preguntas es mucho más rápido y mejor! Aquí va de todos modos.

El número esperado de pasos para simularlo se encuentra dentro de uno de la entropía de la distribución. Esto nunca es más, y potencialmente mucho menos que el registro de la cantidad de resultados, que es el tiempo que necesita si realiza una búsqueda binaria en el cdf.

Como es habitual en un árbol Huffman, los resultados están en las hojas del árbol, y cada resultado está asociado con su probabilidad. Para esta aplicación, también necesitamos pesos de probabilidad en cada nodo interno del árbol: es decir, la suma de los pesos de sus hijos. Entonces, el nodo raíz obtiene el peso 1. (Normalmente, estos pesos de los nodos internos se mantienen durante la construcción del árbol Huffman de todos modos).

Aquí hay un seudocódigo para simular desde el árbol:

Seamos uniformemente aleatorios en [0,1].
Deje n señalar la raíz del árbol Huffman.
mientras n no es una hoja:
dejar w = peso (left_child (n))
si w establecer u = uw
conjunto n = right_child (n)
más
conjunto n = left_child (n)
terminara si
terminar mientras
resultado: resultado almacenado en la hoja n

El árbol Huffman es el árbol binario óptimo para este problema: producirá un resultado después del menor número de pasos en promedio.