Dardos, dados y monedas: algoritmos de distribución discreta

Una vez le hice una pregunta a Stack Overflow sobre la estructura de datos para hacer trampa en los dados . En particular, estaba interesado en la respuesta a esta pregunta: “Si tenemos un hueso n-facet, cuya cara tengo una probabilidad de caerse p _i . ¿Cuál es la estructura de datos más efectiva para simular los rollos de un hueso así?

Esta estructura de datos se puede usar para muchas tareas. Por ejemplo, puede usarlo para simular tiradas hexadecimales honestas, asignando probabilidad $$$\ frac {1} {6}$ cada lado del hueso, o para simular una moneda justa imitando un hueso bilateral, la probabilidad de que se caiga de cada lado es igual a $$$\ frac {1} {2}$ . También puede usar esta estructura de datos para simular directamente la suma de dos huesos hexagonales honestos creando un hueso de 11 lados (con caras 2, 3, 4, ..., 12), cada una de las cuales tiene un peso de probabilidad correspondiente a los rollos de dos huesos honestos. Sin embargo, también puede usar esta estructura de datos para simular huesos de trampa. Por ejemplo, si juegas a los dados con un hueso, que, como sabes, no es completamente honesto, entonces puedes usar esta estructura de datos para simular muchos rollos de hueso y analizar la estrategia óptima. También puede intentar simular una rueda de ruleta igualmente imperfecta.

Si va más allá de los juegos, puede aplicar esta estructura de datos en la simulación de robots cuyos sensores tienen niveles de falla conocidos. Por ejemplo, si un sensor de rango tiene un 95% de probabilidad de devolver el valor correcto, un 4% de probabilidad de un valor demasiado pequeño y un 1% de probabilidad de un valor demasiado alto, entonces puede usar esta estructura de datos para simular la lectura de lecturas del sensor generando un resultado aleatorio y simulando la lectura del sensor resultado.

La respuesta que recibí en Stack Overflow me impresionó por dos razones. En primer lugar, en la solución se me recomendó utilizar una técnica poderosa llamada método alias , que, con ciertas suposiciones razonables sobre el modelo de la máquina, es capaz, después de una simple etapa de preparación preliminar, de simular rollos óseos con el tiempo $$$O (1)$ . En segundo lugar, me sorprendió aún más que este algoritmo se conociera desde hace décadas, ¡pero nunca lo he conocido! Dado el tiempo computacional que se dedica a la simulación, uno esperaría que esta técnica sea mucho más ampliamente conocida. Unas pocas consultas en Google me dieron mucha información sobre esta técnica, pero no pude encontrar un solo sitio donde se uniera una comprensión intuitiva y una explicación de esta técnica.

Este artículo es mi intento de dar una breve descripción de los diferentes enfoques para simular el engaño óseo, desde técnicas simples y poco prácticas hasta un método de alias muy optimizado y efectivo. Espero poder transmitir varias formas de comprender intuitivamente la tarea y cómo cada una de ellas enfatiza algún aspecto nuevo de simular un hueso tramposo. Mi objetivo para cada enfoque es estudiar una idea motivadora, un algoritmo básico, prueba de fidelidad y análisis del tiempo de ejecución (en términos de tiempo requerido, memoria y aleatoriedad).

Entrada

Antes de pasar a los detalles específicos de las diversas técnicas, primero estandaricemos la terminología y la notación.

En la introducción del artículo, utilicé el término "hueso de engaño" para describir un escenario generalizado en el que hay un conjunto finito de resultados, cada uno de los cuales tiene una probabilidad. Formalmente, esto se denomina distribución de probabilidad discreta , y la tarea de simular un hueso de engaño se llama muestreo de una distribución discreta .

Para describir nuestra distribución de probabilidad discreta (hueso tramposo), asumiremos que tenemos un conjunto de n probabilidades $$$p_0, p_1, ..., p_ {n - 1}$ relacionado con los resultados $$$0, 1, ..., n - 1$ . Aunque los resultados pueden ser cualquiera (águila / cruz, números en huesos, colores, etc.), por simplicidad consideraré el resultado como algún tipo de número real positivo correspondiente a un índice dado.

Trabajar con números reales en una computadora es el "área gris" de la informática. Hay muchos algoritmos rápidos, cuya velocidad se proporciona únicamente por la capacidad de calcular la función de piso de un número real arbitrario en un tiempo constante, y las imprecisiones numéricas en la representación de números de coma flotante pueden destruir completamente algunos algoritmos. Por lo tanto, antes de comenzar cualquier discusión sobre algoritmos que funcionan con probabilidades, es decir, al ingresar al mundo oscuro de los números reales, debo aclarar lo que una computadora puede y no puede hacer.

De aquí en adelante, asumiré que todas las siguientes operaciones se pueden realizar en tiempo constante:

• Además resta, multiplicación, división y comparación de números reales arbitrarios . Tendremos que hacer esto para manipular las probabilidades. Esto puede parecer una suposición audaz, pero si suponemos que la precisión de cualquier número real está limitada por algún polinomio del tamaño de palabra de la máquina (por ejemplo, un doble de 64 bits en una máquina de 32 bits), pero no creo que sea demasiado irrazonable.
• Generación de un número real uniforme en el intervalo [0, 1). Para simular aleatoriedad, necesitamos alguna fuente de valores aleatorios. Supongo que podemos generar un número real de precisión arbitraria en tiempo constante. Esto supera con creces las capacidades de una computadora real, pero me parece que para los propósitos de esta discusión esto es aceptable. Si aceptamos sacrificar una fracción de la precisión al decir que un doble IEEE-754 arbitrario está en el intervalo [0, 1], entonces realmente perderemos precisión, pero el resultado probablemente será lo suficientemente preciso para la mayoría de las aplicaciones.
• Cálculo del piso entero (redondeando hacia abajo) de un número real. Esto es aceptable si suponemos que estamos trabajando con IEEE-754 doble, pero en general, tal requisito para una computadora no es factible.

Vale la pena hacer la pregunta: ¿es razonable suponer que podemos llevar a cabo todas estas operaciones de manera efectiva? En la práctica, raramente usamos probabilidades indicadas con un nivel de precisión tal que el error de redondeo inherente en el IEEE-754 doble pueda causar serios problemas, por lo que podemos cumplir con todos los requisitos anteriores simplemente trabajando exclusivamente con IEEE doble. Sin embargo, si estamos en un ambiente donde la probabilidad indica con precisión cómo racional número de alta precisión, restricciones similares pueden ser irrazonable.

Simulación ósea honesta

Antes de pasar al caso más general de lanzar un hueso de engaño arbitrario, comencemos con un algoritmo más simple que servirá como un bloque de construcción para los siguientes algoritmos: simular un hueso honesto con cara n. Por ejemplo, los dados hexagonales honestos al jugar Monopolio o Riesgo, o lanzar una moneda honesta (dados de doble cara), etc. pueden ser útiles para nosotros.

Para este caso particular, existe un algoritmo simple, elegante y efectivo para simular el resultado. El algoritmo se basa en la siguiente idea: supongamos que podemos generar números reales realmente aleatorios, distribuidos uniformemente en el intervalo $$$[0, 1)$ . Este intervalo puede ilustrarse de la siguiente manera:


Ahora si queremos renunciar $$$n$ hueso facetado, entonces una forma es dividir el intervalo $$$[0, 1)$ en $$$n$ áreas de igual tamaño, cada una de las cuales tiene una longitud $$$\ frac {1} {n}$ . Se ve así:


A continuación, generamos un número real elegido al azar en el intervalo $$$[0, 1)$ eso seguramente cae en una de estas pequeñas áreas. A partir de esto, podemos calcular el resultado del giro del hueso al observar el área en la que cayó el número. Por ejemplo, si nuestro valor seleccionado al azar cayó en este lugar:


entonces podemos decir que 2 cayeron sobre el hueso (si suponemos que los bordes del hueso están indexados desde cero).

Es gráficamente fácil ver qué región tiene un valor aleatorio, pero ¿cómo codificamos esto en un algoritmo? Y aquí aprovechamos el hecho de que este es un hueso honesto. Dado que todos los intervalos son del mismo tamaño, a saber $$$\ frac {1} {n}$ , entonces podemos ver cuál es el mayor valor $$$i$ es tal que $$$\ frac {i} {n}$ no más que un valor generado aleatoriamente (llamemos a este valor x). Puede notar que si queremos encontrar el valor máximo, tal que $$$\ frac {i} {n} \ le x$ , entonces esto es similar a encontrar el valor máximo $$$n$ tal que $$$i \ le xn$ . Pero esto, por definición, significa que $$$i = \ lfloor xn \ rfloor$ , el entero positivo más grande no es mayor que xn. Por lo tanto, esto nos lleva a este algoritmo de simulación ósea honesto (muy simple) honesto:

Algoritmo: simulación ósea honesta

1. Generar un valor aleatorio distribuido uniformemente $$$x$ en el rango $$$[0, 1)$ .
2. Volver $$$\ lfloor xn \ rfloor$ .

Dados nuestros supuestos anteriores sobre los cálculos, este algoritmo se ejecuta a tiempo $$$O (1)$ .

Se pueden sacar dos conclusiones de esta sección. Primero, podemos dividir el intervalo $$$[0, 1)$ en parte para que un número real aleatorio distribuido uniformemente en este intervalo se reduzca naturalmente a una de las muchas opciones discretas disponibles para nosotros. En el resto de este artículo, explotaremos activamente esta técnica. En segundo lugar, puede ser difícil determinar a qué intervalo específico pertenece un valor aleatorio, pero si sabemos algo sobre las partes (en este caso, que todas tienen el mismo tamaño), matemáticamente podemos determinar qué parte se refiere a un determinado punto.

Hacer trampa simulación ósea con hueso honesto

Con un algoritmo honesto de simulación ósea, ¿podemos adaptarlo para simular un hueso tramposo? Curiosamente, la respuesta es sí, pero una solución requerirá más espacio.

De la sección anterior, es intuitivamente claro que para simular un tiro de hueso de engaño, es suficiente dividir el intervalo $$$[0, 1)$ en pedazos, y luego determinar qué parte golpeamos. Sin embargo, en el caso general, esto puede ser mucho más complicado de lo que parece. Digamos que tenemos un tetraedro con probabilidades faciales. $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ y $$$\ frac {1} {12}$ (podemos asegurarnos de que esta sea la distribución de probabilidad correcta, porque $$$\ frac {1} {2} + \ frac {1} {3} + \ frac {1} {12} + \ frac {1} {12} = \ frac {6} {12} + \ frac {4 } {12} + \ frac {1} {12} + \ frac {1} {12} = \ frac {12} {12}$ ) Si dividimos el intervalo $$$[0, 1)$ en cuatro partes de estos tamaños, entonces obtenemos lo siguiente:


Desafortunadamente, en este paso estamos estancados. Incluso si supiéramos un número aleatorio en el intervalo $$$[0, 1)$ , entonces no hay trucos matemáticos simples para determinar automáticamente en qué parte cayó este número. No quiero decir que esto sea imposible, como verán, podemos usar muchos trucos excelentes, pero ninguno de ellos tiene la simplicidad matemática del algoritmo honesto de lanzamiento de huesos.

Sin embargo, también podemos adaptar la técnica utilizada para que el hueso honesto funcione en este caso. Tomemos el hueso discutido anteriormente como un ejemplo. La probabilidad de caída de bordes es $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ y $$$\ frac {1} {12}$ . Si reescribimos esto para que todos los miembros tengan un divisor común, obtenemos los valores $$$\ frac {6} {12}$ , $$$\ frac {4} {12}$ , $$$\ frac {1} {12}$ y $$$\ frac {1} {12}$ . Por lo tanto, podemos percibir esta tarea de la siguiente manera: en lugar de arrojar un hueso tetraédrico con probabilidades ponderadas, ¿por qué no arrojar un hueso honesto de 12 lados, en cuyos bordes hay valores duplicados? Como sabemos cómo simular hueso honesto, esto será análogo a la separación por intervalos $$$[0, 1)$ en pedazos de esta manera:


Luego los asignamos a varios resultados de la siguiente manera:


Ahora será muy simple simular un lanzamiento de hueso: simplemente lanzamos este nuevo hueso honesto, y luego miramos qué cara ha caído y leemos su valor. Este primer paso puede ser realizado por el algoritmo presentado anteriormente, que nos dará un número entero de números en el intervalo $$$0, 1, ..., 11$ . Para unir este entero a una de las caras del hueso tramposo original, almacenaremos una matriz auxiliar de doce elementos que conectan cada uno de estos números con el resultado original. Esto se puede representar gráficamente de la siguiente manera:


Para formalizar esto en forma de algoritmo, describimos tanto la etapa de inicialización (obtención de la tabla) como la etapa de generación (que simula un lanzamiento de hueso al azar). Es importante tener en cuenta estos dos pasos en este y en los algoritmos posteriores, porque el tiempo de preparación debe ser excelente.

En la etapa de inicialización, comenzamos buscando el mínimo común múltiplo de todas las probabilidades dadas para los bordes del hueso (en nuestro ejemplo, el LCL es 12). El NOC es útil aquí porque corresponde al divisor común más pequeño que podemos usar para todas las fracciones y, por lo tanto, al número de caras del nuevo hueso honesto que rodaremos. Habiendo recibido este NOC (lo denotamos con L), debemos determinar cuántas caras del hueso nuevo se distribuirán en cada una de las caras del hueso tramposo original. En nuestro ejemplo, la cara con probabilidad $$$\ frac {1} {2}$ obtiene seis lados del hueso nuevo desde $$$\ frac {1} {2} \ veces 12 = 6$ . Del mismo modo, la fiesta con probabilidad $$$\ frac {1} {3}$ tiene 4 caras desde $$$\ frac {1} {3} \ veces 12 = 4$ . En una forma más generalizada, si L es un LCL de probabilidades, y $$$p_i$ es la probabilidad de una cara $$$i$ huesos, luego destacamos las caras $$$i$ hueso Sharpie original $$$L \ cdot p_i$ facetas de hueso honesto.

Aquí está el pseudocódigo del algoritmo anterior:

Algoritmo: simulando engaño óseo con hueso honesto

• Inicializacion :
  
  1. Encuentre el NOC de los denominadores de probabilidad $$$p_0, p_1, ..., p_ {n-1}$ ; denotarlo $$$L$
  2. Seleccione una matriz $$$A$ el tamaño $$$L$ comparar los resultados de los rollos de hueso honestos con los rollos del hueso original.
  3. Para cada cara $$$i$ del hueso inicial, realizamos lo siguiente en cualquier orden:
     
     1. Asignamos de la siguiente manera $$$L \ cdot p_i$ elementos $$$A$ valor $$$i$ .
• Generacion :
  
  1. Generamos un tiro de hueso honesto para $$$L$ hueso de la cara; llama a la cara $$$S$ .
  2. Volver $$$A [S]$ .

Este algoritmo puede ser simple, pero ¿qué tan eficiente es? La generación de rollos de hueso es bastante rápida: cada rollo de hueso requiere $$$O (1)$ tiempo de ejecución para generar una tirada de dados aleatoria usando el algoritmo anterior, y más $$$O (1)$ Horas de trabajo para buscar en la mesa. Esto nos da el tiempo de trabajo total. $$$O (1)$ .

Sin embargo, el paso de inicialización puede ser extremadamente costoso. Para que este algoritmo funcione, necesitamos asignar espacio para una matriz del tamaño del NLC de los denominadores de todas las fracciones de entrada. En nuestro ejemplo ( $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ ), es 12, para otros valores de entrada los valores pueden ser patológicamente incorrectos. Por ejemplo, veamos fracciones $$$\ frac {999999} {1,000,000}$ y $$$\ frac {1} {1000000}$ . ¡El NOC de los denominadores es igual a un millón, por lo que debería haber un millón de elementos en nuestra tabla!

Desafortunadamente, las cosas podrían ser aún peores. En el ejemplo anterior, podemos al menos "esperar" que el algoritmo ocupe mucha memoria, ya que ambos denominadores de fracciones son iguales a un millón. Sin embargo, podemos tener muchas probabilidades para las cuales el NOC es significativamente mayor que cada denominador individual. Por ejemplo, veamos las probabilidades $$$\ frac {1} {15}$ , $$$\ frac {1} {10}$ , $$$\ frac {5} {6}$ . Aquí el NOC de los denominadores es 30, que es más que cualquiera de los denominadores. El diseño funciona aquí porque $$$15 = 3 \ por 5$ , $$$10 = 2 \ por 5$ y $$$6 = 2 \ por 3$ ; en otras palabras, cada denominador es un producto de dos primos seleccionados de un conjunto de tres valores. Por lo tanto, su NOC es el producto de todos estos números primos, ya que cada denominador debe ser un divisor del NOC. Si generalizamos esta construcción y consideramos cualquier conjunto de $$$k$ primos y tomar una fracción para cada uno de los productos por pares de estos primos, entonces el NOC será mucho más que cada denominador individual. De hecho, uno de los mejores límites superiores que podemos obtener para el NOC será $$$O (\ prod_ {i = 0} ^ n {d_i})$ donde $$$d_i$ Es el denominador $$$i$ esa probabilidad Esto no permite el uso de dicho algoritmo en condiciones reales, cuando las probabilidades son desconocidas de antemano, ya que la memoria requerida para almacenar la tabla de tamaños $$$O (\ prod_ {i = 0} ^ n {d_i})$ , Puede resultar fácilmente más del volumen que cabe en la RAM.

En otras palabras, en muchos casos, este algoritmo se comporta bien. Si todas las probabilidades son iguales, entonces todas las probabilidades obtenidas en la entrada son iguales $$$\ frac {1} {n}$ para algunos $$$n$ . Entonces los denominadores NOC son iguales $$$n$ , es decir, como resultado, el hueso honesto arrojado tendrá $$$n$ caras, y cada faceta del hueso original corresponderá a una faceta del hueso honesto. Por lo tanto, el tiempo de inicialización es $$$O (n)$ . Esto se puede representar gráficamente de la siguiente manera:


Esto nos da la siguiente información sobre el algoritmo:

Algoritmo	Tiempo de inicialización		Tiempo de generación		Memoria ocupada
	Lo mejor	Lo peor	Lo mejor	Lo peor	Lo mejor	Lo peor
Honestidad hueso hueso más afilado	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$

Otro detalle importante sobre este algoritmo: supone que recibiremos probabilidades convenientes en forma de fracciones con buenos denominadores. Si las probabilidades se especifican como IEEE-754 doble, es probable que este enfoque sea desastroso debido a pequeños errores de redondeo; ¡Imagine que tenemos las probabilidades 0.25 y 0.250000000001! Por lo tanto, este enfoque es probablemente mejor no usar, excepto en casos especiales cuando las probabilidades se comportan bien y se especifican en un formato correspondiente a operaciones con números racionales.

Simulación de monedas asimétricas

Nuestra explicación de una simple primitiva aleatoria (hueso honesto) condujo a un algoritmo de simulación de engaño simple pero potencialmente terriblemente ineficaz. Quizás el estudio de otras primitivas aleatorias simples arroje algo de luz sobre otros enfoques para resolver este problema.

Una tarea simple pero sorprendentemente útil es simular una moneda asimétrica utilizando un generador de números aleatorios. Si tenemos una moneda con la probabilidad de un águila $$$p_ {cabezas}$ , entonces, ¿cómo podemos simular el lanzamiento de una moneda tan asimétrica?

Anteriormente, desarrollamos un enfoque intuitivo: partición de intervalos $$$[0, 1)$ en una secuencia de tales regiones que al elegir un valor aleatorio en el intervalo, aparece en alguna región con una probabilidad igual al tamaño de la región. Para simular una moneda asimétrica utilizando un valor aleatorio distribuido uniformemente en el intervalo $$$[0, 1)$ debemos romper el intervalo $$$[0, 1)$ como sigue:


Y luego generar un valor aleatorio distribuido uniformemente en el intervalo $$$[0, 1)$ para ver en qué área está. Afortunadamente, solo tenemos un punto de división, por lo que es muy fácil determinar en qué área se encuentra el punto; si el valor es menor $$$p_ {cabezas}$ , entonces el águila cayó sobre la moneda, de lo contrario - colas. Pseudocódigo:

Algoritmo: simula una moneda asimétrica

1. Generar un valor aleatorio distribuido uniformemente en el intervalo $$$[0, 1)$ .
2. Si $$$x <p_ {cabezas}$ , devuelve el "águila".
3. Si $$$x \ ge p_ {cabezas}$ , volver colas.

Como podemos generar un valor aleatorio distribuido uniformemente en el intervalo $$$[0, 1)$ a tiempo $$$O (1)$ , y también podemos comparar números reales para $$$O (1)$ , entonces este algoritmo se ejecuta a tiempo $$$O (1)$ .

Simulando huesos honestos usando monedas asimétricas

De la discusión anterior, sabemos que podemos simular un hueso de engaño usando hueso honesto, si suponemos que estamos listos para gastar espacio de memoria adicional. Dado que podemos percibir una moneda asimétrica como un hueso engañoso de doble cara, esto significa que podemos simular una moneda asimétrica con la ayuda de un hueso honesto. Es interesante que también se pueda hacer lo contrario: simular un hueso honesto con una moneda asimétrica.El diseño es simple, elegante y se puede generalizar fácilmente para simular un hueso tramposo usando una variedad de monedas asimétricas.

El diseño para simular una moneda asimétrica divide el intervalo$$$[0, 1)$ en dos áreas: el área de “águilas” y el área de “colas” según la probabilidad de que las águilas caigan sobre los huesos. Ya hemos visto un truco similar usado para simular honestidad$$$n$hueso n facetado: intervalo$$$[0, 1)$ se dividió en$$$n$ áreas iguales. Por ejemplo, al lanzar un hueso tetraédrico, obtuvimos la siguiente separación:


Ahora supongamos que estamos interesados ​​en simular un rollo de este hueso honesto usando un conjunto de monedas asimétricas. Una solución es la siguiente: imagine que recorremos estas áreas de izquierda a derecha, cada vez preguntando si queremos detenernos en el área actual, o si seguiremos adelante. Por ejemplo, supongamos que queremos seleccionar aleatoriamente una de estas áreas. Comenzando desde el área más a la izquierda, lanzaremos una moneda asimétrica, que nos dice si debemos detenernos en esta área o continuar. Como necesitamos elegir entre todas estas áreas de manera uniforme con probabilidad$$$\frac{1}{4}$ , entonces podemos hacer esto lanzando una moneda asimétrica, las águilas en las que caen con probabilidad$$$\frac{1}{4}$ .Si cae un águila, nos detenemos en el área actual. De lo contrario, pasamos a la siguiente área.

Si las monedas caen cruz arriba, entonces nos encontramos en la segunda área y nuevamente preguntamos si debemos seleccionar esta área nuevamente o continuar moviéndonos. Podrías pensar que para esto tenemos que lanzar otra moneda con la probabilidad de un águila$$$\frac{1}{4}$ , pero en realidad esto no es cierto! Para ver la falla en este razonamiento, debemos llegar a una situación extrema: si en cada área arrojamos una moneda sobre la cual el águila cae con probabilidad$$$\frac{1}{4}$ , es decir, hay una pequeña posibilidad de que en cada área la moneda se caiga, es decir, tendremos que abandonar todas las áreas. Cuando nos movemos a través de regiones, de alguna manera debemos continuar aumentando la probabilidad de que un águila caiga sobre una moneda. En una situación extrema, si nos encontramos en la última área, entonces la moneda debe tener un águila con probabilidad$$$1$ , porque si rechazamos todas las áreas anteriores, entonces la decisión correcta sería detenernos en la última área.

Para determinar la probabilidad de que nuestra moneda asimétrica arroje un águila después de saltar la primera área, debemos notar que después de saltar la primera área solo quedan tres. A medida que rodamos un hueso honesto, necesitamos que cada una de estas tres áreas se seleccione con probabilidad$$$\frac{1}{3}$ . Por lo tanto, intuitivamente parece que deberíamos tener un segundo hueso en el que el águila cae con probabilidad $$$\frac{1}{3}$ . Usando un razonamiento similar, puede entenderse que cuando aparece una cola en la segunda región del enrejado en la tercera región, el águila debe dejar caer la moneda con probabilidad $$$\frac{1}{2}$ , y en la última área - con probabilidad$$$1$ .

Esta comprensión intuitiva nos lleva al siguiente algoritmo. Tenga en cuenta que no discutimos la corrección o falacia de este algoritmo; pronto lo haremos.

Algoritmo: simulando huesos honestos usando monedas asimétricas

1. Para $$$i = 0$ a$$$n - 1$ :
   
   1. Lanza una moneda asimétrica con la probabilidad de un águila $$$\frac{1}{n - i}$ .
   2. Si el águila cae, entonces regresa $$$i$ .

Este algoritmo es simple y, en el peor de los casos, se ejecuta a tiempo. $$$O (n)$ .Pero, ¿cómo verificamos si es correcto? Para averiguarlo, necesitamos el siguiente teorema:

Teorema: el algoritmo anterior devuelve el lado$$$i$ con probabilidad$$$\frac{1}{n}$ para cualquier seleccionado$$$i$ .

Prueba: considere cualquier constante$$$n \ge 0$ . Usando una inducción fuerte, demostramos que cada uno de $$$n$ caras tiene una probabilidad de elección$$$\frac{1}{n}$ .

Para nuestro ejemplo, mostramos que la cara $$$0$ dados tiene una probabilidad de elección$$$\frac{1}{n}$ . Pero esto se deduce directamente del algoritmo en sí mismo: elegimos la cara 0 si está en una moneda asimétrica con la probabilidad de un águila $$$\frac{1}{n}$ , $$$\frac{1}{n}$ .

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{1}{n - k}$ . $$$k$ $$$\frac{1}{n}$ , , $$$k$ se da como$$$\frac{k}{n}$ . Esto significa que la probabilidad de que el algoritmo no seleccione uno de los primeros $$$k$ caras es igual$$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ . Es decir, la probabilidad de elegir una cara. $$$k$ se da como$$$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$ , que se debe mostrar. Por lo tanto, cada cara del hueso se selecciona de manera uniforme y aleatoria.

Por supuesto, el algoritmo es bastante ineficiente: utilizando la primera técnica, podemos simular una tirada de dados honestos a tiempo $$$O(1)$ ! Pero este algoritmo puede usarse como un trampolín para un algoritmo suficientemente efectivo para simular un hueso tramposo usando monedas asimétricas.

Simulación de hueso Shuler utilizando monedas asimétricas.

El algoritmo presentado anteriormente es interesante porque nos da un marco simple para simular un hueso usando un conjunto de monedas. Comenzamos lanzando una moneda para determinar si seleccionamos la primera faceta del hueso o pasamos al resto. En este proceso, necesitamos manejar cuidadosamente la escala de las probabilidades restantes.

Veamos cómo puedes usar esta técnica para simular un tiro de hueso que hace trampa. Usamos nuestro ejemplo con probabilidades$$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . Él, si no lo recuerdas, divide el intervalo $$$[0, 1)$ como sigue:


Ahora pensemos en cómo simular un hueso tramposo usando monedas asimétricas. Podemos comenzar lanzando una moneda con la probabilidad de un águila$$$\frac{1}{2}$ para determinar si debemos devolver la cara 0. Si un águila cae sobre esta moneda, ¡está bien! Ya hemos terminado De lo contrario, debemos lanzar otra moneda para decidir si seleccionamos la siguiente faceta. Como antes, a pesar de que la siguiente faceta tiene una probabilidad de elección$$$\frac{1}{3}$ , no queremos lanzar una moneda sobre la cual el águila cae con probabilidad$$$\frac{1}{3}$ , porque la mitad de la "masa" de probabilidades se descartó cuando no seleccionamos una línea con$$$\frac{1}{2}$ . De hecho, dado que la mitad de la masa de probabilidades ha desaparecido, si re-normalizamos las probabilidades restantes, obtendremos probabilidades actualizadas: $$$\frac{2}{3}$ , $$$\frac{1}{6}$ , $$$\frac{1}{6}$ . Por lo tanto, la segunda moneda debe ser lanzada con probabilidad $$$\frac{2}{3}$ . Si esta moneda también es cruz, entonces tenemos que elegir entre dos lados $$$\frac{1}{12}$ . Ya que en esta etapa nos libraremos de $$$\frac{5}{6}$ masas de probabilidades, entonces podemos normalizar nuevamente las probabilidades de las partes$$$\frac{1}{12}$ para que todos tengan una oportunidad$$$\frac{1}{2}$ gotas de un águila, es decir, la tercera moneda tendrá una probabilidad$$$\frac{1}{2}$ . La última moneda, si alguna vez llega a ella, debería arrojar al águila con probabilidad $$$1$ ya que esta es el área más reciente.

Para resumir, las probabilidades de las monedas serán las siguientes:

1. Primer rollo: $$$\frac{1}{2}$
2. Segundo rollo: $$$\frac{2}{3}$
3. Tercer rollo: $$$\frac{1}{2}$
4. Cuarto rollo: $$$1$

Puede ser intuitivo de dónde provienen estos números, pero para convertir la selección en un algoritmo, tenemos que crear una construcción formal de la elección de las probabilidades. La idea será la siguiente: en cada etapa recordamos el resto de la masa de probabilidades. Al principio, antes de lanzar la primera moneda, es igual a$$$1$ . Después de lanzar la primera moneda $$$1 - p_0$ . Después de lanzar una segunda moneda $$$1 - p_0 - p_1$ . Más generalmente después del lanzamiento $$$k$ resto de la masa de probabilidad es$$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . Cada vez que lanzamos una moneda para determinar si seleccionamos o no un área $$$k$ , como resultado arrojamos una moneda, la probabilidad de que caiga un águila que es igual a la fracción de la probabilidad restante ocupada por la probabilidad$$$p_k$ , que se define como$$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ . Esto nos da el siguiente algoritmo para engañar a la simulación ósea con un conjunto de monedas asimétricas (demostraremos su corrección y tiempo de ejecución justo debajo):

Algoritmo: hueso de Schuler de monedas asimétricas

• Inicializacion :
  
  1. Mantenemos probabilidades $$$p_i$ para uso futuro.
• Generación :
  conjunto$$$mass = 1$
  para$$$i = 0$ a$$$n - 1$ :
  
  1. Lanza una moneda asimétrica con la probabilidad de un águila $$$\frac{p_i}{mass}$ .
  2. Si el águila cae, entonces regresa $$$i$ .
  3. De lo contrario, establecemos $$$mass = mass - p_i$

Desde un punto de vista intuitivo, esto es lógico, pero ¿es matemáticamente cierto? Afortunadamente, la respuesta es sí gracias a una generalización de la prueba anterior:

Teorema: el algoritmo que se muestra arriba devuelve una cara$$$i$ con probabilidad$$$p_i$ para cualquier seleccionado$$$i$ .

Prueba: considere cualquier constante$$$n \ge 0$ . , $$$n$ $$$p_i$ .

, $$$0$ $$$p_0$ . $$$0$ , , $$$\frac{p_0}{mass}$ . $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ . Esto significa que la probabilidad general de elegir una cara $$$k$ se da como$$$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$, según sea necesario.

Ahora evalúemos la complejidad temporal de este algoritmo. Sabemos que el tiempo de inicialización puede ser$$$\Theta(1)$ si mantenemos una copia de superficie de la matriz de probabilidad de entrada, pero puede haber$$$\Theta(n)$ para que podamos guardar nuestra propia versión de la matriz (en caso de que la función de llamada quiera cambiarla más adelante). La misma generación de un resultado de lanzamiento de hueso puede requerir en el peor de los casos$$$\Theta(n)$ tiros, y solo un tiro en el mejor de los casos.

Sin embargo, después de reflexionar, queda claro que el número de lanzamientos de monedas necesarios está muy influenciado por la distribución entrante. En el mejor de los casos, tendremos una distribución de probabilidad en la que toda la masa de probabilidades se concentra en el primer borde del hueso, y todas las demás probabilidades son cero. En este caso, un lanzamiento de moneda es suficiente para nosotros. En el peor de los casos, toda la masa de probabilidades se concentra en la última faceta del hueso, y en todas las demás caras es igual a cero. En este caso, tenemos que tirar$$$n$ monedas

Podemos caracterizar clara y matemáticamente el número esperado de lanzamientos de monedas en este algoritmo. Imaginemos una variable aleatoria$$$X$ , que indica el número de lanzamientos de monedas para cualquier ejecución de este algoritmo para una distribución específica. Eso es$$$\mathbb{P}[X = 1]$ es la probabilidad de que para completar el algoritmo sea suficiente para lanzar una moneda,$$$\mathbb{P}[X = 2]$ : la probabilidad de que el algoritmo arroje dos monedas, etc. En este caso, el número esperado de lanzamientos de monedas para nuestro algoritmo está determinado por laexpectativa matemática $$$X$ denotado por$$$\mathbb{E}[X]$ . Por definición, obtenemos que

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

Cual es el significado $$$\mathbb{P}[X = i]$ ?El algoritmo termina después de seleccionar algún borde del hueso. Si elige una cara$$$0$ , luego lanza una moneda. Si elige una cara$$$1$ , luego lanzará dos monedas, una para entender que no quiere elegir una cara$$$0$ , otro para entender que quiere elegir una cara$$$1$ . Si está más generalizado, entonces si el algoritmo selecciona una cara $$$i$ , entonces él va a lanzar$$$i + 1$ monedas:$$$i$ moneda para decidir que no quiere elegir el anterior$$$i - 1$ caras, y una para decidir qué selecciona la cara$$$i$ . Combinado con el hecho de que sabemos sobre elegir una cara $$$i$ con probabilidad$$$p_i$ , esto significa que

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]} = \sum_{i = 1}^n{i \cdot p_{i - 1}} = \sum_{i = 1}^n{((i - 1) p_{i - 1} + p_{i - 1})} = \sum_{i = 1}^n{((i - 1) p_{i - 1})} + \sum_{i = 1}^n{p_{i - 1}}$$

Tenga en cuenta que en la última simplificación, el primer término es equivalente $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ que es equivalente $$$\ mathbb {E} [p]$ , el resultado esperado de un lanzamiento de dados! Además, el segundo término es igual a $$$1$ porque esta es la suma de todas las probabilidades. Esto significa que $$$\ mathbb {E} [X] = \ mathbb {E} [p] + 1$ . Es decir, el número esperado de tiradas de monedas es igual a uno más la expectativa matemática de una tirada de dado.

Algoritmo	Tiempo de inicialización		Tiempo de generación		Memoria ocupada
	Lo mejor	Lo peor	Lo mejor	Lo peor	Lo mejor	Lo peor
Honestidad hueso hueso más afilado	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Schuler hueso de monedas asimétricas	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$

Generalizando monedas asimétricas: simulando un hueso tramposo

En el ejemplo que se muestra arriba, pudimos simular efectivamente una moneda asimétrica, ya que solo teníamos que tener en cuenta un punto de división. ¿Cómo podemos generalizar efectivamente esta idea a un hueso tramposo en el que el número de caras puede ser arbitrario?

Como puede ver, una moneda asimétrica es un hueso tramposo, con solo dos caras. Por lo tanto, podemos percibir una moneda asimétrica simplemente como un caso especial de un problema más general que queremos resolver. Al resolver el problema de la moneda asimétrica, dividimos el intervalo $$$[0, 1)$ en dos áreas, una para el águila, la segunda para las colas, y luego para encontrar el área usamos el hecho de que solo hay un punto dividido. Si tenemos un hueso con cara n, habrá más áreas y, por lo tanto, varios puntos de división. Supongamos, por ejemplo, que tenemos un hueso de siete lados con probabilidades $$$\ frac {1} {4}$ , $$$\ frac {1} {5}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ . Si queremos dividir el intervalo $$$[0, 1)$ en siete partes, luego lo hacemos de la siguiente manera:


Observe dónde se encuentran estas áreas. La primera área comienza con $$$0$ y termina $$$\ frac {1} {4}$ . La segunda área comienza con $$$\ frac {1} {4}$ y termina en $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ . Más generalmente, si las probabilidades son iguales $$$p_0, p_1, ..., p_ {n - 1}$ , entonces las áreas serán intervalos $$$[0, p_0)$ , $$$[p_0, p_0 + p_1)$ , $$$[p_0 + p_1, p_0 + p_1 + p_2)$ etc. Esa es el area $$$i$ limitado por intervalo

$$ $$[\ sum_ {j = 0} ^ {i - 1} {p_j}, \ sum_ {j = 0} ^ {i} {p_j})$$

Tenga en cuenta que la diferencia entre estos dos valores es $$$p_i$ , es decir, el área total de la región es $$$p_i$ según sea necesario

Ahora sabemos dónde están las áreas. Si queremos elegir un valor aleatorio distribuido uniformemente $$$x$ en el rango $$$[0, 1)$ , entonces, ¿cómo determinamos en qué intervalo cae? Si utilizamos un algoritmo de monedas asimétricas como punto de partida, la idea será la siguiente: comenzando desde el punto final de la primera región, avanza constantemente por todas las áreas hasta encontrar un punto final cuyo valor sea mayor que el valor $$$x$ . Si hacemos esto, encontraremos la primera región que contiene el punto $$$x$ y, por lo tanto, nuestro valor. Por ejemplo, si elegimos un valor aleatorio $$$x = \ frac {27} {40}$ , luego realice la siguiente búsqueda:


De lo cual podemos concluir que la faceta 3 cayó en dados con indexación desde cero.

Tal algoritmo de escaneo lineal nos dará un algoritmo de tiempo $$$O (n)$ para encontrar el borde expulsado del hueso. Sin embargo, podemos mejorar significativamente su tiempo de ejecución usando la siguiente observación: una serie de puntos finales de regiones forma una secuencia creciente (ya que siempre agregamos más y más probabilidades, ninguna de las cuales puede ser menor que cero). Por lo tanto, queremos responder la siguiente pregunta: teniendo una secuencia creciente de valores y algún punto de control, necesitamos encontrar el primer valor en el intervalo estrictamente mayor que el punto de control. ¡Este es el momento perfecto para usar la búsqueda binaria ! Por ejemplo, aquí hay una búsqueda binaria en la matriz de arriba para encontrar el área a la que pertenece $$$x = \ frac {39} {40}$ :


Esto nos da un algoritmo con el tiempo. $$$\ Theta (\ log n)$ para unir un valor aleatorio distribuido uniformemente en el intervalo $$$[0, 1)$ al borde de un hueso abandonado. Además, el tiempo de procesamiento previo es suficiente para construir la tabla de puntos finales $$$\ Theta (n)$ ; simplemente calculamos sumas parciales de probabilidades a medida que avanzamos.

Este algoritmo a veces se denomina algoritmo de selección de la rueda de la ruleta porque selecciona un área aleatoria utilizando una técnica similar a la rueda de la ruleta: lanzar una bola en un intervalo y observar dónde se detiene. En pseudocódigo, el algoritmo se ve así:

Algoritmo: selección de rueda de ruleta

• Inicializacion :
  
  1. Seleccione una matriz $$$A$ el tamaño $$$n$
  2. Establecemos $$$A [0] = p_0$ .
  3. Para cada probabilidad $$$i$ de $$$1$ antes $$$n - 1$ :
     
     1. Establecemos $$$A [i] = A [i - 1] + p_i$
  
  
• Generacion :
  
  1. Generar un valor aleatorio distribuido uniformemente $$$x$ en el rango $$$[0, 1)$
  2. Usando una búsqueda binaria, encontramos el índice $$$i$ elemento más pequeño $$$A$ que es menos $$$x$ .
  3. Volver $$$i$ .

La comparación entre este algoritmo y el dado anteriormente parece bastante impresionante:

Algoritmo	Tiempo de inicialización		Tiempo de generación		Memoria ocupada
	Lo mejor	Lo peor	Lo mejor	Lo peor	Lo mejor	Lo peor
Honestidad hueso hueso más afilado	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Schuler hueso de monedas asimétricas	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Selección de rueda de ruleta	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$

Obviamente, ahora tenemos un algoritmo mucho mejor que el original. La discreción de probabilidad solo al principio parecía prometedora, pero este nuevo enfoque, basado en el valor continuo y la búsqueda binaria, se ve mucho mejor. Sin embargo, todavía es posible mejorar estos indicadores con el uso inteligente de un conjunto de técnicas híbridas, que discutiremos a continuación.

Un detalle interesante de este algoritmo es que, aunque el uso de la búsqueda binaria garantiza el peor momento posible para generar números aleatorios $$$O (\ log n)$ , tampoco permite una búsqueda más rápida; es decir, el tiempo de generación también será igual $$$\ Omega (\ log n)$ . ¿Se puede mejorar? Resulta que puedes.

Supongamos que pasamos de una búsqueda binaria en una lista de probabilidades acumulativas a usar un árbol de búsqueda binaria . Por ejemplo, teniendo el conjunto de probabilidades dado anteriormente, podemos construir el siguiente árbol de búsqueda binario para su distribución acumulativa:


Ahora, si queremos simular un rollo de hueso, podemos generar un número distribuido uniformemente en el intervalo $$$[0, 1)$ y luego mira en qué intervalo se encuentra en este árbol de búsqueda binario (BST). Como se trata de un árbol de búsqueda binario equilibrado, el mejor tiempo de búsqueda es $$$O (1)$ y lo peor $$$O (\ log n)$ .

Sin embargo, suponiendo que sepamos más sobre la distribución de probabilidad, podemos hacerlo mucho mejor. Por ejemplo, supongamos que nuestras probabilidades son iguales $$$\ frac {99} {100}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ . Es decir, la distribución de probabilidad es extremadamente sesgada, y casi toda la masa de probabilidades se concentra en una cara. Podemos construir un BST equilibrado para estas probabilidades:


Aunque este árbol de búsqueda binario está perfectamente equilibrado, no es muy adecuado para nuestras tareas. Como sabemos que en 99 de cada 100 casos, el valor aleatorio estará en el rango $$$[0, \ frac {99} {100})$ , entonces no tiene sentido almacenar el nodo para este intervalo donde está ubicado ahora. De hecho, esto significará que casi todo el tiempo haremos dos comparaciones innecesarias con las áreas azul y amarilla. Dado que con una probabilidad muy alta deberíamos ser los primeros en verificar el intervalo más grande, sería lógico desequilibrar el árbol para hacer que el caso promedio sea mucho mejor debido a los restantes. Esto se muestra aquí:


Ahora probablemente completaremos la búsqueda al encontrar inmediatamente el área deseada después del primer intento. En el caso muy improbable de que el área deseada esté en el resto $$$(\ frac {99} {100}, 1]$ bajamos con calma hasta el final del árbol, que en realidad está bien equilibrado.

De forma generalizada, queremos resolver el siguiente problema:

Dado un conjunto dado de probabilidades, encuentre un árbol de búsqueda binario para estas probabilidades que minimice el tiempo de búsqueda esperado.

Afortunadamente, este problema está muy bien estudiado y se llama el problema óptimo del árbol de búsqueda binaria . Hay muchos algoritmos para resolver este problema; se sabe que la solución exacta se puede encontrar a tiempo $$$O (n ^ 2)$ usando programación dinámica , y que existen buenos algoritmos de tiempo lineal que pueden encontrar soluciones aproximadas. Además, para obtener un factor constante de la solución óptima, puede usar la estructura de datos del árbol de despliegue (árbol expansivo) (árbol de búsqueda binaria autobalanceado).

Es interesante que el mejor caso para el comportamiento de tales árboles de búsqueda binarios optimizados ocurre cuando las distribuciones de probabilidad están extremadamente sesgadas, porque simplemente podemos mover los nodos que contienen la gran mayoría de la masa de probabilidad a la raíz del árbol, y el peor de los casos es cuando la distribución está equilibrada, porque entonces el árbol debe ser ancho y poco profundo ¡Esto es lo opuesto al comportamiento del algoritmo anterior, en el que se utilizó uno honesto para simular un hueso tramposo!

En el mejor de los casos, tenemos un hueso tramposo en el que una cara siempre se cae (es decir, tiene una probabilidad de 1, y todas las demás caras tienen una probabilidad de 0). Esta es una exageración extrema de nuestro ejemplo anterior, pero en este caso, la búsqueda siempre terminará después del primer intento. En el peor de los casos, todas las probabilidades son iguales y obtenemos una búsqueda BST estándar. Llegamos a lo siguiente:

Algoritmo	Tiempo de inicialización		Tiempo de generación		Memoria ocupada
	Lo mejor	Lo peor	Lo mejor	Lo peor	Lo mejor	Lo peor
Honestidad hueso hueso más afilado	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Schuler hueso de monedas asimétricas	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Selección de rueda de ruleta	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
Selección óptima de la rueda de ruleta	$$$O (n ^ 2)$		$$$\ Theta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$

Lanzamiento de dardos

Hasta ahora hemos estado considerando dos primitivas que nos ayudaron a construir algoritmos para simular un hueso tramposo: hueso honesto y moneda asimétrica. Usando solo hueso honesto, llegamos a un algoritmo (por desgracia, poco práctico) para hacer trampa de hueso, y comenzando con monedas asimétricas, pudimos inventar un algoritmo rápido para hacer trampa de hueso. ¿Se pueden combinar estos dos enfoques para crear un algoritmo basado en huesos honestos y monedas asimétricas? Resulta que sí, y de hecho el algoritmo resultante es mejor que ambos enfoques.

Hasta este momento, visualizamos el intervalo $$$[0, 1)$ y probabilidades de caras óseas como un intervalo unidimensional. Ambos algoritmos seleccionan algún punto en el intervalo $$$[0, 1)$ y colóquelo en un segmento de línea recta, cuya longitud corresponde a algún tipo de probabilidad. Cuanto más largos sean los segmentos que creamos, mayor será la probabilidad de elegir este segmento. Pero, ¿qué pasa si intentas pensar no en una sino en dos dimensiones? ¿Qué pasa si tomamos probabilidad $$$p_i$ no la longitud de un segmento de línea recta, sino el área de un rectángulo?

Comencemos volviendo a nuestro ejemplo anterior con probabilidades $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ . Representamos estas probabilidades en forma de rectángulos con un ancho $$$w$ (con algo arbitrario $$$w> 0$ ) y altura $$$p_i$ (por lo tanto, el área del rectángulo será igual a $$$w \ cdot p_i$ ):


Tenga en cuenta que el área total de estos rectángulos es $$$w$ desde la zona

$$ $$\ sum_ {i = 0} ^ {n - 1} {w p_i} = w \ sum_ {i = 0} ^ {n - 1} {p_i} = w$$

Ahora supongamos que dibujamos un rectángulo delimitador alrededor de estos rectángulos cuyo ancho es $$$4w$ (ya que hay cuatro cuadrángulos), y la altura es $$$\ frac {1} {2}$ (ya que el rectángulo más alto tiene una altura $$$\ frac {1} {2}$ ):


Podemos imaginar que este rectángulo está dividido en cinco áreas: cuatro áreas corresponden a diferentes probabilidades y un área indica espacio no utilizado. Tomando este descanso, podemos pensar en el algoritmo de simulación de lanzamiento aleatorio de dados como un juego de dardos. Supongamos que lanzamos un dardo (perfectamente distribuido uniformemente) a este objetivo. Si cae en el espacio no utilizado, sacamos el dardo y lo volvemos a lanzar, repitiendo el proceso hasta llegar a uno de los rectángulos. Como cuanto mayor es la probabilidad, cuanto mayor es el rectángulo, mayor es la probabilidad de lanzar el borde del hueso, mayor es la probabilidad de caer en su rectángulo. De hecho, si establecemos la condición de que ya hemos caído en algún tipo de rectángulo, obtenemos lo siguiente:

$$ $$\ mathbb {P} [\ mbox {golpear rectángulo para el lado i} | \ mbox {golpear algún rectángulo}] = \ frac {\ mbox {área del rectángulo para i}} {\ mbox {área total del rectángulo}} = \ frac {w p_i} {w} = p_i$$

En otras palabras, cuando finalmente caemos en algún tipo de rectángulo con nuestro dardo distribuido uniformemente, seleccionamos el rectángulo de la cara $$$i$ hueso tramposo con probabilidad $$$p_i$ , es decir, con la probabilidad que necesitamos! Es decir, si podemos encontrar alguna forma efectiva de simular lanzar dardos aleatorios en este rectángulo, entonces tendremos una forma efectiva de simular lanzar dados aleatorios.

Una forma de simular lanzamientos de dardos en este rectángulo es seleccionar dos valores distribuidos uniformemente en el intervalo $$$[0, 1)$ escalarlos al ancho y alto apropiados, seguido de verificar el área debajo del dardo. Sin embargo, esto causa el mismo problema que tuvimos cuando intentamos determinar la región unidimensional en la que se encuentra el valor aleatorio. Sin embargo, hay una serie de observaciones verdaderamente maravillosas, gracias a las cuales determinar el lugar del impacto puede ser una tarea simple, si no trivial.

Primera observación: mostramos que el ancho de estos rectángulos se puede elegir arbitrariamente, porque todos tienen el mismo ancho. Las alturas, por supuesto, dependen de las probabilidades de las caras de los huesos. Sin embargo, si escalamos uniformemente todas las alturas por algún número real positivo $$$h$ , entonces las áreas relativas de todos los rectángulos serán las mismas. De hecho, para cualquier número real positivo $$$h$ área total de todos los rectángulos después de escalar sus alturas en $$$h$ calculado como

$$ $$\ sum_ {i = 0} ^ {n - 1} {w h p_i} = w h \ sum_ {i = 0} ^ {n - 1} {p_i} = w h$$

Ahora consideraremos la probabilidad de elegir cualquier rectángulo individual, limitándonos a la condición de que definitivamente golpeemos algún tipo de rectángulo. Usando los mismos cálculos, obtenemos lo siguiente:

$$ $$\ mathbb {P} [\ mbox {golpear rectángulo para el lado i} | \ mbox {golpear algún rectángulo}] = \ frac {\ mbox {área del rectángulo para i}} {\ mbox {área total del rectángulo}} = \ frac {w h p_i} {w h} = p_i$$

Es decir, de hecho, la probabilidad de elegir un solo rectángulo no cambia si los escalamos de manera lineal y uniforme.

Dado que podemos elegir cualquier factor de escala adecuado, ¿por qué no escalamos estos rectángulos para que la altura del cuadro delimitador sea siempre 1? Dado que la altura del cuadro delimitador está determinada por el valor máximo $$$p_i$ probabilidades de entrada, entonces podemos comenzar escalando cada uno de los rectángulos por un factor $$$\ frac {1} {p_ {max}}$ donde $$$p_ {max}$ Es la probabilidad máxima de todas las probabilidades de entrada. Gracias a esto, obtenemos la altura del rectángulo 1. De manera similar, dado que podemos elegir cualquier ancho arbitrario para los rectángulos, tomemos el ancho 1. Esto significa que para $$$n$ las probabilidades del ancho total del cuadro delimitador son $$$n$ , y la altura total es 1. Esto se muestra en la figura:


Ahora estamos listos para pensar en cómo podemos lanzar un dardo aleatorio en un rectángulo y determinar en qué cayó. Lo más importante es que podemos dividir el rectángulo para que no consista en varios rectángulos más pequeños y un espacio vacío de una forma extraña. En cambio, el área se corta en un conjunto de $$$2n$ rectángulos, dos en cada uno de $$$n$ probabilidades de entrada Esto se muestra aquí:


Observe cómo se forma este rectángulo. Para cada cara del hueso tramposo, tenemos una columna con un ancho de 1 y una altura de 1, dividida en dos espacios: un "sí" de medio espacio que corresponde a un rectángulo de este tamaño y un "no" de medio espacio que corresponde a la parte restante de la columna.

Ahora pensemos en cómo podemos lanzar un dardo. Un dardo perfectamente uniforme lanzado en este rectángulo tendrá componentes $$$x$ y $$$y$ . Aquí componente $$$x$ que debe estar en el intervalo $$$[0, 1)$ , corresponde a qué columna golpea el dardo. Componente $$$y$ que debe estar en el intervalo $$$[0, 1)$ , corresponde a lo alto que estamos en la columna. Selección de componentes $$$x$ afecta qué cara del hueso tramposo estamos considerando, y la elección del componente $$$y$ corresponde a si hemos elegido esta faceta o no. Pero espera, ¡ya conocemos estas dos ideas! Selección coordinada $$$x$ correspondiente a la columna, similar a tirar un hueso honesto para decidir la elección de la columna. Selección coordinada $$$y$ corresponde al lanzamiento de una moneda asimétrica para determinar si seleccionar una cara o lanzar nuevamente. Esta observación es tan importante que la hacemos absolutamente comprensible:

La elección de un punto aleatorio en este intervalo es similar a tirar un hueso honesto y lanzar una moneda asimétrica.

De hecho, este resultado puede ser percibido como una oportunidad mucho más poderosa. Para simular un hueso tramposo, construimos un conjunto de monedas asimétricas, una para cada cara del hueso, y luego hacemos rodar un hueso honesto para determinar qué moneda lanzar. , , , , .

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ . , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ .
  2. $$$Coins$ $$$n$ , «» .
  3. $$$i$ $$$0$ antes $$$n - 1$ :
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$i$ $$$[0, n)$ .
     2. , $$$Coins[i]$ .
     3. , $$$i$ .

. $$$O (n)$ , $$$O (n)$ $$$Coins$ , $$$O (n)$ . , $$$O(1)$ . ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$i$ $$$\frac{p_i}{p_{max}}$ , -

$$ $$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ . ? $$$p_{max}$ . $$$p_{max}$ $$$1$ ( ). $$$n$ , $$$n$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . Si $$$p_{max} = \frac{1}{n}$ , 1. . Si $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$n$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ . , «» $$$\frac{1}{n \cdot p_{max}}$ . , , «», $$$p_{max}$ . , , .

:

Algoritmo
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . , $$$\frac{1}{4}$ . , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ? , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ . , :


, , $$$\frac{1}{2}$ y $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ? , - , :


, , . , $$$\frac{1}{2}$ y $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ . $$$n$ . , alias , ( ). , . - - $$$i$ . $$$Prob[i]$ . , , $$$i$ , , $$$Alias[i]$ . alias :

Alias

, $$$Alias$ y $$$Prob$ . , , :

• $$$(n \cdot p_i) \times 1$ $$$p_i$ ,
• $$$n$
  
  • , $$$1$ ,
  • , $$$i$ , $$$i$ .

, , . , $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . ( $$$k = n = 4$ ), $$$1 = \frac{4}{4}$ . , alias, , . , 4, :


, , ( $$$\frac{1}{3}$ , $$$\frac{1}{3}$ ) 1. , - . ( ) :


- . , , , 1 ( $$$2$ y $$$\frac{4}{3}$ ) ; $$$\frac{4}{3}$ . $$$\frac{4}{3}$ , ; $$$\frac{2}{3}$ de $$$\frac{4}{3}$ , :


, . , $$$3$ , , , . , . , , $$$1$ , (, $$$\frac{2}{3}$ ) :


, - , 1, . ( $$$2$ ), $$$\frac{1}{3}$ de $$$2$ :


, . , - , 1 ( $$$\frac{1}{3}$ ), :


- $$$1$ , . — $$$\frac{5}{3}$ :


, 1. , :


! .

, :

• - , 1, , $$$Prob$ .
• - , 1, , $$$Alias$ , .

, ? «», ? , . : , 1 ( $$$\frac{1}{n}$ , $$$n$ ) , , , , 1 ( ) 1 ( ). , . , ? , . , , . , .

:

: $$$k$ $$$h_0$ , $$$h_1$ , ..., $$$h_{k-1}$ , , $$$\sum_{i=0}^{k-1}{h_i} = k$ , $$$k$ , 1, , , $$$i$ - $$$i$ - .

: . , $$$k = 1$ , 1. $$$0$ - . , 1, , $$$0$ - $$$0$ - .

, - $$$k$ $$$k + 1$ $$$1$ $$$h_0$ , $$$h_1$ , ..., $$$h_{k}$ , , $$$\sum_{i = 0}^{k}{h_i} = k + 1$ . , $$$h_l$ , , $$$h_l \le 1$ , - $$$h_g$ (, $$$l \ne g$ ), , $$$h_g \ge 1$ . , , $$$h_l$ con $$$h_l \le 1$ ; , $$$h_i > 1$ $$$i$ $$$0 \le i \le k$ . , $$$k + 1 = \sum_{i = 0}^k{h_i} > \sum_{i=0}^k{1} = k + 1$ , . , - $$$l$ , , $$$h_l \le 1$ . , $$$h_g$ ( $$$l \ne g$ ), , $$$h_g \ge 1$ . , $$$h_g < 1$ , ( ) $$$\sum_{i=0}^{k}{h_i} < k + 1$ . , $$$h_l \le 1$ y $$$h_g \ge 1$ .

. $$$h_l$ $$$l$ $$$1 - h_l$ en $$$l$ - $$$h_g$ ( , $$$0 \le 1 - h_l \le 1$ y $$$h_g \ge 1$ ) . $$$k$ , $$$k$ , $$$1$ , $$$k + 1$ . , $$$l$ , . , , $$$k$ en $$$k$ , . , $$$l$ , , , . .

, , alias, , . alias.

Alias

, alias-. 1 1, :

: Alias-

• :
  
  1. $$$p_i$ en $$$n$ .
  2. $$$Alias$ y $$$Prob$ , $$$n$ .
  3. For $$$j = 1 \mbox{ to } n - 1$ :
     
     1. $$$p_l$ , $$$p_l \le 1$ .
     2. $$$p_g$ ( $$$l \ne g$ ), $$$p_g \ge 1$
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_l$ .
     6. $$$p_g := p_g - (1 - p_l)$ .
     
     
  4. Dejar $$$i$ , 1.
  5. $$$Prob[i] = 1$ .
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

, , $$$\Theta(1)$ . . -, $$$\Theta(n)$ $$$n$ , $$$O (n)$ . $$$\Theta(n)$ , $$$O (n)$ , . $$$O(n^2)$ . , :

Algoritmo
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$

alias- , . - (, $$$O (n)$ ), .

. , $$$O (n)$ . . $$$p_g$ y $$$p_l$ $$$O(\log n)$ , . $$$p_l$ $$$O(\log n)$ , $$$p_g$ $$$O(\log n)$ . :

: Alias-

• :
  
  1. $$$Alias$ y $$$Prob$ , $$$n$ .
  2. $$$T$ .
  3. $$$n \cdot p_i$ en $$$T$ $$$i$ .
  4. For $$$j = 1 \mbox{ to } n - 1$ :
     
     1. $$$T$ ; $$$p_l$ .
     2. $$$T$ ; $$$p_g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := p_g - (1 - p_l)$ .
     6. $$$p_g$ $$$T$ .
     
     
  5. Dejar $$$i$ , 1.
  6. $$$Prob[i] = 1$ .
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

. $$$Alias$ y $$$Prob$ - $$$O (n)$ , BST $$$T$ $$$\Theta(n \log n)$ . $$$\Theta(n)$ , $$$O(\log n)$ . $$$O(n \log n)$ :

Algoritmo
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$

, . , , , alias-. «A Linear Algorithm For Generating Random Numbers With a Given Distribution» , alias-.

: 1, 1. . «» , «» «». :

• «» 1.
• «» 1.
• .

, , , . , :

: () Alias-

: . .

• :
  
  1. $$$Alias$ y $$$Prob$ , $$$n$ .
  2. , $$$Small$ y $$$Large$ .
  3. $$$n$ .
  4. $$$p_i$ :
     
     1. Si $$$p_i < 1$ , $$$i$ $$$Small$ .
     2. ( $$$p_i \ge 1$ ) $$$i$ $$$Large$ .
     
     
  5. $$$Small$ :
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Large$ ; $$$g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := p_g - (1 - p_l)$ .
     6. Si $$$p_g < 1$ , $$$g$ en $$$Small$ .
     7. ($p_g \ge 1$) $$$g$ en $$$Large$ .
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$g$ .
     2. $$$Prob[g] = 1$ .
     
     
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

(, ) : - $$$Small$ $$$Large$ , . . $$$Small$ $$$Large$ ( $$$Small$ , , ). $$$Large$ 1, $$$k$ $$$Large$ $$$k$ , $$$Large$ 1, . 1, , , 1.

. , , , . .

, . $$$\frac{1}{4}$ , $$$\frac{1}{5}$ , $$$\frac{1}{8}$ , $$$\frac{1}{8}$ , $$$\frac{1}{10}$ , $$$\frac{1}{10}$ , $$$\frac{1}{10}$ . , , $$$\frac{1}{8}$ , $$$\frac{1}{5}$ , $$$\frac{1}{10}$ , $$$\frac{1}{4}$ , $$$\frac{1}{10}$ , $$$\frac{1}{10}$ , $$$\frac{1}{8}$ . :


$$$Small$ , :


$$$Large$ ( ) . $$$\frac{7}{4} - \frac{1}{8} = \frac{13}{8} \ge 1$ , $$$Large$ :


. $$$Small$ , $$$Large$ :


:


, , , . , :


$$$Small$ , :


$$$Small$ , , :


, $$$Small$ , .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$ $$$Large$ , . , , $$$n$ , , $$$\frac{1}{n}$ , $$$1$ ( $$$Small$ , $$$Large$ )
2. , , . , , $$$Large$ , $$$Small$ .

, $$$Small$ $$$Large$ . , , $$$Small$ , $$$Large$ .

, . , , , $$$Large$ . -, , $$$1$ , , $$$1$ . , . :

: Alias-

• :
  
  1. $$$Alias$ y $$$Prob$ , $$$n$ .
  2. , $$$Small$ y $$$Large$ .
  3. $$$n$ .
  4. $$$p_i$ :
     
     1. Si $$$p_i < 1$ , $$$i$ en $$$Small$ .
     2. ( $$$p_i \ge 1$ ) $$$i$ en $$$Large$ .
     
     
  5. $$$Small$ y $$$Large$ : ( $$$Large$ )
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Large$ ; $$$g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := (p_g + p_l) - 1$ . ( . )
     6. Si $$$p_g < 1$ , $$$g$ en $$$Small$ .
     7. ( $$$p_g \ge 1$ ) $$$g$ en $$$Large$ .
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$g$ .
     2. $$$Prob[g] = 1$ .
     
     
  7. $$$Small$ : - .
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Prob[l] = 1$ .
     
     
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

, — . $$$\Theta(n)$ , . $$$\Theta(1)$ , , . $$$O (n)$ , () , . $$$O (n)$ , $$$Large$ y $$$Small$ $$$O (n)$ . $$$\Theta(n)$ , ( ) :

Algoritmo
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

Wow! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !